Kolaitis Phokion G, Pichler Reinhard, Sallinger Emanuel, Savenkov Vadim
1UC Santa Cruz and IBM Research-Almaden, Santa Cruz, CA USA.
2TU Wien, Wien, Austria.
Theory Comput Syst. 2018;62(4):899-940. doi: 10.1007/s00224-017-9812-7. Epub 2017 Oct 2.
Schema mappings have been extensively studied in the context of data exchange and data integration, where they have turned out to be the right level of abstraction for formalizing data inter-operability tasks. Up to now and for the most part, schema mappings have been studied as static objects, in the sense that each time the focus has been on a single schema mapping of interest or, in the case of composition, on a pair of schema mappings of interest. In this paper, we adopt a dynamic viewpoint and embark on a study of sequences of schema mappings and of the limiting behavior of such sequences. To this effect, we first introduce a natural notion of distance on sets of finite target instances that expresses how "close" two sets of target instances are as regards the certain answers of conjunctive que- ries on these sets. Using this notion of distance, we investigate pointwise limits and uniform limits of sequences of schema mappings, as well as the companion notions of pointwise Cauchy and uniformly Cauchy sequences of schema mappings. We obtain a number of results about the limits of sequences of GAV schema mappings and the limits of sequences of LAV schema mappings that reveal striking differences between these two classes of schema mappings. We also consider the completion of the metric space of sets of target instances and obtain concrete representations of limits of sequences of schema mappings in terms of generalized schema mappings, that is, schema mappings with infinite target instances as solutions to (finite) source instances.
模式映射在数据交换和数据集成的背景下已经得到了广泛研究，在这种情况下，它们已被证明是形式化数据互操作性任务的合适抽象层次。到目前为止，在很大程度上，模式映射一直被作为静态对象来研究，也就是说，每次关注的都是单个感兴趣的模式映射，或者在组合的情况下，关注的是一对感兴趣的模式映射。在本文中，我们采用动态观点，着手研究模式映射序列及其此类序列的极限行为。为此，我们首先在有限目标实例集上引入一种自然的距离概念，该概念表达了两组目标实例在关于这些集合上的合取查询的确定答案方面有多“接近”。利用这个距离概念，我们研究模式映射序列的逐点极限和一致极限，以及模式映射的逐点柯西序列和一致柯西序列的相关概念。我们得到了一些关于全局-局部（GAV）模式映射序列的极限和局部-全局（LAV）模式映射序列的极限的结果，这些结果揭示了这两类模式映射之间的显著差异。我们还考虑目标实例集的度量空间的完备化，并根据广义模式映射得到模式映射序列极限的具体表示，即具有无限目标实例作为（有限）源实例解的模式映射。
