MARITA: Mining approximate rules in tables

Rule mining has been extensively studied for RDF knowledge bases. However, it remains difficult on multi-table relational databases, because the search space grows rapidly with the number of relations and attributes. We present MARITA, an approach for mining approximate Horn rules directly from relational databases. MARITA combines acompact, non-redundantrulerepresentation with foreign-key-guided joins and a novel relation-disjoint semantics that prevents repeated relation occurrences from being satisfied by the same tuple. Its search procedure exploits Horn-specific pruning and evaluates candidate rules directly in SQL. Experiments on 83 public relational benchmarks show that MARITA frequently runs in subsecond time and achieves speed-ups of up to 104× over existing systems.