Inductive database systems typically include algorithms for mining and querying frequent patterns and association rules. When dealing with large databases, the efficiency of these algorithms with respect to execution time and main memory consumption is an important issue.
In a first part we consider the problem of efficient frequent pattern and association rule mining and discuss the trade-off against the expressiveness of the mining language. We compare different levels of language expressiveness: propositional, syntactical relational and relational with background knowledge. We show how frequent patterns and association rules can be organized concisely in a tree structure.
Next, we discuss the mining of frequent patterns. We describe several existing and new optimizations that can be applied in the pattern testing phase and the candidate generation phase. Many of these optimizations exploit the tree structure that we introduced. We present experimental results comparing the different optimizations and measuring the influence of the type of language that is used.
In a third part, we discuss the mining of association rules. Association rules are not only useful on themselves but can also be used to approximate the set of frequent patterns with a more compact set of free or closed patterns. We discuss several levels of freeness depending on the language that is used and empirically validate our results.