Mapping polymorphism

ABSTRACT

We examine schema mappings from a type-theoretic perspective and aim to facilitate and formalize the reuse of mappings. Starting with the mapping language of Clio, we present a type-checking algorithm such that typable mappings are necessarily satisfiable. We add type variables to the schema language and present a theory of polymorphism, including a sound and complete type inference algorithm and a semantic notion of a principal type of a mapping. Principal types, which intuitively correspond to the minimum amount of schema structure required by the mappings, have an important application for mapping reuse. Concretely, we show that mappings can be reused, with the same semantics, on any schemas as long as these schemas are expansions (i.e., subtypes) of the principal types.

References

1. M. Arenas, J. Pérez, and C. Riveros. The Recovery of a Schema Mapping: Bringing Exchanged Data Back. In PODS, pages 13--22, 2008.
2. P. A. Bernstein. Applying Model Management to Classical Meta Data Problems. In CIDR, pages 209--220, 2003.
3. P. A. Bernstein, T. J. Green, S. Melnik, and A. Nash. Implementing Mapping Composition. In VLDB, pages 55--66, 2006.
4. P. A. Bernstein and S. Melnik. Model Management 2.0: Manipulating Richer Mappings. In SIGMOD, pages 1--12, 2007.
5. P. A. Bernstein, S. Melnik, and J. E. Churchill. Incremental Schema Matching. In VLDB (demo), pages 1167--1170, 2006.
6. V. Borkar, M. Carey, D. Engovatov, D. Lychagin, T. Westmann, and W. Wong. XQSE: An XQuery Scripting Extension for the AquaLogic Data Services Platform. In ICDE, pages 1307--1316, 2008.
7. J. V. den Bussche, D. V. Gucht, and S. Vansummeren. A crash course on database queries. In PODS, pages 143--154, 2007.
8. R. Fagin. Inverting schema mappings. ACM TODS, 32(4), 2007.
9. R. Fagin, L. M. Haas, M. A. Hernández, R. J. Miller, L. Popa, and Y. Velegrakis. Clio: Schema Mapping Creation and Data Exchange. In Conceptual Modeling: Foundations and Applications, Essays in Honor of John Mylopoulos, pages 198--236. Springer, 2009.
10. R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: semantics and query answering. Theor. Comput. Sci., 336(1):89--124, 2005.
11. R. Fagin, P. G. Kolaitis, L. Popa, and W. Tan. Composing Schema Mappings: Second-Order Dependencies to the Rescue. TODS, 30(4):994--1055, 2005.
12. J. N. Foster, B. C. Pierce, and A. Schmitt. A logic your typechecker can count on: Unordered tree types in practice. In PLAN-X, informal proceedings, Jan. 2007.
13. M. Friedman, A. Y. Levy, and T. D. Millstein. Navigational Plans For Data Integration. In AAAI/IAAI, pages 67--73, 1999.
14. A. Fuxman, M. A. Hernández, H. Ho, R. J. Miller, P. Papotti, and L. Popa. Nested Mappings: Schema Mapping Reloaded. In VLDB, pages 67--78, 2006.
15. A. Fuxman, M. A. Hernandez, H. Ho, R. J. Miller, P. Papotti, and L. Popa. Nested mappings: schema mapping reloaded. Technical Report CSRG-561, Department of Computer Science, University of Toronto, 2007.
16. V. Gapeyev, M. Y. Levin, B. C. Pierce, and A. Schmitt. The Xtatic experience. In PLAN-X, Jan. 2005. University of Pennsylvania Technical Report MS-CIS-04-24, Oct 2004.
17. B. R. Gaster and M. P. Jones. A polymorphic type system for extensible records and variants. Technical Report NOTTCS-TR-96-3, Department of Computer Science, University of Nottingham, November 1996.
18. M. Greenwald, J. Moore, B. Pierce, and A. Schmitt. A language for bi-directional tree transformations. Technical report, Department of Computer and Information Science, University of Pennsylvania., 2003.
19. L. M. Haas, M. A. Hernández, H. Ho, L. Popa, and M. Roth. Clio Grows Up: From Research Prototype to Industrial Tool. In SIGMOD, pages 805--810, 2005.
20. H. Hosoya and B. C. Pierce. Xduce: A statically typed xml processing language. ACM Trans. Inter. Tech., 3(2):117--148, 2003.
21. M. Lenzerini. Data Integration: A Theoretical Perspective. In PODS, pages 233--246, 2002.
22. J. Madhavan, P. A. Bernstein, A. Doan, and A. Y. Halevy. Corpus-based Schema Matching. In ICDE, pages 57--68, 2005.
23. J. Madhavan and A. Y. Halevy. Composing Mappings Among Data Sources. In VLDB, pages 572--583, 2003.
24. E. Meijer, B. Beckman, and G. M. Bierman. LINQ: reconciling object, relations and XML in the .NET framework. In SIGMOD, page 706, 2006.
25. R. J. Miller, L. M. Haas, and M. A. Hernández. Schema Mapping as Query Discovery. In VLDB, pages 77--88, 2000.
26. P. Papotti and R. Torlone. Schema exchange: Generic mappings for transforming data and metadata. Data Knowl. Eng., 68(7):665--682, 2009.
27. L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernández, and R. Fagin. Translating Web Data. In VLDB, pages 598--609, 2002.
28. J. van den Bussche and E. Waller. Type inference in the polymorphic relational algebra. In PODS, pages 80--90, 1999.
29. J. Vouillon. Polymorphic regular tree types and patterns. In POPL 06, pages 103--114, New York, NY, USA, 2006. ACM.
30. J. B. Wells. The essence of principal typings. In ICALP '02, pages 913--925, London, UK, 2002. Springer-Verlag.
31. R. Wisnesky. Mapping dependence. Technical Report TR-09-09, Harvard University Computer Science Group. Available at ftp://ftp.deas.harvard.edu/techreports/tr-09-09.pdf, 2009.
32. R. Wisnesky, M. A. Hernandez, and L. Popa. Mapping polymorphism - proofs. Technical Report TR-10-09, Harvard University Computer Science Group. Available at ftp://ftp.deas.harvard.edu/techreports/tr-10-09.pdf, 2009.

Index Terms

• Computer systems organization

  • Architectures

    • Other architectures

      • Heterogeneous (hybrid) systems

• Information systems

  • Data management systems

    • Database design and models

    • Database management system engines

    • Information integration

      • Extraction, transformation and loading

    • Query languages

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query languages (principles)