Negation and minimality in non-horn databases

ABSTRACT

Two main approaches have been followed in the literature to give a semantics to non-Horn databases. The first one is based on considering the set of rules composing the programs as inference rules and interpreting the negation in the body as failure to prove. The other approach is based on the so-called closed-world assumption and its objective is to define a stronger notion of consequence from a theory than the classical one, where, very roughly, negative information can be inferred whenever its positive counterpart cannot be deduced from the theory. In this work we generalize the semantics for negation in logic programs, putting together the constructive nature of the rule-based deductive databases with the syntax-independence of the closed-world reasoning rules. These generalized semantics are shown to be a well-motivated and well-founded alternative to closed-world assumptions since they enjoy nice semantic and computational properties.

REFERENCES

• ABW88: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• BED92: R. Ben-Eliyahu and R. Dechter. Propositional semantics for disjunctive logic programs. In Proceedings of the International Joint Conference and Symposium on Logic Programming (IJCSLP-9P), pages 379-385, 1992.
• BH86: Nicole Bidoit , Richard Hull, Positivism vs minimalism in deductive databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.123-132, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15409]
• CL90: Marco Cadoli , Maurizio Lenzerini, The complexity of propositional closed world reasoning and circumscription, Journal of Computer and System Sciences, v.48 n.2, p.255-310, April 1994 [doi>10.1016/S0022-0000(05)80004-2]
• CS92: M. Cadoli and M. Schaerf. A survey on complexity results for non-monotonic logics. Submitted for publication, June 1992.
• EG91: T. Eiter and G. Gottlob. Propositional circumscription and extended closed world reasoning are II#-complete. Technical Report CD-TR 91/20, Technische Universit#it Wien, Vienna Austria, Christian Doppler Labor fiir Expertensysteme, May 1991. To appear in Theoretical Computer Science.
• EG92: T. Eiter and G. Gottlob. Complexity resuits for disjunctive logic programming and application to nonmonotoninc logics. Technical Report CD-TR 92/41, Technische Universit#it Wien, Vienna Austria, Christian Doppler Labor fiir Expertensysteme, 1992.
• EG93: Thomas Eiter , Georg Gottlob, Complexity aspects of various semantics for disjunctive databases, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.158-167, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153864]
• GL88: M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proceedings of #he Fifth Logic Programming Symposium, pages 1070-1080. MIT Press, 1988.
• GL91: M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. New Generation Computing, 9:365-385, 1991.
• GPP89: Michael Gelfond , H. Przymusinska , Teodor C. Przymusinski, On the relationship between circumscription and negation as failure, Artificial Intelligence, v.38 n.1, p.75-94, Feb. 1989 [doi>10.1016/0004-3702(89)90068-4 ]
• KN88: R. Krishnamurthy and S. A. Naqvi. Nondeterministic choice in datalog. In Proceedings of the Third International Conference on Data and Knowledge Bases, pages 416-424. Morgan Kaufmann, 1988.
• Min82: Jack Minker, On Indefinite Databases and the Closed World Assumption, Proceedings of the 6th Conference on Automated Deduction, p.292-308, June 07-09, 1982
• MT91a: Wiktor Marek , Mirosław Truszczyński, Autoepistemic logic, Journal of the ACM (JACM), v.38 n.3, p.587-618, July 1991 [doi>10.1145/116825.116836]
• MT91b: W. Marek and M. Truszczyfiski. Computing intersection of autoepistemic expansions. In Proceedings of the First International Workshop on Logic Programming and Non Monotonic Reasoning, pages 37-50. The MIT press, 1991.
• Prz88: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• Prz91a: T. Przymusinski. Semantics of disjunctive logic programs and deductive databases. In Proceedings of the Second International Conference on Deductive and Object-Oriented Databases (DOOD-91), pages 85-107, 1991.
• Prz91b: T. Przymusinski. Stable semantics for disjunctive programs. New Generation Computing, 9:401-424, 1991.
• PY92: Christos H. Papadimitriou , Mihalis Yannakakis, Tie-breaking semantics and structural totality, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.16-22, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137103]
• Rei78: R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 119-140. Plenum, 1978.
• RLM89: A. Rajasekar , J. Lobo , J. Minker, Weak generalized closed world assumption, Journal of Automated Reasoning, v.5 n.3, p.293-307, September 1989 [doi>10.1007/BF00248321]
• Sch92: M. Schaerf. Logic programming and autoepistemic logics" new relations and complexity results, submitted, 1992.
• Sto76: L.J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1-22, 1976.
• SZ90: Domenico Sacca , Carlo Zaniolo, Stable models and non-determinism in logic programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-217, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298572]
• vEK76: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• vGRS91: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• YH85: A. Yahya and L. J. Henschen. Deduction in non-horn databases, journal of Automated Reasoning, 1:141-160, 1985.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages, Theory