Mining Short‐Rule Covers in Relational Databases
Claudio Carpineto, Giovanni Romano · Computational Intelligence · 2003
An implication ruleQ→Ris a statement of the form “for all objects in the database, if an object has the attribute–value pairsQthen it has also the attribute–value pairsR.” This simple type of rule is theoretically interesting, because it supports reasoning, similar to functional dependencies in database theory, and it may be of practical significance because the size of the set of implication rules that hold in a relation can remain substantially high even when mining real data and considering only most general covers; i.e., covers containing rules with unredundant right and left sizes. Motivated by these observations, we focus on the extraction of short‐rule covers, which cannot be efficiently mined by standard rule miners. We present an algorithm driven by “negative examples” (i.e., satisfyQbut notR) to prune the rule‐candidate lattice associated with each “positive example” (i.e., satisfies bothQandR). The algorithm scales up quite well with respect to the number of objects and it is particularly suitable for databases with attributes described by large domains. Furthermore, a perfect hash function ensures extraction of short‐rule covers even from databases containing a large number of attributes.