模式匹配问题的描述框架与算法模型<sup>*</sup>

Abstract
Figure/Table
References
Related Citation (8)

Download: PDF (349 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

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.

Key words： Schema Matching Homomorphism Schema Homomorphism

Received: 18 July 2005

ZTFLH:

TP301

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	ZHANG Zhi
	CHE HaoYang
	SHI PengFei

Cite this article:

ZHANG Zhi,CHE HaoYang,SHI PengFei. Framework and Algorithm Model of Schema Matching Problem[J]. , 2006, 19(6): 715-721.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/ OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2006/V19/I6/715

[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