Efficiently ordering subgoals with access constraints
Efficiently ordering subgoals with access constraints
复制标题
通过访问限制有效地排序子目标
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
V. Chaudhri
中科院分区：
文献类型：
--
作者：
Guizhen Yang;M. Kifer;V. Chaudhri
在本文中，我们研究了作为非递归数据记录程序的查询在绑定模式限制下排序子目标的问题。我们证明，尽管它们的表达能力有限，但即使对于相当有限的情况，该问题在非递归数据记录程序的大小上也是计算困难的——PSPACE-完全的。作为该问题的实用解决方案，我们开发了一种渐近最优算法，该算法的运行时间与查询计划的大小呈线性关系。我们还研究了算法的扩展，可以在绑定模式限制下有效地解决其他查询规划问题。这些问题包括具有嵌套分组约束的联合查询、分布式联合查询和一阶查询。
In this paper, we study the problem of ordering subgoals under binding pattern restrictions for queries posed as nonrecursive Datalog programs. We prove that despite their limited expressive power, the problem is computationally hard—PSPACE-complete in the size of the nonrecursive Datalog program even for fairly restricted cases. As a practical solution to this problem, we develop an asymptotically optimal algorithm that runs in time linear in the size of the query plan. We also study extensions of our algorithm that efficiently solve other query planning problems under binding pattern restrictions. These problems include conjunctive queries with nested grouping constraints, distributed conjunctive queries, and first-order queries.