Relational Completeness

From: Marshall Spight <mspight_at_dnai.com>
Date: Fri, 17 Sep 2004 23:02:14 GMT
Message-ID: <V1K2d.451720$%_6.441906_at_attbi_s01>

I'm confused by the term "relational completeness."

As near as I can tell, someone (Codd?) came up with a set of operations on relations, and said they were complete, because they were just as expressive as the relational calculus, and everyone since then who wishes to show completeness of some set of operators merely showed their set was as powerful as the original set. But I've never found any reference for why the relational calculus is supposed to be complete.

In boolean algebra, one can show that NAND is sufficient to construct any truth table. While I don't actually know any clever proof of this, it's easy enough to show by construction. One can show completeness of a set of boolean operators by construction.

Consider this table:
1 1 xa
1 0 xb
0 1 xc
0 0 xd

Now one can imagine {xa, xb, xc, xd} as completely specifying a boolean operation. Given that this is boolean *algebra* then each of the xn is either 1 or 0, so there are exactly sixteen possible values for the set of xn. (Again, we can construct a truth table for them.)

In order for a set of boolean operators to be complete, one must be able to construct every one of the 16 possible values of {xn}. Which can be done with {AND, NOT}, or with {OR, NOT}, or with {NAND}, etc.

Now while this is certainly not any earth shaking result, it's certainly COMPLETE for the domain; every function on two bits that can exist has been accounted for.

Is there a similar demonstration that can be done for relations? Clearly it would be more complicated than the boolean problem. (What wouldn't?) Or is there some clever proof of the completeness of the relational calculus? What is the basis for calling the relational calculus complete, especially given that it isn't computationally complete?

I'm also not clear on where aggregates or folds fit in here. Map and filter are pretty easily expressed in the relational algebra with join and restrict, but what about aggregate/fold/reduce or whateven you want to call it? I mean, you can't do count() with the "complete" relational algebra.

Marshall Received on Sat Sep 18 2004 - 01:02:14 CEST