Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations
Find in a Library
A chain query seeks, for each input database (viewed as 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.
(1992). Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations. Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 81-90.