Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: What databases have taught me

Re: What databases have taught me

From: Marshall <marshall.spight_at_gmail.com>
Date: 25 Jun 2006 17:39:20 -0700
Message-ID: <1151282360.639939.48970@i40g2000cwc.googlegroups.com>


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.

Marshall Received on Sun Jun 25 2006 - 19:39:20 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US