Information-theoretic tools for mining database structure from large data sets

ABSTRACT

Data design has been characterized as a process of arriving at a design that maximizes the information content of each piece of data (or equivalently, one that minimizes redundancy). Information content (or redundancy) is measured with respect to a prescribed model for the data, a model that is often expressed as a set of constraints. In this work, we consider the problem of doing data redesign in an environment where the prescribed model is unknown or incomplete. Specifically, we consider the problem of finding structural clues in an instance of data, an instance which may contain errors, missing values, and duplicate records. We propose a set of information-theoretic tools for finding structural summaries that are useful in characterizing the information content of the data, and ultimately useful in data design. We provide algorithms for creating these summaries over large, categorical data sets. We study the use of these summaries in one specific physical design task, that of ranking functional dependencies based on their data redundancy. We show how our ranking can be used by a physical data-design tool to find good vertical decompositions of a relation (decompositions that improve the information content of the design). We present an evaluation of the approach on real data sets.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Sanjay Agrawal , Surajit Chaudhuri , Vivek Narasayya, Materialized view and index selection tool for Microsoft SQL server 2000, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.608, May 21-24, 2001, Santa Barbara, California, United States
• 4: R. Ananthakrishna, S. Chaudhuri, and V. Ganti. Eliminating Fuzzy Duplicates in Data Warehouses. In VLDB, pages 586--597, Hong Kong, China, 2002.
• 5: P. Andritsos, P. Tsaparas, R. J. Miller, and K. C. Sevcik. LIMBO: Scalable Clustering of Categorical Data. In EDBT, pages 123--146, Heraklion, Greece, 2004.
• 6: Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.15-26, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773155]
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: Mehmet M. Dalkilic , Edward L. Roberston, Information dependencies, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.245-253, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.336059]
• 9: Tamraparni Dasu , Theodore Johnson, Exploratory Data Mining and Data Cleaning, John Wiley & Sons, Inc., New York, NY, 2003
• 10: Tamraparni Dasu , Theodore Johnson , S. Muthukrishnan , Vladislav Shkapenyuk, Mining database structure; or, how to build a data quality browser, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564719]
• 11: Ran El-Yaniv , Oren Souroujon, Iterative Double Clustering for Unsupervised and Semi-supervised Learning, Proceedings of the 12th European Conference on Machine Learning, p.121-132, September 05-07, 2001
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
• 14: J. A. Hoffer and D. G. Severance. The Use of Cluster Analysis in Physical Data Base Design. In VLDB, pages 69--86, Framingham, MA, USA, 1975.
• 15: Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen. TANE: An efficient algorithm for discovering functional and approximate dependencies. The Computer Journal, 42(2):100--111, 1999.
• 16: David Maier, Minimum Covers in Relational Database Model, Journal of the ACM (JACM), v.27 n.4, p.664-674, Oct. 1980 [doi>10.1145/322217.322223]
• 17: Shamkant Navathe , Stefano Ceri , Gio Wiederhold , Jinglie Dou, Vertical partitioning algorithms for database design, ACM Transactions on Database Systems (TODS), v.9 n.4, p.680-710, Dec. 1984 [doi>10.1145/1994.2209]
• 18: Shamkant B. Navathe , Mingyoung Ra, Vertical partitioning for database design: a graphical algorithm, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.440-450, June 1989, Portland, Oregon, United States
• 19: L. Popa, Y. Velegrakis, M. Hernandez, R. J. Miller, and R. Fagin. Translating web data. In VLDB, pages 598--609, Hong Kong, China, Aug. 2002.
• 20: Ravishankar Ramamurthy , David J. DeWitt , Qi Su, A case for fractured mirrors, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.89-101, August 2003 [doi>10.1007/s00778-003-0093-1]
• 21: 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
• 22: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
• 23: S. Sarawagi-(Editor). Special Issue on Data Cleaning. Bulletin of the Technical Committee on Data Engineering, Volume 23(4), December 2000.
• 24: I. Savnik and P. A. Flach. Bottom-up induction of functional dependencies from relations. In AAAI-93 Workshop: Knowledge Discovery in Databases, pages 174--185, Washington, DC, USA, 1993.
• 25: I. Savnik and P. A. Flach. Disocvery of Mutlivalued Dependencies from Relations. Intelligent Data Analysis Journal, 4(3):195--211, 2000.
• 26: N. Slonim and N. Tishby. Agglomerative Information Bottleneck. In NIPS-12, pages 617--623, Breckenridge, CO, 1999.
• 27: N. Tishby, F. C. Pereira, and W. Bialek. The Information Bottleneck Method. In 37th Annual Allerton Conference on Communication, Control and Computing, Urban-Champaign, IL, 1999.
• 28: Catharine Wyss , Chris Giannella , Edward L. Robertson, FastFDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances - Extended Abstract, Proceedings of the Third International Conference on Data Warehousing and Knowledge Discovery, p.101-110, September 05-07, 2001
• 29: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada