Bottom-Up Computation of Perfect Models for Disjunctive Theories

Jose Alberto Fernandez and Jack Minker

Computer Science Department,
University of Maryland
College Park

The complete paper is available in:

Abstract

We present a new fixpoint characterization of the minimal models of disjunctive logic programs. We prove that by applying the operator iteratively, it characterizes the perfect models semantics of stratified disjunctive logic programs. Given the equivalence between the perfect models semantics of stratified programs and prioritized circumscription our fixpoint characterization captures the meaning of the corresponding circumscribed theory. Based on these results we present a bottom-up evaluation algorithm for stratified disjunctive databases. This algorithm uses the model-tree data structure to represent the information contained in the database and to compute answers to queries.

Bibliography

[ABW88] K.R. Apt, H.A. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89-148. Morgan Kaufmann Pub., Washington, D.C., 1988.
[BLM92] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics for logic programs. Annals of Mathematics and Artificial Intelligence, 5:89-131, 1992.
[BPRM91] I. Balbin, G.S. Port, K. Ramamohanarao, and K. Meenakshi. Efficient bottom-up computation of queries on stratified databases. The Journal of Logic Programming, 11(3 & 4):295-344, October 1991.
[Bry90] F. Bry. Query evaluation in recursive databases: bottom-up and top-down reconciled. Data & Knowledge Engineering, pages 289-312, 1990.
[CS90] J. Chomicki and V.S. Subramanian. Generalized closed worl assumption is 02-complete. Information Processing Letters, 34:289-291, 1990.
[FM91] 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.
[GL88] 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.
[GPP89] M. Gelfond, H. Przymusinska, and T.C. Przymusinski. On the Relationship between Circumscription and Negation as Failure. Artificial Intelligence, 38:75-94, 1989.
[Lif85] V. Lifschitz. Computing circumscription. In IJCAI 85, pages 121-127, 1985.
[Llo87] J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, second edition, 1987.
[LMR92] J. Lobo, J. Minker, and A. Rajasekar. Fundations of Disjunctive Logic Programming. MIT Press, 1992.
[LS90] 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.
[McC80] J. McCarthy. Circumscription - a form of non-monotonic reasoning. Artificial Intelligence, 13(1 and 2):27-39, 1980.
[Min82] J. Minker. On indefinite databases and the closed world assumption. In Lecture Notes in Computer Science 138, pages 292-308. Springer-Verlag, 1982.
[MR90] J. Minker and A. Rajasekar. A fixpoint semantics for disjunctive logic programs. Journal of Logic Programming, 9(1):45-74, July 1990.
[Prz88] T. C. Przymusinski. On the declarative semantics of deductive databases and logic programming. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, chapter 5, pages 193-216. Morgan Kaufmann Pub., Washington, D.C., 1988.
[Rei80] R. Reiter. Equality and domain closure in first order data bases. Journal of the ACM, 27(2):235-249, 1980.
[RM90] A. Rajasekar and J. Minker. On stratified disjunctive programs. Annals of Mathematics and Artifitial Intelligence, 1:339-357, 1990.
[She88] J.C. Shepherdson. Negation in Logic Programming. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 19-88. Morgan Kaufman Pub., 1988.
[vG89] A. van Gelder. The alternating fixpoint of logic programs with negation. In Proceedings of the Symposium on Principles of Database Systems, 1989.
[YC89] 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.
[YH85] A. Yahya and L.J. Henschen. Deduction in Non-Horn Databases. J. Automated Reasoning, 1(2):141-160, 1985.