Tools for Datalog Boundedness.
Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi:
Tools for Datalog Boundedness.
PODS 1991: 1-12@inproceedings{DBLP:conf/pods/HillebrandKMV91,
author = {Gerd G. Hillebrand and
Paris C. Kanellakis and
Harry G. Mairson and
Moshe Y. Vardi},
title = {Tools for Datalog Boundedness},
booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
publisher = {ACM Press},
year = {1991},
isbn = {0-89791-430-9},
pages = {1-12},
ee = {http://doi.acm.org/10.1145/113413.113414, db/conf/pods/HillebrandKMV91.html},
crossref = {DBLP:conf/pods/91},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
A given Datalog program is bounded if its
depth of recursion is independent of the input database.
Deciding boundedness is a basic task for the analysis of
these database logic programs. We develop a number of
new tools for proving (un)decidability of various kinds
of boundedness for programs with: a small arity of the
recursively defined predicates or a small number of rules.
(1) We use the mortality problem of Turing machines
to show that uniform boundedness is undecidable for
arity 3 predicates and for arity 1 predicates when != is
also allowed. (2) We use a single rule polymorphically to
show that program (predicate) boundedness is undecidable
for two linear rules (one rule and a projection), one
initialization rule and small arity predicates. (3) We use
the theory of semi-linear sets to sharpen the conditions
under which one can decide boundedness for one linear
rule, any initialization rules and any arity predicates.
Copyright © 1991 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 Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado.
ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX
[Index Terms]
[Full Text in PDF Format, 1246 KB]
References
- [A89]
- Serge Abiteboul:
Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule.
Inf. Process. Lett. 32(6): 281-287(1989) BibTeX
- [AG89]
- Miklós Ajtai, Yuri Gurevich:
Datalog vs. First-Order Logic.
FOCS 1989: 142-147 BibTeX
- [CH85]
- Ashok K. Chandra, David Harel:
Horn Clauses Queries and Generalizations.
J. Log. Program. 2(1): 1-15(1985) 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
- [GMSV87]
- Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi:
Undecidable Optimization Problems for Database Logic Programs.
J. ACM 40(3): 683-713(1993) BibTeX
- [G90]
- Irène Guessarian:
Deciding Boundedness for Uniformly Connected Datalog Programs.
ICDT 1990: 395-405 BibTeX
- [H66]
- ...
- [I85]
- Yannis E. Ioannidis:
A Time Bound on the Materialization of Some Recursively Defined Views.
Algorithmica 1(3): 361-385(1986) BibTeX
- [K88]
- ...
- [K90]
- ...
- [KTU90]
- A. J. Kfoury, Jerzy Tiuryn, Pawel Urzyczyn:
The Undecidability of the Semi-Unification Problem (Preliminary Report).
STOC 1990: 468-476 BibTeX
- [MUV84]
- David Maier, Jeffrey D. Ullman, Moshe Y. Vardi:
On the Foundations of the Universal Relation Model.
ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX
- [M90]
- ...
- [N86]
- Jeffrey F. Naughton:
Data Independent Recursion in Deductive Databases.
J. Comput. Syst. Sci. 38(2): 259-289(1989) BibTeX
- [N89]
- Jeffrey F. Naughton:
Minimizing function-free recursive inference rules.
J. ACM 36(1): 69-91(1989) BibTeX
- [NS87]
- Jeffrey F. Naughton, Yehoshua Sagiv:
A Decidable Class of Bounded Recursions.
PODS 1987: 227-236 BibTeX
- [P66]
- Rohit Parikh:
On Context-Free Languages.
J. ACM 13(4): 570-581(1966) BibTeX
- [S85]
- Yehoshua Sagiv:
On Bounded Database Schemes and Bounded Horn-Clause Programs.
SIAM J. Comput. 17(1): 1-22(1988) BibTeX
- [S88]
- ...
- [Sh87]
- Oded Shmueli:
Decidability and Expressiveness of Logic Queries.
PODS 1987: 237-249 BibTeX
- [U89a]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
- [U89b]
- 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
- [V88]
- Moshe Y. Vardi:
Decidability and Undecidability Results for Boundedness of Linear Recursive Queries.
PODS 1988: 341-351 BibTeX
Referenced by
- Ke Wang:
Some Positive Results for Boundedness of Multiple Recursive Rules.
ICDT 1995: 383-396
- Guozhu Dong, Jianwen Su:
Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries.
ICDT 1995: 397-410
- Inderpal Singh Mumick, Oded Shmueli:
Universal Finiteness and Satisfiability.
PODS 1994: 190-200
- Surajit Chaudhuri, Moshe Y. Vardi:
On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs.
PODS 1994: 107-116
- Surajit Chaudhuri:
Finding Nonrecursive Envelopes for Datalog Predicates.
PODS 1993: 135-146
- Guozhu Dong, Jianwen Su:
First-Order Incremental Evaluation of Datalog Queries.
DBPL 1993: 295-308
- Surajit Chaudhuri, Moshe Y. Vardi:
On the Equivalence of Recursive and Nonrecursive Datalog Programs.
PODS 1992: 55-66
- Guozhu Dong, Rodney W. Topor:
Incremental Evaluation of Datalog Queries.
ICDT 1992: 282-296
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:02 2009