Efficient schema matching algorithm based on pre‐checking
Kengo Kubo, Keizo Yamada, Kouichi Hirata, Masateru Harao · Systems and Computers in Japan · 2007
Abstract Matching, which is an operation that applies a substitution to one representation to make it identical to another representation, is indispensable for knowledge processing. In this paper, we formulate generalized knowledge, which is referred to as a schema, as a second‐order logical formula and discuss schema matching, which is a matching of that schema and a first‐order logical formula. First, we formulate the schema matching algorithm based on the imitation, projection, and unification operations of the second‐order matching algorithm. Generally, there is an exponential number of matching substitutions (or simply matchers) for schema matching. However, from a knowledge processing viewpoint, obtaining the optimum matcher is more important than obtaining all matchers. Therefore, in this paper, we introduce pre‐checking for checking the applicability of projection in advance to efficiently extract matchers that preserve the syntax information of the schema and design a complete schema matching algorithm. Finally, we implement this algorithm and use experimental results to show that efficiency is improved. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(4): 84–92, 2007; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/scj.10273