How to Best Nest Regular Path Queries
How to Best Nest Regular Path Queries
复制标题
如何最好地嵌套常规路径查询
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Rudolph
中科院分区：
文献类型：
--
作者：
P. Bourhis;M. Krötzsch;S. Rudolph
规则路径查询（RPQ）根据规则表达式定义查询模式，因此非常适合查询DL中的角色路径。RPQ可以扩展到2路RPQ（具有匡威），CRPQ（具有合取）或PRPQ（任意正布尔组合），所有这些都已在DL研究中进行了探索。任何查询语言的另一个自然扩展是嵌套，其中查询谓词可以根据子查询来定义。本文讨论了在PRPQ中引入嵌套的几种方法，并指出它们导致了表达能力越来越强的查询语言：最近在DL上下文中研究的CN2 RPQ;嵌套的P2 RPQ;以及在二元谓词上具有传递闭包的正查询。后者是最具表现力的语言之一，查询回答仍然可以决定在DL知识库。我们提出了初始的复杂性结果，显示查询回答是非小学在最坏的情况下，与指数级增加嵌套的传递闭包算子。
Regular path queries (RPQs) define query patterns in terms of regu-lar expressions and are therefore well-suited to query for paths over roles in DL. RPQs can be extended to 2-way RPQs (with converse), CRPQs (with conjunc-tions), or PRPQs (arbitrary positive Boolean combinations), all of which have been explored in DL research. Another natural extension of any query language is nesting, where query predicates can be defined in terms of subqueries. In this pa-per, we discuss several ways of introducing nesting to PRPQs, and show that they lead to increasingly expressive query languages: CN2RPQs, which were stud-ied in the context of DLs recently; nested P2RPQs; and positive queries with transitive closure on binary predicates. The latter is one of the most expressive languages for which query answering can still be decided over DL knowledge bases. We present initial complexity results that show query answering to be non-elementary in the worst case, with an exponential increase for each level of nest-ing of the transitive closure operator.