ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Inductive Pebble Games and the Expressive Power of Datalog.

V. S. Lakshmanan, Alberto O. Mendelzon: Inductive Pebble Games and the Expressive Power of Datalog. PODS 1989: 301-310
@inproceedings{DBLP:conf/pods/LakshmananM89,
  author    = {V. S. Lakshmanan and
               Alberto O. Mendelzon},
  title     = {Inductive Pebble Games and the Expressive Power of Datalog},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {301-310},
  ee        = {http://doi.acm.org/10.1145/73721.73751, db/conf/pods/LakshmananM89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

As an alternative to logic-based query languages for recursive queries, we are investigating a graphical query language called G+, which allows, among other things, easy formulation of certain queries involving simple paths in directed graphs. This led us to study whether such queries are expressible in DATALOG, the language of function-free Horn clauses. Since some G+ queries are NP-hard, and all DATALOG queries are polynomial time computable, the answer appears to be negative. However, it would be interesting to have proof techniques and tools for settling such questions with certainty. The objective of this paper is the development of one such tool, inductive pebble games, based on a normal form for DATALOG programs derived here, and its relationship to Alternating Turing Machine computations. As an application, we sketch a proof that the query "find all pairs of nodes connected by a directed simple path of even length" cannot be expressed in DATALOG.

Copyright © 1989 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 Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[ChHa 85]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[CKS 81]
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) BibTeX
[CMW 87]
Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330 BibTeX
[CMW 88]
Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: G+: Recursive Queries Without Recursion. Expert Database Conf. 1988: 645-666 BibTeX
[Eh 61]
...
[Fa 74]
...
[FHW 80]
Steven Fortune, John E. Hopcroft, James Wyllie: The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci. 10: 111-121(1980) BibTeX
[Fr 72]
...
[Gu 83]
...
[Im 82]
Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152 BibTeX
[Im 82a]
Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX
[LM 88]
...
[Ll 87]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[MW 88]
...
[Ro 87]
...
[Sh 84]
Ehud Y. Shapiro: Alternation and the Computational Complexity of Logic Programs. J. Log. Program. 1(1): 19-33(1984) BibTeX
[Ul 88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Va 82]
...
[Ya 88]
...

Referenced by

  1. Stavros S. Cosmadakis: Inherent Complexity of Recursive Queries (Extended Abstract). PODS 1999: 148-154
  2. Phokion G. Kolaitis: Combinatorial Games In Database Theory. PODS 1995: 231-232
  3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  4. Guozhu Dong: Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations. PODS 1992: 81-90
  5. Stéphane Grumbach: A Paradox in Database Theory. ICDT 1992: 312-325
  6. Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25
  7. Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990: 61-71
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:33:57 2009