Bounded Arity Datalog (!=) Queries on Graphs.
Foto N. Afrati:
Bounded Arity Datalog (!=) Queries on Graphs.
PODS 1994: 97-106@inproceedings{DBLP:conf/pods/Afrati94,
author = {Foto N. Afrati},
title = {Bounded Arity Datalog (!=) Queries on Graphs},
booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, May 24-26, 1994, Minneapolis,
Minnesota},
publisher = {ACM Press},
year = {1994},
isbn = {0-89791-642-5},
pages = {97-106},
ee = {http://doi.acm.org/10.1145/182591.182603, db/conf/pods/pods94-97.html},
crossref = {DBLP:conf/pods/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
We show that there are Datalog(!=) queries on graphs (i.e., the
extensional database contains a single binary relation) that require
recursively defined predicates of arbitrarilly large width.
More specifically, we prove that fixed subgraph homeomorphism
queries require
width of recursively defined predicates which is at least equal to the
number of arcs in the pattern graph.
Copyright © 1994 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 Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota.
ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX
[Abstract and Index Terms]
[Full Text in PDF Format, 838 KB]
Journal Edition
Foto N. Afrati:
Bounded Arity Datalog (not-)Queries on Graphs.
J. Comput. Syst. Sci. 55(2): 210-228(1997) BibTeX
References
- [AV91]
- ...
- [AG89]
- Miklós Ajtai, Yuri Gurevich:
Datalog vs. First-Order Logic.
FOCS 1989: 142-147 BibTeX
- [AC89]
- Foto N. Afrati, Stavros S. Cosmadakis:
Expressiveness of Restricted Recursive Queries (Extended Abstract).
STOC 1989: 113-126 BibTeX
- [ACY91]
- Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis:
On Datalog vs. Polynomial Time.
PODS 1991: 13-25 BibTeX
- [BR86]
- François Bancilhon, Raghu Ramakrishnan:
An Amateur's Introduction to Recursive Query Processing Strategies.
SIGMOD Conference 1986: 16-52 BibTeX
- [BKBR87]
- Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan:
Bounds on the Propagation of Selection into Logic Programs.
PODS 1987: 214-226 BibTeX
- [CH85]
- Ashok K. Chandra, David Harel:
Horn Clauses Queries and Generalizations.
J. Log. Program. 2(1): 1-15(1985) BibTeX
- [CV92]
- Surajit Chaudhuri, Moshe Y. Vardi:
On the Equivalence of Recursive and Nonrecursive Datalog Programs.
PODS 1992: 55-66 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
- [Co74]
- Stephen A. Cook:
An Observation on Time-Storage Trade Off.
J. Comput. Syst. Sci. 9(3): 308-316(1974) BibTeX
- [FHW80]
- Steven Fortune, John E. Hopcroft, James Wyllie:
The Directed Subgraph Homeomorphism Problem.
Theor. Comput. Sci. 10: 111-121(1980) BibTeX
- [GMSV87]
- Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi:
Undecidable Optimization Problems for Database Logic Programs.
LICS 1987: 106-115 BibTeX
- [KV90]
- Phokion G. Kolaitis, Moshe Y. Vardi:
On the Expressive Power of Datalog: Tools and a Case Study.
PODS 1990: 61-71 BibTeX
- [Ps85]
- ...
- [Sh87]
- Oded Shmueli:
Decidability and Expressiveness of Logic Queries.
PODS 1987: 237-249 BibTeX
- [Ul88]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents 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
- [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
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:10 2009