Datalog expressiveness of chain queries

1 January 1992

conference paper
Published by Association for Computing Machinery (ACM)

p. 81-90
https://doi.org/10.1145/137097.137113

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 grammarr” (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.

Keywords

END NODE
LINEAR DATALOG
CONTEXT-FREE PRODUCTION
GRAMMAR TOOL
BINARY PREDICATE
EXPRESSIVE POWER
GENERAL DATALOG
INPUT DATABASE
NON CONTEXT-FREE
SEMI-LINEAR DATALOG
CHAIN QUERY
DATALOG EXPRESSIVENESS
CONTEXT FREE LANGUAGE
INDEXATION
DIRECTED GRAPH

This publication has 0 references indexed in Scilit: