Representations for Disjunctive Deductive Databases

Adnan Yahya and Jack Minker

• DVI
• Postscript

Abstract

The concepts of the dual and complementary databases as alternative representations for a given disjunctive deductive database, DB, are introduced. The dual database results from interchanging the occurrences of OR and AND operators in the positive clause representation of DB. The complementary database is defined to have as minimal models the complements of the minimal models of DB relative to the underlying Herbrand base, HBDB . The properties of these derivative databases are studied. In particular, we show that the minimal models of DB correspond to the minimally derivable clauses of the dual database and that the complementary database defines the Extended Generalized Closed World Assumption (EGCW A) completion, and consequently the Generalized Closed World Assumption (GCW A) completion, of DB. A tree structure for minimally derivable clauses is defined and algorithms for constructing and performing update and search operations on such trees are given.

Bibliography

• [1] C.-L. Chang and C.-T. Lee. Symbolic Logic and Mechanical Theorem Proving. Academic Press, 1973.
• [2] R. Fagin, J. Ullman, and M. Vardi. Contributions to the view update problem. In Proc. of the Sixth Intl. Conf. on Logic Programming, pages 398-415, 1989.
• [3] J.A. Fernandez, Z.A. Khandakar, and J. Minker. A tractable class of disjunctive deductive databases. In Proc. Workshop on Deductive Databases, Joint International Conference and Symposium on Logic Programming (JICSLP'92), Washington, D.C., Nov. 1992.
• [4] J.A. Fernandez and J. Minker. Disjunctive deductive database. In 3rd International Conference on Logic Programming and Automated Reasoning, pages 332-356, July 1992. Invited Paper.
• [5] J.A. Fernandez and J. Minker. Semantics of disjunctive deductive databases. In Proceedings of the International Conference on Database Theory, pages 332-356, 1992. (Invited Paper).
• [6] J.A. Fernandez and J. Minker. Theory and algorithms for disjunctive deductive databases. Pro- grammirovanie, N 3:5-39, 1993. (also appears as University of Maryland Technical Report, CSTR -3223, UMIACS-TR-94-17,1994. Invited Paper in Russian).
• [7] Jose Alberto Fernandez and Jack Minker. Bottom-up evaluation of Hierarchical Disjunctive Deductive Databases. In Koichi Furukawa, editor, Logic Programming Proceedings of the Eighth International Conference, pages 660-675. MIT Press, 1991.
• [8] J. Grant, J. Horty, J. Lobo, and J. Minker. View updates in stratified disjunctive databases. Journal Automated Reasoning, 11:249-267, March 1993.
• [9] J. Grant and J. Minker. Answering queries in indefinite databases and the null value problem. In P. Kanellakis, editor, Advances in Computing Research: The Theory of Databases, pages 247-267. 1986.
• [10] K.C. Liu and R. Sunderraman. Indefinite and maybe information in relational databases. ACM Transactions on Database Systems, 15(1):1-39, 1990.
• [11] K.C. Liu and R. Sunderraman. On representing indefinite and maybe information in relational databases. In Proceedings of IEEE Data Engineering, pages 495-502, Los Angeles, 1990.
• [12] J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, 1992.
• [13] J. Minker. On indefinite databases and the closed world assumption. In Proceedings of 6th Conference on Automated Deduction, pages 292-308, New York, 1982.
• [14] J. Minker. Toward a foundation of disjunctive logic programming. In Proc. North American Conference on Logic Programming, pages 1215-1235, 1989. (Invited Paper).
• [15] J. Minker. An overview of nonmonotonic reasoning and logic programming. Journal of Logic Programming, 17(2, 3, and 4):95-126, November 1993.
• [16] A. Rajasekar, J. Lobo, and J. Minker. Skeptical reasoning and disjunctive programs. In Proceedings of First International Conference on Knowledge Representation and Reasoning, pages 349-357. Morgan-Kaufmann, 1989.
• [17] R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55-76. Plenum, New York, 1978.
• [18] F. Rossi and S. Naqvi. Contributions to the view update problem. In International Conference on Logic Programming, pages 398-415, Lisbon, 1989.
• [19] M. Suchenek. First-order syntactic characterizations of minimal entailment, and Herbrand entailment. Journal of Automated Reasoning, 10:237-263, 1993.
• [20] A. Yahya, J. A. Fernandez, and J. Minker. Ordered model trees: a normal form for disjunctive deductive databases. Technical Report UMIACS-TR-93-14 and CS-TR-3034, University of Maryland Institute for Advance Computer Studies, College Park, MD 20742, 1993.
• [21] A. Yahya and L.J. Henschen. Deduction in Non-Horn Databases. J. Automated Reasoning, 1(2):141-160, 1985.
• [22] A. Yahya and J. Minker. Query answering in partitioned disjunctive deductive databases. Technical Report UMIACS-TR-93-14 and CS-TR-3034, University of Maryland Institute for Advance Computer Studies, College Park, MD 20742, 1993