Searching for dependencies at multiple abstraction levels

ABSTRACT

The notion of roll-up dependency (RUD) extends functional dependencies with generalization hierarchies. RUDs can be applied in OLAP and database design. The problem of discovering RUDs in large databases is at the center of this paper. An algorithm is provided that relies on a number of theoretical results. The algorithm has been implemented; results on two real-life datasets are given. The extension of functional dependency (FD) with roll-ups turns out to capture meaningful rules that are outside the scope of classical FD mining. Performance figures show that RUDs can be discovered in linear time in the number of tuples of the input dataset.

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: Rakesh Agrawal , Hiekki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Renaud Bassée , Jef Wijsen, Neighborhood Dependencies for Prediction, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.562-567, April 16-18, 2001
• 5: Bay, S. 1999. The UCI KDD archive, http://kdd.ics.uci.edu/. University of California, Irvine, Dept. of Information and Computer Sciences.
• 6: Bell, S. 1995. Discovery and maintenance of functional dependencies by independencies. In Proceedings of the 1st International Conference on Knowledge Discovery in Databases. AAAI Press, Montreal, Canada, 27--32.
• 7: Bettini, C., Dyreson, C., Evans, W., Snodgrass, R., and Wang, X. 1998. A glossary of time granularity concepts. In Temporal Databases: Research and Practice, O. Etzion, S. Jajodia, and S. Sripada, Eds. Number 1399 in LNCS State-of-the-art Survey. Springer-Verlag, 406--413.
• 8: 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
• 9: Luca Cabibbo , Riccardo Torlone, Querying Multidimensional Databases, Proceedings of the 6th International Workshop on Database Programming Languages, p.319-335, August 18-20, 1997
• 10: CIA. 2001. The world factbook 2001, http://www.cia.gov/cia/publications/factbook.
• 11: Davey, B. and Priestley, H. 1990. Introduction to Lattices and Order. Cambridge University Press.
• 12: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 13: Han, J. 1997. OLAP mining: An integration of OLAP with data mining. In Proceedings of the 7th IFIP 2.6 Working Conference on Database Semantics (DS-7). Leysin, Switzerland, 1--9.
• 14: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 15: Huhtala, Y., Kärkkäinen, J., Porkka, P., and Toivonen, H. 1999. TANE: An efficient algorithm for discovering functional and approximate dependencies. Comput. J. 42, 2, 100--111.
• 16: Kantola, M., Mannila, H., Räihä, K.-J., and Siirtola, H. 1992. Discovering functional and inclusion dependencies in relational databases. Int. J. Intelligent Systems 7, 591--607.
• 17: Jyrki Kivinen , Heikki Mannila, Approximate inference of functional dependencies from relations, Theoretical Computer Science, v.149 n.1, p.129-149, Sept. 18, 1995
• 18: Stéphane Lopes , Jean-Marc Petit , Lotfi Lakhal, Efficient Discovery of Functional Dependencies and Armstrong Relations, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.350-364, March 27-31, 2000
• 19: Heikki Mannila , Kari-Jouko Räihä, Design by exmple: An application of Armstrong relations, Journal of Computer and System Sciences, v.33 n.2, p.126-141, Oct. 1986 [doi>10.1016/0022-0000(86)90015-2]
• 20: Heikki Mannila , Kari-Jouko Räihä, Dependency Inference, Proceedings of the 13th International Conference on Very Large Data Bases, p.155-158, September 01-04, 1987
• 21: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281]
• 22: May, W. 1999. Information extraction and integration with Florid: The Mondial case study. Tech. Rep. 131, Universität Freiburg, Institut für Informatik.
• 23: Noel Novelli , Rosine Cicchetti, FUN: An Efficient Algorithm for Mining Functional and Embedded Dependencies, Proceedings of the 8th International Conference on Database Theory, p.189-203, January 04-06, 2001
• 24: Schlimmer, J. C. 1993. Efficiently inducing determinations: A complete and systematic search algorithm that uses optimal pruning. In Proceedings of the 10th International Conference on Machine Learning. Morgan Kaufmann, Amherst, MA, 284--290.
• 25: van der Heyden, J. 2001. Global statistics, http://www.geohive.com/. GeoHive.
• 26: van der Laag, P. R. J. and Nienhuys-Cheng, S.-H. 1998. Completeness and properness of refinement operators in inductive logic programming. J. Logic Program. 34, 3, 201--225.
• 27: X. Sean Wang , Claudio Bettini , Alexander Brodsky , Sushil Jajodia, Logical design for temporal databases with multiple granularities, ACM Transactions on Database Systems (TODS), v.22 n.2, p.115-170, June 1997 [doi>10.1145/249978.249979]
• 28: Jef Wijsen, Temporal FDs on complex objects, ACM Transactions on Database Systems (TODS), v.24 n.1, p.127-176, March 1999 [doi>10.1145/310701.310715]
• 29: Jef Wijsen , Robert Meersman, On the Complexity of Mining Quantitative Association Rules, Data Mining and Knowledge Discovery, v.2 n.3, p.263-281, September 1998 [doi>10.1023/A:1009755120593]
• 30: Jef Wijsen , Raymond T. Ng , Toon Calders, Discovering roll-up dependencies, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.213-222, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312232]
• 31: Jef Wijsen , Raymond T. Ng, Temporal Dependencies Generalized for Spatial and Other Dimensions, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.189-203, September 10-11, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms, Experimentation, Management, Performance, Theory

Keywords:
Data mining, functional dependencies, knowledge discovery, online analytical processing