Surajit Chaudhuri
Moshe Y. Vardi
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.
- AU79.Aho, A.V., Ullman, J.D.: Universality of data retrieval languages. Proc. 6th A CM Syrup. on Principles 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's introduction to recursive query processing strategies. Proc. A CM Con/. on Management o/Data, Washington, 1986, pp. 16- 52. Google ScholarDigital Library
- Ch81.Chandra, A.K.,: Programming primitives for database languages. Proc. 8th A CM Syrup. on Principles o/ Programming Languages, Williamsburg, 1981, 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., Hare1, D.: Horn Clause Queries and Generalizations. j. Logic Programming, 2 (1985), 1- 15.Google ScholarCross Ref
- CKS81.Chandra, h., Kozen, A., Stockmeyer, L.: Alternation, J. A CM 28(1981), pp. 114-133. Google ScholarDigital Library
- CLM81.Chandra, A. K., H. R. Lewis, and J. A. Makowsky, Embedded implicational dependencies and their inference problem. Proc. 13th A CM Symp. on Theory of Computing, 1981, pp. 342-354. Google ScholarDigital Library
- CGKV88.Cosmadakis, S.S., Gaifman, H., Kanellakis, P.C., Vardi, M.Y.: Decidable optimization problems for database logic programs. Proc. 20th ACM Syrup. on Theory of Computing, 1988, pp. 477-490. 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
- Cou90.Courcelle, B.: The monadic secondorder theory of graphs I- Recognizable sets of finite graphs. Information and Computation 85(1990), pp. 12-75. Google ScholarDigital Library
- Cou91.Courcelle, B.: Recursive queries and context-free graph grammars. Theoretical Computer Science 78(1991), pp. 217-244. Google ScholarDigital Library
- 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.Google Scholar
- GM78.Gallaire, H., Minker, J.: Logic and Databases. Plenum Press, 1978. Google ScholarDigital Library
- 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.Google Scholar
- HKMV91.Hillebrand, G.G., Kanellakis, P.C., Mairson, H.G., Vardi, M.Y.: Tools for Datalog boundedness. Proc. l Oth A CM Syrup. on Principles of Database Systems, May 1991, pp. 1- 12. Google ScholarDigital Library
- HKMV92.Hillebrand, G.G., Kanellakis, P.C., Mairson, H.G., Vardi, M.Y.: Uudecidable boundedness problems for Datalog programs. To appear.Google Scholar
- Im86.Immerman, N.: Relational queries computable in polynomial time. In- .formation and Control 68(1986), pp. 86-104. Google ScholarDigital Library
- K90.Kanellakis P.C.: Elements of Relational Database Theory. Handbook o/ 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
- KA89.Kanellakis, P., Abiteboul, S.: Deciding bounded recursion in database logic programs. SIGA CT News 20:4, Fall 1989. Google ScholarDigital Library
- 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.Google Scholar
- MP91.Mumick, I.S.,Pirahesh, H.: Overbound and right-linear queries. Proc. l Oth A CM Symp. on Principles of Database Systems, 1991, pp. 127-141. Google ScholarDigital Library
- Mo74.Moschovakis, Y.N.: Elementary Induction on Abstract Structures. North Holland, 1974. Google ScholarDigital Library
- Na89a.Naughton, J.F.: Data independent recursion in deductive databases. J. Computer and System Sciences, 38(1989), pp. 259-289.Google ScholarCross Ref
- Na89b.Naughton, J.F.: Minimizing function-free recursive definitions. J. ACM 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
- Ra69.Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. AMS 141(1969), pp. 1-35.Google Scholar
- RSUV89.Ramakrishnan, R., Sagiv, Y., Ullman, J.D., Vardi, M.Y.: Proof-tree transformation theorems and their applications. Proc. 8th A CM Syrup. on Principles of Database Systems, 1989, pp. 171-181. Google ScholarDigital Library
- Sa88b.Sagiv, Y.: Optimizing Datalog programs. In Foundations of Deductive Databases and Logic Programming, J. Minker (ed.), Morgan Kaufmann Publishers, 1988, pp. 659-698. Google ScholarDigital Library
- Se90.Seidl, H.: Deciding equivalence of finite tree automata. SIAM j. Computing 19(1990), pp. 424-437. Google ScholarDigital Library
- Shm87.Shmueli, 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
- 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.Google ScholarCross Ref
- Ul89.Ullman, J.D.: Principles o# Database and Knowledge Base Systems, Vol. 2, Computer Science Press, 1989. Google ScholarDigital Library
- UV88.UIlman, J.D., Van Gelder, A.: Parallel complexity of logical query programs. Algorithmica 3(1988), pp. 5- 42.Google ScholarDigital Library
- Va82.Vardi, M.Y.: The complexity of relational query languages. Proc. l#th ACM Syrup. on Theory of Computing, San Francisco, 1982, pp. 137- 146. Google ScholarDigital Library
- Va88.Vardi, M.Y.: Decidability and undecidability results for boundedness of linear recursive queries. Proc. 7th A CM Symp. on Principles o/ Database Systems, 1988, pp. 341- 351. Google ScholarDigital Library
- Va92.Vardi, M.Y.: Automata theory for database theoreticians. In Theoretical Studies in Computer Science (J.D. Ullman, ed.), Academic Press, 1992, pp. 153-180. Google ScholarDigital Library
- VW86.Vardi, M.Y., Wolper, P.: Automatatheoretic techniques for modal logic of programs. J. Computer and System Sciences 32(1986), pp. 183-221. Google ScholarDigital Library
- Zl76.Zloof, M.; Query-by-Example: Operations on the Transitive Closure. IBM Research Report RC5526, 1976.Google Scholar
Index Terms
- On the equivalence of 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 complexity of equivalence between recursive and nonrecursive Datalog programs
PODS '94: Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsIn 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 ...
Equivalence between extended datalog programs -- a brief survey
Datalog'10: Proceedings of the First international conference on Datalog ReloadedThis paper gives a brief overview about the research field on equivalences in Answer-Set Programming. More precisely, we are concerned here with disjunctive logic programs under the stable-model semantics. Such programs can be understood as extended ...
Comments