DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2016.19

Limits of Schema Mappings

Authors: Phokion G. Kolaitis, Reinhard Pichler, Emanuel Sallinger, and Vadim Savenkov

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract

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 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, i.e., schema mappings with infinite target instances as solutions to (finite) source instances.

Cite as

Phokion G. Kolaitis, Reinhard Pichler, Emanuel Sallinger, and Vadim Savenkov. Limits of Schema Mappings. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kolaitis_et_al:LIPIcs.ICDT.2016.19,
  author =	{Kolaitis, Phokion G. and Pichler, Reinhard and Sallinger, Emanuel and Savenkov, Vadim},
  title =	{{Limits of Schema Mappings}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.19},
  URN =		{urn:nbn:de:0030-drops-57882},
  doi =		{10.4230/LIPIcs.ICDT.2016.19},
  annote =	{Keywords: Limit, Pointwise convergence, Uniform convergence, Schema mapping}
}

Document

DOI: 10.4230/DFU.Vol5.10452.38

Algorithms for Core Computation in Data Exchange

Authors: Vadim Savenkov

Published in: Dagstuhl Follow-Ups, Volume 5, Data Exchange, Integration, and Streams (2013)

Abstract

We describe the state of the art in the area of core computation for data exchange. Two main approaches are considered: post-processing core computation, applied to a canonical universal solution constructed by chasing a given schema mapping, and direct core computation, where the mapping is first rewritten in order to create core universal solutions by chasing it.

Cite as

Vadim Savenkov. Algorithms for Core Computation in Data Exchange. In Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, Volume 5, pp. 39-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{savenkov:DFU.Vol5.10452.38,
  author =	{Savenkov, Vadim},
  title =	{{Algorithms for Core Computation in Data Exchange}},
  booktitle =	{Data Exchange, Integration, and Streams},
  pages =	{39--68},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-61-3},
  ISSN =	{1868-8977},
  year =	{2013},
  volume =	{5},
  editor =	{Kolaitis, Phokion G. and Lenzerini, Maurizio and Schweikardt, Nicole},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol5.10452.38},
  URN =		{urn:nbn:de:0030-drops-42896},
  doi =		{10.4230/DFU.Vol5.10452.38},
  annote =	{Keywords: Data integration, Data exchange, Core computation}
}

Search Results

Documents authored by Savenkov, Vadim

Limits of Schema Mappings

Abstract

Cite as

Algorithms for Core Computation in Data Exchange

Abstract

Cite as

Thanks for your feedback!

Could not send message