Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!usc!cs.utexas.edu!uunet!murtoa.cs.mu.oz.au!munnari.oz.au!kemp@munnari.cs.mu.oz
From: kemp@munnari.cs.mu.oz (David Kemp)
Newsgroups: comp.databases
Subject: Deductive databases (was Re: Dumb Question (Outer Join))
Message-ID: <1601@munnari.oz.au>
Date: 21 Jun 89 00:36:16 GMT
References: <549@daitc.daitc.mil>
Sender: news@cs.mu.oz.au
Reply-To: kemp@munnari.cs.mu.oz
Lines: 98

From article <549@daitc.daitc.mil>, by jkrueger@daitc.daitc.mil (Jonathan Krueger):
> <Deleted good comment on researchers and the net, and other stuff related to>
> <outer-joins, SQL, prolog and deductive databases.>
>
> ....  As a prolog dilettante, this has always been a source of great
> mystery to me.  For instance, does it matter if rules are written in
> the opposite order?  If so, the result is not the union of the results
> of the two rules, but rather a bayes function.

In Prolog, the order the rules are written in does matter.  However,
in deductive databases it doesn't (at least it is not supposed to).
In fact the order in which literals are written in the body of a rule
in deductive databases shouldn't matter either.
The query/rule  languages for deductive databases are, in general,
not supposed to be general purpose programming languages in the way
Prolog is.  Thus there is no concept of "order of execution" of the rules.
Some positive aspects of this are:
	i) The language is even more declarative than Prolog. That is,
you say what you want, not how to get it.
	ii) The system has a lot of flexibility to transform and re-order
the rules in a logical way without changing the meaning of the rules.

> 
> <Deleted comments on how we weren't really looking at outer joins anyway>
>
So this is what an outer join really is...
> To amplify the point, let's add another row:
> 
>  	A 1 2		B 1 2
> 	  a b		  a a
> 	  c d		  c c
> 	  e f		  g h
>  
> Is not the outer join of "A.1 = B.1":
>  
>  		a b a a
>  		c d c c
> 		e f _ _
> 		_ _ g h
In a deductive database this is done with
	answer(X, Y, X, Z) :- relA(X, Y), relB(X, Z).
	answer(X, Y, nil, nil) :- relA(X, Y), not some Z relB(X, Z)
	answer(nil, nil, X, Y) :- relB(X, Y), not some Z relA(X, Z)
	?- answer(A, B, C, D).
> 
> <Deleted stuff about comparing efficiency of SQL with Prolog>
>
>>The outer joins in [RTI's technical note] are expressed as follows:
>>Example 1. (The case where we are not interested in entries in appraisal
>>that do not have corresponding personnel entries.)
>>	answer(X, Y) :- personnel(X), appraisal(X, Y).
>>	answer(X, 0) :- personnel(X), not some Y appraisal(X, Y).
>>("some Y" means "there exists a Y")
> 
> So, which prolog is this with negation :-) ?
This syntax is accepted by NU-Prolog (University of Melbourne).  I guess that,
as with most languages, once you have used them a lot, you find them
easy to understand.  (When I first saw C code I thought it would be
impossible to become familiar with, but now it is my 1'st choice in many
situations).

>  Seriously, "not exists"
> seems as awkward to express in prolog as outer joins are in standard
> SQL.  Prolog's limits appear to be straightforward consequences of the
> expressive power of Horne clauses, however.  SQL limits appear to be
> casualties of poor language design, unrelated to the relational model.
> Although hardly to SQL's credit, this implies we might fix outer joins
> for SQL more easily than add negation to prolog.

I am quite happy with NU-Prolog's implementaion of negation, but as I
mentioned, that may be because I have been working with it for too long :-).
Deductive databases use a logical foundation for negation that
isn't too difficult to understand either.

> I'd be interested in
> seeing the full example in prolog using cut and fail, and comparing
> that syntax to the typical SQL superset for the same.

In NU-Prolog, no cuts or fails are needed.  You just give the query:
?- solutions(answer(A, B, C, D), answer(A, B, C, D), ANS).
ANS will be a list of all the requested answers.
NU-Prolog has other logical features that allow you to avoid cuts and
fail-loops, so that more understandable code can be written without
losing efficiency (much anyway :-).
In deductive databases cuts have no meaning!!!

I Guess net news is not the place to be giving a tutorial intro to
deductive databases, so I will stop here and give some reasonable
references worth reading in my next posting.

---------------------------
David B. Kemp
University of Melbourne
Parkville 3052
Australia

e_mail: kemp@murtoa.cs.mu.oz.au
---------------------------