Query planning with limited source capabilities
Query planning with limited source capabilities
复制标题
源能力有限的查询规划
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
E. Chang
中科院分区：
文献类型：
--
作者：
Chen Li;E. Chang
在信息集成系统中，信息源可能具有多样化且有限的查询能力。我们表明，由于源在检索其信息方面有限制，因此查询中未提及的源可以通过提供有用的绑定来影响查询结果。在某些情况下，我们可以重复访问源以检索绑定来回答查询，因此查询规划变得非常具有挑战性。我们通过将查询和源描述转换成一个简单的递归Datalog程序，并根据源关系对该程序进行评估，找到对查询的所有可获得的答案。该程序经常访问不在查询中的源。其中一些访问是必不可少的，因为它们提供了允许我们查询源的绑定，否则我们无法做到这一点。但是，可以证明其中一些访问不会给查询结果增加任何内容。我们展示了在哪些情况下这些查询外访问是无用的，并证明了在这些情况下，我们可以通过仅使用查询中的源来计算查询的完整答案。在需要查询外访问的情况下，我们提出了一种查找一个查询的所有有用源的算法。因此，我们解决了消除不必要的源访问的优化问题，并优化了程序以回答查询。
In information-integration systems, sources may have diverse and limited query capabilities. We show that because sources have restrictions on retrieving their information, sources not mentioned in a query can contribute to the query result by providing useful bindings. In some cases we can access sources repeatedly to retrieve bindings to answer a query, and query planning thus becomes considerably more challenging. We find all the obtainable answers to a query by translating the query and source descriptions to a simple recursive Datalog program, and evaluating the program on the source relations. This program often accesses sources that are not in the query. Some of these accesses are essential, as they provide bindings that let us query sources, which we could not do otherwise. However, some of these accesses can be proven not to add anything to the query's answer. We show in which cases these off-query accesses are useless, and prove that in these cases we can compute the complete answer to the query by using only the sources in the query. In the cases where off-query accesses are necessary, we propose an algorithm for finding all the useful sources for a query. We thus solve the optimization problem of eliminating the unnecessary source accesses, and optimize the program to answer the query.