Discovering topical structures of databases

ABSTRACT

The increasing complexity of enterprise databases and the prevalent lack of documentation incur significant cost in both understanding and integrating the databases. Existing solutions addressed mining for keys and foreign keys, but paid little attention to more high-level structures of databases. In this paper, we consider the problem of discovering topical structures of databases to support semantic browsing and large-scale data integration. We describe iDisc, a novel discovery system based on a multi-strategy learning framework. iDisc exploits varied evidence in database schema and instance values to construct multiple kinds of database representations. It employs a set of base clusterers to discover preliminary topical clusters of tables from database representations, and then aggregate them into final clusters via meta-clustering. To further improve the accuracy, we extend iDisc with novel multiple-level aggregation and clusterer boosting techniques. We introduce a new measure on table importance and propose an approach to discovering cluster representatives to facilitate semantic browsing. An important feature of our framework is that it is highly extensible, where additional database representations and base clusterers may be easily incorporated into the framework. We have extensively evaluated iDisc using large real-world databases and results show that it discovers topical structures with a high degree of accuracy.

REFERENCES

• 1: CA ERwin Data Modeler (www.ca.com).
• 2: IBM Rational Data Modeler (www.ibm.com).
• 3: Periklis Andritsos , Renée J. Miller , Panayiotis Tsaparas, Information-theoretic tools for mining database structure from large data sets, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007650]
• 4: Philip A. Bernstein , Sergey Melnik , John E. Churchill, Incremental schema matching, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 5: U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163--177, 2001.
• 6: P. Brown et al. Toward automated large-scale information integration and discovery. In Data Management in a Connected World, 2005.
• 7: S. Castano , V. De Antonellis , M. G. Fugini , B. Pernici, Conceptual schema analysis: techniques and applications, ACM Transactions on Database Systems (TODS), v.23 n.3, p.286-333, Sept. 1998 [doi>10.1145/293910.293150]
• 8: F. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
• 9: C. Clifton, E. Housman, and A. Rosenthal. Experience with a combined approach to attribute-matching across heterogeneous databases. In IFIP, 1997.
• 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: 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
• 12: AnHai Doan , Alon Y. Halevy, Semantic-integration research in the database community, AI Magazine, v.26 n.1, p.83-94, March 2005
• 13: P. Feldman and D. Miller. Entity model clustering: Structuring a data model by abstraction. The Computer Journal, 29(4):348--360, 1986.
• 14: Dayne Freitag, Multistrategy Learning for Information Extraction, Proceedings of the Fifteenth International Conference on Machine Learning, p.161-169, July 24-27, 1998
• 15: Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering Aggregation, Proceedings of the 21st International Conference on Data Engineering, p.341-352, April 05-08, 2005 [doi>10.1109/ICDE.2005.34]
• 16: L. Haas. Beauty and the beast: The theory and practice of information integration. In ICDT, 2007.
• 17: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 18: Stephen Hayne , Sudha Ram, Multi-User View Integration System (MUVIS): An Expert System for View Integration, Proceedings of the Sixth International Conference on Data Engineering, p.402-409, February 05-09, 1990
• 19: IBM Corporation. Attributes & Capabilities Study, 2006.
• 20: T. Johnson, A. Marathe, and T. Dasu. Database exploration and Bellman. Data Eng. Bull., 26(3), 2003.
• 21: A. Koeller and E. Rundensteiner. Heuristic strategies for the discovery of inclusion dependencies and other patterns. Journal on Data Semantics, V, 2006.
• 22: 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]
• 23: R. Michalski and G. Tecuci, editors. Machine Learning: A Multistrategy Approach. Morgan Kaufmann, 1994.
• 24: M. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 2004.
• 25: 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]
• 26: Erhard Rahm , Hong-Hai Do , Sabine Maßmann, Matching large XML schemas, ACM SIGMOD Record, v.33 n.4, December 2004 [doi>10.1145/1041410.1041415]
• 27: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 28: Yannis Sismanis , Paul Brown , Peter J. Haas , Berthold Reinwald, GORDIAN: efficient and scalable discovery of composite keys, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 29: Toby J. Teorey , Guangping Wei , Deborah L. Bolton , John A. Koenig, ER model clustering as an aid for user communication and documentation in database design, Communications of the ACM, v.32 n.8, p.975-987, Aug. 1989 [doi>10.1145/65971.65976]
• 30: Toby J. Teorey , Guangping Wei , Deborah L. Bolton , John A. Koenig, ER model clustering as an aid for user communication and documentation in database design, Communications of the ACM, v.32 n.8, p.975-987, Aug. 1989 [doi>10.1145/65971.65976]
• 31: Cong Yu , H. V. Jagadish, Schema summarization, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
clustering, database structure, discovery, topical structure