Re: deductive databases
Date: Tue, 17 May 2005 06:04:04 GMT
Message-ID: <42898951$1_at_news.unimelb.edu.au>
In article <o5-dnaR_h4DiwhTfRVn-uQ_at_comcast.com>, VC wrote:
>> Thank you for clarifying that, Jan. Returning to OP question: >> >> "AFAIK the expressive power of modern state-of-art database software >> like >> Oracle and PostgreSQL still falls far behind first-order logic: it >> essentially doesn't have functors or recursion."
>
> As to the expressive power, let's take for instance Datalog, a decidable
> subset of Prolog without structures. Datalog's expressive power is
> equivalent to that of relational algebra + recursion.
...
> Since all the major databases implement some form of recursive query (DB2
> amd Yukon WITH....UNION ALL, and Oracle CONNECT BY), SQL's expressive
> power equals and even exceeds Datalog's since the latter does not even
> implemet arithmetic addition (it would have made it undecidable), let alone
> more complicated stuff.
Pure Datalog is a tool for proving theorems about the expressiveness of different query languages. No-one would use pure Datalog as a serious query language; they would use something much more expressive. For example, the Aditi deductive database will be able to use the full power of the Mercury programming language in queries.
SQL with recursive extensions may be able to express all queries expressible in Datalog (I haven't seen a proof), but in all but very simple cases it won't be at all convenient. Queries that would naturally be written as mutually recursive predicates in Datalog would most likely be very painful to write in SQL.
Simon Taylor. Received on Tue May 17 2005 - 08:04:04 CEST