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},
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},
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}
}
BibTeX
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 ...
BibTeX
Printed Edition
Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California.
ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX
[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) BibTeX
References
- [AU79]
- Alfred V. Aho, Jeffrey D. Ullman:
The Universality of Data Retrieval Languages.
POPL 1979: 110-120 BibTeX
- [AV89]
- Serge Abiteboul, Victor Vianu:
Fixpoint Extensions of First-Order Logic and Datalog-Like Languages.
LICS 1989: 71-79 BibTeX
- [BR86]
- François Bancilhon, Raghu Ramakrishnan:
An Amateur's Introduction to Recursive Query Processing Strategies.
SIGMOD Conference 1986: 16-52 BibTeX
- [Ch81]
- Ashok K. Chandra:
Programming Primitives for Database Languages.
POPL 1981: 50-62 BibTeX
- [CH80]
- Ashok K. Chandra, David Harel:
Computable Queries for Relational Data Bases.
J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
- [CH82]
- Ashok K. Chandra, David Harel:
Structure and Complexity of Relational Queries.
J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
- [CH85]
- Ashok K. Chandra, David Harel:
Horn Clauses Queries and Generalizations.
J. Log. Program. 2(1): 1-15(1985) BibTeX
- [CKS81]
- Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer:
Alternation.
J. ACM 28(1): 114-133(1981) BibTeX
- [CLM81]
- Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky:
Embedded Implicational Dependencies and their Inference Problem.
STOC 1981: 342-354 BibTeX
- [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 BibTeX
- [CK86]
- Stavros S. Cosmadakis, Paris C. Kanellakis:
Parallel Evaluation of Recursive Rule Queries.
PODS 1986: 280-293 BibTeX
- [Cou90]
- Bruno Courcelle:
The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs.
Inf. Comput. 85(1): 12-75(1990) BibTeX
- [Cou91]
- Bruno Courcelle:
Recursive Queries and Context-free Graph Grammars.
Theor. Comput. Sci. 78(1): 217-244(1991) BibTeX
- [EJ88]
- E. Allen Emerson, Charanjit S. Jutla:
The Complexity of Tree Automata and Logics of Programs (Extended Abstract).
FOCS 1988: 328-337 BibTeX
- [GM78]
- ...
- [GMSV87]
- Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi:
Undecidable Optimization Problems for Database Logic Programs.
LICS 1987: 106-115 BibTeX
- [HKMV91]
- Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi:
Tools for Datalog Boundedness.
PODS 1991: 1-12 BibTeX
- [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) BibTeX
- [Im86]
- Neil Immerman:
Relational Queries Computable in Polynomial Time.
Information and Control 68(1-3): 86-104(1986) BibTeX
- [K90]
- ...
- [KA89]
- Paris C. Kanellakis, Serge Abiteboul:
Database Theory Column: Deciding Bounded Recursion in Database Logic Programs.
SIGACT News 20(4): 17-23(1989) BibTeX
- [MS72]
- ...
- [MP91]
- Inderpal Singh Mumick, Hamid Pirahesh:
Overbound and Right-Linear Queries.
PODS 1991: 127-141 BibTeX
- [Mo74]
- ...
- [Na89a]
- Jeffrey F. Naughton:
Data Independent Recursion in Deductive Databases.
J. Comput. Syst. Sci. 38(2): 259-289(1989) BibTeX
- [Na89b]
- Jeffrey F. Naughton:
Minimizing function-free recursive inference rules.
J. ACM 36(1): 69-91(1989) BibTeX
- [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 BibTeX
- [Ra69]
- ...
- [RSUV89]
- Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi:
Proof-Tree Transformation Theorems and Their Applications.
PODS 1989: 172-181 BibTeX
- [Sa88b]
- ...
- [Se90]
- Helmut Seidl:
Deciding Equivalence of Finite Tree Automata.
SIAM J. Comput. 19(3): 424-437(1990) BibTeX
- [Shm87]
- Oded Shmueli:
Decidability and Expressiveness of Logic Queries.
PODS 1987: 237-249 BibTeX
- [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) BibTeX
- [Ul89]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
- [UV88]
- Jeffrey D. Ullman, Allen Van Gelder:
Parallel Complexity of Logical Query Programs.
Algorithmica 3: 5-42(1988) BibTeX
- [Va82]
- Moshe Y. Vardi:
The Complexity of Relational Query Languages (Extended Abstract).
STOC 1982: 137-146 BibTeX
- [Va88]
- Moshe Y. Vardi:
Decidability and Undecidability Results for Boundedness of Linear Recursive Queries.
PODS 1988: 341-351 BibTeX
- [Va92]
- ...
- [VW86]
- Moshe Y. Vardi, Pierre Wolper:
Automata-Theoretic Techniques for Modal Logics of Programs.
J. Comput. Syst. Sci. 32(2): 183-221(1986) BibTeX
- [Zl76]
- ...
Referenced by
- Chen Li, Edward Y. Chang:
On Answering Queries in the Presence of Limited Access Patterns.
ICDT 2001: 219-233
- Todd D. Millstein, Alon Y. Levy, Marc Friedman:
Query Containment for Data Integration Systems.
PODS 2000: 67-75
- Daniela Florescu, Alon Y. Levy, Dan Suciu:
Query Containment for Conjunctive Queries with Regular Expressions.
PODS 1998: 139-148
- Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini:
On the Decidability of Query Containment under Constraints.
PODS 1998: 149-158
- Serge Abiteboul, Oliver M. Duschka:
Complexity of Answering Queries Using Materialized Views.
PODS 1998: 254-263
- Alon Y. Levy, Dan Suciu:
Deciding Containment for Queries with Complex Objects.
PODS 1997: 20-31
- Jeffrey D. Ullman:
Information Integration Using Logical Views.
ICDT 1997: 19-40
- Alon Y. Levy:
Obtaining Complete Answers from Incomplete Databases.
VLDB 1996: 402-412
- Alon Y. Levy, Yehoshua Sagiv:
Semantic Query Optimization in Datalog Programs.
PODS 1995: 163-173
- Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava:
Answering Queries Using Views.
PODS 1995: 95-104
- Guozhu Dong, Jianwen Su:
Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries.
ICDT 1995: 397-410
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom:
Constraint Checking with Partial Information.
PODS 1994: 45-55
- Surajit Chaudhuri, Moshe Y. Vardi:
On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs.
PODS 1994: 107-116
- Foto N. Afrati:
Bounded Arity Datalog (!=) Queries on Graphs.
PODS 1994: 97-106
- Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli:
Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions.
PODS 1993: 109-122
- Surajit Chaudhuri:
Finding Nonrecursive Envelopes for Datalog Predicates.
PODS 1993: 135-146
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:05 2009