论文标题
跳跃评估嵌套的常规路径查询
Jumping Evaluation of Nested Regular Path Queries
论文作者
论文摘要
嵌套的常规路径查询用于查询图形数据库和RDF三重存储。我们提出了一种新算法，用于从组合线性时间中的一组启动节点上评估图表上嵌套的常规路径查询。我们表明，可以通过使查询自上而下所需子图的大小（我们引入的概念）的大小来降低这种复杂性上限。在实践中许多查询中，需要自上而下的子图比整个图都小。我们的算法基于从嵌套的常规路径查询到Monadic DataLog查询的新型汇编模式。它的复杂性上限遵循自上而下数据评估的已知属性。作为应用程序，我们表明我们的算法允许简单地重新重新重新重新重新制定Maneth和Nguyen提出的非常有效的基于自动机的算法的变体，该算法根据索引和跳跃评估数据数据中的导航路径查询。此外，它克服了Maneth和Nguyen's的一些局限性：它不受树的束缚，并适用于图。它不仅限于向前导航XPath，还可以使用任何有效的数据级评估器（例如LogicBlox）来对其进行任何嵌套的常规路径查询，并且可以在没有任何专用技术的情况下有效地实现。
Nested regular path queries are used for querying graph databases and RDF triple stores. We propose a new algorithm for evaluating nested regular path queries on a graph from a set of start nodes in combined linear time. We show that this complexity upper bound can be reduced by making it dependent on the size of the query's top-down needed subgraph, a notion that we introduce. For many queries in practice, the top-down needed subgraph is way smaller than the whole graph. Our algorithm is based on a novel compilation schema from nested regular path queries to monadic datalog queries. Its complexity upper bound follows from known properties of top-down datalog evaluation. As an application, we show that our algorithm permits to reformulate in simple terms a variant of a very efficient automata-based algorithm proposed by Maneth and Nguyen that evaluates navigational path queries in datatrees based on indexes and jumping. Moreover, it overcomes some limitations of Maneth and Nguyen's: it is not bound to trees and applies to graphs; it is not limited to forward navigational XPath but can treat any nested regular path query and it can be implemented efficiently without any dedicated techniques, by using any efficient datalog evaluator such as LogicBlox.
