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_at_ursa-nb00s0.nbnet.nb.ca>
>
> 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.
Date: Mon, 26 Jun 2006 01:45:37 GMT
Message-ID: <5%Gng.2307$pu3.57431_at_ursa-nb00s0.nbnet.nb.ca>
Marshall 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