Re: What databases have taught me

From: Bob Badour <>
Date: Mon, 26 Jun 2006 01:45:37 GMT
Message-ID: <5%Gng.2307$>

Marshall wrote:

> Dmitry A. Kazakov wrote:

>>My feeling is that it could turn quite hard for RA. That's why I've
>>presented it! (:-)) The feeling is based on a trivial observation that the
>>nodes of the dual graph aren't present in the original graph either as
>>nodes or as relations. You have to "invent" them (identify the regions).

> Every query is an "invention" in this sense. Sometimes it is a trivial
> one, when all one does it pick out some rows and/or columns. But
> you can also write expressions. Simple example: select a+b as c from R.
> Where did c come from in the result set? It wasn't there in the
> original relation.
> Does anyone know if SQL with transitive closure is Turing complete
> or not? Alternatively, does anyone know what minimum additional
> functionality is necessary to bring SQL to Turing completeness?
> What about same question for the RA?
> I note that any relational algebra that allows natural join with
> recursive functions is Turing complete.

Dmitry is wrong about identifying regions. (See my reply where I directed you to EWD 696.) An edge is a non-empty set of at most two nodes. A region is a non-empty set of nodes. This suggests to me the domains in question are relation valued.

The 'nodes' of a dual are regions. The 'edges' of a dual are a tuple of a non-empty set of at most two regions plus the edge in the original graph which acts as the separator between the region(s). Received on Mon Jun 26 2006 - 03:45:37 CEST

Original text of this message