On Deductive Databases with Incomplete Information

Qinzheng Kong and Graham Chen

In order to extend the ability to handle incomplete information in a definite deductive database, a Horn clause based system representing incomplete information as incomplete constants is proposed. By using the notion of incomplete constants the deductive database system handles incomplete information in the form of sets of possible values, thereby giving more information than null values. The resulting system extends Horn logic to express a restricted form of indefiniteness. Although a deductive database with this kind of incomplete information is, in fact, a subset of an indefinite deductive database system, it represents indefiniteness in terms of value incompleteness and therefore it can make use of the existing Horn logic computation rules. The inference rules for such a system are presented, its model theory discussed and an indefinite model theory proposed. The indefinite model theory is consistent with minimal model theory and extends its expressive power.

H.1.1 [ Models and Principles ]: Systems and Information Theory-- information theory ; H.2.4 [ Database Management ]: Systems-- query processing ; I.2.3 [ Artificial Intelligence ]: Deduction and Theorem Proving-- logic programming

Design, Management, Theory

Deductive databases, incomplete information, Horn clause, query evaluation, Prolog

ACM Transactions on Information Systems, Vol. 13, No. 3, July 1995, pp 354-369.