On schema matching with opaque column names and data values

ABSTRACT

Most previous solutions to the schema matching problem rely in some fashion upon identifying "similar" column names in the schemas to be matched, or by recognizing common domains in the data stored in the schemas. While each of these approaches is valuable in many cases, they are not infallible, and there exist instances of the schema matching problem for which they do not even apply. Such problem instances typically arise when the column names in the schemas and the data in the columns are "opaque" or very difficult to interpret. In this paper we propose a two-step technique that works even in the presence of opaque column names and data values. In the first step, we measure the pair-wise attribute correlations in the tables to be matched and construct a dependency graph using mutual information as a measure of the dependency between attributes. In the second stage, we find matching node pairs in the dependency graphs by running a graph matching algorithm. We validate our approach with an experimental study, the results of which suggest that such an approach can be a useful addition to a set of (semi) automatic schema matching techniques.

REFERENCES

• 1: Domenico Beneventano , Sonia Bergamaschi , Silvana Castano , Alberto Corni , R. Guidetti , G. Malvezzi , Michele Melchiori , Maurizio Vincini, Information Integration: The MOMIS Project Demonstration, Proceedings of the 26th International Conference on Very Large Data Bases, p.611-614, September 10-14, 2000
• 2: Jacob Berlin , Amihai Motro, Database Schema Matching Using Machine Learning with Feature Selection, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.452-466, May 27-31, 2002
• 3: Phillip A. Bernstein , Alon Y. Halevy , Rachel A. Pottinger, A vision for management of complex models, ACM SIGMOD Record, v.29 n.4, p.55-63, Dec. 2000 [doi>10.1145/369275.369289]
• 4: Silvana Castano , Valeria De Antonellis , Sabrina De Capitani di Vimercati, Global Viewing of Heterogeneous Data Sources, IEEE Transactions on Knowledge and Data Engineering, v.13 n.2, p.277-297, March 2001 [doi>10.1109/69.917566]
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: 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
• 7: AnHai Doan, Pedro Domingos, Alon Y. Levy: Learning Source Description for Data Integration. WebDB (Informal Proceedings) 2000: 81--86
• 8: Nir Friedman, Iftach Nachman, Dana Peer: Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm. UAI 1999: 206--215
• 9: 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]
• 10: Lise Getoor , Benjamin Taskar , Daphne Koller, Selectivity estimation using probabilistic models, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.461-472, May 21-24, 2001, Santa Barbara, California, United States
• 11: D. Heckerman. A tutorial on learning with Bayesian networks. Technical Report MSR-TR-95-06, Microsoft Research, March, 1995 (revised November, 1996)
• 12: Mauricio A. Hernández , Renée J. Miller , Laura M. Haas, Clio: a semi-automatic tool for schema mapping, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.607, May 21-24, 2001, Santa Barbara, California, United States
• 13: 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]
• 14: Wen-Syan Li , Chris Clifton, Semantic Integration in Heterogeneous Databases Using Neural Networks, Proceedings of the 20th International Conference on Very Large Data Bases, p.1-12, September 12-15, 1994
• 15: 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
• 16: Sergey Melnik, Hector Garcia-Molina, Erhard Rahm: Similarity Flooding: A Versatile Graph Matching Algorithm. ICDE 2002
• 17: Renée J. Miller , Laura M. Haas , Mauricio A. Hernández, Schema Mapping as Query Discovery, Proceedings of the 26th International Conference on Very Large Data Bases, p.77-88, September 10-14, 2000
• 18: Tova Milo , Sagit Zohar, Using Schema Matching to Simplify Heterogeneous Data Translation, Proceedings of the 24rd International Conference on Very Large Data Bases, p.122-133, August 24-27, 1998
• 19: PKDD 2001 Discovery Challenge on Thrombosis Data. http://lisp.vse.cz/challenge/pkdd2001/
• 20: 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]
• 21: Triada, Ltd. http://www.triada.com/
• 22: U.S. Census Bureau. Census data file ftp site. ftp://ftp2.census.gov/census_2000/datasets/
• 23: Ling Ling Yan , Renée J. Miller , Laura M. Haas , Ronald Fagin, Data-driven understanding and refinement of schema mappings, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.485-496, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Algorithms, Design, Theory