Adding disjunction to datalog (extended abstract)

ABSTRACT

We study the expressive power and complexity of disjunctive datalog, i.e., datalog with disjunctive rule heads, under three different semantics: the minimal model semantics, the perfect models semantics, and the stable model semantics. We show that the brave variants of these semantics express the same set of queries. In fact, they precisely capture the complexity of class &Sgr;P/2. The combined complexity of disjunctive datalog is shown to be NEXPTIMENP-complete.

REFERENCES

• ASV90: Serge Abiteboul , Eric Simon , Victor Vianu, Non-deterministic languages to express deterministic transformations, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.218-229, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298575]
• AV91: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• BLT92: José L. Balcázar , Antoni Lozano , Jacobo Torán, The complexity of algorithmic problems on succinct instances, Computer science: research and applications, Plenum Press, New York, NY, 1992
• BF87: N. Bidoit and C. Froidewux. Minimalism Subsumes Default Logic and Circumscription in Stratified Lo$ic Prosrammin$. In Proceeding# LIUS-87, pp. 89-9T. IEEE Press, 1987.
• CEG94: M. Cadoli, T. Eiter, and G. Gottlob. Using Default Logic as a Query Language. In Proceedings KR.94, 1994. Forthcoming.
• CH85: A. Chandra and D. Harel. Horn Clause Queries and Generalizations. Journal of Logic Programming, 2:1-15, 1985.
• CK73: C.C. Chang and H. J. Keisler. Model Theory. North-Holland, 2nd edition, 1973.
• Dix92: Jitrgen Dix. Classifying Semantics of Disjunctive Logic Programs. In Proceedings JICSLP-92, pp. 798-812, Washington DC, November 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]
• Fag74: R. Fagin. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In R. M. Karp, editor, Complexity of Computation, pp. 43-74. AMS, 1974.
• GL88: M. Gelfond and V. Lifsckitz. The Stable Model Semantics for Logic Programming. In Proc. Fifth Logic Programming Symposium, pp. 1070-1080, Cambridge Mass., 1988. MIT Press.
• Gur88: Y. Gurevich. Logic and the Challenge of Computer Science. In E. BSrger, editor, Trends in Theoretical Computer Science, chapter 1. Computer Science Press, 1988.
• HS91: Richard Hull , Jianwen Su, On the expressive power of database queries with intermediate types, Journal of Computer and System Sciences, v.43 n.1, p.219-267, Aug. 1991 [doi>10.1016/0022-0000(91)90036-5]
• IFI94: IFIP-GI. Workshop: Disjunctive Logic Program. mint and Disjunctive Databases. To be held #t 13th IFIP World Computer Congress, Hamburg, August 1994.
• Joh90: David S. Johnson. A Catalog of Complexity Classes. In van Leeuwen {vang0}, chapter 2.
• Kan90: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• KP91: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Journal of Computer and System Sciences, v.43 n.1, p.125-144, Aug. 1991 [doi>10.1016/0022-0000(91)90033-2]
• KV90: Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of datalog: tools and a case study, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.61-71, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298542]
• KV92: Ph.G. Kolaitis and M. Vardi. Fixpoint Logic vs. Infiaita#y Logic ia Finite-Model Theory, In Proceedings LICS-92, pages 61-71. IEEE Computer Science Press, 1992.
• LMR92: Jorge Lobo , Jack Minker , Arcot Rajasekar, Foundations of disjunctive logic programming, MIT Press, Cambridge, MA, 1992
• Lyn82: J.F. Lynch. Complexity Classes and Theories of Finite Models. Mathematical Systems Theory, 15:127-144, 1982.
• McC80: J. McCarthy. Circumscription- A Form of Non- Monotonic Reasoning. Artificial intelligence, 13:27-39, 1980.
• 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
• MV93: David Maier , Bennet Vance, A call to order, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-16, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153851]
• 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
• Prz91: T. Przymusinski. Stable Semantics for Disjunctive Programs. New Generation Computing, 9:401-424, 1991.
• PY85: Christos H. Papadimitriou , Mihalis Yannakakis, A note on succinct representations of graphs, Information and Control, v.71 n.3, p.181-185, Dec. 1986 [doi>10.1016/S0019-9958(86)80009-2]
• Sch90: John S. Schlipf, The expressive powers of the logic programming semantics (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.196-204, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298564]
• Ste91: I. Stewart. Complete Problems involving Boolean Labelled Structures and Projection Transactions. Journal of Logic and Computation, 1(6):861-882, 1991.
• Sto77: L.J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science, 3:1-22, 1977.
• Van87: D. Van Gucht, On the expressive power of the extended relational algebra for the unnormalized relational model, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.302-312, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28692]
• van90: Jan van Leeuwen, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• Var82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• vRS91: 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]
• VVAG92: J. Van den Bussche, D. Van Gucht, M. Andries, and M. Gyssens. On the Completeness of Object Creating Query Languages. In Proceedings FOCS.92, pp. 372-379, 1992.
• YH85: A. Yahya and L. Henschen. Deduction in Non-Horn Databases. Journal of Automated Reasoning, 1(2):141-160, 1985.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages, Theory, Verification