From: Charles Giefer (cgiefer@cgiefer.kicks-ass.net)
Date: Wed Apr 28 2004 - 00:44:27 PDT
On the Unusual Effectiveness of Logic in Computer Science
Halpern, et al.
This paper shows that there are several areas of Computer Science that have
significantly benefited from formal logic. Logic, while mostly unimportant
to most other sciences (as claimed by this paper), has many significant
applications in Computer Science. Analyzing complexity of algorithms and
querying databases are two places where logic has helped.
In complexity, it has helped show what problems are easily computable and
what others belong to a set of difficult-to-compute problems.
In databases, logic is the basis for querying the data. Logic allows for
optimizations and subqueries to be performed for best performance. Having
subqueries also makes databases highly parallelizable. In practice, it
seems that no system can be perfectly parallelizable (twice the hardware =
twice the performance). There must be some overhead that limits the
parallelization of databases. However, I have limited knowledge of parallel
databases, so I cannot offer any suggestions for these limits.
Something that perplexed me was their example about bars and drinkers. Its
seems that they made a mistake (or maybe I misunderstood) that they are
trying to find "serves(d,Bass)" which are drinkers who drink Bass. But
this information is not available. I think the mean "serves(b,Bass)", which
would find the bars that server Bass so that they could be paired with the
drinkers for that bar.
This paper talks about relational database query languages. I wonder if
semi-structured data query languages also follow these rules or if they
allow for more complicated logic. It seems like the recursive structure of
XML would allow for more difficult logic expressions.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 00:44:38 PDT