Disjunctive datalog

ABSTRACT

We consider disjunctive Datalog, a powerful database query language based on disjunctive logic programming. Briefly, disjunctive Datalog is a variant of Datalog where disjunctions may appear in the rule heads; advanced versions also allow for negation in the bodies which can be handled according to a semantics for negation in disjunctive logic programming. In particular, we investigate three different semantics for disjunctive Datalog: the minimal model semantics the perfect model semantics, and the stable model semantics. For each of these semantics, the expressive power and complexity are studied. We show that the possibility variants of these semantics express the same set of queries. In fact, they precisely capture the complexity class P2 . Thus, unless the Polynomial Hierarchy collapses, disjunctive Datalog is more expressive that normal logic programming with negation. These results are not only of theoretical interest; we demonstrate that problems relevant in practice such as computing the optimal tour value in the Traveling Salesman Problem and eigenvector computations can be handled in disjunctive Datalog, but not Datalog with negation (unless the Polynomial Hierarchy collapses). In addition, we study modularity properties of disjunctive Datalog and investigate syntactic restrictions of the formalisms.

REFERENCES

• 1: 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]
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: 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
• 4: BARAL, C. AND GELFOND, M. 1994. Logic programming and knowledge representation. J. Logic Program. 19/20, 73-148.
• 5: Chitta R. Baral , V. S. Subrahmanian, Stable and extension class theory for logic programs and default logics, Journal of Automated Reasoning, v.8 n.3, p.345-366, June 1992 [doi>10.1007/BF02341854]
• 6: Colin Bell , Anil Nerode , Raymond T. Ng , V. S. Subrahmanian, Mixed integer programming methods for computing nonmonotonic deductive databases, Journal of the ACM (JACM), v.41 n.6, p.1178-1215, Nov. 1994 [doi>10.1145/195613.195637]
• 7: Colin Bell , Anil Nerode , Raymond T. Ng , V. S. Subrahmanian, Implementing deductive databases by mixed integer programming, ACM Transactions on Database Systems (TODS), v.21 n.2, p.238-269, June 1996 [doi>10.1145/232616.232691]
• 8: BEN-ELIYAHU, R. AND DECHTER, R. 1994. Propositional semantics for disjunctive logic programs. Ann. Math. Artif. Intell. 12, 53-87.
• 9: BEN-ELIYAHU, R. AND PALOPOLI, L. 1994. Reasoning with minimal models: Efficient algorithms and applications. In Proceedings Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR-94) (Bonn, Germany, May 24-27), 39-50.
• 10: BIDOIT, N. AND FROIDEVAUX, C. 1987. Minimalism subsumes default logic and circumscription in stratified logic programming. In Proceedings of LICS-87 (Ithaca, NY, June 22-25), IEEE CS Press, 89-97.
• 11: Nicole Bidoit , Christine Froidevaux, General logical databases and programs: default logic semantics and stratification, Information and Computation, v.91 n.1, p.15-54, March 1991 [doi>10.1016/0890-5401(91)90073-B]
• 12: Piero A. Bonatti , Thomas Eiter, Querying disjunctive databases through nonmonotonic logics, Theoretical Computer Science, v.160 n.1-2, p.321-363, June 10, 1996 [doi>10.1016/0304-3975(95)00192-1]
• 13: Alexander Borgida, Description Logics in Data Management, IEEE Transactions on Knowledge and Data Engineering, v.7 n.5, p.671-682, October 1995 [doi>10.1109/69.469829]
• 14: BRASS, S. AND DIX, J. 1995. Disjunctive semantics based upon partial and bottom-up evaluation. In Proceedings 12th International Conference on Logic Programming, Leon Sterling, Ed., (Tokyo, June 13-16), 199-213.
• 15: BRASS, S. AND DIX, J. 1997. A general framework for semantics of disjunctive logic programs based on partial evaluation. J. Logic Program. (to appear).
• 16: BRASS, S., DIX, J., NIEMELA, I., AND PRZYMUSINSKI, T. 1996b. A comparison of the static and disjunctive well-founded semantics. University of California at Riverside, (in preparation).
• 17: BRASS, S., DIX, J., AND PRZYMUSINSKI, T. 1996a. Super logic programs. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR-96) (Vancouver, Canada), Morgan-Kaufmann, San Mateo, CA, 529-540.
• 18: Marco Cadoli , Thomas Eiter , Georg Gottlob, Default Logic as a Query Language, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.448-463, May 1997 [doi>10.1109/69.599933]
• 19: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 20: CHANDRA, A. AND HAREL, D. 1982. Structure and complexity of relational queries. J. Comput. Syst. Sci. 25, 99-128.
• 21: CHANDRA, A. AND HAREL, D. 1985. Horn clause queries and generalizations. J. Logic Program. 2, 1-15.
• 22: Jianhua Chen, Minimal knowledge + negation as failure = only knowing (sometimes), Proceedings of the second international workshop on Logic programming and non-monotonic reasoning, p.132-150, June 1993, Lisbon
• 23: Pawel Cholewinski, Reasoning with Stratified Default Theories, Proceedings of the Third International Conference on Logic Programming and Nonmonotonic Reasoning, p.273-286, June 26-28, 1995
• 24: J. Chomicki , V. S. Subrahmanian, Generalized closed world assumption is II-complete, Information Processing Letters, v.34 n.6, p.289-291, May 1990 [doi>10.1016/0020-0190(90)90012-M]
• 25: Jane K. Cullum , Ralph A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Vol. 1, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 26: Anuj Dawar, A Restricted Second Order Logic for Finite Structures, Selected Papers from the International Workshop on Logical and Computational Complexity, p.393-413, October 13-16, 1994
• 27: DIx, J. 1992. Classifying semantics of disjunctive logic programs. In Proceedings JIC- SLP-92 (Washington DC, Nov.), 798-812.
• 28: Martin Müller , Jürgen Dix, Implementing semantics of disjunctive logic programs using fringes and abstract properties, Proceedings of the second international workshop on Logic programming and non-monotonic reasoning, p.43-59, June 1993, Lisbon
• 29: DIx, J., LOVELAND, D., MINKER, J., AND WARREN, D., EDS. 1996. Disjunctive Logic Programruing and Databases: Nonmonotonic Aspects, Seminar Report 150, Schlog Dagstuhl, Germany.
• 30: Jon Doyle , Ramesh S. Patil, Two theses of knowledge representation: language restrictions, taxonomic classification, and the utility of representation services, Artificial Intelligence, v.48 n.3, p.261-297, April 1991 [doi>10.1016/0004-3702(91)90029-J]
• 31: LITER, T. AND GOTTLOB, a. 1995a. Note on the complexity of some eigenvector problems. Tech. Rep. CD-TR 95/89, Christian Doppler Laboratory for Expert Systems, TU Vienna, Dec.
• 32: LITER, T. AND GOTTLOB, G. 1995b. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell. 15, 3/4, 289-323.
• 33: LITER, T., GOTTLOB, G., AND GUREVICH, Y. 1996. Normal forms for second-order logic over finite structures, and classification of NP optimization problems. Ann. Pure App. Logic 78, 111-125.
• 34: Thomas Eiter , Georg Gottlob , Heikki Mannila, Adding disjunction to datalog (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.267-278, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182639]
• 35: Thomas Eiter , Nicola Leone , Domenico Saccà, The Expressive Power of Partial Models in Disjunctive Deductive Databases, Proceedings of the International Workshop on Logic in Databases, p.245-264, July 01-02, 1996
• 36: FAGIN, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, R. M. Karp, Ed., AMS, Providence, RI, 43-74.
• 37: GELFOND, M. AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In Proceedings of the Fifth Logic Programming Symposium, MIT Press. Cambridge, MA, 1070-1080.
• 38: GELFOND, M. AND LIFSCHITZ, V. 1991. Classical negation in logic programs and disjunctive databases. New Gen. Comput. 9, 365-385.
• 39: Georg Gottlob, Translating default logic into standard autoepistemic logic, Journal of the ACM (JACM), v.42 n.4, p.711-740, July 1995 [doi>10.1145/210332.210334]
• 40: Georg Gottlob , Nicola Leone , Helmut Veith, Second Order Logic and the Weak Exponential Hierarchies, Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, p.66-81, August 28-September 01, 1995
• 41: GUREVICH, Y. 1988. Logic and the Challenge of Computer Science. In Trends in Theoretical Computer Science, Chapter 1, E. B~rger, Ed., Computer Science Press, New York.
• 42: IMIELINSKI, T. AND LIPSKI, W. 1984. The relational model of data and cylindric algebras. J. Comput. Syst. Sci. 28, 80-102.
• 43: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• 44: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 45: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• 46: Phokion G. Kolaitis, The expressive power of stratified logic programs, Information and Computation, v.90 n.1, p.50-66, Jan. 1991 [doi>10.1016/0890-5401(91)90059-B]
• 47: 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]
• 48: KOLAITIS, P. AND VARDI, M. 1992. Fixpoint logic vs. infinitary logic in finite-model theory. In Proceedings LICS-92 (Santa Cruz, CA, June 22-25), IEEE Computer Science Press, Los Alamitos, CA, 61-71.
• 49: Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of Datalog: tools and a case study, Journal of Computer and System Sciences, v.51 n.1, p.110-134, Aug. 1995
• 50: Mark W. Krentel, The complexity of optimization problems, Journal of Computer and System Sciences, v.36 n.3, p.490-509, June 1988 [doi>10.1016/0022-0000(88)90039-6]
• 51: LEONE, N., RULLO, P., AND SCARCELLO, F. 1995. Disjunctive stable models: Unfounded sets, fixpoint semantics and computation. Abstract in Proceedings of International Logic Programming Symposium (ILPS-95) (Portland, OR), MIT Press, New York, 399-413.
• 52: Vladimir Lifschitz , Grigori Schwarz, Extended logic programs as autoepistemic theories, Proceedings of the second international workshop on Logic programming and non-monotonic reasoning, p.101-114, June 1993, Lisbon
• 53: Vladimir Lifschitz , Hudson Turner, Splitting a logic program, Proceedings of the eleventh international conference on Logic programming, p.23-37, August 1994
• 54: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 55: Jorge Lobo , Jack Minker , Arcot Rajasekar, Foundations of disjunctive logic programming, MIT Press, Cambridge, MA, 1992
• 56: 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]
• 57: John McCarthy, Applications of circumscription to formalizing common-sense knowledge, Artificial Intelligence, v.28 n.1, p.89-116, Feb. 1986 [doi>10.1016/0004-3702(86)90032-9]
• 58: 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
• 59: MINKER, J. 1994. Overview of disjunctive logic programming. Ann. Math. Artif. Intell. 12, 1-24.
• 60: Robert C. Moore, Semantical considerations on nonmonotonic logic, Artificial Intelligence, v.25 n.1, p.75-94, Jan. 1985 [doi>10.1016/0004-3702(85)90042-6]
• 61: Anil Nerode , Raymond T. Ng , V. S. Subrahmanian, Computing circumscriptive databases, I: theory and algorithms, Information and Computation, v.116 n.1, p.58-80, Jan. 1995 [doi>10.1006/inco.1995.1005]
• 62: Christos H. Papadimitriou, On the complexity of unique solutions, Journal of the ACM (JACM), v.31 n.2, p.392-400, April 1984 [doi>10.1145/62.322435]
• 63: PAPADIMITRIOU, C.H. 1994. Computational Complexity. Addison-Wesley, Reading, MA.
• 64: 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]
• 65: 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
• 66: PRZYMUSINSKI, T. 1991. Stable semantics for disjunctive programs. New Gen. Comput. 9, 401-424.
• 67: Teodor C. Przymusinski, A knowledge representation framework based on autoepistemic logic of minimal beliefs, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.952-958, October 1994, Seattle, Washington, United States
• 68: PRZYMUSINSKI, T.C. 1995. Static semantics for normal and disjunctive logic programs. Ann. Math. Artif. Intell. 14, 323-357.
• 69: REITER, R. 1980. A logic for default reasoning. Artif. Intell. 13, 81-132.
• 70: Kenneth A. Ross, Modular stratification and magic sets for Datalog programs with negation, Journal of the ACM (JACM), v.41 n.6, p.1216-1266, Nov. 1994 [doi>10.1145/195613.195646]
• 71: Domenico Saccà, The expressive powers of stable models for bound and unbound DATALOG queries, Journal of Computer and System Sciences, v.54 n.3, p.441-464, June 1997 [doi>10.1006/jcss.1997.1446]
• 72: Domenico Sacca , Carlo Zaniolo, Stable models and non-determinism in logic programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-217, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298572]
• 73: Chiaki Sakama , Katsumi Inoue, Relating disjunctive logic programs to default theories, Proceedings of the second international workshop on Logic programming and non-monotonic reasoning, p.266-282, June 1993, Lisbon
• 74: SAKAMA, C. AND INOUE, K. 1994. An alternative approach to the semantics of disjunctive logic programs and deductive databases. J. Autom. Reason. 13, 145-172.
• 75: SAKAMA, C. AND INOUE, K. 1995. Paraconsistent stable semantics for extended disjunctive programs. J. Logic Comput. 5, 3, 265-285.
• 76: SCHLIPF, J. 1987. Decidability and definability with circumscription. Ann. Pure App. Logic 35, 173-191.
• 77: SCHLIPF, J. 1995a. A survey of complexity and undecidability results in logic programming. Ann. Math. Artif. Intell. 15, 3/4, 257-288.
• 78: John S. Schlipf, The expressive powers of the logic programming semantics, Journal of Computer and System Sciences, v.51 n.1, p.64-86, Aug. 1995
• 79: SEIPEL, D. 1994. Non-monotonic reasoning based on minimal models and its efficient implementation. In Proceedings of the Thirteenth IFIP World Computer Congress, Workshop F62: Disjunctive Logic Programming and Disjunctive Databases (Hamburg, Aug.), 53-60.
• 80: STEWART, I. 1991. Complete problems involving Boolean labelled structures and projection transactions. J. Logic Comput. 1, 6, 861-882.
• 81: STOCKMEYER, L.J. 1977. The polynomial-time hierarchy. Theor. Comput. Sci. 3, 1-22.
• 82: TURNER, H. 1996. Representing actions in default logic: A situation calculus approach. In Proceedings of Common Sense '96.
• 83: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 84: 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]
• 85: 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]
• 86: VEITH, H. 1994. Logical reducibilities in finite model theory. Master's Thesis, Information Systems Department, TU Vienna, Austria, Sept.
• 87: Helmut Veith, Succinct Representation, Leaf Languages, and Projection Reductions, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.118, May 24-27, 1996
• 88: WOLFINGER, B. ED. 1994. 13th IFIP World Computer Congress, Proceedings Workshop FG2: Disjunctive Logic Programming and Disjunctive Databases (Hamburg, Aug.), Springer, Berlin.
• 89: YAHYA, A. AND HENSCHEN, L. 1985. Deduction in non-Horn databases. J. Autom. Reason. 1, 2, 141-160.
• 90: You, J.-H. AND YUAN, L.-Y. 1993. Autoepistemic circumscription and logic programming. J. Autom. Reason. 10, 143-160.
• 91: Li-Yan Yuan , Jia-Huai You, On the Extension of Logic Programming with Negation through Uniform Proofs, Proceedings of the Third International Conference on Logic Programming and Nonmonotonic Reasoning, p.231-244, June 26-28, 1995

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
  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.3 Languages
          Subjects: Query languages

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Languages, Theory