Re: Complete axiomatization of relational algebra

Jan Hidders wrote:

> Wolfgang Schoenfeld wrote:
> > Relational algebra as I understand it is equivalent to first-order
> > logic (i.e. there is a transformation - in both directions - which
> > preserves validity). Since the set of valid first-order sentences is
> > recursively enumerable, the same applies to relational algebra.
> >
> > But I presume your question is: Is there a finite axiom system for
> > relational algebra?
>
> Yes, that is correct.
>
> > I do not know an answer to this, but I remember the corresponding
> > question was open for the algebra of BINARY relations. And it was
> > answered negatively, i.e. there is no finite equational axiom system.
>
> It depends of course on what type of operations you have in your
> algebra. If they have for instance something higher order like the
> transitive closure then this does not imply that there is no finite
> axiomatization of relational algebra. Could you perhaps give me a
> reference to some paper that discusses this?

Any algebra will be complete for what it does, but maybe the object is to be `complete' as that word is used in logic. Or do we want the algebra to be `complete' (to faithfully represent) for some set of operations that are associated with databases? A relational database as some combination of tables with pointers between them would not seem to aspire to the complexity of arbitrary mathematical relations. All a database has is some finite number of fixed elements r with some finite number of properties (field or column, and perhaps better identified as property classes) c and where each property exhibits for a given n some maximal n number of values.

The objective of having a database is to store and retrieve data, and that is done (equivalently) by forming, as previously noted, a normal form propositional logic formula that when applied to the database returns all those elements satisfying that formula. How the predicates of that formula are assembled would seem to be a matter external to the purpose of the database. If we were to ask: what is the algebra that would represent an arbitrary application that could use a database (the possible relations on an arbitrary database), then such an algebra is merely some Turing complete language. However since our purpose is databases and not applications that use databases we only need to identify that small restricted language (I expect).

Perhaps we want to know as a standard feature of the database language what row contains the smallest value (or nearest, next greatest to some value) for a column. We then have a sort or key sequence. What else do we want from the database language (algebra)? What are we trying to do with this algebra?

Regards,

Neil Nelson Received on Wed Feb 21 2001 - 17:17:23 CET