Query processing in deductive databases with incomplete information

ABSTRACT

We study here automated deduction in databases in the presence of various types of inference rules of the form of Horn Clauses with Skolem functions. These inference rules are typical for databases with incomplete information. We demonstrate a number of results related to processing of conjunctive queries for different types of database intensions. In particular, we show that when a database intension is built from possibly cyclic inclusion dependencies and view definitions any conjunctive query can be translated to the an equivalent form which can be evaluated directly over the database extension (disregarding inference rules). We also demonstrate that the complexity of query processing significantly grows when we mix incomplete information with recursive rules. In particular, we demonstrate here that even the power of least fixpoint extension of first order logic may be not sufficient to process queries in the presence of incomplete data and recursive rules. The same is demonstrated in case disjunctive information is allowed in the database.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 2: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• 3: Ashok K. Chandra , David Harel, Horn clauses and the fixpoint query hierarchy, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588137]
• 4: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• 5: Richard Hull, Finitely Specifiable Implicational Dependency Families, Journal of the ACM (JACM), v.31 n.2, p.210-226, April 1984 [doi>10.1145/62.2162]
• 6: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 7: Immhnskl,T Abstraction m Query Processing 1985
• 8: Johnson,D and Klug,A Testing Containment of ConjuncUve Querms under Functional and Inclusion Dependencies Journal of Computer System Sczences , 1984
• 9: Loveland,D Automated Theorem Prowng Springer Verlag, 1979
• 10: Mamr,D and Vardl,M and Ullman,J D On the Foundations of Umversal Relation Model A CM TODS, 1984
• 11: Relter, R On closed world databases Logzc and databases Plenum Press, 1978
• 12: Relter,R Deductive Query Answering on Relational Databases Logzc and Databases Plenum Press, 1978
• 13: Ullman,J Pmnc#ples of Database Systems Computer Scmnce Press, 1982
• 14: \ ardt \1 The Cornptexlt# of Relatmnal Quer) Language In ACM FOCS, 1982

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Verification