Inductive pebble games and the expressive power of datalog
- 29 March 1989
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 301-310
- https://doi.org/10.1145/73721.73751
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.Keywords
This publication has 8 references indexed in Scilit:
- A graphical query language supporting recursionPublished by Association for Computing Machinery (ACM) ,1987
- Alternation and the computational complexity of logic programsThe Journal of Logic Programming, 1984
- Toward logic tailored for computational complexityLecture Notes in Mathematics, 1984
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- Relational queries computable in polynomial time (Extended Abstract)Published by Association for Computing Machinery (ACM) ,1982
- AlternationJournal of the ACM, 1981
- The directed subgraph homeomorphism problemTheoretical Computer Science, 1980
- An application of games to the completeness problem for formalized theoriesFundamenta Mathematicae, 1960