From: Joe Xavier (joexav@microsoft.com)
Date: Wed Apr 28 2004 - 10:39:35 PDT
Review: On the unusual Effectiveness of Logic in Computer Science (First 3 sections)
Main concepts:
The paper stresses on the importance of logic in CS and pushes some arguments for why it's more effectively used in CS than in Mathematics.
They use a number of illustrations including computational complexity and using FO logic as a query language for databases. They hint at the path from FO logic to relational algebra (Codd).
As far as databases go, they discuss why FO logic works for a query language. Advantages they talk about include syntactic variants, using relational algebra for an efficient implementation and scaling using parallel processes.
An important concept that comes out here is that FO queries can (in principle) be evaluated in constant time (given parallelism) despite database size. Although this is easier said than done, it helps to understand that this is theoritically possible. Another interesting point was that every FO query can be broken down into subqueries and the intermediate results produced can be used by subsequent subqueries. This is precisely how the relational operators in databases work - by flowing the results of different operations upwards.
I haven't really thought about database query language from this angle. I'm too used to thinking of tables and columns and that messes things up.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 10:39:41 PDT