Re: Relational lattice

Jan Hidders wrote:
> That would be fine if all your definitions and proofs were easily
> generalizable for the n-ary case. For most of them this is true, but
I
> have severe doubts over the simulation of the set difference. So the
> conclusion is that you did not proof what you claim in the article,
> i.e., that your operators are relationally complete.
>
> At first sight I would say you can express exactly all unions of
> conjunctive queries with negation. That's not relationally complete,
but
> still quite a large class of queries and having a nice algebra for
that
> could be very interesting.

I'm confused what does it mean for a set of operators to be relationally complete. Is it

1. All the classic operators should be expressed in terms of the new ones. More precisely, given an expression in terms of projection, selection, CP, union, and minus, then one have to be able to exhibit an equivalent expression in terms of generalized union and join.

or

2. Given a set of equations in terms of classic operators, one have to exhibit an equivalent set of equations in new terms.

Clearly 1 is stronger than 2. Set difference equation X=A\B could be written as

(A join B) union X = A
A join B join X = {}

As you might see, I'm reluctant to consider set difference as an operator of the same importance as join and union. The situation is similar to traditional algebras in math, where minus is not an operator admitted into the primary set of axioms.

> > sigma_R(x,y) pi(x,y,z) A(w,x,y,z) = pi(x,y,z) sigma_R(x,y)
> > A(w,x,y,z)
>
> Of course. The proof is trivial. You can simply prove it from the
> set-theoretic definitions. You have a problem with that just because
it
> is not an algebraic proof?

Algebraic proof is supposed to be much easier for the machine (aka query optimizer) to do. Covering all the query transformations with a single method seems to be a very attractive goal.

> It's very unlikely that such a normal form with reasonable properties

> exists because the equality of relational algebra is undecidable.

OK

> Let's start with understanding with (1) what it is that you actually
> claim (i.e. formulating a formal theorem) and

That is the hard part.

BTW, implementing "an experimental relational lattice system" was a breeze. One day exercise in java programming! Among the other things I checked if the lattice is special in any way. Unfortunately, even weekest lattice property -- semiconvexity -- doesn't generally hold. Received on Wed Mar 02 2005 - 23:56:31 CET