Abstracts of Deductive Databases Papers

The Aditi Deductive Database System

Jayen Vaghani, Kotagiri Ramamohanarao, David Kemp, Zoltan Somogyi, Peter Stuckey, Tim Leask and James Harland

VLDB Journal 3:2:245-288, April, 1994. Deductive databases generalize relational databases by providing support for recursive views and non-atomic data. Aditi is a deductive database system based on the client-server model: it is inherently multi-user and capable of exploiting parallelism on shared-memory multiprocessors. The back-end uses relational technology for efficiency in the management of disk based data and uses optimization algorithms especially developed for the bottom-up evaluation of logical queries involving recursion. The front-end interacts with the user in a logical language that has more expressive power than relational query languages. We present the structure of Aditi, discuss its components in some detail, and present performance figures. Paper

An Aditi Implementation of a Flights Database

James Harland and Kotagiri Ramamohanarao

in Applications of Logic Databases, Raghu Ramakrishnan (ed.), Kluwer Academic, 1994.

We describe the implementation of a flights database in the Aditi deductive database system. Such a database requires a large amount of information to be stored, as well as using a variety of rules to construct flight schedules. Hence we believe that the flights database is a good example of the application of deductive database technology to a realistic problem. The flights database also provides a platform on which new optimisation methods and techniques may be tested and measured, and was the main motivation for the integration of top-down and bottom-up execution mechanisms within Aditi. Paper

Subsumption-free Bottom-up Evaluation of Logic Programs with Partially Instantiated Data Structures

Zoltan Somogyi, David Kemp, James Harland and Kotagiri Ramamohanarao

Proceedings of the International Conference on Extending Database Technology, Cambridge, March, 1994.

Most deductive databases impose restrictions on the terms that can be used in them: they require that generated tuples be fully ground, i.e. contain no variables. Without this restriction, query evaluation of general programs needs subsumption tests in order to terminate correctly, and subsumption tests are expensive. We study a class of programs that can handle terms with both variables and function symbols but for which subsumption tests are not necessary. This class is based on the notion of modes, which generalise adornments by not requiring that ``bound'' be synonymous with ``ground''. We show how programs in this class may be recognized and how they should be transformed into an executable form, and then prove that bottom-up evaluation of the resulting programs does not require subsumption tests. Paper

Constraint Propagation for Linear Recursive Rules

James Harland and Kotagiri Ramamohanarao

Proceedings of the International Conference on Logic Programming 683-699, Budapest, June, 1993.

There are many ways in which the query answering process for deductive databases may be optimised. Many of these methods rely on applying constraints as soon as possible, to avoid the production and later rejection of facts which are not relevant to the query. This propagation of constraints is much simpler for left-linear programs than for many others. In this paper we show how to transform right-linear and mixed-linear programs into a left-linear form, to make constraint propagation more effective. Our technique generalises the magic set transformation for linear programs; the magic set transformation can only propagate constraints of the form X = a, whereas our technique can handle arbitrary goals as constraints. Paper

Constraints for Query Optimization in Deductive Databases

James Harland and Kotagiri Ramamohanarao

Proceedings of the Second Far-East Workshop on Future Database Systems 332-336, Kyoto, April, 1992.

There are many ways in which the query answering process for deductive databases may be optimised. At the heart of many of these methods is some form of constraint on the variables of the query, so that facts which are not relevant to the query are not computed. In this paper we show how fold/unfold transformations may be used to propagate some forms of constraint which are not captured by techniques such as magic sets. In particular, the fold/unfold transformation provides a straightforward way to propagate constraints involving multiple occurrence of a variable. Paper