Schema Matching Based on Labeled Graph

Schema matching is a critical problem for achieving semantic interoperability between heterogeneous information sources, and plays a key role in database applications. The aim of schema matching problem (SMP) is to find semantic correspondences between two schemas and indeed a combinatorial problem. In this paper, we use the labeled graph as the internal schema model, so SMP can be formulized as a semantic homomorphism from a labeled graph to another. Moreover, the homomorphism problem is equivalent to the constraint satisfaction problem (CSP) and H-coloring problem, so SMP can be reformulated, and an example is followed to show this process.