We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Mining frequent conjunctive queries using functional and inclusion dependencies.
- Authors
Dieng, Cheikh; Jen, Tao-Yuan; Laurent, Dominique; Spyratos, Nicolas
- 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 article, we show that mining frequent projection-selection-join queries becomes tractable if joins are performed along keys and foreign keys, in a database satisfying functional and inclusion dependencies, under certain restrictions. We note that these restrictions cover most practical cases, including databases operating over star schemas, snow-flake schemas and constellation schemas. In our approach, 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. We report on experiments showing that, in our context, mining frequent projection-selection-join queries is indeed tractable, even for large data sets.
- Subjects
FUNCTIONAL dependencies; QUERYING (Computer science); DATABASES; COMPUTER algorithms; DATA mining; IMDB.COM Inc.
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2013, Vol 22, Issue 2, p125
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-012-0277-7