From: Alexander Moshchuk (anm@cs.washington.edu)
Date: Wed Apr 28 2004 - 00:15:56 PDT
The paper talks about the importance and influence of logic on
computer science. The authors focus on a few areas to illustrate how
logic helped shape the field - we read about descriptive complexity
and database querying.
Descriptive complexity allows a simple and elegant view of computation
based on expressing properties using logic. Logic can effectively
characterize complexity classes (e.g. NP) as well as some basic
complexity questions.
First-order logic lies at the heart of modern relational database
systems and is the underlying model for querying languages. It is
efficiently implemented using relational algebra, which provides
operators for set union and difference, selection, projection, and
join. Indexing and simplifying rewriting of relational algebra
queries increases efficiency. Theoretically speaking, FO queries
scale perfectly with enough parallel processing, but such perfect
scaling is unlikely to ever be feasible. Even if enough processors
were available, coordinating all of them would cause enormous amounts
of overhead.
In discussing logic and databases, the paper focuses on the relational
model - I wonder if/how logic can also be used with semi-structured
(XML) data, which is all the rage nowadays.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 00:14:45 PDT