Mining frequent conjunctive queries in star schemas

ABSTRACT

We address the issue of mining frequent conjunctive queries in a relational database, a problem known to be intractable even for conjunctive queries over a single table. In this paper, we extend our previous work to projection-selection-join queries for which joins are performed along keys and foreign keys. Although functional and inclusion dependencies are not axiomatizable in general, we provide general results in this setting and show that mining frequent projection-selection-join queries from a database defined over a star schema is tractable.

More precisely, as in our previous work, we define an equivalence relation over queries using a pre-ordering with respect to which the support is shown to be anti-monotonic. We propose a level-wise algorithm for computing all frequent queries by exploiting the fact that equivalent queries have the same support.

REFERENCES

• 1: R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Verkamo. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining, pages 309--328. AAAI-MIT Press, 1996.
• 2: W. Armstrong. Dependency structures of data base relationships. In IFIP Congress, pages 580--583. North Holland, 1974.
• 3: L. Copin, N. Pecheur, A. Laurent, Y. Augusta, B. Sentana, D. Laurent, and T.-Y. Jen. Dbfrequentqueries: Extraction de requêtes fréquentes. In EGC, volume RNTI-E-15 of Revue des Nouvelles Technologies de l'Information, page 499. Cépaduès-Éditions, 2009.
• 4: L. Dehaspe and L. D. Raedt. Mining association rules in multiple relations. In 7th International Workshop on Inductive Logic Programming, volume 1297 of LNCS, pages 125--132. Springer Verlag, 1997.
• 5: C. Diop, A. Giacometti, D. Laurent, and N. Spyratos. Composition of mining contexts for efficient extraction of association rules. In EDBT'02, volume 2287 of LNCS, pages 106--123. Springer Verlag, 2002.
• 6: B. Goethals and J. V. den Bussche. Relational association rules: getting warmer. In ESF Exploratory Workshop on Pattern Detection and Discovery in Data Mining, volume 2447 of LNCS, pages 125--139. Springer-Verlag, 2002.
• 7: B. Goethals, E. Hoekx, and J. V. den Bussche. Mining tree queries in a graph. In 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 61--69, 2005.
• 8: B. Goethals, W. L. Page, and H. Mannila. Mining association rules of simple conjunctive queries. In SIAM, 2008.
• 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: J. Han, J. Pei, Y. Yin, and R. Mao. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8:53--87, 2004.
• 11: T. Jen, D. Laurent, and N. Spyratos. Mining all frequent selection-projection queries from a relational table. In EDBT'08, pages 368--379. ACM Press, 2008.
• 12: T. Jen, D. Laurent, N. Spyratos, and O. Sy. Towards mining frequent queries in star schemes. In International Workshop on Knowledge Discovery in Databases (KDID), volume 3933 of LNCS, pages 104--123. Springer Verlag, 2005.
• 13: T. Jen, R. Taouil, and D. Laurent. A dichotomous algorithm for association rule mining. In International workshop Grid and Peer-to-Peer Computing Impacts on Large Scale Heterogeneous Distributed Database Systems (GLOBE), in conjunction with intl. conf. DEXA, pages 567--571. IEEE Press, 2004.
• 14: D. S. Johnson and A. C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. In PODS, pages 164--169, 1982.
• 15: R. Meo, G. Psaila, and S. Ceri. An extension to sql for mining association rules. Data Mining and Knowledge Discovery, 9:275--300, 1997.
• 16: J. Ullman. Principles of Databases and Knowledge-Base Systems, volume 1. Computer Science Press, 1988.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
frequent queries, functional dependencies, inclusion dependencies, query comparison