From: Steven Balensiefer (alaska@cs.washington.edu)
Date: Wed Apr 28 2004 - 02:47:20 PDT
On the Unusual Effectiveness of Logic in Computer Science
I understand that the idea for this paper was an earlier work of similar
title. Even so, I find if amusing that the title suggests an evolution
of methods that finally resulte in logic. Without Logic, there would be
no computer science, so mentioning that logic works well for computer
science seems redundant.
That being said, I was surprised by the theorems for descriptive
complexity. My only experience with complexity was in 531, so I don't
find it wierd that I'd never heard or descriptive complexity. I was
surprised that something like adding the ability to make inductive
relations would allow first order relations to be equivalent to P.
The theorems presented were new to me, but I wish there had been
further explanation or examples of their import.
I wasn't surprised that relational algebra was discussed here, because
its relation to first order logic is readily apparent. The mention of
rewriting rules led me to an interesting question. If the query optimizer
contains all of these kinds of rules, is there an unnecessary cost in
the form of repeated effort when the user strives to optimize his query?
The conventional wisdom in OS is that providing the user with additional
control can lead to better performance because the user knows the details
of his requirements. However, in a DBMS it seems equally believable that
the query optimizer knows far more about the way the query should be
handled than the user. Just from the first part of the homework, I'd
suspect that simply applying these rewriting rules isn't enough to
counteract poor query structure by the user.
The discussion about the scalability of databases based on the
properties of first order queries also grabbed my attention. The authors
note that all of the calculations take place independently, and therefore
a sufficiently parallel machine could do these operations in O(1) time.
My mind immediately leapt to two alternatives for exploiting this
property. The first would be to design Processor in Memory systems so
that large vector-style operations could be orchestrated without the cost
of all the bus communication. The feasibility of this system might be
questionable based on the fact that any reasonable DB application has
it's performance determined by disk access. The other thought was to
wonder about the performance of DB applications on WaveScalar.
I guess what I took from this is that the application of relational
algebra to the problem of querying relations was fundamental to the
performance of these systems. I think it's safe to assume that the
development of an algebra for expressing semi-structured queries over XML
will lead to the same kind of gains.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 02:47:21 PDT