Re: deductive databases

In article <Y5Age.33690$B82.990538_at_news20.bellglobal.com>, Christopher Browne wrote:
> In the last exciting episode, alex goldman <hello_at_spamm.er> wrote:

>> Nilsson's book [1] talks about using first-order logic (and its subsets) as
>> the language for deductive databases. The book is 10 years old, and yet,
>> 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. Does anyone know why?
 

> The point is more that people don't generally understand logic, and
> _especially_ the folk for whom it the move from COBOL-based ISAM to
> the uncertainty of the degree of declarativeness of SQL.
>
> If the fact that cost-based optimizers makes it somewhat uncertain how
> an SQL processor will evaluate a particular query is disturbing (and,
> to many, it is), the leap to the greatly less certainty of
> backtracking is too scary for words.

Efficient deductive databases do not use backtracking. They use relational operations just like SQL databases. For non-recursive queries, there is no reason for a deductive database to be any less efficient or predictable in performance than an SQL database. The performance of recursive queries is much more difficult to predict, whether you are using SQL or a deductive database. For example the sizes of relations to be joined can be very different from one recursive invocation to the next within the same query, which makes the optimizer's life very difficult.

Part of the reason for the lack of interest in deductive databases is that the systems that have been implemented have been university research projects that have produced nice query languages, but without the (perceived) robustness, performance, tools and guaranteed ongoing support needed for commercial adoption. I have been involved with one of these efforts (the Aditi project <http://www.cs.mu.oz.au/aditi>, which uses Mercury <http://www.cs.mu.oz.au/mercury> as its query language).

I think it would be much easier to promote a deductive query language built on top of an existing mature database system, selling it as cleaner and easier to use than SQL, with the increased expressive power being an added bonus. At the time the Aditi project started, SQL databases weren't extendable enough for this to be done with reasonable performance. Looking at PostgreSQL now, I think that has changed.

> One genuine problem with "the Prolog way" is that the order in which
> rules are established will affect outcomes. That's a bit disturbing
> for all of us...

While deductive query languages may look like Prolog, they are not Prolog, and do not share Prolog's non-logical behaviour.

Simon Taylor. Received on Fri May 13 2005 - 08:47:40 CEST