Mining all frequent projection-selection queries from a relational table

ABSTRACT

In this paper we study the problem of mining all frequent queries in a given database table, a problem known to be intractable even for conjunctive queries. We restrict our attention to projection-selection queries, and we assume that the table to be mined satisfies a set of functional dependencies. Under these assumptions we define a pre-ordering &cupre; over queries and we show the following: (a) the support measure is anti-monotonic (with respect to &cupre;), and (b) if we define q &cupre; q' iff q &cupre; q' and q' &cupre; q then all queries of an equivalence class have the same support.

With these results at hand, we further restrict our attention to star schemas of data warehouses. In those schemas, the set of functional dependencies satisfies an important property, namely, the union of keys of all dimension tables is a key for the fact table. The main contribution of this paper is the proposal of a level-wise algorithm for mining all frequent projection-selection queries in a data warehouse over a star schema. Moreover, we show that, in the case of a star schema, the complexity in the number of scans of our algorithm is similar to that of the well known Apriori algorithm, i.e., linear with respect to the number of attributes.

REFERENCES

• 1: Rakesh Agrawal , Heikki 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
• 2: W. Armstrong. Dependency structures of data base relationships. In IFIP Congress, pages 580--583. North Holland, 1974.
• 3: Luc Dehaspe , Luc De Raedt, Mining Association Rules in Multiple Relations, Proceedings of the 7th International Workshop on Inductive Logic Programming, p.125-132, September 17-20, 1997
• 4: Cheikh Talibouya Diop , Arnaud Giacometti , Dominique Laurent , Nicolas Spyratos, Composition of Mining Contexts for Efficient Extraction of Association Rules, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.106-123, March 25-27, 2002
• 5: A. Faye, A. Giacometti, D. Laurent, and N. Spyratos. Mining rules in databases with multiple tables: Problems and perspectives. In 3rd International Conference on Computing Anticipatory Systems (CASYS), 1999.
• 6: B. Goethals. Mining queries. In Workshop on inductive databases and constraint based mining. http://www.informatik.unifreiburg.de/ml/IDB/talks/Goethals_slides.pdf, 2004.
• 7: Bart Goethals , Jan Van den Bussche, Relational Association Rules: Getting WARMeR, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, p.125-139, September 16-19, 2002
• 8: Bart Goethals , Eveline Hoekx , Jan Van den Bussche, Mining tree queries in a graph, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081881]
• 9: J. Han, Y. Fu, W. Wang, K. Koperski, and O. Zaiane. Dmql: A data mining query language for relational databases. In SIGMOD-DMKD'96, pages 27--34, 1996.
• 10: Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004 [doi>10.1023/B:DAMI.0000005258.31418.83]
• 11: T. Y. Jen, D. Laurent, N. Spyratos, and O. Sy. Towards mining frequent queries in star schemes. In International Workshop on Knowledge Discovery in Databases (KDID), LNCS 3933, pages 104--123. Springer Verlag, 2005.
• 12: Rosa Meo , Giuseppe Psaila , Stefano Ceri, An Extension to SQL for Mining Association Rules, Data Mining and Knowledge Discovery, v.2 n.2, p.195-224, June 1998 [doi>10.1023/A:1009774406717]
• 13: T. Turmeaux, A. Salleb, C. Vrain, and D. Cassard. Learning caracteristic rules relying on quantified paths. In PKDD, LNCS 2838, pages 471--482. Springer Verlag, 2003.
• 14: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

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.4 Systems
          Subjects: Relational databases
      H.2.7 Database Administration
          Subjects: Data warehouse and repository