Organization: European Computer-Industry Research Centre GmbH, Munich, Germany
Date: Tue, 21 Jul 1992 07:57:18 GMT
Lines: 160
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
