Mining all frequent projection-selection queries from a relational table

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 at-tention to projection-selection queries, and we assume that the table to be mined satisfies a set of functional depen-dencies. 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. With these results at hand, we further restrict our atten-tion 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 fre-quent 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 algo-rithm is similar to that of the well known Apriori algorithm, i.e., linear with respect to the number of attributes. 1