Mining all frequent projection-selection queries from a relational table
Tao-Yuan Jen, Dominique A. Laurent, Nicolas Spyratos · 2008
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 ≺ over queries and we show the following: (a) the support measure is anti-monotonic (with respect to ≺), and (b) if we define q ≺ q' iff q ≺ q' and q' ≺ q then all queries of an equivalence class have the same support.