Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!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: Re: Dumb Question (Outer Join)
Message-ID: <1591@munnari.oz.au>
Date: 17 Jun 89 07:34:26 GMT
References: <423@cimshop.UUCP>
Sender: news@cs.mu.oz.au
Reply-To: kemp@munnari.cs.mu.oz
Lines: 88

From article <423@cimshop.UUCP>, by davidm@cimshop.UUCP (David Masterson):
> What is the method for doing an outer join in SQL?  For instance, given:
> 
> 	A 1 2		B 1 2
> 	  a b		  a a
> 	  c d		  c c
> 
> The outer join of "A.1 = B.1" should be:
> 
> 		a b a a
> 		a b _ _
> 		c d c c
> 		c d _ _
> 
> but how do you express it in standard SQL????
> 

jkrueger@daitc.daitc.mil (Jonathan Krueger) answered David Masterson's
question by posting INGRES Technical Note #79. (Article: <538@daitc.daitc.mil>)

I wish to give a "deductive database" type solution.

I have been disappointed at the complete lack of discussion about deductive
databases in this news group.  I realize they are yet to hit the commercial
world (except in the form of Prolog front ends to existing relational
database products), but huge amounts of research is being done in the area.
So why don't any of you researchers use the net?

Now to the point of my posting.
Without trying to claim that languages based on relational calculus, or
symbolic logic are any better than SQL, I am posting a solution to
David's question which uses a deductive database language (just a pure
form of Prolog with some logical extensions).

The outer join of "A.1 = B.1", as defined by David Masterson, is expressed
using just two rules.  Those of you who are not familiar with Prolog, may
not understand what follows,  but believe me, it is far simpler than
explicitly creating temporary relations as suggested in the INGRES
Technical Note #79.
My solution:
	answer(X, Y, nil, nil) :- relA(X, Y).
	answer(X, Y, X, Z) :- relA(X, Y), relB(X, Z).

The result is the union of the results from the two rules. Using the data
given in David's posting, the first rule would give:
	a b _ _
	c d _ _
and the second rule would give
	a b a a
	c d c c

Those of you who are familiar with Prolog may scream that Prolog is slow
since it will use a very naive "loop join" of relA and relB.  However,
the new deductive databases being developed can execute this query just
as fast (if not faster) as any SQL based product.
A deductive database would actually execute the same relational algebra
operations as a relational one with a SQL front end.

The outer joins in Jonathan Krueger's posting 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")

Example 2. (For cases where appraisal may have entries without corresponding
personnel entries and we want those included in the answer)...
	answer(X, Y) :- appraisal(X, Y).
	answer(X, 0) :- personnel(X), not some Y appraisal(X, Y).

By the way, this is only just the tip of the ice-burg.  Deductive databases
allow recursive rules and some will even allow structured data (non-first
normal form) and even nested relations.  This allows simple solutions to
problems like the "Correlated Update Problem" (posted to comp.databases by
carl.pedersen@dartmouth.edu (Carl Pedersen) on 24 May 89 article <13626@dartvax.Dartmouth.EDU>).

Why have I posted this?  Is it an attempt to justify all the work we have
been putting into developing one of these monsters?  Are deductive databases
just another neat idea destined to never make much impact in the real world?
------------------------------
David B. Kemp
University of Melbourne
Parkville 3052
Australia

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