Traditional knowledge representation and reasoning systems rely heavily on syntactic formulas—collections of rules, axioms, or clauses. To deduce new information, find explanations, or answer queries, these systems perform theorem proving via symbolic manipulation. However, syntactic reasoning is computationally brutal: common-sense deduction, abduction, and query answering frequently scale into NP-hard, coNP-complete, or even undecidable territory.
To bypass this complexity, a powerful alternative paradigm has emerged: model-based reasoning. Instead of storing abstract rules, a system can represent knowledge using concrete models (semantic interpretations or examples) of the world. Reasoning then shifts from expensive theorem proving to efficient model checking.
The core challenge of this paradigm is scale: a logical theory can have exponentially many or even infinitely many valid models. The breakthrough insight shared across this research direction is that we do not need to store every possible model. Instead, we can compress the entire model space into a small, carefully selected set of characteristic models, a single canonical (universal) model, or a finite type-based abstraction.
Propositional Logic: Speeding up Inference with Characteristic Models
In propositional logic, a knowledge base is typically represented as a conjunction of formulas. To check if a query is logically implied, a formula-based reasoner must prove that no valid assignment satisfies the knowledge base while falsifying the query.
Henry A. Kautz et al. demonstrated that for Horn theories—a cornerstone of common-sense reasoning—we can replace these formulas with a minimal basis of truth assignments called characteristic models. Because the models of a Horn theory are closed under bitwise intersection, this small subset implicitly generates all other satisfying assignments.
Syntactic Representation (Formula-Based):
[ Rule 1 ] ∧ [ Rule 2 ] ∧ [ Rule 3 ] ---> Expensive Theorem Proving
Semantic Representation (Model-Based):
{ Model A, Model B, Model C } ---> Fast Model Checking / Evaluation
As shown by Roni Khardon et al., this representation shifts the computational burden from the online inference step to the offline construction phase. To determine logical implication, the system simply checks if the query is satisfied by the pre-selected characteristic models. This model-checking approach operates in polynomial time relative to the size of the model set, bypassing the traditional combinatorial explosion. The authors later extended this principle to default reasoning in Default-Reasoning with Models, showing that human-like "usually true" logic can be executed via concrete examples rather than complex exception-handling rules.
This semantic compression is particularly effective for abductive reasoning (finding the best explanation for an observation). Syntactically, abduction requires searching through an exponential space of proofs to find a minimal set of assumptions. By shifting to a model-based representation, Henry A. Kautz et al. and Thomas Eiter et al. proved that abduction drops to polynomial time. Instead of proving theorems, the algorithm inspects the characteristic models to find a valid state where the observation holds, and then greedily minimizes the necessary assumptions directly over that structure.
First-Order Ontologies: The Power of a Single Universal Model
When moving from propositional logic to first-order ontologies—such as Description Logics (DLs) used in the Semantic Web—the space of possible models grows dramatically. In Ontology-Based Data Access (OBDA), a database of facts (an ABox) is paired with an ontology of rules (a TBox). A query answer is only "certain" if it holds across all possible models consistent with both the data and the rules.
Evaluating a query across an infinite number of valid models seems impossible. However, for "Horn-like" ontology languages (such as the $\mathcal{EL}$ and DL-Lite families), the logic guarantees a property known as materializability. As explored by Carsten Lutz et al. and Carsten Lutz et al., materializable ontologies allow for the construction of a single universal model (or canonical interpretation) that encapsulates all logical consequences of the system.
All Possible Models Consistent with Ontology
[ Model 1 ] [ Model 2 ] [ Model 3 ] ... [ Model ∞ ]
▲ ▲ ▲ ▲
│ │ │ │ (Homomorphic Mappings)
┌───────────────────────────────────────────────┐
│ SINGLE UNIVERSAL MODEL │
│ (Constructed via Chase / Materialization) │
└───────────────────────────────────────────────┘
This universal model is typically constructed using a chase procedure, which iteratively applies the ontology's rules to the database to materialize inferred facts. Why does a single model suffice? Because a universal model can be homomorphically mapped into any other valid model of the ontology. For positive existential queries (like conjunctive queries), if a match exists in the universal model, it is guaranteed to exist in all valid models.
This mechanism dramatically simplifies query evaluation:
- Data Integration: Lucian Popa 0001 et al. and Lucian Popa et al. utilize this framework to unify entity resolution with query answering, evaluating queries on a single universal model and filtering out null values to obtain certain answers.
- Alternative Semantics: Charalampos Nikolaou et al. adapt the chase to build a canonical model under multiset (bag) semantics, ensuring accurate database counting and aggregation.
- Constraint Validation: Evgeny Kharlamov et al. leverage the canonical model property to validate SHACL data constraints over knowledge graphs, ensuring that validating the representative model validates all implied models.
- Uncertainty: Jeff Z. Pan et al. show that even when handling subjective or uncertain logic, a single canonical interpretation remains a sufficient representative for sound query entailment.
By establishing these representative structures, researchers can precisely map the boundaries of query complexity, as seen in the analysis of tree-like queries by Stanislav Kikot et al. and guarded fragments by André Hernich et al..
Taming Infinity: Finite Type Semantics and Abstractions
A significant complication arises with existential restrictions (e.g., the rule "Every Person has a parent who is a Person"). When the chase procedure encounters these rules, it generates new, unnamed individuals, which recursively trigger more rules, causing the canonical model to expand infinitely.
To perform actual computation—such as updating a knowledge base or verifying inseparability—we cannot materialize an infinite structure. Instead, researchers use finite type semantics or semantic abstractions to collapse infinite models into bounded, manageable representations.
Infinite Canonical Model:
(Alice) ──parent──> (Anonymous 1) ──parent──> (Anonymous 2) ──parent──> ... [Infinite]
Collapsed Finite Type Model:
(Alice) ──parent──> [ Type: {Person, Taxpayer} ] ↺ parent [Bounded]
Instead of tracking an infinite sequence of distinct individuals, we group individuals into equivalence classes called types or features based on the specific set of concepts and roles they satisfy within the ontology's vocabulary.
This abstraction transforms infinite model spaces into finite graphs:
- Knowledge Base Evolution: Standard model-based revision fails when models are infinite. Zhe Wang et al. introduced finite type semantics to replace infinite interpretations with succinct sets of concept and role groupings. This allowed the authors to develop polynomial-time algorithms for knowledge contraction and revision (Zhe Wang et al.; Zhe Wang et al.). When updates yield disjunctive outcomes, a finite "prototypal set" of these representative models can be used instead of a single model, as shown by Evgeny Kharlamov et al..
- Handling Inconsistency: Xiaowang Zhang et al. map infinite interpretations to finite structured features. This mapping enables distance-based paraconsistent reasoning, allowing systems to find the "closest" logical interpretation of a conflicting knowledge base within a bounded search space.
- Query Answering and Learning: To answer queries without infinite generation, Carsten Lutz et al. construct a collapsed canonical model using auxiliary objects tracked via relational database tables. For highly expressive logics like $\mathcal{SHIQ}$ that lack the finite model property, Magdalena Ortiz et al. and Thomas Eiter et al. utilize finite "completion forests" to represent and unravel infinite chains. These finite proxies are also vital for active learning algorithms, where a system must verify properties against a foundational model structure (Ana Ozaki et al.; Maurice Funk et al.).
Whether dealing with temporal data via canonical quasimodels (as developed by the authors of Temporalized), counting constraints (Meghyn Bienvenu et al.), or checking if two ontologies are query-indistinguishable (Elena Botoeva et al.), the underlying intuition remains identical. By shifting from syntactic formulas to compressed, representative semantic models, the computational complexity of reasoning is successfully tamed.
Key Foundational Work
Reasoning with Models (1994) — contributed 4 concept elements to this direction.
Learning to Reason (1994) — contributed 2 concept elements to this direction.
Reasoning With Characteristic Models (1993) — contributed 2 concept elements to this direction.