Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations

Document Type

Conference Proceeding

Publication Date

6-1992

Find in a Library

Catalog Record

Abstract

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.

Comments

Presented at the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, San Diego, CA, June 2-4, 1992.

DOI

10.1145/137097.137113

Catalog Record

Share

COinS