Surajit Chaudhuri
Moshe Y. Vardi
ABSTRACT
In a previous paper, we have proved tight complexity bounds for the equivalence of recursive and nonrecursive Datalog programs: triply exponential time in general and doubly-exponential space for linear programs. In this paper, we show that under realistic restrictions on the classes programs under consideration, equivalence of recursive and nonrecursive programs can be less intractable; for the classes of programs we consider the complexity of equivalence ranges from NP to co-NEXPTIME.
- AU79.Aho, A.V., Ullman, J.D.: Universality of data retrieval languages. Proc. 6th A CM Symp. on Prznczples of Programming Languages, 1979, pp. 110-117. Google Scholar
Digital Library
- AV89.Abiteboul, S., Vianu, V.: Fixpoint Extensions of First-Order Logic and Datalog-like languages. Proc. 4th IEEE Syrup. on Logic in Computer Science, 1989, pp. 71-79. Google ScholarDigital Library
- BR86.Bancilhon, F., Ramakrishnan, R.: An amateur'# introduction to recur#ive query processing strategies. Proc. A CM Conf. on Management of Data, Washington, 1986, pp. 16-52. Google ScholarDigital Library
- Ch81.Chandra, A.K.,: Programming primitives for database languages. Proc. 8th A CM Symp. on Pmnc,ples of Programming Languages, Williamsburg, 198i, pp. 50-62. Google ScholarDigital Library
- CH80.Chandra, A.K., Harel, D.: Computable queries for relational databases. J. Computer and Systems Sciences 21(1980), pp. 156-178.Google ScholarCross Ref
- CH82.Chandra, A.K., Harel, D.: Structure and Complexity of Relational Queries. J. Computer and Systems Sciences 25(1982), pp. 99-128.Google ScholarCross Ref
- CH85.Chandra, A.K., Harel, D.: Horn Clause Queries and Generalizations. J. Logzc Programmzng, 2 (1985), 1-15.Google ScholarCross Ref
- CLM81.Chandra, A. K., H. R. Lewis, and J. A. Makowsky, Embedded implicational dependencies and their inference problem. Proc. 13th A CM Syrup. on Th eory of Computing, 1981, pp. 342-354. Google ScholarDigital Library
- Co89.Cosmadakis, S.S.: On the First-Order Expressibility of Recursive Queries. Proc. 8th ACM Syrup. on Principles of Database Systems, Austin, 1989, pp. 311-323. Google ScholarDigital Library
- CK86.Cosmadakis, S.S., Kanellakis, P.: Parallel evaluation of recursive rule queries. Proc. 5th A CM Syrup. on Principles of Database Systems, Cambridge, 1986, pp. 280-293. Google ScholarDigital Library
- CV92.Chaudhuri S., Vardi M. Y.: On the Equivalence of Recursive and Nonrecursive Programs. Proc. 11th ACM Symp. on Principles of Database Systems, San Diego. Full version available as IBM Research Report RJ9596, Nov 1993. Google ScholarDigital Library
- GMSV93.Gaifman, H., Mairson, H., Sagiv, Y, Vardi M.Y." Undecidable optimization problems for database logic programs. J. ACM 40(1993), pp. 683-713. Google ScholarDigital Library
- GM78.Gallaire, H., Minker, J.: Logic and Databases. Plenum Press, 1978. Google ScholarDigital Library
- HKMV91.Hillebrand, G.G., Kanellakis, P.C., Mairson, H.G., Vardi, M.Y.: Tools for Datalog boundedness. Proc. 10th A CM Zoymp. on Pr#nczples of Database Systems, May 1991, pp. 1-12. Google ScholarDigital Library
- HU79.Itopcroft, J.E., Ullman, J.D.: Introduct#on to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. Google ScholarDigital Library
- Im86.Immerman, N.: Relational queries computable in polynomial time. Information and Control 68(1986), pp. 86-104. Google ScholarDigital Library
- Ka88.Kanellakis, P. C.: Logic programming and parallel complexity, in Foundations of Deductive Databnses and Logic Programming (J. Minker, ed.), Morgan Kaufmann, Los Altos, pp. 545-585, 1988. Google ScholarDigital Library
- Ka90.Kanellakis P.C.: Elements of Relational Database Theory. Handbook of Theoretical Computer Science, Vol. B, Chapter 17, J. van Leeuwen, A.R. Meyer, N. Nivat, M.S. Paterson, D. Perrin ed., North- Holland 1990. Google ScholarDigital Library
- MP91.Mumick, I.S.,Pirahesh, H.: Overbound and right-linear queries. Proc. l Oth A CM Syrup. oR Prz#czples of Database Systems, 1991, pp. 127-14I. Google ScholarDigital Library
- Me93.Van der Meyden, R.: Recursively indefinite databases. Theoretical Computer Science 116(1993), 151-194. Google ScholarDigital Library
- Mo74.Moschovakis, Y.N.: Elementary Induction on Abstract Structures. North Holland, 1974. Google ScholarDigital Library
- Na89.Naughton, J.F.: Minimizing function-free recursive definitions. J. A CM 36(1989), pp. 69-91. Google ScholarDigital Library
- NRSU89.Naughton, J.F., Ramakrishnan, R., Sagiv, Y., Ullman, J.D.: Efficient evaluation of right , left , and multilinear rules. Proc. A CM-SIGMOD Int'l Conf. on Management of Data, 1989, pp. 235-242. Google ScholarDigital Library
- RSUV93.Ramakrishnan, R., Sagiv, Y., Ullman, J.D., Vardi, M.Y.: Logical query optimization by proof-tree transformation. J. Computer and System Sciences 47(1993), pp. 222-248. Google ScholarDigital Library
- Sa88.Sagiv, Y.: Optimizing Datalog programs. In Foundatzons of Deductive Databases and Logzc Programmzng, J. Minker (ed.), Morgan Kaufmann Publishers, 1988, pp. 659-698. Google ScholarDigital Library
- SV89.Sagiv, Y. and Vardi M. Y.: Safety of Datalog Queries over Infinite Databases. Proc. 8th A CM Syrup. on Pr#nczples of Database Systems, 1989, pp. 160-171. Google ScholarDigital Library
- SY81.Sagiv,Y., Yannakakis M.: Equivalences among Relational Expressions with the union and difference operators. JACM, 27:4, pp 633-655. Google ScholarDigital Library
- Sh87.Shmueti, O.: Decidability and expressiveness aspects of logic queries. Proc. 6th A CM Syrup. on Principles of Database Systems, 1987, pp. 237-249. Google ScholarDigital Library
- Ul89.Ullman, J.D.: Prznc,pIes of Database and Knowledge Base Systems, Vol. 2, Computer Science Press, 1989. Google ScholarDigital Library
- Va82.Vardi, M.Y.: The complexity of relational query languages. Proc. l#,th A CM Coymp. on Theory of Computzng, San Francisco, 1982, pp. 137-146. Google ScholarDigital Library
- Zl76.Zloof, M.; Query-by-Example: Operalzons on the Transitive Closure. IBM Research Report RC5526, 1976.Google Scholar
Index Terms
- On the complexity of equivalence between recursive and nonrecursive Datalog programs
Recommendations
On the Equivalence of Recursive and Nonrecursive Datalog Programs
Special issue: dedicated to the memory of Paris KanellakisWe study the problem of determining whether a given recursive Datalog program is equivalent to a given nonrecursive Datalog program. Since nonrecursive Datalog programs are equivalent to unions of conjunctive queries, we study also the problem of ...
On the equivalence of recursive and nonrecursive datalog programs
PODS '92: Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsWe 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.
Complexity classes of partial recursive functions
This paper studies possible extensions of the concept of complexity class of recursive functions to partial recursive functions. Many of the well-known results for total complexity classes are shown to have corresponding, though not exactly identical, ...
Reviews
Prokop Vondracek
First-order database query languages are lacking in expressive power. Datalog, the language of logic programs (Horn-clause programs), is essentially a fragment of fixpoint logic. In this paper, the authors study the effect of reasonable restrictions on the complexity of the equivalence problem. Equivalence of recursive and nonrecursive programs can be less intractable; for the classes of programs considered, the complexity of equivalence ranges from NP to co-NEXPTIME.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments