Re: Concurrency in an RDB

From: Sampo Syreeni <>
Date: Fri, 29 Dec 2006 18:00:37 +0200
Message-ID: <>

On 2006-12-28, Aloha Kakuikanu wrote:

> What "text" do you have in mind? A set of strings is formalized nicely
> as Kleene algebra.

Yes, but the problem is how to mesh that structure with the RM. The usual way is to treat strings as a domain. To me that somehow seems wrong: of course you can embed any sort of algebraic structure this way, and often it makes ample sense, but then we already know of at least one counter-example (the nested relational model) to the principle. Practically speaking treating a text simply as a string in a column also hides any structure it might have from the relational model, and so forces one to use a separate API (string functions, etc.) and internal data model (e.g. XML) for the text. If you've ever worked with a text database, you'll know that the result can be messy. Then 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.

> 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. The only problem is that transitive closures of natural join structures aren't too interesting. But I bet in the presence of domains, you could work around that as well.

This sort of thinking is also interesting in that it comes close to the categorical point of view -- we're abstracting away from the fine, set theoretical structure of the objects and redefining the domain of discourse in terms of the algebraic properties of the operators -- and it also forces one to work with sets of relations and/or a universal relation scheme, because arbitrary unions are permitted.

Sampo Syreeni, aka decoy -, tel:+358-50-5756111 
student/math+cs/helsinki university, 
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2
Received on Fri Dec 29 2006 - 17:00:37 CET

Original text of this message