Relational lattice

Jan Hidders wrote:
> Mikito Harakiri wrote:
> > http://arxiv.org/abs/cs.DB/0501053
>
> Very interesting link. But you not only have to admit them as
> intermediate results, you need them in your base language in order to

> express certain queries. Strictly speaking the language consists of
the
> two operators plus an (infinite?) set of these infinite relations.
I'm
> not sure if that simplifies much.
>
> Strictly speaking Vadim doesn't really prove that because he only
shows
> that he can simulate the manipulation of binary relations, which is
> strictly weaker than full first order logic. But it could be that his

> proof can be generalized for the n-ary case, I haven't checked that.

I'm not sure if I understand your comment about binary relations. The use of binary relations is purely accidental in most parts of the article. It simply reflects my preference to use cleaner notation. Alternative, more formal language would involve "more general" expressions spiced with a lot of subscripts.

It is indeed hard to tell if this development has any practical applications yet. The main goal is to make all algebraic manipulations formal. Consider, for example, the following identity in the standard RA:

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)

where R(x,y) just an arbitrary predicate for selection operator (it doesn't have to be binary).

This rule is folklore, so it's hard to find a reference which would contain a proof. I assume that the "standard" proof would be something like this.

1. Let's make sure the relation signature is identical on both sides of the equation.
2. Let's check which tuples on the both sides of the equation are.

Algebraic proof would start with rewriting this equation in terms of lattice operations, first

R(x,y) join ( A(w,x,y,z) union E(x,y,z) ) = ( R(x,y) join A(w,x,y,z) ) union E(x,y,z)

where E(x,y,z) is empty relation. Note that we also have

R(x,y) <= E(x,y,z)

The equation looks like lattice modular law, but the problem is that relational lattice is not modular.

Being unable to prove even simplest identities is very disappointing. For larger RA expressions transforming them to lattice form just increases the size, without any obvious benefits. Without distributivity law it's even unclear if there is a normal form for lattice expressions.

One more disappointment is that the alternative reduction for minus is goofy. Without it, the only other reduction that works uses aggregates. Aggregates, however, are out of scope of the article, as we can no longer appeal to the idea of aggregation being an extension of projection.

It is fair to conclude that a lot remains yet to undestand. Received on Sun Feb 13 2005 - 17:28:38 CET