Phokion G. Kolaitis
Reinhard Pichler
ABSTRACT
During the past decade, schema mappings have been extensively used in formalizing and studying such critical data interoperability tasks as data exchange and data integration. Much of the work has focused on GLAV mappings, i.e., schema mappings specified by source-to-target tuple-generating dependencies (s-t tgds), and on schema mappings specified by second-order tgds (SO tgds), which constitute the closure of GLAV mappings under composition. In addition, nested GLAV mappings have also been considered, i.e., schema mappings specified by nested tgds, which have expressive power intermediate between s-t tgds and SO tgds. Even though nested GLAV mappings have been used in data exchange systems, such as IBM's Clio, no systematic investigation of this class of schema mappings has been carried out so far. In this paper, we embark on such an investigation by focusing on the basic reasoning tasks, algorithmic problems, and structural properties of nested GLAV mappings. One of our main results is the decidability of the implication problem for nested tgds. We also analyze the structure of the core of universal solutions with respect to nested GLAV mappings and develop useful tools for telling apart SO tgds from nested tgds. By discovering deeper structural properties of nested GLAV mappings, we show that also the following problem is decidable: given a nested GLAV mapping, is it logically equivalent to a GLAV mapping?
- M. Arenas, P. Barceló, L. Libkin, and F. Murlak. Relational and XML Data Exchange. 2010. Google Scholar
Digital Library
- M. Arenas, J. Pérez, J. Reutter, and C. Riveros. The language of plain SO-tgds: Composition, inversion and structural properties. JCSS, 79(6):763 -- 784, 2013. Google ScholarDigital Library
- M. Arenas, J. Pérez, and C. Riveros. The recovery of a schema mapping: Bringing exchanged data back. ACM TODS, 34(4), 2009. Google ScholarDigital Library
- R. Fagin and P. G. Kolaitis. Local transformations and conjunctive-query equivalence. In PODS, pages 179--190, 2012. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. TCS, 336(1):89--124, 2005. Google Scholar
- R. Fagin, P. G. Kolaitis, A. Nash, and L. Popa. Towards a theory of schema-mapping optimization. In PODS, pages 33--42, 2008. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, and L. Popa. Data Exchange: Getting to the Core. ACM TODS, 30(1):174--210, 2005. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan. Composing schema mappings: Second-order dependencies to the rescue. ACM TODS, 30(4):994--1055, 2005. Google ScholarDigital Library
- I. Feinerer, R. Pichler, E. Sallinger, and V. Savenkov. On the undecidability of the equivalence of second-order tuple generating dependencies. In AMW, 2011.Google Scholar
- A. Fuxman, M. A. Hernández, C. T. H. Ho, R. J. Miller, P. Papotti, and L. Popa. Nested mappings: Schema mapping reloaded. In VLDB, pages 67--78, 2006. Google ScholarDigital Library
- P. Hell and J. Ne\vset\vril. The Core of a Graph. Discrete Mathematics, 109:117--126, 1992. Google ScholarDigital Library
- M. A. Hernández, H. Ho, L. Popa, A. Fuxman, R. J. Miller, T. Fukuda, and P. Papotti. Creating nested mappings with Clio. In ICDE, pages 1487--1488, 2007.Google ScholarCross Ref
- P. G. Kolaitis, M. Lenzerini, and N. Schweikardt, editors. Data Exchange, Integration, and Streams, volume 5 of Dagstuhl Follow-Ups. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013.Google Scholar
- M. Lenzerini. Data Integration: A Theoretical Perspective. In PODS, pages 233--246, 2002. Google ScholarDigital Library
- L. Libkin. Elements of Finite Model Theory. Springer, 2004. Google ScholarDigital Library
- J. Madhavan and A. Y. Halevy. Composing mappings among data sources. In VLDB, pages 572--583, 2003. Google ScholarDigital Library
- B. ten Cate and P. G. Kolaitis. Structural characterizations of schema-mapping languages. In ICDT, pages 63--72, 2009. Google ScholarDigital Library
Index Terms
- Nested dependencies: structure and reasoning
Recommendations
On the Language of Nested Tuple Generating Dependencies
Best of SIGMOD 2018, Best of PODS 2018 and Regular PapersDuring the past 15 years, schema mappings have been extensively used in formalizing and studying such critical data interoperability tasks as data exchange and data integration. Much of the work has focused on GLAV mappings, i.e., schema mappings ...
Characterizing schema mappings via data examples
PODS '10: Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsSchema mappings are high-level specifications that describe the relationship between two database schemas; they are considered to be the essential building blocks in data exchange and data integration, and have been the object of extensive research ...
Characterizing schema mappings via data examples
Schema mappings are high-level specifications that describe the relationship between two database schemas; they are considered to be the essential building blocks in data exchange and data integration, and have been the object of extensive research ...
Comments