From: francois@ecrc.de (Francois Bry)
Subject:  Databases and Deduction
Organization: European Computer-Industry Research Centre GmbH, Munich, Germany
Date: Tue, 21 Jul 1992 07:57:18 GMT


Gerry Trinidad (gerry@coral.cs.jcu.edu.au) recently asked if someone could 
elaborate on Manfred Jeusfeld's (jeusfeld@picasso.informatik.rwth-aachen.de)
remarks: 

> In last December i participated in a workshop on applications of 
> deductive databases. It seems that there are only very limited ideas
> on how to use deductive techniques for applications development.
> 
> The reason is quite obvious: deductive rules are Turing-incomplete. Thus,
> one has to program anything which is "non-deductive" in a programming
> language, e.g. Cobol,C++.

In my opinion, Manfred's remarks reflect a slight misunderstanding of what 
deduction techniques and deductive databases are. (I am sorry, Manfred!) Since 
Manfred's opinion seems to be widespread, it might be worth to give here 
another viewpoint.

First of all, what are deduction rules and deductive databases? 

For many people, deduction rules and deductive databases preclude nested terms 
(such as p(f(a,b), g(c)), like 1st-normal form relational databases. This 
belief, has several sources. 

One of them is the notion of "datalog". Datalog is indeed a 1st-normal-form 
formalism. Historically, this name is a contraction of "database Prolog", an
expression which was used in the Prolog and Logic Programming community some 
15 years ago for denoting a strict subset of Prolog and Logic Programming which 
is very close to the query languages of 1st-normal form relational databases 
(cf. for example [1]). Thus, the notion "database Prolog" has been created 
because databases had no nested terms. Now, some people believe that deductive 
databases should have no nested terms because of the notion "datalog"! In my 
opinion, there are no reasons for precluding nested terms from databases in 
general, and from deductive databases in particular. One should remember that 
providing database systems with data structuring notions (i.e. object-
orientation) is an important and productive area of research!

A second reason is that many theoretical studies on and prototypes of deductive
database systems are restricted to 1st-normal-form languages. Again, this is
no more than a step in the research. (As a matter of fact, the restriction seems
to be more frequent in theoretical studies than in running systems.)

A language of deduction rules and facts which does not preclude recursion and 
nested terms is Turing complete. This is almost immediate if a forward 
(bottom-up) evaluation of the deduction rules is assumed (just take a 
logician's definition of a Turing machine such as given in [2]). This is by 
far less immediate if a backward (top-down) evaluation is assumed, but also 
holds, as it has been shown by Sten-Ake Taernlund in a paper published in [3]. 

LDL and Prolog are Turing-complete, while Datalog is not (because it has no 
nested terms).

So much for the assumed limitation of deductive databases, and the necessity
to call for a conventional programming language.


I am a bit surprised about the claim that not much is known on how to use 
deductive techniques for implementing applications. Let me just refer to the
articles [4] and [5] and to the work in Logic Programming for disproving this 
claim. I agree that it would be useful to know even more than we yet know. 
However, I do not think it is senseful to underestimate our understanding of 
the issue. 


There are nevertheless interesting critical questions to ask about the 
deductive database research. I would like to submit the following ones, with 
remarks of my own. Comments are welcome, also from the "opposition"!

+ Should deduction replace conventional programming paradigms in databases? 

I do not think so. In my opinion, deduction techniques are primarily needed for
an intensional specification of data, not for replacing all application 
programs. My own experience in analyzing database applications from the angle
of deductive DBMS is that deduction rules should be seen as playing a similar 
role as facts, records, etc. do in non-deductive databases. I would even 
guess that deductive databases with as many rules as facts will be frequent.
My feeling is that an imperative language is desirable for updating
the data (= the deduction rules and facts). I do not think the side-effect
approach of LISP and PROLOG is appropriate for accommodating changes in 
databases (simple but, in my opinion, convincing arguments are given in [7]).

+ Why arn't there more running deductive DBMSs and up till now no commercially
available systems? 

In my opinion, this is mostly because building such systems require to
combine skills in DBMS implementations and in automated reasoning. I do not
know many people really skilled in both. In general, DBMS implementors have
a rather limited knowledge of automated deduction (often more limited than they
assume, I would say), while people skilled in automated deduction do know 
enough about system issues (they usually are aware of it). However, in 
principle, nothing prevents from overcoming this "culture gap". Whether this 
will happend depend on our capability in starting up database projects 
investigating both system and deduction aspects.

Another reason for the limited number of deductive DBMSs that have been
built is that there a still a number of formal issues that need to be 
clarified (like for example, the semantics and processing of negation). However,
this should not be seen as a drawback of the approach. After all, there already
has been a lot of important issues that took much more time to solve 
than it had been assumed!

A third important reason is the conjuncture: a significant part of the research on deductive database systems was pursued in industrial labs. These labs are,
as I can observe, nowadays not very wealthy. Moreoverer, the research pursued 
there often suffers from a lack of continuity as far as the goals are concerned. 

+ Have deduction techniques a future in database research? 

I think so, but I would guess that this future is not to be expected only
where deduction is currently used in databases. Decution in databases is usually
understood as deduction in the data model. This is, I think, desirable, but 
this is not all. Why not to apply deduction to specifying and analyzing 
Abstract Data Types (in lieu of algebraic specifications [6])? Why not to use 
deduction for compiling database queries (like was done at ECRC for simplifying 
integrity constraints or for implementing the Magic Sets method)? Why not to 
use deduction for query optimization? To database schema design (something like 
that has been studied at ECRC)? More generally, my feeling is that deduction is 
not only relevant in data modeling, but also for some aspects of DBMS 
implementation. Whether this relevance will be exploited depends on our 
capability in building up research teams for investigating the issue...

(Disclaimer: This note is not an official statement of my employer ECRC. The
viewpoints expressed here are not necessarily those of ECRC. F.B.)


References:
-----------

[1]   F. Pereira
      Prolog and Natural Language Analysis
      CSLI, 1987
      (in my opinion, this excellent tutorial deserves more attention from
      the database community).

[2]   J. Barwise, editor.
      Handbook of Mathematical Logic
      North-Holland, 1977

[3]   K. Clark and S.-A. Taernlund
      Logic Programming
      Academic Press, 1982

[4]   S. Tsur
      Applications of Deductive Database Systems
      Proc. COMPCON 1990

[5]   S. Tsur
      Deductive Databases in Action. 
      Proc. PODS 1991

[6]   J. Guttag
      Abstract Data Types and the Development of Data Structures
      Comm. ACM, 20 (6), 1977

[7]   F. Bancilhon
      A Logic-Programming/Object-Oriented Cocktail
      SIGMOD-RECORD, 15 (3), 1986
--
Francois Bry
ECRC, Arabellastrasse 17, D - W 8000 Muenchen 81, Germany
e-mail: bry@ecrc.de   tel.: 089 - 92 69 91 48   fax: 089 - 92 69 91 70
Newsgroups: comp.databases.theory