Re: Concurrency in an RDB

Sampo Syreeni wrote:
> ...if you try to
> work directly with the Kleene algebra analogy, so that concatenation is
> treated on an equal footing with joins, the result will no longer look
> like the relational model, and you'll also have great trouble defining
> the counterparts of the rest of the relational operations, like
> projection.

They are two different ("incompatible"?) algebras. One is distributive semiring, the other is some kind of non-distributive lattice (with boolean fragments as shown at the pictures at http://arxiv.org/pdf/cs.DB/0603044).

Well, let's see if Kleene algebra has some analog of projection. In RA projection is

<relation> \/ <empty relation>

and the result is interesting only when both relations have different set of attributes. In Kleene algebra union is always a set operation, so nothing interesting there.

What about selection? In RA it is a join

<relation1> /\ <relation2>

and the result is interesting when both relations have some attributes in common. If we blindly apply this idea to Kleene algebra then we'd have selection to be nothing like word pattern matching (which I assume we are after).

> > If one accepts that join and union are the 2 fundamental operators of
> > relational algebra, and agrees that Kleene star is somewhat less
> > important operator, than both algebras hinge on join and union. The
> > fundamental difference is that relational join is commutative, while
> > Kleene's is not.
>
> Yes. The analog of the star would then be the transitive closure, so it
> can be practically important as well.

In matrix language transitive closure is exponent. Exponent is important operator but not basic algebraic operation like addition and multiplication. Received on Fri Dec 29 2006 - 19:05:48 CET