Logical foundations of relational data exchange
Logical foundations of relational data exchange
复制标题
关系数据交换的逻辑基础
DOI：
10.1145/1558334.1558341
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
P. Barceló
中科院分区：
文献类型：
--
作者：
P. Barceló
数据交换被定义为在源模式下获取结构化的数据并具体化尽可能准确地反映源数据的目标模式的实例的问题[19]。在过去的几年中，对数据交换应用程序的需求有所增加，特别是由于各种格式（关系，XML，RDF等）的Web数据的激增以及需要通信数据但仍保持自治的电子商务应用程序的出现。为了满足这一需求，最近建立了商业数据交换系统[12]。尽管数据交换是一个古老而常见的数据管理问题，但直到最近才对其最基本的方面进行了研究。原因有二。首先，早期对数据库的研究大多集中在独立的关系模型上，而对互操作性、集成和交换的研究很少。第二，数据交换问题没有坚实的基础，甚至没有适当的正式模型。2003年，Fagin、Kolaitis、米勒和Popa [19]最终提出了这样一个模型，并很快被采纳为数据交换的正确模型。关于该主题的调查已经出现在数据库理论的首要会议PODS上，[30]，并且已经举办了两个关于数据交换和集成的研讨会[10，39]。本次调查的组织如下。在第2节中，我们介绍了数据交换的基础知识。数据交换的目标之一是实现一个目标实例，该实例既与源数据一致，又与源和目标之间的关系规范一致。这样的目标实例称为给定源数据的解决方案。Fagin等人的工作。[19]确定了一类解，称为通用解，具有良好的数据交换特性。我们在第3节中介绍了泛解类。在第四节中，我们研究了普适解的具体化问题。特别是，我们表明，有一个有意义的类的数据交换设置的通用解决方案是保证存在的，如果一个解决方案存在，如果是这样的话，那么一个通用的解决方案总是可以在多项式时间内构造。在第四节中，我们还研究了泛解的核心，它恰好是最小的泛解。
Data exchange has been defined as the problem of taking data structured under a source schema and materializing an instance of a target schema that reflects as accurately as possible the source data [19]. In the last years, the need for data exchange applications has increased, particularly due to the proliferation of web data in various formats (relational, XML, RDF, etc) and the emergence of e-business applications that need to communicate data yet remain autonomous. Responding to this demand, commercial data exchange systems have been built recently [12]. Even though data exchange is an old and common data management problem, its most foundational aspects had not been studied until very recently. There are two reasons for this. First, most of the early research on databases concentrated on the stand-alone relational model, and much less on interoperability, integration, and exchange. Second, there were no solid foundation, nor even a proper formal model, for the problem of data exchange. Such a model was finally proposed in 2003 by Fagin, Kolaitis, Miller and Popa [19], and was quickly adopted as the right model for data exchange. A survey on the topic has already appeared in the premier conference on database theory, PODS, [30], and two workshops on exchange and integration of data have already been held [10, 39]. This survey is organized as follows. In Section 2, we present the basics of data exchange. One of the goals of data exchange is materializing a target instance that is consistent both with the source data and the specification of the relationship between the source and the target. Such a target instance is called a solution for the given source data. The work of Fagin et al. [19] identified a class of solutions, called universal solutions, with good properties for data exchange. We introduce the class of universal solutions in Section 3. In Section 4, we study the problem of the materialization of universal solutions. In particular, we show that there is a meaningful class of data exchange settings for which universal solutions are guaranteed to exist, if a solution exists at all, and, if that is the case, then a universal solution can always be constructed in polynomial time. Also in Section 4 we study the core of the universal solutions, which happens to be the smallest universal solution.
XML 模式映射
DOI：
10.1145/1559795.1559801
发表时间：
2009
期刊：
--
影响因子：
--
作者：
Amano S
通讯作者：
Amano S