Regular path queries with constraints

Abstract

The evaluation of path expression queries on semistructured data in a distributed asynchronous environment is considered. The focus is on the use of local information expressed in the form of path constraints in the optimization of path expression queries. In particular, decidability and complexity results on the implication problem for path constraints are established. 1 Introduction Navigational queries on data represented in a graph-like manner have proven to be useful in a variety of database contexts, ranging from hypertext data to object-oriented databases. Typically, navigational queries are expressed using regular expressions denoting paths in the graph representing the data. Such path queries have assumed renewed interest in the context of semistructured data [1, 24, 4, 9, 19, 26, 23]) as found for instance in the Web. We focus on a path query evaluation that takes advantage of local knowledge about the data graph. We consider such local knowledge represented as path constrai...