dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

On the Equivalence of Recursive and Nonrecursive Datalog Programs.

Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
@inproceedings{DBLP:conf/pods/ChaudhuriV92,
  author    = {Surajit Chaudhuri and
               Moshe Y. Vardi},
  editor    = {Moshe Y. Vardi and
               Paris C. Kanellakis},
  title     = {On the Equivalence of Recursive and Nonrecursive Datalog Programs},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California, USA},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {55-66},
  ee        = {http://doi.acm.org/10.1145/137097.137109, db/conf/pods/ChaudhuriV92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Moshe Y. Vardi, Paris C. Kanellakis (Eds.): Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California, USA. ACM Press 1992, ISBN 0-89791-519-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 957 KB]

Journal Version

Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. J. Comput. Syst. Sci. 54(1): 61-78(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AV89]
Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BR86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ch81]
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CH82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CH85]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CKS81]
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CLM81]
Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CGKV88]
Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988: 477-490 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CK86]
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cou90]
Bruno Courcelle: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput. 85(1): 12-75(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cou91]
Bruno Courcelle: Recursive Queries and Context-free Graph Grammars. Theor. Comput. Sci. 78(1): 217-244(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EJ88]
E. Allen Emerson, Charanjit S. Jutla: The Complexity of Tree Automata and Logics of Programs (Extended Abstract). FOCS 1988: 328-337 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GM78]
...
[GMSV87]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HKMV91]
Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HKMV92]
Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. J. Log. Program. 25(2): 163-190(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Im86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[K90]
...
[KA89]
Paris C. Kanellakis, Serge Abiteboul: Database Theory Column: Deciding Bounded Recursion in Database Logic Programs. SIGACT News 20(4): 17-23(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MS72]
...
[MP91]
Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mo74]
...
[Na89a]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Na89b]
Jeffrey F. Naughton: Minimizing function-free recursive inference rules. J. ACM 36(1): 69-91(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NRSU89]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ra69]
...
[RSUV89]
Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sa88b]
...
[Se90]
Helmut Seidl: Deciding Equivalence of Finite Tree Automata. SIAM J. Comput. 19(3): 424-437(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shm87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TW68]
James W. Thatcher, Jesse B. Wright: Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic. Mathematical Systems Theory 2(1): 57-81(1968) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ul89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[UV88]
Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Va82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Va88]
Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Va92]
...
[VW86]
Moshe Y. Vardi, Pierre Wolper: Automata-Theoretic Techniques for Modal Logics of Programs. J. Comput. Syst. Sci. 32(2): 183-221(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zl76]
...

Last update Fri Sep 14 17:28:30 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page