Mining and Learning Disjunctive Rules

26 concepts19 papers1 proposal

When machine learning and data mining systems try to make sense of the world, they naturally default to the path of least resistance: conjunctions. Traditional association rules and concept-learning algorithms excel at finding patterns of co-occurrence, framing the world through logical AND conditions. For instance, a market basket analysis might easily discover that if a customer buys bread AND butter, they will also buy milk.

However, real-world relationships are rarely purely conjunctive. They are filled with alternatives, substitutions, and branching pathways. A customer might buy bread because they intend to buy milk OR butter. A linguistic rule might trigger based on one of several distinct phonetic environments. When systems are forced to rely solely on conjunctive logic, they fail to capture these fundamental "either-or" relationships.

To bridge this gap, a robust body of research focuses on mining and learning disjunctive rules—logical expressions that incorporate OR and XOR operations to model non-contiguous, multi-pathway phenomena without succumbing to combinatorial explosion.

The Geometry of Failure

To understand why disjunctive rules are necessary, it helps to look at how traditional algorithms view data geometrically. In a classic paper, Chris Thornton analyzed early symbolic learning frameworks through the lens of Hypercuboid-Formation Behaviour.

When an algorithm learns a conjunctive concept, it is essentially drawing a single, contiguous "hypercuboid" (a multi-dimensional box) around positive examples in the feature space. Every condition added to the conjunction ($A \land B \land C$) slices away dimensions, shrinking the box until it tightly bounds the target concept.

Conjunctive Concept (Single Hypercuboid)
+-----------------+
|  Positive       |
|  Examples       |
+-----------------+

Disjunctive Concept (Non-Contiguous Regions)
+-------+         +-------+
| Box A |   OR    | Box B |
+-------+         +-------+

As noted in further analysis of Hypercuboid-Formation, this geometric strategy completely breaks down when encountering a disjunctive concept. If a concept is defined by alternative sub-concepts (e.g., "vehicles" could be cars OR boats), the positive examples form non-contiguous regions in the feature space. A conjunctive learner attempting to fit these examples into a single hypercuboid will either expand the box so wide that it includes massive amounts of negative space (overgeneralization) or fail to converge entirely.

This limitation is not unique to simple classification. Young et al. demonstrated that standard concept-learning frameworks stumble when tasked with extended learning challenges that require alternative criteria. Similarly, Pericliev et al. found that multi-class discrimination methods lose their intelligibility and conciseness when forced to represent concepts that are inherently disjunctive.

Formalizing Disjunctions in Data Mining

To capture these non-contiguous patterns, researchers extended traditional data mining frameworks to support disjunctive logic.

In transactional data mining, standard Association Rule Mining (ARM) identifies rules like $A \rightarrow B$. Nanavati et al. introduced generalized disjunctive association rules (d-rules), which allow disjunctions and exclusive disjunctions within the rule's consequent, such as:

$$\text{Bread} \rightarrow (\text{Milk} \lor \text{Butter}) \land \text{Eggs}$$

This formulation captures item substitutability—the idea that a customer might treat milk and butter as alternatives in a given context. To make this even more flexible, Jabbour et al. generalized this structure further, allowing disjunctions to appear in both the antecedent and the consequent ($A \lor B \rightarrow C \lor D$).

Beyond association rules, this expressive power is vital for capturing complex patterns in structured data. For example:

  • Disjunctive Normal Form (DNF) Patterns: Instead of mining single itemsets, Li et al. focused on mining patterns in DNF (conjunctions of disjunctions), which map out alternative pathways driving an outcome.
  • Relational Graphs: Nguyen et al. extended this to multidimensional association rules within dynamic graphs, allowing any subset of dimensions to form disjunctive relationships.
  • Data Constraints: In database management, Geerts et al. developed extended Conditional Functional Dependencies (eCFDs) by replacing single constant values with sets and complement sets, allowing data cleaning rules to natively express disjunctions and inequalities.

Taming the Combinatorial Explosion

