Aaron Bingham wrote:
David Fetter wrote:
In SQL, you can do this (this example condensed from Libkin's
"Expressive Power of SQL" on the page above):
SELECT
(SELECT count(*) FROM table_1) <
(SELECT count(*) FROM table_2)
AS "Can't compare cardinalities in first order logic";
Note the name of the output column. It's important and true, as you
can verify if you care to do your homework on foundations of
mathematics. Relational algebra is a subset of first-order logic
<http://en.wikipedia.org/wiki/Relational_algebra>, and as a direct
consequence, you can't do this simple but interesting thing with it.
I must be missing something important. What aspect of the above query
is supposedly impossible in relational algebra and/or relational
calculus?
Having looked at this again, I now see that your statement above is
strictly correct, but misleading. Relational algebra consists of a
limited number of operators on relations. As such, relational algebra
says nothing about aggregate functions such as COUNT, or how to build a
relation from scaler values. Relational algebra is, however, only part
of the relational model as defined by Date, and Tutorial D includes all
the previsions we need to re-write the above query. The above query
could be expressed in Tutorial D more-or-less as follows (I'm not sure
if arbitrary strings are allowed as column names in Tutorial D, but
that's beside the point):
RELATION { TUPLE { "Can't compare cardinalities in first order logic"
(COUNT(table_1) < COUNT(table_2)) } }
Placing the result of the comparison in a relation seems unnecessary,
but I have done so for equivalence to your example. Or did I miss the
point?
Regards,
--
--------------------------------------------------------------------
Aaron Bingham
Senior Software Engineer
Cenix BioScience GmbH
--------------------------------------------------------------------
