Data exchange and incomplete information
Data exchange and incomplete information
复制标题
数据交换和不完整信息
DOI：
10.1145/1142351.1142360
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
L. Libkin
中科院分区：
文献类型：
--
作者：
L. Libkin
数据交换的问题是，给定源模式的实例和源与目标之间关系的规范，找到目标模式的实例，并以与源中的信息在语义上一致的方式回答对目标实例的查询。近年来，数据交换的理论基础得到了积极的探索。还注意到标准的某些答案语义可能以非常奇怪的方式表现。在本文中，我解释了这种行为是由于目标实例中不完全信息的存在被忽略了；特别是，没有为带有null的数据库使用适当的查询评估技术，也没有对封闭世界和开放世界语义进行区分。在封闭世界假设的基础上，提出了目标解的概念，并证明了所有解的空间有两个极值点：规范通用解和核心，这在数据交换中得到了很好的研究。我将展示如何定义考虑不完整信息的查询回答的语义，并展示众所周知的异常与新语义一起消失。本文还包含查询回答的复杂性，查询（可能-答案）的上近似值和各种扩展的结果。
Data exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target, and answering queries over target instances in a way that is semantically consistent with the information in the source. Theoretical foundations of data exchange have been actively explored recently. It was also noticed that the standard certain answers semantics may behave in very odd ways.In this paper I explain that this behavior is due to the fact that the presence of incomplete information in target instances has been ignored; in particular, proper query evaluation techniques for databases with nulls have not been used, and the distinction between closed and open world semantics has not been made. I present a concept of target solutions based on the closed world assumption, and show that the space of all solutions has two extreme points: the canonical universal solution and the core, well studied in data exchange. I show how to define semantics of query answering taking into account incomplete information, and show that the well-known anomalies go away with the new semantics. The paper also contains results on the complexity of query answering, upper approximations to queries (maybe-answers), and various extensions.