An instance-based approach for domain-independent schema matching

ABSTRACT

The process of schema matching lies at the heart of database applications related to data integration. Many instance-based solutions to the schema matching problem have been proposed. These approaches focus on analyzing the values of attributes especially within the application domain. The approach presented in this paper is a two-step domain-independent schema matching technique. The technique first measures shared information between pair-wise attributes using the concept of mutual information. Next, a graph representation with weighted links is constructed for each input schema. At this stage, schema matching switches to a weighted graph matching problem. At this stage, a graduated assignment algorithm is applied to find the correspondence of vertices between graphs. We perform experiments using two real-world data sets in different application domains to roughly evaluate the performance of this schema matching technique in terms of precision, recall and running time.

REFERENCES

• 1: Steven Gold , Anand Rangarajan, A Graduated Assignment Algorithm for Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.4, p.377-388, April 1996 [doi>10.1109/34.491619]
• 2: http://www.stat.ucla.edu
• 3: http://lib.stat.cmu.edu/datasets
• 4: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 5: Alexander Bilke , Felix Naumann, Schema Matching Using Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.69-80, April 05-08, 2005 [doi>10.1109/ICDE.2005.126]
• 6: Cecil Eng H. Chua , Roger H. L. Chiang , Ee-Peng Lim, Instance-based attribute identification in database integration, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.228-243, October 2003 [doi>10.1007/s00778-003-0088-y]
• 7: Jaewoo Kang , Jeffrey F. Naughton, On schema matching with opaque column names and data values, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872783]
• 8: AnHai Doan , Pedro Domingos , Alon Y. Halevy, Reconciling schemas of disparate data sources: a machine-learning approach, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.509-520, May 21-24, 2001, Santa Barbara, California, United States
• 9: Wen-Syan Li , Chris Clifton, SEMINT: a tool for identifying attribute correspondences in heterogeneous databases using neural networks, Data & Knowledge Engineering, v.33 n.1, p.49-84, April 2000 [doi>10.1016/S0169-023X(99)00044-0]
• 10: Jiying Wang , Ji-Rong Wen , Fred Lochovsky , Wei-Ying Ma, Instance-based schema matching for web databases by domain-specific query probing, Proceedings of the Thirtieth international conference on Very large data bases, p.408-419, August 31-September 03, 2004, Toronto, Canada
• 11: http://en.wikipedia.org/wiki/Mutual_information
• 12: Jayant Madhavan , Philip A. Bernstein , Erhard Rahm, Generic Schema Matching with Cupid, Proceedings of the 27th International Conference on Very Large Data Bases, p.49-58, September 11-14, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

Keywords:
graduated assignment algorithm, instance-based, mutual information, schema matching