<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.0 20120330//EN" "JATS-journalpublishing1.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" article-type="research-article">
	<front>
		<journal-meta>
			<journal-id journal-id-type="publisher-id">INFORMATICA</journal-id>
			<journal-title-group>
				<journal-title>Informatica</journal-title>
			</journal-title-group>
			<issn pub-type="epub">0868-4952</issn>
			<issn pub-type="ppub">0868-4952</issn>
			<publisher>
				<publisher-name>VU</publisher-name>
			</publisher>
		</journal-meta>
		<article-meta>
			<article-id pub-id-type="publisher-id">inf19307</article-id>
			<article-id pub-id-type="doi">10.15388/Informatica.2008.222</article-id>
			<article-categories>
				<subj-group subj-group-type="heading">
					<subject>Research article</subject>
				</subj-group>
			</article-categories>
			<title-group>
				<article-title>An Algebraic Framework for Schema Matching</article-title>
			</title-group>
			<contrib-group>
				<contrib contrib-type="Author">
					<name>
						<surname>Zhang</surname>
						<given-names>Zhi</given-names>
					</name>
					<xref ref-type="aff" rid="j_INFORMATICA_aff_000"/>
				</contrib>
				<contrib contrib-type="Author">
					<name>
						<surname>Shi</surname>
						<given-names>Pengfei</given-names>
					</name>
					<xref ref-type="aff" rid="j_INFORMATICA_aff_000"/>
				</contrib>
				<contrib contrib-type="Author">
					<name>
						<surname>Che</surname>
						<given-names>Haoyang</given-names>
					</name>
					<email xlink:href="mailto:chehy@hotmail.com">chehy@hotmail.com</email>
					<xref ref-type="aff" rid="j_INFORMATICA_aff_001"/>
				</contrib>
				<contrib contrib-type="Author">
					<name>
						<surname>Gu</surname>
						<given-names>Jun</given-names>
					</name>
					<xref ref-type="aff" rid="j_INFORMATICA_aff_001"/>
				</contrib>
				<aff id="j_INFORMATICA_aff_000">Institute of Image Processing and Pattern Recognition, Shanghai Jiaotong University SAP Labs China, Shanghai 200030, China, e-mail: uphenix@hotmail.com</aff>
				<aff id="j_INFORMATICA_aff_001">Institute of Software, The Chinese Academy of Sciences Beijing 100080, China</aff>
			</contrib-group>
			<pub-date pub-type="epub">
				<day>01</day>
				<month>01</month>
				<year>2008</year>
			</pub-date>
			<volume>19</volume>
			<issue>3</issue>
			<fpage>421</fpage>
			<lpage>446</lpage>
			<history>
				<date date-type="received">
					<day>01</day>
					<month>03</month>
					<year>2006</year>
				</date>
				<date date-type="accepted">
					<day>01</day>
					<month>02</month>
					<year>2008</year>
				</date>
			</history>
			<abstract>
				<p>It is well known that a formal framework for the schema matching problem (SMP) is important because it facilitates the building of algorithm model 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 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 formulize 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.</p>
			</abstract>
			<kwd-group>
				<label>Keywords</label>
				<kwd>schema matching</kwd>
				<kwd>schema homomorphism</kwd>
				<kwd>schema isomorphism</kwd>
				<kwd>graph homomorphism</kwd>
				<kwd>labeled graph matching</kwd>
				<kwd>computation complexity</kwd>
			</kwd-group>
		</article-meta>
	</front>
</article>