Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-18T15:50:46.829Z Has data issue: false hasContentIssue false
  • English
  • Français

Relational theories with null values and non-herbrand stable models

Published online by Cambridge University Press:  05 September 2012

VLADIMIR LIFSCHITZ ,
KARL PICHOTTA  and
FANGKAI YANG
VLADIMIR LIFSCHITZ
Affiliation:
Department of Computer Science, University of Texas at Austin (e-mail: [email protected], [email protected], [email protected])
KARL PICHOTTA
Affiliation:
Department of Computer Science, University of Texas at Austin (e-mail: [email protected], [email protected], [email protected])
FANGKAI YANG
Affiliation:
Department of Computer Science, University of Texas at Austin (e-mail: [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Generalized relational theories with null values in the sense of Reiter are first-order theories that provide a semantics for relational databases with incomplete information. In this paper we show that any such theory can be turned into an equivalent logic program, so that models of the theory can be generated using computational methods of answer set programming. As a step towards this goal, we develop a general method for calculating stable models under the domain closure assumption but without the unique name assumption.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 12 , Issue 4-5: 28th International Conference on Logic Programming , July 2012 , pp. 565 - 582
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Clark, K. 1978. Negation as failure. In Logic and Data Bases, Gallaire, H. and Minker, J., Eds. Plenum Press, New York, 293–322.CrossRefGoogle Scholar
Denecker, M. and Ternovska, E. 2008. A logic of nonmonotone inductive definitions. ACM Transactions on Computational Logic 9, 2.CrossRefGoogle Scholar
Ferraris, P., Lee, J. and Lifschitz, V. 2007. A new perspective on stable models. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 372–379.Google Scholar
Ferraris, P., Lee, J. and Lifschitz, V. 2011. Stable models and circumscription. Artificial Intelligence 175, 236–263.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.CrossRefGoogle Scholar
Gottlob, G., Cali, A., Lukasiewicz, T., Marnette, B. and Pieris, A. 2010. Datalog+/-: A family of knowledge representation and query languages for new applications. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science.Google Scholar
Lee, J. and Palla, R. 2009. System F2LP — computing answer sets of first-order formulas. In Proceedings of International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). 515–521.CrossRefGoogle Scholar
Lifschitz, V. 1994. Circumscription. In Handbook of Logic in AI and Logic Programming, Gabbay, D., Vol. 3, Hogger, C. and Robinson, J., Eds. Oxford University Press, 298–352.Google Scholar
Lifschitz, V. 2008. What is answer set programming? In Proceedings of the AAAI Conference on Artificial Intelligence. MIT Press, 1594–1597.Google Scholar
Lifschitz, V., Morgenstern, L. and Plaisted, D. 2008. Knowledge representation and classical logic. In Handbook of Knowledge Representation, van Harmelen, F., Lifschitz, V. and Porter, B., Eds. Elsevier, 3–88.CrossRefGoogle Scholar
Lifschitz, V., Pearce, D. and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic 2, 526–541.CrossRefGoogle Scholar
Lifschitz, V., Pearce, D. and Valverde, A. 2007. A characterization of strong equivalence for logic programs with variables. In Procedings of International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). 188–200.CrossRefGoogle Scholar
Marek, V. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective. Springer Verlag, 375–398.CrossRefGoogle Scholar
McCarthy, J. 1980. Circumscription—a form of non-monotonic reasoning. Artificial Intelligence 13, 27–39, 171–172.CrossRefGoogle Scholar
McCarthy, J. 1986. Applications of circumscription to formalizing common sense knowledge. Artificial Intelligence 26, 3, 89–116.CrossRefGoogle Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 241–273.CrossRefGoogle Scholar
Niemelä, I. and Simons, P. 1996. Efficient implementation of the well-founded and stable model semantics. In Proceedings Joint Int'l Conference and Symposium on Logic Programming. 289–303.Google Scholar
Reiter, R. 1984. Towards a logical reconstruction of relational database theory. In On Conceptual Modelling: Perspectives from Artificial Intelligence, Databases and Programming Languages, Brodie, M., Mylopoulos, J. and Schmidt, J., Eds. Springer, 191–233.CrossRefGoogle Scholar
Robinson, A. 1963. Introduction to Model Theory and to the Metamathematics of Algebra. North-Holland.Google Scholar
Sakama, C. and Inoue, K. 1994. An alternative approach to the semantics of disjunctive logic programs and deductive databases. Journal of Automated Reasoning 13, 145–172.CrossRefGoogle Scholar
Traylor, B. and Gelfond, M. 1994. Representing null values in logic programming. In Logical Foundations of Computer Science, Proceedings of 3rd International Symposium, LFCS'94, St. Petersburg, Russia, July 11-14, 1994, Nerode, A. and Matiyasevich, Y., Eds. Lecture Notes in Computer Science, vol. 813. 341–352.Google Scholar
Supplementary material: PDF

LIFSCHITZ et al. supplementary material

Appendix

Download LIFSCHITZ et al. supplementary material(PDF)
PDF 186.6 KB