Characteristic relational patterns

ABSTRACT

Research in relational data mining has two major directions: finding global models of a relational database and the discovery of local relational patterns within a database. While relational patterns show how attribute values co-occur in detail, their huge numbers hamper their usage in data analysis. Global models, on the other hand, only provide a summary of how different tables and their attributes relate to each other, lacking detail of what is going on at the local level.

In this paper we introduce a new approach that combines the positive properties of both directions: it provides a detailed description of the complete database using a small set of patterns. More in particular, we utilise a rich pattern language and show how a database can be encoded by such patterns. Then, based on the MDLprinciple, the novel RDB-KRIMP algorithm selects the set of patterns that allows for the most succinct encoding of the database. This set, the code table, is a compact description of the database in terms of local relational patterns. We show that this resulting set is very small, both in terms of database size and in number of its local relational patterns: a reduction of up to 4 orders of magnitude is attained.

REFERENCES

• 1: 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
• 2: Jeroen De Knijf, FAT-miner: mining frequent attribute trees, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244099]
• 3: Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999 [doi>10.1023/A:1009863704807]
• 4: Peter A. Flach , Iztok Savnik, Database dependency discovery: a machine learning approach, AI Communications, v.12 n.3, p.139-160, August 1999
• 5: L. Getoor, N. Friedman, D. Koller, A. Pfeffer, and B. Taskar. Probabilistic relational models. In L. Getoor and B. Taskar, editors, An Introduction to Statistical Relational Learning. MIT Press, 2007.
• 6: B. Goethals, W. Le Page, and H. Mannila. Mining association rules of simple conjunctive queries. In M. Zaki and K. Wang, editors, SDM, pages 96--107. SIAM, 2008.
• 7: P. D. Grünwald. Minimum description length tutorial. In P. Grünwald and I. Myung, editors, Advances in Minimum Description Length. MIT Press, 2005.
• 8: A. Knobbe. Multi-Relational Data Mining. PhD thesis, Universiteit Utrecht, Utrecht, the Netherlands, 2004.
• 9: Daphne Koller , Avi Pfeffer, Probabilistic frame-based systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.580-587, July 1998, Madison, Wisconsin, United States
• 10: A. Koopman and A. Siebes. Discovering relational items sets efficiently. In M. Zaki and K. Wang, editors, SDM, pages 108--119. SIAM, 2008.
• 11: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993
• 12: Heikki Mannila , Kari-Jouko Räihä, Algorithms for inferring functional dependencies from relations, Data & Knowledge Engineering, v.12 n.1, p.83-99, Feb. 1994 [doi>10.1016/0169-023X(94)90023-X]
• 13: S. Nijssen and J. N. Kok. Efficient frequent query discovery in farmer. In In Proc. of the 7th PKDD, volume 2838 of LNCS, pages 350--362. Springer, 2003.
• 14: A. Siebes, J. Vreeken, and M. van Leeuwen. Item sets that compress. In J. Ghosh, D. Lambert, D. B. Skillicorn, J. Srivastava, J. Ghosh, D. Lambert, D. B. Skillicorn, and J. Srivastava, editors, SDM, pages 393--404. SIAM, 2006.
• 15: Maytal Saar Tsechansky , Nava Pliskin , Gadi Rabinowitz , Avi Porath, Mining relational patterns from multiple relational tables, Decision Support Systems, v.27 n.1-2, p.177-195, Nov. 1999 [doi>10.1016/S0167-9236(99)00043-3]
• 16: Xiaoxin Yin , Jiawei Han , Jiong Yang , Philip S. Yu, CrossMine: Efficient Classification Across Multiple Database Relations, Proceedings of the 20th International Conference on Data Engineering, p.399, March 30-April 02, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

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

General Terms:
Algorithms, Experimentation

Keywords:
MDL, frequent patterns, relational data mining