| dc.description.abstract | Graph data appears in a variety of application domains, and many uses of it, such as querying, matching,
and transforming data, naturally result in incompletely specified graph data, that is, graph patterns. While
queries need to be posed against such data, techniques for querying patterns are generally lacking, and
properties of such queries are not well understood.
Our goal is to study the basics of querying graph patterns. The key features of patterns we consider
here are node and label variables and edges specified by regular expressions. We provide a classification of
patterns, and study standard graph queries on graph patterns. We give precise characterizations of both
data and combined complexity for each class of patterns. If complexity is high, we do further analysis of
features that lead to intractability, as well as lower-complexity restrictions. Since our patterns are based on
regular expressions, query answering for them can be captured by a new automata model. These automata
have two modes of acceptance: one captures queries returning nodes, and the other queries returning paths.
We study properties of such automata, and the key computational tasks associated with them. Finally, we
provide additional restrictions for tractability, and show that some intractable cases can be naturally cast
as instances of constraint satisfaction problems. | |
