Answering aggregate queries in data exchange
Answering aggregate queries in data exchange
复制标题
回答数据交换中的聚合查询
DOI：
10.1145/1376916.1376936
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Phokion G. Kolaitis
中科院分区：
文献类型：
--
作者：
F. Afrati;Phokion G. Kolaitis
数据交换，也称为数据转换，近年来得到了广泛的研究。一个主要的研究方向集中在语义和在关系模式之间的数据交换上下文中回答一阶查询的复杂性。在本文中，我们对数据交换中聚合查询的语义和复杂性进行了系统的研究，并做出了一些概念和技术上的贡献。数据交换是产生不完整信息的环境，因此必须处理一组可能的世界，而不是单个数据库。在对数据交换中一阶查询的特定答案的研究中，探索了三种不同的可能世界集：所有解的可能世界集、所有全称解的可能世界集和由cwa -解派生的可能世界集。我们检查了这些集合中的每一个，并指出它们都不适合用于数据交换中的聚合，因为每个集合都会产生相当琐碎的语义。我们的分析还表明，为了在数据交换中具有有意义的聚合语义，在选择可能世界集时必须采用严格的封闭世界假设。为此，我们引入并研究了正则全解的自同态象集作为数据交换中聚合的可能世界集。我们的主要技术结果是，对于由源到目标tgds指定的模式映射，存在多项式时间算法来计算每个标量聚合查询的范围语义，其中聚合查询的范围语义是查询接管可能世界集合的值的最大下界和最小上界。在这些算法中，较为复杂的是平均算子算法，它利用了最初在研究数据交换通用解核心时引入的概念。我们还证明，如果我们不考虑范围语义，而是考虑可能的答案语义，那么判断一个数字是否是具有平均运算符的给定标量聚合查询的可能答案是一个np完全问题。
Data exchange, also known as data translation, has been extensively investigated in recent years. One main direction of research has focused on the semantics and the complexity of answering first-order queries in the context of data exchange between relational schemas. In this paper, we initiate a systematic investigation of the semantics and the complexity of aggregate queries in data exchange, and make a number of conceptual and technical contributions. Data exchange is a context in which incomplete information arises, hence one has to cope with a set of possible worlds, instead of a single database. Three different sets of possible worlds have been explored in the study of the certain answers of first-order queries in data exchange: the set of possible worlds of all solutions, the set of possible worlds of all universal solutions, and a set of possible worlds derived from the CWA-solutions. We examine each of these sets and point out that none of them is suitable for aggregation in data exchange, as each gives rise to rather trivial semantics. Our analysis also reveals that, to have meaningful semantics for aggregation in data exchange, a strict closed world assumption has to be adopted in selecting the set of possible worlds. For this, we introduce and study the set of the endomorphic images of the canonical universal solution as a set of possible worlds for aggregation in data exchange. Our main technical result is that for schema mappings specified by source-to-target tgds, there are polynomial-time algorithms for computing the range semantics of every scalar aggregation query, where the range semantics of an aggregate query is the greatest lower bound and the least upper bound of the values that the query takes over the set of possible worlds. Among these algorithms, the more sophisticated one is the algorithm for the average operator, which makes use of concepts originally introduced in the study of the core of the universal solutions in data exchange. We also show that if, instead of range semantics, we consider possible answer semantics, then it is an NP-complete problem to tell if a number is a possible answer of a given scalar aggregation query with the average operator.