Review 4

From: L. Yan (lanti@u.washington.edu)
Date: Tue Apr 27 2004 - 23:27:40 PDT

  • Next message: Alexander Moshchuk: "review"

    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 ...


  • Next message: Alexander Moshchuk: "review"

    This archive was generated by hypermail 2.1.6 : Tue Apr 27 2004 - 23:27:41 PDT