SQUALID: A deductive DBMS

Abstract

Most modern companies probably could not function without a database management system (DBMS). Although current DBMSs are becoming increasingly sophisticated, they are still deficient in several areas. One of these areas is deduction.

Human beings have the interesting ability to derive facts from a set of data, even though these facts are not explicitly represented in the data. That is, given appropriate information, humans can deduce new information by applying rules. A deductive database is a database which can perform similar deductions on the data stored within it. This has the advantage that some data can be stored implicitly using rules, rather than explicitly. This reduces the amount of storage the database occupies. The use of rules also allows us to store new kinds of data, such as recursive data or indefinite data.

Several deductive database systems have been developed, but many of them only approach the problem from a theoretical point of view; practical considerations such as efficiency and ease of use for end-users have often been neglected. Many systems were also developed completely from scratch, rather than taking advantage of existing facilities. That is, it should be possible to take an existing DBMS, and extend it with deductive capabilities.

In this work we introduce the concept of a deductive database, and some of the problems associated with implementing such a system. We then discuss the implementation of a system called SQUALID (for Structured Query And Logical Inference Database). This system is based on an existing DBMS, Rdb/VMS, which has been extended with facilities for creating and manipulating rules. An extended version of the standard query language SQL is used. All rules and data are stored in a conventional database, allowing SQUALID to take advantage of the efficiency of the underlying DBMS.