Mining database structure; or, how to build a data quality browser

ABSTRACT

Data mining research typically assumes that the data to be analyzed has been identified, gathered, cleaned, and processed into a convenient form. While data mining tools greatly enhance the ability of the analyst to make data-driven discoveries, most of the time spent in performing an analysis is spent in data identification, gathering, cleaning and processing the data. Similarly, schema mapping tools have been developed to help automate the task of using legacy or federated data sources for a new purpose, but assume that the structure of the data sources is well understood. However the data sets to be federated may come from dozens of databases containing thousands of tables and tens of thousands of fields, with little reliable documentation about primary keys or foreign keys.We are developing a system, Bellman, which performs data mining on the structure of the database. In this paper, we present techniques for quickly identifying which fields have similar values, identifying join paths, estimating join directions and sizes, and identifying structures in the database. The results of the database structure mining allow the analyst to make sense of the database content. This information can be used to e.g., prepare data for data mining, find foreign key joins for schema mapping, or identify steps to be taken to prevent the database from collapsing under the weight of its complexity.

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
• 2: Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303978]
• 3: C. Batini , M. Lenzerini , S. B. Navathe, A comparative analysis of methodologies for database schema integration, ACM Computing Surveys (CSUR), v.18 n.4, p.323-364, Dec. 1986 [doi>10.1145/27633.27634]
• 4: Dina Bitton , Jeffrey Millman , Solveig Torgersen, A Feasibility and Performance Study of Dependency Inference, Proceedings of the Fifth International Conference on Data Engineering, p.635-641, February 06-10, 1989
• 5: V. Borkar, K. Deshmukh, and S. Sarawagi. Automatically extracting structure from free text addresses. Data Engineering Bulletin, 23(4):27-32, 2000.
• 6: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 7: Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335225]
• 8: C. Clifton, E. Housman, and A. Rosenthal. Experience with a combined approach to attribute-matching across heterogeneous databases. In IEEE Workshop on Data Semantics, 1997.
• 9: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 10: 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
• 11: A. Doan, P. Domingos, and A. Levy. Learning source description for data integration. In Proc. Intl. Workshop on The Web and Databases, 2000.
• 12: Evoke Software. http://www.evokesoftware.com/.
• 13: Evoke Software. Data profiling and mapping, the essential first step in data migration and integration projects. http://www.evokesoftware.com/pdf/wtpprDPM.pdf, 2000.
• 14: Helena Galhardas , Daniela Florescu , Dennis Shasha , Eric Simon, AJAX: an extensible data cleaning tool, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.590, May 15-18, 2000, Dallas, Texas, United States
• 15: Sumit Ganguly , Phillip B. Gibbons , Yossi Matias , Avi Silberschatz, Bifocal sampling for skew-resistant join size estimation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.271-281, June 04-06, 1996, Montreal, Quebec, Canada
• 16: Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
• 17: Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, Proceedings of the 27th International Conference on Very Large Data Bases, p.541-550, September 11-14, 2001
• 18: Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
• 19: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
• 20: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 21: 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
• 22: Mauricio A. Hernández , Salvatore J. Stolfo, Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem, Data Mining and Knowledge Discovery, v.2 n.1, p.9-37, January 1998 [doi>10.1023/A:1009761603038]
• 23: Ykä Huhtala , Juha Kärkkäinen , Pasi Porkka , Hannu Toivonen, Efficient Discovery of Functional and Approximate Dependencies Using Partitions, Proceedings of the Fourteenth International Conference on Data Engineering, p.392-401, February 23-27, 1998
• 24: Piotr Indyk , Nick Koudas , S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Proceedings of the 26th International Conference on Very Large Data Bases, p.363-372, September 10-14, 2000
• 25: Y. Ioannidis and V. Poosala. Histogram-based solutions to diverse database estimation problems. Data Engineering Bulletin, 18(3):10-18, 1995.
• 26: W. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. In Conference in Modern Analysis and Probability, pages 189-206, 1984.
• 27: Vipul Kashyap , Amit Sheth, Semantic and schematic similarities between database objects: a context-based approach, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.276-304, December 1996 [doi>10.1007/s007780050029]
• 28: Knowledge Driver. http://www.knowledgedriver.com/.
• 29: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 30: S. Kramer and B. Pfahringer. Efficient search of string parital determinations. In Proc. Intl. Conf. on Knowledge Discover and Data Mining, pages 371-378, 1996.
• 31: S. Kuchin. Oracle, odbc and db2-cli template library programmer's guide. http://www.geocities.com/skuchin/otl/home.htm.
• 32: Mong-Li Lee , Tok Wang Ling , Hongjun Lu , Yee Teng Ko, Cleansing Data for Mining and Warehousing, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.751-760, August 30-September 03, 1999
• 33: 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]
• 34: Metagenix Inc. http://www.metagenix.com/home.asp.
• 35: 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
• 36: 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
• 37: A. Monge. The field matching problem: Algorithms and applications. IEEE Data Engineering Bulletin, 23(4):14-20, 2000.
• 38: A. Monge and P. Elkan. The field matching problem: Algorithms and applications. In Proc. Intl. Conf. Knowledge Discovery and Data Mining, 1996.
• 39: A. Monge and P. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In Proc. SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 1997.
• 40: S. Muthukrishnan. Estimating number of rare values on data streams, 2001. Submitted for publication.
• 41: Christine Parent , Stefano Spaccapietra, Issues and approaches of database integration, Communications of the ACM, v.41 n.5es, May 1998 [doi>10.1145/276404.276408]
• 42: E. Rahm and H. Do. Data cleaning: Problems and current approaches. IEEE Data Engineering Bulletin, 23(4):1-11, 2000.
• 43: Vijayshankar Raman , Joseph M. Hellerstein, Potter's Wheel: An Interactive Data Cleaning System, Proceedings of the 27th International Conference on Very Large Data Bases, p.381-390, September 11-14, 2001
• 44: I. Savnik and P. Flach. Bottom-up induction of functional dependencies from relations. In Proc. AAAI Knowledge Discovery in Databases, pages 174-185, 1993.
• 45: J. Schlimmer. Efficiently inducing determinations: A complete and systematic search algorithm that uses pruning. In Proc. AAAI Knowledge Discovery in Databases, pages 284-290, 1993.
• 46: P. Vassiliadias, Z. Vagena, S. Skiadopoulos, N. Karayannidis, and T. Sellis. ARKTOS: A tool for data cleaning and transformation in data warehouse environments. Data Engineering Bulletin, 23(4):43-48, 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

General Terms:
Algorithms, Documentation, Theory