Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!ukma!uflorida!haven!vrdxhq!daitc!daitc.daitc.mil
From: jkrueger@daitc.daitc.mil (Jonathan Krueger)
Newsgroups: comp.databases
Subject: Re: Dumb Question (Outer Join)
Message-ID: <549@daitc.daitc.mil>
Date: 19 Jun 89 08:37:51 GMT
References: <423@cimshop.UUCP> <1591@munnari.oz.au>
Sender: jkrueger@daitc.daitc.mil
Reply-To: jkrueger@daitc.daitc.mil (Jonathan Krueger)
Organization: DTIC Special Projects Office (DTIC-SPO), Alexandria VA
Lines: 113
In-reply-to: kemp@munnari.cs.mu.oz (David Kemp)

In article <1591@munnari.oz.au>, kemp@munnari (David Kemp) writes:
>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?

Researchers, their peers, tenure committees, grant reviewers, and
employers don't consider USENET a technical or academic forum.  In
fact, they don't consider it at all.  A moment's calm thought should
convince anyone that they're quite right to think so.  But nothing
stops anyone from reading the literature.  You just won't find it in
comp.databases.  Usually.

>I wish to give a "deductive database" type solution [to outer joins]
>	answer(X, Y, nil, nil) :- relA(X, Y).
>	answer(X, Y, X, Z) :- relA(X, Y), relB(X, Z).

This syntax is indeed simpler.  However, no one ever claimed SQL has a
good syntax.  And you've left unspecified how Z gets instantiated or
not.  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.

>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

Seems to me the first rule would give
	a b
	c d

No?  Actually, checking through David's example, I see

> 	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 _ _

Isn't that the cartesian product?  Isn't the outer join rather:

 		a b a a
 		c d c c

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

>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.

No, we know it can't be any slower than temporary tables.  But it
would be comparable to performance of (nonstandard) SQL engines with
support for outer joins.  In general the syntax that lets you express
clearly and concisely what you want is likely to achieve efficient
implementation.

>However, the new deductive databases being developed can execute this
>query just as fast (if not faster) as any SQL based product.

Of course.  Better yet, they're not mutually exclusive, any more than
use of awk excludes use of sed on textual data.

>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 :-) ?  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'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.

>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?

Well, I'd say the interest is there.  Database programmers need better
tools.  It just takes time to make them available off-the-shelf, to
evaluate them, and to relate them to existing problems and solutions.
Remember where we were only ten years ago.  Or where most systems and
applications still are.

-- Jon
--