Complexity aspects of various semantics for disjunctive databases

ABSTRACT

This paper addresses complexity issues for important problems arising with disjunctive databases. In particular, the complexity of inference of a literal and a formula from a propositional disjunctive database under a variety of well-known disjunctive database semantics is investigated, as well deciding whether a disjunctive database has a model under a particular semantics. The problems are located in appropriate slots of the polynomial hierarchy.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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
	2	Nicole Bidoit , Christine Froidevaux, Negation by default and unstratifiable logic programs, Theoretical Computer Science, v.78 n.1, p.85-112, Jan. 21, 1991
	3	M. Cadoli and M. Lenzerini. The Complexity of Closed World Reasoning and Circumscription. In Proceedings AAAI-90, pages 550-555, 1990.
	4	M. Cadoli and M. Schaerf. A Survey on Complexity Results for Non-monotonic Logics. Technical report, Dipartimento di Informatica e Sistemistica, Universit#t di Roma "La Sapienza", 1992. Journal of Logic Programming, to appear.
	5	E. Chart. A Possible Worlds Semantics for Disjunctive Databases. IEEE Transactions on Data and Knowledge Engineering, 1991. To appear.
	6	A. Chandra and D. Harel. Horn Clause Queries and Generalizations. Journal of Logic Programming, 2:1- 15, 1985.
	7	T. Eiter and G. Gottlob. Propositional Circumscription and Extended Closed World Reasoning are IIP- complete. Technical Report CD-TR 91/20, Christian Doppler Laboratory for Expert Systems, Vienna University of Technology, Austria, May 1991. To appear in Theoretical Computer Science.
	8	T. Eiter and G. Gottlob. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Manuscript, March 1993.
	9	José Alberto Fernández , Jack Minker, Semantics of Disjunctive Deductive Databases, Proceedings of the 4th International Conference on Database Theory, p.21-50, October 14-16, 1992
	10	M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Proceedings Fifth Logic Programming Symposium, pages 1070-1080, C#tmbridge Mass., 1988. MIT Press.
	11	M Gelfond , H Przymusinska, Negation as failure: Careful closure procedure, Artificial Intelligence, v.30 n.3, p.273-288, Dec. 1986 [doi>10.1016/0004-3702(86)90001-9]
	12	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]
	13	David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	14	V. Lifschitz. Computing Circumscription. In Proceedings IJCAI-85, pages 121-127, 1985.
	15	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]
	16	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
	17	J. Minker, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	18	C. H. Papadimitriou and M. Yannakakis. The Complexity of Facets (And Some Facets of Complexity). Journal of Computer and System Sciences, 28:244-259, 1984.
	19	T. Przymusinski. On the Declarative and Procedural Semantics of Stratified Deductive Databases. In Minker {17}, pages 193-216.
	20	T. Przymusinski. Stable Semantics for Disjunctive Programs. New Generation Computing, 9:401-424, 1991.
	21	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]
	22	R. Reiter. On Closed-World Databases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55-76. Plenum Press, New York, 1978.
	23	Kenneth A. Ross , Rodney W. Topor, Inferring negative information from disjunctive databases, Journal of Automated Reasoning, v.4 n.4, p.397-424, Dec. 1988 [doi>10.1007/BF00297247]
	24	C. Sakama. Possible Model Semantics for Disjunctive Databases. In Proceedings 1st lntl. Conf. DOOD-89, pages 337-351, Kyoto Japan, 1989.
	25	M. Schaerf. Logic Programming and Autoepistemic Logics: New Relations and Complexity Results. Submitted, December 1992.
	26	Marco Schaerf, Negation and minimality in non-horn databases, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.147-157, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153863]
	27	J. Schlipf. A Survey of Complexity and Undecidability Results in Logic Programming. In H. Blair, W. Marek, A. Nerode, and J. Remmel, editors, lnfor. real Proceedings of the Workshop on Structural Gomplezity and Recursion-Theoretic Methods in Logic Pro- 9ramming, pages 93-102, Washington DC, November 13 1992. Cornell University, Mathematical Sciences institute.
	28	A. V. Gelder, Negation as failure using tight derivations for general logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	29	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]
	30	A. Yahya and L. Henschen. Deduction in Non-Horn Databases. Journal o/ A utomated Reasoning, 1(2):141- 160, 1985.