The recovery of a schema mapping: bringing exchanged data back
The recovery of a schema mapping: bringing exchanged data back
复制标题
模式映射的恢复：恢复交换的数据
DOI：
10.1145/1376916.1376920
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Cristian Riveros
中科院分区：
文献类型：
--
作者：
M. Arenas;Jorge Pérez;Cristian Riveros
模式映射是描述如何将来自源模式的数据映射到目标模式的规范。一旦数据从源传输到目标，一个自然的问题是是否可以撤消该过程并恢复初始数据，或者至少恢复其中的一部分。实际上，需要找到一个从目标到源的反向模式映射，指定如何将交换的数据带回来。在本文中，我们介绍了恢复模式映射的概念：它是一个反向映射M'的映射M恢复声音数据关于M。我们进一步介绍了一个顺序关系的恢复。这允许我们选择恢复最大数量的声音信息的映射。我们称这种映射为最大恢复。我们详细研究了最大回收率，提供了它们存在的充分必要条件。特别是，我们证明了最大的回收率存在的一类指定的FO到CQ源到目标的依赖关系的映射。这个类包含了在以前的数据交换工作中使用的源到目标元组生成依赖项类。对于由FO到CQ依赖关系指定的映射类，我们提供了一个指数时间算法来计算最大恢复率，并提供了一个简化版本，用于在二次时间内工作的完全依赖关系。我们还描述了表达最大回收率所需的语言，我们包括一个详细的比较与以前提出的数据交换文献中的逆（和准逆）映射的概念。特别是，我们证明了最大回收率严格广义逆。我们研究了一些决策问题的复杂性有关的恢复和最大恢复的概念。最后，我们报告我们的初步结果，一个宽松的概念，最大的恢复，表明它严格概括的概念，最大的恢复。
A schema mapping is a specification that describes how data from a source schema is to be mapped to a target schema. Once the data has been transferred from the source to the target, a natural question is whether one can undo the process and recover the initial data, or at least part of it. In fact, it would be desirable to find a reverse schema mapping from target to source that specifies how to bring the exchanged data back. In this paper, we introduce the notion of a recovery of a schema mapping: it is a reverse mapping M' for a mapping M that recovers sound data with respect to M. We further introduce an order relation on recoveries. This allows us to choose mappings that recover the maximum amount of sound information. We call such mappings maximum recoveries. We study maximum recoveries in detail, providing a necessary and sufficient condition for their existence. In particular, we prove that maximum recoveries exist for the class of mappings specified by FO-to-CQ source-to-target dependencies. This class subsumes the class of source-to-target tuple-generating dependencies used in previous work on data exchange. For the class of mappings specified by FO-to-CQ dependencies, we provide an exponential-time algorithm for computing maximum recoveries, and a simplified version for full dependencies that works in quadratic time. We also characterize the language needed to express maximum recoveries, and we include a detailed comparison with the notion of inverse (and quasi-inverse) mapping previously proposed in the data exchange literature. In particular, we show that maximum recoveries strictly generalize inverses. We study the complexity of some decision problems related to the notions of recovery and maximum recovery. Finally, we report our initial results about a relaxed notion of maximal recovery, showing that it strictly generalizes the notion of maximum recovery.
逻辑和数据交换：哪些解决方案是“好的”解决方案？
DOI：
10.1007/978-3-642-15164-4_4
发表时间：
2008
期刊：
影响因子：
--
作者：
André Hernich;Nicole Schweikardt
通讯作者：
Nicole Schweikardt