Skip to main content
SpringerLink
Log in

Implementing mapping composition

  • Special Issue Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

Mapping composition is a fundamental operation in metadata driven applications. Given a mapping over schemas σ1 and σ2 and a mapping over schemas σ2 and σ3, the composition problem is to compute an equivalent mapping over σ1 and σ3. We describe a new composition algorithm that targets practical applications. It incorporates view unfolding. It eliminates as many σ2 symbols as possible, even if not all can be eliminated. It covers constraints expressed using arbitrary monotone relational operators and, to a lesser extent, non-monotone operators. And it introduces the new technique of left composition. We describe our implementation, explain how to extend it to support user-defined operators, and present experimental results which validate its effectiveness.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bernstein, P.A.: Applying model management to classical meta-data problems. In: CIDR (2003)

  2. Bernstein P.A., Halevy A.Y. and Pottinger R. (2006). A vision of management of complex models. SIGMOD Record 29(4): 55–63

    Article  Google Scholar 

  3. Buneman, P., Davidson, S.B., Kosky, A.: Theoretical aspects of schema merging. In: Proc. EDBT, pp. 152–167 (1992)

  4. Fagin R., Kolaitis P.G., Popa L. and Tan W.C. (2005). Composing schema mappings: second-order dependencies to the rescue. ACM TODS 30(4): 994–1055

    Article  Google Scholar 

  5. Madhavan, J., Halevy, A.Y.: Composing mappings among data sources In: Proc. VLDB, pp. 572–583 (2003)

  6. Melnik, S., Bernstein, P.A., Halevy, A., Rahm, E.: Supporting Executable Mappings in model management. In: Proc. ACM SIGMOD (2005)

  7. Nash, A., Bernstein, P.A., Melnik, S.: Composition of mappings given by embedded dependencies. ACM TODS 32(1) (2007)

  8. Pottinger, R., Bernstein, P.A.: Merging models based on given correspondences. In: Proc. VLDB, pp. 826–873 (2003)

  9. Stonebraker, M.: Implementation of integrity constraints and views by query Modification. In: Proc. ACM SIGMOD, pp. 65–78 (1975)

  10. Tatarinov, I., Halevy, A.Y.: Efficient query reformulation in peer-data management systems. In: Proc. ACM SIGMOD (2004)

  11. Taylor, N., Ives, Z.: Reconciling changes while tolerating disagreement in collaborative data sharing. In: Proc. ACM SIGMOD (2006)

  12. Yannakakis M., (1982). Papadimitriou, C.H.: Algebraic dependencies. J. Comput. System. Sci. 25(1): 2–41

    Article  MATH  MathSciNet  Google Scholar 

  13. Yu, C., Popa, L.: Semantic adaptation of schema mappings when schemas evolve. In: Proc. VLDB, pp. 1006–1017 (2005)

Download references

Author information

Authors and Affiliations

  1. Microsoft Research, Redmond, WA, USA

    Philip A. Bernstein & Sergey Melnik

  2. University of Pennsylvania, Philadelphia, PA, USA

    Todd J. Green

  3. IBM Almaden Research Center, San Jose, CA, USA

    Alan Nash

Authors
  1. Philip A. Bernstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Todd J. Green
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sergey Melnik
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Alan Nash
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Philip A. Bernstein.

Additional information

T.J. Green and A. Nash’s work was performed during an internship at Microsoft Research.

A preliminary version of this work was published in the VLDB 2006 conference proceedings.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bernstein, P.A., Green, T.J., Melnik, S. et al. Implementing mapping composition. The VLDB Journal 17, 333–353 (2008). https://doi.org/10.1007/s00778-007-0059-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-007-0059-9

Keywords

Search

Navigation