If disjunctive rules are so expressive, why aren't they the default? The answer is computational complexity.

In standard conjunctive mining, algorithms can use the apriori property (downward closure) to prune the search space: if an itemset is infrequent, all of its supersets must also be infrequent. Disjunctions destroy this property. If the itemset $A$ is rare, the disjunction $A \lor B$ might still be incredibly frequent because of $B$. This causes the search space to explode exponentially.

To make disjunctive mining practical, researchers rely on three main algorithmic mechanisms:

1. Symbolic Compilation and SAT Solvers

Instead of exhaustively counting itemsets in a database, modern approaches often translate the rule-mining problem into a propositional logic formula. Jabbour et al. demonstrated that by encoding frequency and confidence thresholds as boolean constraints, they could leverage modern, highly optimized SAT solvers. These solvers use conflict-driven clause learning to rapidly navigate and prune the massive search space of disjunctive combinations.

2. Markov Chain Monte Carlo (MCMC) Sampling

When finding all disjunctive patterns is computationally impossible, we can instead aim to find a representative, high-quality subset. Li et al. developed an MCMC-based approach to sample minimal frequent DNF patterns. By setting up a random walk over the space of boolean formulas, the algorithm jumps directly to meaningful disjunctive patterns, achieving near-uniform sampling without ever enumerating the full space.

3. Graph Traversal and Thrifty Heuristics

To mine d-rules efficiently, Nanavati et al. proposed the thrifty-traverse algorithm. It organizes items into a graph based on their co-occurrence and uses localized heuristics to explore only the most promising disjunctive branches, bypassing the need to evaluate every mathematically possible OR combination.

Applications Across Domains

By mastering the computational challenges of disjunction, these frameworks enable automated systems to discover rules that mirror human reasoning and complex natural processes.

Knowledge Representation and Logic Programming

In artificial intelligence, Disjunctive Logic Programming (DLP) allows rules to have multiple head atoms ($A \lor B \leftarrow C$). As detailed by Leone et al., systems like DLV use disjunction to elegantly model real-world planning, scheduling, and common-sense reasoning problems that would otherwise require convoluted, deeply nested conjunctive logic. Furthermore, França et al. showed that extracting first-order rules with explicit disjunctions from neural attribute-value learners bridges the gap between efficient propositional learning and expressive relational reasoning.

Linguistics and Phonology

Human language is notoriously non-linear. Phonological rules (how sounds change based on context) often rely on alternative triggers. Barke et al. showed that traditional conjunctive rule frameworks fail to learn these processes accurately. By using program synthesis and Satisfiability Modulo Theories (SMT) solvers, their system, SYPHON, successfully learns human-readable phonological rules that accommodate disjunctive linguistic environments.

Category Definitions and Data Trust

In large-scale knowledge bases, categories are rarely defined by a single set of properties. For instance, a "Liquid" might be defined by its chemical state OR its utility. Xu et al. utilized pattern-based rule learning to discover these multi-faceted, disjunctive defining features across millions of entities.

Finally, in data engineering, Fariha et al. utilized compound conformance constraints to partition data spaces into disjunctive regions. This allows data-driven systems to detect data drift and measure trust by verifying whether incoming data conforms to any of the valid alternative operational profiles discovered during training.

Ultimately, moving from conjunctive to disjunctive rules is about moving from rigid approximations to flexible representations. Whether through SAT solvers, stochastic sampling, or specialized logic architectures, capturing the power of OR allows machines to map the non-contiguous, branching reality of the real world.

Key Foundational Work

Applying General Induction Methods to the Card Game Eleusis (1980) — contributed 1 concept elements to this direction.
Analysis of an Extended Concept-Learning Task (1977) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_generalized_association_rules_e8ef145e,
  title = {generalized association rules},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalized-association-rules/rdr_e8ef145ed4484b759dadb84e110b0b17},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_generalized_association_rules_e8ef145e_v1,
  title = {generalized association rules},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalized-association-rules/rdr_e8ef145ed4484b759dadb84e110b0b17/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake