Re: deductive databases

Please see below:

"Mikito Harakiri" <mikharakiri_nospaum_at_yahoo.com> wrote in message news:1116265939.405452.181220_at_o13g2000cwo.googlegroups.com...
>
> Jan Hidders wrote:
>> Mikito Harakiri wrote:
>> >
>> > For crist sake, what "functor" in logic are you talking about?
> There is
>> > no such index entry in the Mendelson's "Intro to Mathematical
> Logic"
>> > textbook.
>>
>> Try looking for "function symbol".
>
> 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."
>
> In SQL DBMSs aren't "function symbols" just UDFs (aka stored
> procedures), then? Including fairly recent incarnations: table
> functions?
>

Using the word "function symbol" with respect to the Prolog data structure makes as much sense as the "functor" but that's the jargon people use. Whatever you call the beast, it's just a data structure label, not much different from say a C/C++ structure variable name.

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. E.g. a row in the Oracle demo table 'Emp(id int, name varchar(10), salary int)' might be represented by the following Datalog "fact":

emp(1234, john, 120000).

Datalog's relation/predicate maps to a relational table. Now, to find out the employee name and salary knowing his id, you'd ask this:

emp(1234, N, S).

... which is the same as SELECT name, salary FROM emp WHERE Id=1234;

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.

If you are curious about this sort of things, you might take a look at the XSB Prolog database interface (
http://www.cs.sunysb.edu/~sbprolog/manual2/node69.html ).

VC Received on Tue May 17 2005 - 05:05:44 CEST