UNCERTAIN DEDUCTIVE DATABASES - A HYBRID APPROACH

Uncertainty in deductive databases and logic programming has been mode led using a variety of (numeric and non-numeric) formalisms in the pas t, including probabilistic, possibilistic, and fuzzy set-theoretic app roaches, and many valued logic programming. In this paper, we consider a hybrid approach to the modeling of uncertainty in deductive databas es. Our model, called deductive IST (DIST) is based on an extension of the Information Source Tracking (IST) model, recently proposed for re lational databases. The DIST model permits uncertainty to be modeled a nd manipulated in essentially qualitative terms with an option to conv ert qualitative expressions of uncertainty into numeric form (e.g., pr obabilities). An uncertain deductive database is modeled as a Horn cla use program in the DIST framework, where each fact and rule is annotat ed with an expression indicating the ''sources'' contributing to this information and their nature of contribution. (1) We show that positiv e DIST programs enjoy the least model/least fixpoint semantics analogo us to classical logic programs. (2) We show that top-down (e.g., SLD-r esolution) and bottom-up (e.g., magic sets rewriting followed by semi- naive evaluation) query processing strategies developed for datalog ca n be easily extended to DIST programs. (3) Results and techniques for handling negation as failure in classical logic programming can be eas ily extended to DIST. As an illustration of this, we show how stratifi ed negation can be so extended. We next study the problem of query opt imization in such databases and establish the following results. (4) W e formulate query containment in qualitative as well as quantitative t erms. Intuitively, our qualitative sense of containment would say a qu ery Q(1) is contained in a query Q(2) provided for every input databas e D, for every tuple t, t is an element of Q(2)(D) holds in every ''si tuation'' in which t is an element of Q(1)(D) is true. The quantitativ e notion of containment would say Q(1) is contained in Q(2) provided o n every input, the certainty associated with any tuple computed by Q(1 ) is no more than the certainty associated with the same tuple by Q(2) on the given input. We also prove that qualitative and quantitative n otions of containment (both absolute and uniform versions) coincide. ( 5) We establish necessary and sufficient conditions for the qualitativ e containment of conjunctive queries. (6) We extend the well-known cha se technique to develop a test for uniform containment and equivalence of positive DIST programs. (7) Finally, we prove that the complexity of testing containment of conjunctive DIST queries remains the same as in the classical case when number of information sources is regarded as a constant (so, it's NP-complete in the size of the queries). We al so show that testing containment of conjunctive queries is co-NP-compl ete in the number of information sources. (C) 1997 Published by Elsevi er Science Ltd. All rights reserved.