Computing Protected Circumscription

Jack Minker and Donald Perlis

Computer Science Department
University of Maryland
College Park

The complete paper is available in:

• PostScript

Abstract

This paper deals with computing circumscription in the case of Horn data with additional protection (indefinite data), an intermediate investigation between Reiter's result on predicate completion and Lifschitz's efforts to make general (formula) circumscription more efficient as a computational tool. Reiter has shown a close tie between McCarthy's circumscription and Clark's predicate completion. Here we investigate a similar tie between an extended version of circumscription involving protected data, and an extended version of predicate completion. When we have a fully ground atomic protected theory, we show that an extension to the relational algebra can be used to obtain all (and only) correct answers. When general Horn axioms are added to the protected theory, we show that Horn axioms also can be used to compute sound answers; however, some correct answers will not be found.

Bibliography

• (1) Bossu, G. and Siegel, P. [1985] Saturation, nonmonotonic reasoning, and the closed-world assumption. Artificial Intelligence, 25 (1), pp. 13-63.
• (2) Clark, K. [1978] Negation as failure. In: Logic and Databases, Gallaire, H. and Minker, J. (eds.). Plenum Press, New York, pp. 293-322.
• (3) Etherington, D. [1984] Personal communication, Week on Logic and AI, U of Md.
• (4) Etherington, D., Mercer, R., and Reiter, R. [1984] On the adequacy of predicate circumscription for closed-world reasoning. University of British Columbia, Dept. of Computer Science, Tech. Report 84-5.
• (5) Grant, J. and Minker, J. [1984] Answering queries in indefinite databases and the null value problem. Tech. Report 1374, University of Maryland.
• (6) Henschen, L. and Yahya [1985] Deduction in Non-Horn Databases, to appear, J. of Automated Reasoning. 9 9
• (7) Lifschitz, V. [1984] Some results on circumscription. Workshop on Nonmonotonic Reasoning, Mohonk.
• (8) McCarthy, J. [1980] Circumscription--a form of nonmonotonic reasoning. Artificial Intelligence, 13
• (1,2), pp. 27-39.
• (9) McCarthy, J. [1984] Applications of circumscription to formalizing common sense knowledge. Workshop on Nonmonotonic Reasoning, Mohonk.
• (10) Minker, J. [1982] On indefinite databases and the closed-world assumption. Lecture Notes in Computer Science, v. 138, pp. 292-308, Springer. (6th Conference on Automated Deduction).
• (11) Minker, J. [1983] On theories of definite and indefinite databases. Tech. Report, University of Mary- land.
• (12) Minker, J. and Perlis, D. [1984a] Applications of protected circumscription. Lecture Notes in Computer Science, v. 170, pp. 414-425, Springer. (7th Conference on Automated Deduction). 9 9
• (13) Minker, J. and Perlis, D. [1984b] Protected circumscription. Workshop on Nonmonotonic Reasoning, Mohonk.
• (14) Perlis, D. and Minker, J. [1985] Completeness results for circumscription. Draft.
• (15) Reiter, R. [1978] On closed world databases. In: Logic and Databases, Gallaire, H. and Minker, J.
• (eds.), Plenum, pp. 55-76.
• (16) Reiter, R. [1980] Equality and domain closure in first-order databases. J. ACM, v. 27, pp. 235-249.
• (17) Reiter, R. [1982] Circumscription implies predicate completion (sometimes). Proc. AAAI82, pp. 418-420.
• (18) Zaniolo, C. [1984] Database relations with null values. J. Comp. and System Sci., v. 28, pp. 142-166. 9 9