Why is schema matching tough and what can we do about it?

Abstract

In this paper we analyze the problem of schema matching, explain why it is such a "tough" problem and suggest directions for handling it effectively. In particular, we present the monotonicity principle and see how it leads to the use of top-K mappings rather than a single mapping.

References

1. A. Anaby-Tavor. Enhancing the formal similarity based matching model. Master's thesis, Technion-Israel Institute of Technology, May 2003.]]
2. M. Benerecetti, P. Bouquet, and S. Zanobini. Soundness of schema matching methods. In Proceedings of ESWC 2005, pages 211--225, 2005.]]
3. T. Berners-Lee, J. Hendler, and O. Lassila. The semantic Web. Scientific American, May 2001.]]
4. P. A. Bernstein and S. Melnik. Meta data management. In Proceedings of the IEEE CS International Conference on Data Engineering. IEEE Computer Society, 2004.]]
5. A. Bilke and F. Naumann. Schema matching using duplicates. In Proceedings of the IEEE CS International Conference on Data Engineering, pages 69--80, 2005.]]
6. B. Convent. Unsolvable problems related to the view integration approach. In Proceedings of the International Conference on Database Theory (ICDT), Rome, Italy, September 1986. In Computer Science, Vol. 243, G. Goos and J. Hartmanis, Eds. Springer-Verlag, New York, pp. 141--156.]]
7. H. Do, S. Melnik, and E. Rahm. Comparison of schema matching evaluations. In Proceedings of the 2nd Int. Workshop on Web Databases (German Informatics Society), 2002., 2002.]]
8. H. H. Do and E. Rahm. COMA - a system for flexible combination of schema matching approaches. In Proceedings of the International conference on very Large Data Bases (VLDB), pages 610--621, 2002.]]
9. A. Gal. On the cardinality of schema matching. In IFIP WG 2.12 and WG 12.4 International Workshop on Web Semantics (SWWS), pages 947--956, 2005.]]
10. A. Gal. Managing uncertainty in schema matching with top-k schema mappings. Journal of Data Semantics, 6:90-114, 2006.]]
11. A. Gal, A. Anaby-Tavor, A. Trombetta, and D. Montesi. A framework for modeling and evaluating automatic semantic reconciliation. VLDB Journal, 14(1):50--67, 2005.]]
12. B. He and K. C.-C. Chang. Making holistic schema matching robust: an ensemble approach. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Illinois, USA, August 21--24, 2005, pages 429--438, 2005.]]
13. R. Hull. Managing semantic heterogeneity in databases: A theoretical perspective. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 51--61. ACM Press, 1997.]]
14. M. Lenzerini. Data integration is harder than you thought. In C. Batini, F. Giunchiglia, P. Giorgini, and M. Mecella, editors, Cooperative Information Systems, 9th International Conference, CoopIS 2001, Trento, Italy, September 5--7, 2001, Proceedings, volume 2172 of Lecture Notes in Computer Science, pages 22--26. Springer, 2001.]]
15. J. Madhavan, P. A. Bernstein, P. Domingos, and A. Y. Halevy. Representing and reasoning about mappings between domain models. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence (AAAI/IAAI), pages 80--86, 2002.]]
16. M. Magnani, N. Rizopoulos, P. McBrien, and D. Montesi. Schema integration based on uncertain semantic mappings. In ER, pages 31--46, 2005.]]
17. S. Melnik. Generic Model Management: Concepts and Algorithms. Springer-Verlag, 2004.]]
18. S. Melnik, H. Garcia-Molina, and E. Rahm. Similarity flooding: A versatile graph matching algorithm and its application to schema matching. In Proceedings of the IEEE CS International Conference on Data Engineering, pages 117--140, 2002.]]
19. R. J. Miller, L. M. Haas, and M. A. Hernández. Schema mapping as query discovery. In A. El Abbadi, M. L. Brodie, S. Chakravarthy, U. Dayal, N. Kamel, G. Schlageter, and K.-Y. Whang, editors, Proceedings of the International conference on very Large Data Bases (VLDB), pages 77--88. Morgan Kaufmann, 2000.]]
20. K. G. Murty. An algorithm for ranking all the assignments in order of increasing cost. Operations Research, 16:682--687, 1968.]]
21. E. Rahm and P. A. Bernstein. A survey of approaches to automatic schema matching. VLDB Journal, 10(4):334--350, 2001.]]
22. M. Sayyadian, Y. Lee, A. Doan, and A. Rosenthal. Tuning schema matching software using synthetic scenarios. In Proceedings of the International conference on very Large Data Bases (VLDB), pages 994--1005, 2005.]]
23. P. Shvaiko and J. Euzenat. A survey of schema-based matching approaches. Journal of Data Semantics, 4:146 -- 171, December 2005.]]
24. W. Su, J. Wang, and F. Lochovsky. Aholistic schema matching for web query interfaces. In Advances in Database Technology - EDBT 2006, 10th International Conference on Extending Database Technology, Munich, Germany, March 26--31, 2006, Proceedings, pages 77--94, 2006.]]

Index Terms

• Information systems

  • Data management systems

    • Database design and models