Finite Representations of Infinite Description Logic Models

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 229 papers41 conceptsfrozen 2026-10-04

In classical database systems, we assume that the data we see is all the data there is. However, in the world of Description Logics (DLs)—the formalisms powering the Semantic Web—we often deal with "open worlds" where rules can imply the existence of objects not explicitly mentioned in the database.

A simple rule like "Every person has a parent" can trigger an infinite chain of inferences: Alice has a parent (let's call them $P_1$), who has a parent ($P_2$), and so on. This creates a fundamental problem: how do we answer queries or update knowledge bases when the underlying logical models are infinite?

The research direction across these papers focuses on semantic abstraction: the construction of finite, manageable structures that act as proxies for these infinite models. By identifying the "essential" parts of a model, researchers can perform complex reasoning tasks—like query answering and belief revision—without getting lost in an infinite recursion.

The Canonical Model as a Universal Proxy

The most powerful tool in this area is the canonical model (sometimes called a universal model). The intuition is that for many fragments of logic, such as the Horn-DLs used in the OWL 2 QL and EL profiles, there exists a single "least committed" model. If a query is true in this specific model, it is guaranteed to be true in all possible models of the knowledge base.

Charalampos Nikolaou, Ian Horrocks, and their colleagues demonstrate this in The Bag Semantics of Ontology-Based Data Access. They use a "chase" procedure—a step-by-step application of logical rules—to build a canonical model that captures the minimum multiplicities required for query answering. Similarly, Alessandro Artale and Frank Wolter show in First-Order Rewritability of Temporal Ontology-Mediated Queries that a single canonical model can represent all possible data instances even in complex temporal domains.

Collapsing Infinity into Types and Features

While canonical models are useful for query answering, they can still be unwieldy. A more radical form of abstraction is type semantics. Instead of tracking individual entities (Alice, $P_1, P_2$), we track the sets of properties (types) that those entities satisfy.

Zhe Wang, Kewen Wang, and Guilin Qi have pioneered this approach for knowledge base revision. In papers like DL-Lite Contraction and Revision, they replace infinite interpretations with finite sets of "features" or "types."

The intuition works like this: in a logic like DL-Lite, there are only a finite number of concept combinations possible. Even if there are infinite people in our "parent" chain, they eventually start looking the same logically. By mapping the infinite domain to a finite set of types, the authors transform a difficult description logic problem into a standard propositional logic problem. This allows them to apply classical belief revision techniques—deciding which rules to keep or discard when new data arrives—to ontologies that were previously computationally intractable.

Structural Proxies for Querying

For more expressive logics, the abstraction must be more sophisticated than simple types. Thomas Eiter, Diego Calvanese, and Magdalena Ortiz introduced completion forests in Data Complexity of Answering Unions of Conjunctive Queries in SHIQ. These are finite data structures that represent a collection of models by capturing the "core" data and the "patterns" of how the infinite parts of the model must behave.

This "pattern-based" reasoning is also central to determining query inseparability—the question of whether two different knowledge bases will always give the same answers to a user. Elena Botoeva and Roman Kontchakov use "finite generating structures" as computable proxies for the full semantic materialization of a knowledge base in When Are Description Logic Knowledge Bases Indistinguishable?.

Why It Works: The Boundary of Tractability

The reason these finite abstractions work is that most practical description logics are designed with the tree-model property. This means that if a set of rules has a model, it has one that looks like a tree. Because these trees are generated by a finite set of rules, they are highly repetitive.

Researchers like Adila Krisnadhi and Rafael Peñaloza exploit this regularity to build "polynomially-sized finite models" (Conjunctive Query Answering in Rough EL). They "cut" the infinite tree at a certain depth or "loop" it back on itself, creating a finite structure that still contains all the information needed to answer queries.

By shifting the focus from the infinite reality of the logic to these finite semantic summaries, this research direction enables efficient data integration, knowledge evolution, and automated reasoning in the face of incomplete and growing information.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 42 papers
  2. Version 1 · 2026-10-04 · 29 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_model_based_knowledge_representation_f2f6669a,
  title = {model-based knowledge representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/model-based-knowledge-representation/rdr_f2f6669a66c94fa9a2def17791c0d716},
  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_finite_representations_of_infinite_descr_f2f6669a_v1,
  title = {Finite Representations of Infinite Description Logic Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-representations-of-infinite-description-logic-models/rdr_f2f6669a66c94fa9a2def17791c0d716/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}