From: L. Yan (lanti@u.washington.edu)
Date: Tue Apr 27 2004 - 23:27:40 PDT
This is an striking paper, talking logic in the context of computer
science, which is something completely new to me, although I have met
both in a few courses.
The second section focused on computation complexity and descriptive
complexity in first/second order logic. The theorems presented here
offered a completely different perspective viewing complexity class NP
and PSPACE. Given only introductory knowledge in this area, I would
say no more than that the arguments are amazing but the proof should
be involved.
Section 3 is probably the most relavant to this class, the
relationship between first order logic and relational algebra, the
latter being the heart of query engines. In the example given, it is
clear that queries in FO can be written by relational algebra
operators on variables (in FO terms) or attributes(database
terms). Further, queries expressed in relational algebra could be
rewritten for more efficient execution, and this often makes the
difference between infeasible and feasible given large databases. It
is also worth note the linear scaling property of FO queries, which
implies that given number of processors increases linearly with size
of database, query execution is bounded by constant time, a highly
desirable feature. Although the requirement for linear increasing
resource is, in most cases, unrealistic, the linear increase in time
complexity is still a big win over naive implementations.
- Li
This is Unix
explanatory error messages are seen as a sign of
weakness ...
This archive was generated by hypermail 2.1.6 : Tue Apr 27 2004 - 23:27:41 PDT