Re: What databases have taught me

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Mon, 26 Jun 2006 01:45:37 GMT
Message-ID: <5%Gng.2307$pu3.57431@ursa-nb00s0.nbnet.nb.ca>

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 Sun Jun 25 2006 - 20:45:37 CDT