Ordered Model Trees: A normal Form for Disjunctive Deductive Databases

Adnan Yahya, Jose Alberto Fernandez and Jack Minker

Computer Science Department,
University of Maryland
College Park

The complete paper is available in:

Abstract

Model trees were conceived as a structure sharing approach to represent information in disjunctive deductive databases. In this paper we introduce the concept of ordered minimal model trees as a normal form for disjunctive deductive databases. These are model trees in which an order is imposed on the elements of the Herbrand base. The properties of ordered minimal model trees are investigated as well as their possible utilization for efficient manipulation of disjunctive deductive databases. Algorithms are presented for the construction of and performing operations on ordered model trees. The complexity of ordered model tree processing is addressed. Model forests are presented as an approach to reduce the complexity of ordered model tree construction and processing.

Bibliography

[1] C. L. Chang and R. C. T. Lee. Symbolic Logic and Mechanical Theorem Proving. Academic Press, New York, 1973.
[2] M. Davis and H. Putnam. A computing procedure for quantification theory. J. ACM, 7:201-215, April 1960.
[3] Jose Alberto Fernandez, Jorge Lobo, Jack Minker, and V.S. Subrahmanian. Disjunctive LP + integrity constraints = stable model semantics. Annals of Mathematics and Artificial Intelligence, 8(3-4):449-474, 1993.
[4] 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.
[5] Jose Alberto Fernandez and Jack Minker. Bottom-up computation of perfect models for disjunctive theories. The Journal of Logic Programming, 1993. Submitted. Preliminary version presented at the ILPS'91 Workshop on Disjunctive Logic Programs, San Diego, California.
[6] M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In R.A. Kowalski and K.A. Bowen, editors, Proc. 5th International Conference and Symposium on Logic Programming, pages 1070-1080, Seattle, Washington, August 15-19 1988.
[7] K.-C. Liu and R. Sunderraman. Indefinite and maybe information in relational databases. ACM Transactions on Database Systems, 15(1):1-39, 1990.
[8] K.-C. Liu and R. Sunderraman. On representing indefinite and maybe information in relational databases: A generalization. In Proceedings of IEEE Data Engineering, pages 495-502, Los Angeles, February 1990.
[9] J. Minker. On indefinite databases and the closed world assumption. In Lecture Notes in Computer Science 138, pages 292-308. Springer-Verlag, 1982.
[10] T.C. Przymusinski. Perfect Model Semantics. In R.A. Kowalski and K.A. Bowen, editors, Proc. 5th International Conference and Symposium on Logic Programming, pages 1081-1096, Seattle, Washington, August 15-19 1988.
[11] M. A. Suchenek. Minimal models for closed world databases. In Z.W. Ras, editor, Proc. of ISMIS 4, pages 515-522. Elsvier Sience Publishing Co. Inc., 1989.
[12] M. A. Suchenek and R. Sunderraman. Minimal models for closed world databases with views. In Z.W. Ras and M. Zemankova, editors, Proc. of ISMIS 5, pages 182-193. Elsvier Sience Publishing Co. Inc., 1990.
[13] A. Yahya and L.J. Henschen. Deduction in Non-Horn Databases. J. Automated Reasoning, 1(2):141-160, 1985.
[14] L. Y. Yuan and D.-A. Chiang. A sound and complete query evaluation algorithm for relational databases with disjunctive information. In Proceedings of the Eighth Symposium on Principles of Database Systems, pages 66-74. ACM Press, March 1989.