Zhang, Zhi; Shi, Pengfei; Che, Haoyang; Gu, Jun An algebraic framework for schema matching. (English) Zbl 1160.68364 Informatica, Vilnius 19, No. 3, 421-446 (2008). Summary: It is well known that a formal framework for the schema matching problem (SMP) is important because it facilitates the building of algorithm models and the evaluation of algorithms. An algebraic framework for schema matching is developed in this paper. First, based on universal algebra, we propose a meta-meta structure for a schema, which is named multi-labeled schema. This definition has a distinctive feature: it is able to formally describe any particular style of schemas, and transforms a schema and other available information into a finite structure over specific signature. Later, we introduce a formal definition of schema matching that is called multivalent matching. Then, we formalize SMP as a schema homomorphism problem, and prove that SMP is equivalent to finding a semantic homomorphism from one schema to another. These results lead to the main contribution of this paper: an algebraic framework for SMP. This framework builds the algorithm model for SMP. Thirdly, we show a classification of schema matching based on the algebraic framework. Finally, we discuss the relations between matching cardinality and subclasses of schema homomorphism. MSC: 68P15 Database theory 08A70 Applications of universal algebra in computer science 68Q55 Semantics in the theory of computing 68W05 Nonnumerical algorithms Keywords:schema homomorphism; labeled graph matching; computational complexity Software:SEMINT PDFBibTeX XMLCite \textit{Z. Zhang} et al., Informatica, Vilnius 19, No. 3, 421--446 (2008; Zbl 1160.68364)