Expressive languages for path queries over graph-structured data
Expressive languages for path queries over graph-structured data
复制标题
DOI：
10.1145/1807085.1807089
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
Pablo Barceló;Carlos A. Hurtado;Leonid Libkin;Peter T. Wood
中科院分区：
文献类型：
--
作者：
Pablo Barceló;Carlos A. Hurtado;Leonid Libkin;Peter T. Wood
对于图查询设置中出现的许多问题（如在RDF图中查找语义关联、精确和近似模式匹配、序列对齐等），标准语言（如广泛研究的合取规则路径查询（CRPQs））的能力至少在两个方面是不足的。首先，它们不能输出路径，其次，更关键的是，它们不能表达路径之间的关系。因此，我们提出了一类扩展的crpq，称为ecrpq，它在路径元组上添加正则关系，并允许在查询的头部使用路径变量。我们提供了几个例子来说明它们在查询图结构数据方面的用处，并研究了它们的属性。我们利用自动机分析了输出中路径元组的查询求值和表示。我们对数据和查询的组合复杂性进行了详细的分析，并考虑了将ecrpq的复杂性降低到关系连接查询的复杂性的限制。我们研究了包含问题，并研究了基于标签出现的长度和次数的一阶特征和表达路径算术性质的非正则关系的进一步扩展。
For many problems arising in the setting of graph querying (such as finding semantic associations in RDF graphs, exact and approximate pattern matching, sequence alignment, etc.), the power of standard languages such as the widely studied conjunctive regular path queries (CRPQs) is insufficient in at least two ways. First, they cannot output paths and second, more crucially, they cannot express relations among paths. We thus propose a class of extended CRPQs, called ECRPQs, which add regular relations on tuples of paths, and allow path variables in the heads of queries. We provide several examples of their usefulness in querying graph structured data, and study their properties. We analyze query evaluation and representation of tuples of paths in the output by means of automata. We present a detailed analysis of data and combined complexity of queries, and consider restrictions that lower the complexity of ECRPQs to that of relational conjunctive queries. We study the containment problem, and look at further extensions with first-order features, and with non-regular relations that express arithmetic properties of paths, based on the lengths and numbers of occurrences of labels.