Limits of Schema Mappings

Kolaitis, Phokion and Pichler, Reinhard and Sallinger, Emanuel and Savenkov, Vadim (2018) Limits of Schema Mappings. Theory of Computing Systems, 62 (4). pp. 899-940. ISSN 1433-0490

Available under License Creative Commons: Attribution 4.0 International (CC BY 4.0).

Download (980kB)


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 interoperability 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 queries 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.

Item Type: Article
Additional Information: The research of Reinhard Pichler, Emanuel Sallinger, and Vadim Savenkov was supported by the Austrian Science Fund, projects (FWF):P25207-N23 and (FWF):Y698, and the Vienna Science and Technology Fund, project ICT12-015. The research of Phokion Kolaitis on this paper was partially supported by NSF Grant IIS-1217869. The full version was completed while Kolaitis was visiting the Simons Institute for the Theory of Computing during the fall of 2016. The research of Emanuel Sallinger was supported by the EPSRC programme grant EP/M025268/1.
Keywords: Schema mappings, Limits, Pointwise convergence, Uniform convergence
Divisions: Departments > Informationsverarbeitung u Prozessmanag. > Informationswirtschaft > Polleres
Version of the Document: Published
Depositing User: Gertraud Novotny
Date Deposited: 09 Nov 2018 12:15
Last Modified: 22 Aug 2020 15:50
Related URLs:


View Item View Item


Downloads per month over past year

View more statistics