A Tractable Class of Disjunctive Deductive Databases

Z. Khandaker, J.A. Fernandez, and J. Minker

• DVI
• PostScript

Abstract

In general, computing answers to queries in disjunctive deductive databases is CoNP-complete and therefore computationally infeasible. However, there are some tractable classes of disjunctive databases. In this paper, we present polynomial time algorithms to compute answers to queries in one such tractable class of disjunctive databases where at most two atoms are allowed in any disjunction.

Bibliography

• [CL90] M. Cadoli and M. Lenzerini. The complexity of closed world reasoning and circumscription. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI-90), pages 550-555. MIT Press, July 1990.
• [Dal92] M. Dalal. Some tractable classes of disjunctive logic programs. Technical report, Rutgers University , Department of Computer Science, 1992.
• [Dem89] R. Demolombe. An efficient evaluation strategy for non-horn deductive databese. In Proceedings of IFIP, 1989.
• [FM91] J. A. Fernandez and J. Minker. Bottom-up evaluation of hierarchical disjunctive deductive databases. In K. Furukawa, editor, Logic Programming proceedings of the 8th International Conference , pages 660-675. MIT Press, 1991.
• [GM86] J. Grant and J. Minker. Answering queries in indefinite databases and the null value problem. In P. Kanellakis, editor, Advances in Computing Research, pages 247-267. 1986.
• [GM92] J. Grant and J. Minker. The impact of logic programming on databases. Communications of the ACM, 35(3):66-81, March 1992.
• [HP88] L. J. Henschen and H. Park. Compiling the gcwa in indefinite database. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 395-438. Morgan Kaufmann Pub., Washington, D.C., 1988.
• [Imi91] T. Imielinsky. Incomplete deductive databases. Annals of Mathematics and Artificial Intelligence, 3:259-294, 1991.
• [IV89] T. Imielinsky and K. Vadaparty. Complexity of query processing in databases with or-objects. In Proceedings of the 7th ACM SIGACT/SIGMOD Symposium on Principles of Database Systems, pages 51-65, Philadelphia, Pennsylvania, March 1989.
• [LMR92] J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, 1992.
• [LS91] K.C. Liu and R. Sunderraman. A generalized relational model for indefinite and maybe information . IEEE Transactions on Knowledge and Data Engineering, 3(1):65-77, 1991.
• [LYW92] J. Lobo, C. Yu, and G. Wang. Computing the transitive closure in disjunctive databases. Technical report, University of Illinois at Chicago, Department of Electrical Engineering and Computer Science, 1992.
• [Var86] M. Vardi. Querying logical databases. Journal of Computing and Systems Sciences, (33):142-160, 1986.
• [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 8th Symposium on Principles of Database Systems, pages 66-74, March 1989.
• [YH85] A. Yahya and L. J. Henschen. Deduction in non-horn databases. Journal of Automated Reasoning, 1(2):141-160, 1985.

  Web Accessibility