Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations.
Guozhu Dong:
Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations.
PODS 1992: 81-90@inproceedings{DBLP:conf/pods/Dong92,
author = {Guozhu Dong},
title = {Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations},
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 = {81-90},
ee = {http://doi.acm.org/10.1145/137097.137113, db/conf/pods/Dong92.html},
crossref = {DBLP:conf/pods/92},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
A chain query seeks, for each input database (viewed as a directed graph),
all pairs of start and end nodes of paths whose labels spell words in an
associated (possibly non context-free) language over some binary predicates.
We study the expressive power of Datalog for chain queries.
Extending context-free productions with labels, we introduce a new tool
called "indexed positive programmed grammar" (IPPG). Three variations of
IPPG are introduced to characterize chain queries computable (i) by linear
Datalog, (ii) by "semi-linear Datalog", and (iii) by general Datalog,
respectively, under a natural "addressable" condition.
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, 825 KB]
References
- [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
- [AG90]
- Miklós Ajtai, Yuri Gurevich:
Datalog vs First-Order Logic.
J. Comput. Syst. Sci. 49(3): 562-588(1994) BibTeX
- [Aho68]
- Alfred V. Aho:
Indexed Grammars - An Extension of Context-Free Grammars.
J. ACM 15(4): 647-671(1968) BibTeX
- [AU79]
- Alfred V. Aho, Jeffrey D. Ullman:
The Universality of Data Retrieval Languages.
POPL 1979: 110-120 BibTeX
- [CH85]
- Ashok K. Chandra, David Harel:
Horn Clauses Queries and Generalizations.
J. Log. Program. 2(1): 1-15(1985) BibTeX
- [DG91]
- ...
- [Don91a]
- ...
- [Don91b]
- ...
- [KV90]
- Phokion G. Kolaitis, Moshe Y. Vardi:
On the Expressive Power of Datalog: Tools and a Case Study.
PODS 1990: 61-71 BibTeX
- [Llo87]
- John W. Lloyd:
Foundations of Logic Programming, 2nd Edition.
Springer 1987, ISBN 3-540-18199-7
BibTeX
- [LM89]
- V. S. Lakshmanan, Alberto O. Mendelzon:
Inductive Pebble Games and the Expressive Power of Datalog.
PODS 1989: 301-310 BibTeX
- [Pap85]
- ...
- [Ros69]
- Daniel J. Rosenkrantz:
Programmed Grammars and Classes of Formal Languages.
J. ACM 16(1): 107-131(1969) BibTeX
- [Sal73]
- ...
- [Shm87]
- Oded Shmueli:
Decidability and Expressiveness of Logic Queries.
PODS 1987: 237-249 BibTeX
- [UV88]
- Jeffrey D. Ullman, Allen Van Gelder:
Parallel Complexity of Logical Query Programs.
Algorithmica 3: 5-42(1988) BibTeX
Referenced by
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Guozhu Dong, Jianwen Su:
First-Order Incremental Evaluation of Datalog Queries.
DBPL 1993: 295-308
- Sergio Greco:
Optimization of Chain Queries.
DASFAA 1993: 261-268
- 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:05 2009