david@cullsj.UUCP (David Taylor) (06/20/89)
Could you please post some references on deductive databases? I'm interested in tutorials as well as surveys of recent work. Thanks David L. Taylor
kemp@munnari.cs.mu.oz (David Kemp) (06/21/89)
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 ---------------------------
kemp@munnari.cs.mu.oz (David Kemp) (07/02/89)
Here are some references as I promised. Hundreds of papers have been published in this area, and so I will just list a few of my favourites... A reasonable introduction is the book "Principles of Database and Knowledge-base Systems", J. Ullman, Computer Science Press, 1988. J. Ullman also wrote a reasonable introductory paper %A Jeffrey D. Ullman %T Implementation of logical query languages for databases %J ACM Transactions on Database Systems %K tods %V 10 %N 3 %D September 1985 %P 289-321 %K nonprocedural languages, query languages, logic programming predicate logic, capture rule, Horn clause, Prolog relational database, recursion A reasonable introduction to some different methods of answering queries to deductive databases is given in %A Francois Bancilhon %A Raghu Ramakrishnan %T An amateur's introduction to recursive query processing strategies %J Proceedings of SIGMOD '86 %E Carlo Zaniolo %C Washington, D.C. %D May 1986 %O published as SIGMOD Record 15:2 %K sigmod86 %P 16-52 The following book has some good papers on the topic %B Foundations of Deductive Databases and Logic Programming %E Jack Minker %I Morgan Kaufmann Publishers %C Los Altos, California %D 1988 %K fddlp %P 217-240 There is a book containing a very large bibliography on logic prgramming. (deductive databases have their roots in logic prgramming). %A Isaac Balbin %A Koenraad Lecot %T Logic Programming: A Classified Bibliography %I Wildgrass Books %C Melbourne, Australia %K book %D 1985 Most database conferences these days have a section devoted to deductive databases. Have fun reading and learning. - David
kemp@munnari.cs.mu.oz (David Kemp) (07/22/89)
Just realized I should have put a more descriptive Subject: entry in my first posting in case anyone interested in deductive databases happens to see the Subject: entry only and skips it.