Non-Determinism in Deductive Databases


Keywords: non-determinism, deductive databases, active databases

Start Date: 1 January 94 / Status: finished / Duration: 30 months

[ participants / contact]

Objectivies and Approach

The ultimate goal of this collaborative action is the design of a logic-based language which incorporates appropriate non-deterministic operators.

The European participants will contribute both in the analysis of the non-deterministic operators and in the design of a prototypical logic database language supporting non-determinism. The American team will share the work on analysis of non-determinism in deductive databases with the European participants, and will provide a test bed for the language extensions which may emerge during the collaborative activity.

Progress and Results

The main technical results of the project are:

A complete understanding of the role of non-determinism in logic-based database languages regarding their semantics, implementation efficiency, expressiveness, query complexity, and application impact has been achieved.

The design of a logic-based language which incorporates non-deterministic operators of increasing expressive power has been laid down. The current prototype of LDL++ developed at UCLA provides an approximation of such non-deterministic logic-based database language.

A class of application areas has been identified which are amenable to be tackled with the language designed in this project. The application areas include temporal and spatial reasoning, uncertainty and approximate reasoning, dynamic aspects of databases and information systems, knowledge discovery, semantic integration in heterogeneous databases, planning, GIS, and intelligent information interfaces.

Information Dissemination Activities and/or Exploitation

A workshop on Advances in Logic-based Database Languages has been organised (supported also by COMPULOG NET) in Prague in January 1995. The final workshop on Logic in Databases, LID'96, took place in San Miniato, Italy, in July 1996. A special issue of "Annals of Mathematics and Artificial Intelligence" that is dedicated to the first workshop is in press. The proceedings of the second workshop have been published in the LNCS series, Vol. 1154, by Springer-Verlag, 1996. More information about the two workshops can be found at: http//, and http// respectively. The project's home page is:


Università di Pisa
Dipartemento di Informatica
Corso Italia 40
I - 56125 Pisa, I

EU Partners

University of Pisa, I
INRIA Rocquencourt, F
University of Calabria, I

Non-EU Partners

University of California at Los Angeles, USA
University of Maryland, USA


Prof. Dino Pedreschi
Tel: +39 50 887 252
Fax: +39 50 887 226

INCO synopses home page INCO cooperation index INCO keyword index
INCO acronym index INCO number index INCO Working Groups index
synopses home page all keywords index all acronyms index all numbers index

NDID - EC-US033, May 1997

please address enquiries to the ESPRIT Information Desk

html version of synopsis by Nick Cook