Conjunctive Query Containment under Access Limitations
Conjunctive Query Containment under Access Limitations
复制标题
访问限制下的联合查询包含
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
D. Martinenghi
中科院分区：
文献类型：
--
作者：
A. Calí;D. Martinenghi
访问限制可能发生在通过Web查询数据源或以关系表表示的异构数据源时：例如，在数据交换和集成、数据仓库和Web信息系统中会发生这种情况。访问限制强制选择某些属性才能访问表。众所周知，在这样的访问限制下评估合取查询相当于评估可能递归的数据库程序。我们解决的问题，检查约束条件下的连接查询，这是高度相关的查询优化。在这样的设置中检查包容性将相当于检查某个类的递归Datastrom程序的包容性，而对于一般的Datastrom程序，这个问题是不可判定的。我们提出了一个决策过程的基础上的新概念的crayfish-chase查询包容，包容性可以决定在co-nexptime，这提高了已知的2exptime的界限。此外，通过一个直接的证明，我们的技术提供了一个新的见解的结构问题。
Access limitations may occur when querying data sources over the web or heterogeneous data sources presented as relational tables: this happens, for instance, in Data Exchange and Integration, Data Warehousing, and Web Information Systems. Access limitations force certain attributes to be selected in order to access the tables. It is known that evaluating a conjunctive query under such access restrictions amounts to evaluating a possibly recursive Datalog program. We address the problem of checking containment of conjunctive queries under access limitations, which is highly relevant in query optimization. Checking containment in such a setting would amount to checking containment of recursive Datalog programs of a certain class, while, for general Datalog programs, this problem is undecidable. We propose a decision procedure for query containment based on the novel notion of crayfish-chase, showing that containment can be decided in co- nexptime , which improves upon the known bound of 2exptime . Moreover, by means of a direct proof, our technique provides a new insight into the structure of the problem.