Framework and Algorithm Model of Schema Matching Problem
ZHANG Zhi1, CHE HaoYang2, SHI PengFei1
1.Institute of Image Processing and Pattern Recognition, Shanghai Jiaotong University, Shanghai 200030 2.Institute of Software, Chinese Academy of Sciences, Beijing 100080
Abstract In this paper, an algebraic framework for Schema Matching Problem (SMP) is built. By using universal algebra, the mathematical foundations of SMP is studied. A SMP instance can be viewed as a pair of structures (algebras), then the solutions to the problem are the structure preserving mappings between these two finite structures, i.e. schema matching can be formulized as finding the homomorphism between two structures. It is proved that the schema homomorphism (SHOM) is equivalent to the SMP, and the SMP can be reduced to the homomorphism between two finite structures. Based on this framework, the algorithmic model of SMP is presented.
[1] Rahm E, Bernstein P A. A Survey of Approaches to Automatic Schema Matching. The International Journal on Very Large Data Bases, 2001, 10(4): 334-350 [2] Batini C, Lenzerini M, Navathe S B. A Comparative Analysis of Methodologies for Database Schema Integration. ACM Computing Surveys, 1986, 18(4): 323-364 [3] Do H H, Melnik S, Rahm E. Comparison of Schema Matching Evaluations // Chaudhri A B, Jeckle M, Rahm E, et al, eds. Lecture Notes in Computer Science. London, UK: Springer-Verlag, 2002, 2593: 221-237 [4] Do H H, Rahm E. COMA-A System for Flexible Combination of Schema Matching Approaches // Proc of the 28th International Conference on Very Large Databases. Hongkong, China, 2002: 610-621 [5] Bernstein P A. Generic Model Management: A Database Infrastructure for Schema Manipulation // Batini C, Giunchiglia F, Giorgini P, eds. Lecture Notes in Computer Science. Heidelberg, Germany: Springer, 2001, 2172: 1-6 [6] Doan A, Domingos P, Halevy A. Learning to Match the Schemata of Data Sources: A Multistrategy Approach. Machine Learning, 2003, 50(3): 279-301 [7] Hell P. Algorithmic Aspects of Graph Homomorphisms // Wensley C D, ed. London Mathematical Society Lecture Note Series. Cambridge, UK: Cambridge University Press, 2003: 239-276 [8] Federa T, Madelaineb F, Stewartc I A. Dichotomies for Classes of Homomorphism Problems Involving Unary Functions. Theoretical Computer Science, 2004, 314(1): 1-43 [9] Burris S N, Sankappanavar H P. A Course in Universal Algebra (Graduate Texts in Mathematics). New York, USA: Springer-Verlag, 1981 [10] Dubhashi D P. Complexity of Logical Theories [EB/OL]. [1995-06-01]. http://www.brics.dk/LS/95/BRICS-LS-95.bib [11] Melnik S. Generic Model Management: Concepts and Algorithms. Ph.D Dissertation. Leipzig, Germany: University of Leipzig. College of Computer Science, 2004 [12] Madhavan J, Bernstein P A, Rahm E. Generic Schema Matching with Cupid // Apers P M, Atzeni P, et al, eds. Proc of the 27th International Conference on Very Large Data Bases. Roma, Italy, 2001: 49-58
2006, Vol. 19 
