Querying Regular Graph Patterns
Querying Regular Graph Patterns
复制标题
DOI：
10.1145/2559905
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
P. Barceló;L. Libkin;Juan L. Reutter
中科院分区：
文献类型：
--
作者：
P. Barceló;L. Libkin;Juan L. Reutter
图数据出现在各种应用领域中，对它的许多使用，例如查询，匹配和转换数据，自然会导致不完全指定的图数据，即图模式。虽然需要对这些数据提出查询，但通常缺乏查询模式的技术，并且这些查询的属性没有很好地理解。我们的目标是学习查询图模式的基础知识。我们在这里考虑的模式的关键特征是节点和标签变量以及由正则表达式指定的边。我们提供了一个分类的模式，并研究标准的图模式上的图查询。我们给出了精确的特征的数据和组合的复杂性为每一类模式。如果复杂度很高，我们会进一步分析导致棘手的特性，以及复杂度较低的限制。由于我们的模式是基于正则表达式，查询回答他们可以捕获一个新的自动机模型。这些自动机有两种接受模式：一种捕获返回节点的查询，另一种捕获返回路径的查询。我们研究这样的自动机的属性，以及与之相关的关键计算任务。最后，我们提供了额外的限制，易处理性，并表明，一些棘手的情况下，可以自然地投约束满足问题的实例。
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.