Review: On The Unusual Effectiveness of Logic in CS

    In their paper the authors discuss the impact that formal logic has had on computer science.  They begin by first discussing the precedent for such explorations, by pointing to two papers which discuss the effect that mathematics has had on the natural sciences.  They then go on to discuss how formal logic was initially explored predominatly as a mathematical persuit (in that it was seen to serve as the foundation of mathematics).  However, the authors suggest that formal logic has had minimal impact on mathematics but has had a tremendous impact on computer science. 
    The first area where they suggest that logic has impacted computer science is in the study of complexity and complexity classes.  In particular, they describe how descriptive complkexity exactly captures the important complexity classes.
    The second area they describe (and the one that is more germaine to our class) is the impact that first-order logic has had on databases.  The authors suggest that not only does first order logic provide an intuitive means for the user to structure their querry, but that it is also easy to break down into subquerries and has the amazing property that it can easily be made parallel such that it features 'perfect scaling'.
    It has been discussed in the past that databases present one of the cononical examples of how theory translated to effective and widespread success in a vital application area but I found this paper to be a nice explination of why it had that effect.  In addition, I was struct by the discussion of the huge desgree of potential parallelisms in databases.  I am curious however, becuase I havge heard that such parallelism fails to materialize in real systems.  I wonder if this is an impact of Databases being entities which not only querry but which also record data.  What is the botleneck in this process which impeded parallelism in real systems?

-Lucas Kreger-Stickles