On the equivalence of recursive and nonrecursive datalog programs

ABSTRACT

We study the problem of determining whether a given recursive Datalog program is equivalent to a given nonrecursive Datalog program. We prove triply exponential upper and lower time bounds.

REFERENCES

• AU79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• AV89: S. Abiteboul , V. Vianu, Fixpoint extensions of first-order logic and datalog-like languages, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.71-79, June 1989, Pacific Grove, California, United States
• BR86: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• Ch81: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• CH80: Chandra, A.K., Harel, D.: Computable queries for relational databases. J. Computer and Systems Sciences 21(1980), pp. 156- 178.
• CH82: Chandra, A.K., Harel, D.: Structure and Complexity of Relational Queries. J. Computer and Systems Sciences 25(1982), pp. 99-128.
• CH85: Chandra, A.K., Hare1, D.: Horn Clause Queries and Generalizations. j. Logic Programming, 2 (1985), 1- 15.
• CKS81: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• CLM81: Ashok K. Chandra , Harry R. Lewis , Johann A. Makowsky, Embedded implicational dependencies and their inference problem, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.342-354, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802488]
• CGKV88: Stavros Cosmadakis , Haim Gaifman , Paris Kanellakis , Moshe Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.477-490, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62259]
• CK86: S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
• Cou90: Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
• Cou91: Bruno Courcelle, Recursive queries and context-free graph grammars, Theoretical Computer Science, v.78 n.1, p.217-244, Jan. 21, 1991
• EJ88: Emerson, E.A., Jutla, C.S.: Complexity of tree automata and modal logics of programs. Proc. 29th IEEE Syrup. on Foundations of Computer Science, 1988, pp. 328-337.
• GM78: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• GMSV87: Gaifman, H., Mairson, H., Sagiv, Y., Vardi M.Y.: Undecidable optimization problems for database logic programs. Proc. Pnd IEEE Syrup. on Logic in Computer Science, Ithaca, 1987, pp. 106-115. To appear in J. A CM.
• HKMV91: Gerd G. Hillebrand , Paris C. Kanellakis , Harry G. Mairson , Moshe Y. Vardi, Tools for Datalog boundedness, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-12, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113414]
• HKMV92: Hillebrand, G.G., Kanellakis, P.C., Mairson, H.G., Vardi, M.Y.: Uudecidable boundedness problems for Datalog programs. To appear.
• Im86: 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]
• K90: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• KA89: P. Kanellakis , S. Abiteboul, Database theory column, ACM SIGACT News, v.20 n.4, p.17-23, Nov. 1989 [doi>10.1145/74074.74077]
• MS72: Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. Proc. 13th IEEE Syrup. on Switching and Automata Theory, 1972, pp. 125-129.
• MP91: Inderpal Singh Mumick , Hamid Pirahesh, Overbound and right-linear queries, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.127-141, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113425]
• Mo74: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• Na89a: Naughton, J.F.: Data independent recursion in deductive databases. J. Computer and System Sciences, 38(1989), pp. 259-289.
• Na89b: Jeffrey F. Naughton, Minimizing function-free recursive inference rules, Journal of the ACM (JACM), v.36 n.1, p.69-91, Jan. 1989 [doi>10.1145/58562.59303]
• NRSU89: J. F. Naughton , R. Ramakrishnan , Y. Sagiv , J. D. Ullman, Efficient evaluation of right-, left-, and multi-linear rules, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.235-242, June 1989, Portland, Oregon, United States
• Ra69: Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. AMS 141(1969), pp. 1-35.
• RSUV89: R. Ramakrishnan , Y. Sagiv , J. D. Ullman , M. Y Vardi, Proof-tree transformation theorems and their applications, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73739]
• Sa88b: Y. Sagiv, Optimizing datalog programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• Se90: Helmut Seidl, Deciding equivalence of finite tree automata, SIAM Journal on Computing, v.19 n.3, p.424-437, June 1990 [doi>10.1137/0219027]
• Shm87: O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
• TW68: Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical System Theory 2(1968), pp. 57-81.
• Ul89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• UV88: UIlman, J.D., Van Gelder, A.: Parallel complexity of logical query programs. Algorithmica 3(1988), pp. 5- 42.
• Va82: 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]
• Va88: Moshe Y. Vardi, Decidability and undecidability results for boundedness of linear recursive queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.341-351, March 1988, Austin, Texas, United States [doi>10.1145/308386.308470]
• Va92: Moshe Y. Vardi, Automata theory for database theoreticians, Theoretical studies in computer science: thr, Academic Press Professional, Inc., San Diego, CA, 1991
• VW86: Moshe Y Vardi , Pierre Wolper, Automata-Theoretic techniques for modal logics of programs, Journal of Computer and System Sciences, v.32 n.2, p.183-221, April 1986 [doi>10.1016/0022-0000(86)90026-7]
• Zl76: Zloof, M.; Query-by-Example: Operations on the Transitive Closure. IBM Research Report RC5526, 1976.

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Theory