Data exchange and schema mappings in open and closed worlds
Data exchange and schema mappings in open and closed worlds
复制标题
开放和封闭世界中的数据交换和模式映射
DOI：
10.1145/1376916.1376937
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Cristina Sirangelo
中科院分区：
文献类型：
--
作者：
L. Libkin;Cristina Sirangelo
在数据交换的研究中，人们通常假设一个开放世界的语义，使得扩展目标模式的实例成为可能。另一种封闭世界语义仅将“所需的数据”从源移动到目标，以满足模式映射的约束。它避免了开放世界语义所表现出的一些问题，但限制了模式映射的表达能力。在这里，我们提出了一个混合的方法：一个可以指定不同的属性的目标模式为开放或封闭，联合收割机结合的开放世界语义的额外的表达能力与更好的行为，在封闭的世界查询回答。我们定义这样的模式映射，并表明，它们涵盖了一个大的空间的数据交换解决方案，两个极端是已知的开放和封闭世界的语义。研究了查询应答和模式映射合成问题，证明了两个可分性定理，并根据开放属性的个数对它们的复杂性进行了分类。我们发现的条件下，模式映射组成，扩展已知的结果，以广泛的封闭世界映射。我们还提供了限制类的查询和映射保证较低的复杂性的结果。
In the study of data exchange one usually assumes an open-world semantics, making it possible to extend instances of target schemas. An alternative closed-world semantics only moves 'as much data as needed' from the source to the target to satisfy constraints of a schema mapping. It avoids some of the problems exhibited by the open-world semantics, but limits the expressivity of schema mappings. Here we propose a mixed approach: one can designate different attributes of target schemas as open or closed, to combine the additional expressivity of the open-world semantics with the better behavior of query answering in closed worlds. We define such schema mappings, and show that they cover a large space of data exchange solutions with two extremes being the known open and closed-world semantics. We investigate the problems of query answering and schema mapping composition, and prove two trichotomy theorems, classifying their complexity based on the number of open attributes. We find conditions under which schema mappings compose, extending known results to a wide range of closed-world mappings. We also provide results for restricted classes of queries and mappings guaranteeing lower complexity.