Document Open Access Logo

Limits of Schema Mappings

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

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2016.19.pdf
  • Filesize: 0.53 MB
  • 17 pages

Document Identifiers

Author Details

Phokion G. Kolaitis
Reinhard Pichler
Emanuel Sallinger
Vadim Savenkov

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICDT.2016.19

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.

Subject Classification

Keywords
  • Limit
  • Pointwise convergence
  • Uniform convergence
  • Schema mapping

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Marcelo Arenas, Pablo Barceló, Leonid Libkin, and Filip Murlak. Foundations of Data Exchange. Cambridge University Press, 2014. Google Scholar
  2. Marcelo Arenas, Jorge Pérez, Juan Reutter, and Cristian Riveros. The language of plain SO-tgds: Composition, inversion and structural properties. Journal of Computer and System Sciences, 79(6):763-784, 2013. URL: http://dx.doi.org/10.1016/j.jcss.2013.01.002.
  3. Philip A. Bernstein. Applying model management to classical meta data problems. In CIDR, 2003. Google Scholar
  4. Ronald Fagin. Probabilities on finite models. J. Symb. Log., 41(1):50-58, 1976. Google Scholar
  5. Ronald Fagin and Phokion G. Kolaitis. Local transformations and conjunctive-query equivalence. In PODS, pages 179-190, 2012. URL: http://dx.doi.org/10.1145/2213556.2213583.
  6. Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: Semantics and query answering. Theor. Comput. Sci., 336(1):89-124, May 2005. Google Scholar
  7. Ronald Fagin, Phokion G. Kolaitis, Alan Nash, and Lucian Popa. Towards a theory of schema-mapping optimization. In PODS, pages 33-42, 2008. URL: http://dx.doi.org/10.1145/1376916.1376922.
  8. Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang Chiew Tan. Composing schema mappings: Second-order dependencies to the rescue. ACM Trans. Database Syst., 30(4):994-1055, 2005. Google Scholar
  9. Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang Chiew Tan. Schema mapping evolution through composition and inversion. In Schema Matching and Mapping, pages 191-222. Springer, 2011. Google Scholar
  10. Ingo Feinerer, Reinhard Pichler, Emanuel Sallinger, and Vadim Savenkov. On the undecidability of the equivalence of second-order tuple generating dependencies. Inf. Syst., 48:113-129, 2015. URL: http://dx.doi.org/10.1016/j.is.2014.09.003.
  11. Phokion G. Kolaitis. Schema mappings, data exchange, and metadata management. In PODS, pages 61-75, 2005. Google Scholar
  12. Maurizio Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233-246, 2002. Google Scholar
  13. László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012. Google Scholar
  14. Jayant Madhavan and Alon Y. Halevy. Composing mappings among data sources. In VLDB, pages 572-583, 2003. URL: http://www.vldb.org/conf/2003/papers/S18P01.pdf.
  15. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27875-4.
  16. Jaroslav Nešetřil and Patrice Ossona de Mendez. A unified approach to structural limits, and limits of graphs with bounded tree-depth. arXiv:1303.6471, 2013. Google Scholar
  17. Jean-Eric Pin. Profinite methods in automata theory. In STACS, pages 31-50, 2009. Google Scholar
  18. Satish Shirali and Harkrishan Vasudeva. Metric spaces. Springer, 2006. Google Scholar
  19. Balder ten Cate and Phokion G. Kolaitis. Structural characterizations of schema-mapping languages. In ICDT, pages 63-72, 2009. URL: http://dx.doi.org/10.1145/1514894.1514903.
  20. Szymon Torunczyk. Languages of profinite words and the limitedness problem. In ICALP, pages 377-389, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact