From: CR (chrisre@cs.washington.edu)
Date: Wed Apr 28 2004 - 09:08:28 PDT
This paper is meant to extol the virtues of logic in computer science.
It does so in two main areas (that we read). It shows how complexity
classes can be framed purely as sets. This abstraction has been
particularly useful in understanding advanced measures of complexity.
The other, and for us, more relevant area is that of databases. In
particular, the use of first-order logic to express queries While I
certainly agree that declarative languages are one of the best portions
of CS and databases, it was not first-order logic that allowed us to
execute them efficiently. It was the relational algebra which allowed
this. Being based over first-order logic was a clean idea but without
the algebra it would have been worthless for databases.
One thing that is not discussed is that although logic is a powerful
tool which is capable of viewing these constructs, it is not necessarily
the most natural. For example, the machines have running times, their
elegant characterization hides this detail from us if we are to
understand the problem. I suppose this is just a general critique of any
abstraction – but first order logic seems particularly unnatural.
Perhaps this is why the authors view its effectiveness as unusual.
My review is negative because I think there are so many good things to
be said for having query languages based on a solid formal model,
especially one as clean as first-order logic.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 09:08:29 PDT