From: Michael Gubanov (mgubanov@cs.washington.edu)
Date: Wed Apr 28 2004 - 11:55:35 PDT
Paper: On the Unusual Effectiveness of Logic in Computer Science , J.
Halpern et al
Summary: The paper represent the retrospective on the impact
mathematical logic made
on the computer science
Main Ideas:
- Connection of first-order logic to complexity classes. It is
interesting
how simple NP complexity class could be expressed in terms of
first-order logic.
It is just one line: NP = SO exist.
- Similarly, the set of first-order expressible properties is equal to
CRAM[1].
The useful corollary is that parallel time is equal to first-order
iteration
(Least fixed point operator like "fix" in lambda-calculus could be used
to "unroll" the recursion in the formula)
- The next two useful results are
1. Polynomial time class is equal to the set of problems expressible by
the first-order logic with "fix" operator.
2. Polynomial space is equal to the set of problems expressible by a
first-order
formula iterated exponentially.
- Some of the important applied results in respect to databases are
1. Relational algebra
2. Relational algebra queries and their intrinsic parallelism as they
operate
on the sets.
3. Each algebra operation can be evaluated in constant parallel time
And the most important one - every algebra query can be also evaluated
in constant parallel time and the time is independent of the database
size.
The corollary is that the implementation of First-order logic via
relational algebra scales linearly given parallel processing resources.
Relevance:
Thanks to this important theoretical result relational databases
are based on the implementation of relational algebra. Therefore
we can enjoy today effective query optimization as it is and good
scalability
in respect to data increase.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 11:55:31 PDT