The Expressivity Frontier in Description Logics

17 concepts18 papers1 proposal

Description Logics (DLs) serve as the formal foundation for knowledge representation, powering everything from the Semantic Web to complex biomedical ontologies. They allow us to model domains using concepts (classes of objects) and roles (binary relationships between objects). However, DL research is caught in a perpetual tug-of-war between expressivity (what the logic can say) and computational complexity (how hard it is to reason over what is said).

Lightweight DLs, such as the $\mathcal{EL}$ and $\mathcal{ALC}$ families, are computationally well-behaved. They allow for fast reasoning, polynomial-time query answering, and clean geometric representations. But real-world knowledge is messy. It demands richer constructs—such as negation, disjunction, nominals (enumerated individuals), and role hierarchies—found in highly expressive description logics like $\mathcal{SHIQ}$ or $\mathcal{SHOIQ}$ (which underpin the OWL 2 standard).

When researchers try to migrate successful reasoning, optimization, or learning techniques from lightweight families to these highly expressive description logics, they hit a wall. Algorithms break down, foundational logical properties vanish, and problems frequently cross the threshold into undecidability.

The Complexity Wall in Querying and Containment

To understand why extending these frameworks is difficult, consider Ontology-Mediated Query Answering (OMQA), where database queries are enriched with ontological knowledge. In lightweight logics, querying is highly predictable. Carsten Lutz et al. established a complete classification of query complexity in the $\mathcal{EL}$ description logic in A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL. They demonstrated a clean trichotomy ($\text{AC}^0$, $\text{NL}$-complete, $\text{PTIME}$-complete) corresponding directly to whether a query can be rewritten into first-order logic, linear Datalog, or monadic Datalog.

In $\mathcal{EL}$, queries can be rewritten cleanly because the logic lacks disjunction and negation, preventing complex case-analyses. However, the authors note that extending this elegant classification to more expressive logics like $\mathcal{ALC}$ or $\mathcal{SHIQ}$ remains a major open challenge. Once a logic allows disjunction, a query might be true across a combination of possibilities without being true in any single one, forcing the reasoner to explore an exponential or double-exponential space of models.

When we step fully into expressive description logics, the computational cost of managing these queries skyrockets. Pierre Bourhis analyzed query containment—determining if one query's results are always a subset of another's—across expressive DLs like $\mathcal{ALC}$, $\mathcal{ALCI}$, and $\mathcal{SHI}$ in Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics, proving that the problem becomes 2NEXPTIME-complete. This extreme complexity underscores why optimization techniques designed for simpler profiles cannot easily scale upward.

The Breakdown of Logical and Structural Properties

Beyond raw complexity, expressive DLs frequently lose fundamental logical properties that computer scientists rely on to build clean engineering tools.

Interpolation and Definability

Take Craig interpolation and Beth definability—properties that guarantee that if a concept definition is implicitly implied by an ontology, we can extract an explicit, readable definition for it. Alessandro Artale et al. explored this in Living Without Beth and Craig: Definitions and Interpolants in Description Logics with Nominals and Role Inclusions. They showed that when nominals (names for specific individuals) and role inclusions are introduced to $\mathcal{ALC}$ variants, these classical properties completely fail. While the authors prove that finding definitions remains decidable, extending these insights to full OWL 2 standards ($\mathcal{SHOIQ}$) introduces severe computational hurdles because the structural patterns used to build interpolants break down.

Non-Monotonic Reasoning

Non-monotonic reasoning mechanisms like circumscription—which allows for default reasoning and exceptions (e.g., "birds fly, unless they are penguins")—face similar barriers. Carsten Lutz et al. investigated this integration in The Complexity of Circumscription in DLs. They demonstrated that while circumscription is decidable for simpler DLs, it instantly collapses into high undecidability if role names are fixed in expressive DLs. The authors note that handling finite model property issues in even richer logics like $\mathcal{SHIQ}$ remains an unsolved problem.

Dynamic Verification

Even dynamic verification suffers from this expressivity barrier. Diego Calvanese et al. built a decidable $\text{PSPACE}$ framework for verifying safety properties in Ontology-Based Processes (OBPs) in SMT Safety Verification of Ontology-Based Processes. However, their framework is strictly tailored to RDFS. The authors highlighted that moving to more expressive logics like DL-Lite introduces translation challenges, shifting from logical equivalence to weaker equisatisfiability properties, which complicates backward reachability analysis.

Engineering Bottlenecks: Modularization and Repair

In practical applications, managing massive ontologies requires breaking them down into smaller, logically sound pieces called "deductive modules" to allow for localized reasoning and reuse.

For simpler logics, module extraction is highly efficient. Hui Yang et al. developed the ForMod method to extract concise modules from $\mathcal{EL}$ ontologies in Efficient Extraction of EL-Ontology Deductive Modules, and the authors extended general module computation to $\mathcal{ALC}$ ontologies in Efficient Computation of General Modules for ALC Ontologies. Yet, both works acknowledge that generalizing these techniques to highly expressive description logics remains an open question.

[ Lightweight DLs: EL / ALC ] ───> Exact Uniform Interpolation is Decidable (Finite Modules)
                                       │
                                       ▼ (Adding Nominals, Role Inclusions, Negation)
                                       │
[ Expressive DLs: SHIQ / SROIQ ] ──> Uniform Interpolation can become Undecidable (Requires Approximations)

The reason for this barrier lies in uniform interpolation, the mathematical engine behind module extraction. Uniform interpolation requires eliminating specific symbols from an ontology while preserving all logical entailments among the remaining symbols. In simple logics, the resulting structures remain finite and decidable. However, as Patrick Koopmann et al. observe in Deductive Module Extraction for Expressive Description Logics, moving past basic extensions like $\mathcal{ALCH}$ causes deductive modules to become completely undecidable, requiring a shift away from exact logical preservation toward complex, lossy approximations.

A similar bottleneck appears when optimizing query performance or fixing reasoning gaps. Wafaa EL HUSSEINI et al. introduced ABox summaries to prune query paths in Ontology-mediated query answering: performance challenges and advances, but the technique is strictly limited to the lightweight DL-Lite family. To bridge the gap between fast, incomplete reasoners and heavy-duty OWL 2 DL reasoners, Giorgos Stoilos et al. proposed "repairing" ontologies by adding optimized axioms in Repairing Ontologies for Incomplete Reasoners. However, their framework is optimized for the restricted OWL 2 RL profile, leaving repairs for fully expressive DLs as an open challenge.

The Representation Gap in Learning and Embeddings

The expressivity wall is not unique to symbolic reasoning; it equally constrains modern neuro-symbolic and machine learning approaches to knowledge representation.

Consider geometric ontology embeddings, which map logical concepts to geometric regions (like spheres or boxes) in Euclidean space to predict missing links or protein-protein interactions. Maxat Kulmanov et al. designed geometric constructions specifically for $\mathcal{EL}^{++}$ in EL Embeddings: Geometric Construction of Models for the Description Logic EL++, where conjunction is modeled as the intersection of spatial regions and existential quantification is modeled as a spatial transformation. Similarly, Hui Yang et al. introduced TransBox to model complex many-to-many relationships within $\mathcal{EL}^{++}$-closed ontologies in TransBox: $\mathcal{EL}^{++}$-closed Ontology Embedding.

Geometric Embeddings (Convex Regions):
  Conjunction (A ⊓ B) ───> Intersection of Regions (Easy)
  Negation (¬A)        ───> Spatial Complement (Breaks Convexity)
  Disjunction (A ⊔ B)  ───> Spatial Union (Non-convex, breaks geometric guarantees)

Both sets of authors explicitly note that their geometric paradigms cannot yet accommodate the richer constructs of expressive DLs. Modeling negation requires representing the entire complement of a region, and disjunction requires non-convex unions. These constructs break the geometric guarantees of simple convex spaces, creating a fundamental mathematical barrier to scaling embeddings upward.

In inductive learning, Caglar Demir et al. leveraged deep Q-learning (DRILL) to accelerate class expression learning in Neuro-Symbolic Class Expression Learning, but their evaluation was restricted to $\mathcal{ALC}$. To achieve broader applicability, the framework must be extended to handle the intricate, highly expressive constructs of $\mathcal{SROIQ}$.

Even probabilistic extensions struggle to scale. Ismail Ilkan Ceylan et al. successfully combined Bayesian networks with description logics to handle uncertainty in The Bayesian Description Logic ${\mathcal{BEL}}$, but the underlying logic is strictly bounded by the limited expressiveness of $\mathcal{EL}$.

Moving Forward

The overarching challenge across all these facets—from database integration to neuro-symbolic learning—is that expressive description logics break the assumptions of local, monotonic, or structurally uniform reasoning. As early noted by the authors of What Can Knowledge Representation Do for Semi-Structured Data?, while expressive DLs are necessary to capture complex constraints, extending reasoning frameworks to handle general theories remains an open question. Similarly, Martín Rezk proposed a semantics to unify production rule systems with ontologies in Combining Production Systems and Ontologies, but demonstrated it only on $\mathcal{ALC}$, leaving the challenges of more expressive DLs for future work.

The frontier of Description Logic research lies not just in inventing new algorithms for isolated logic profiles, but in finding ways to generalize modularization, approximation, and geometric representation so they can withstand the immense computational pressure of fully expressive description logics.

Key Foundational Work

Non-Standard Reasoning Services for the Debugging of Description Logic Terminologies (2003) — contributed 1 concept elements to this direction.
What Can Knowledge Representation Do for Semi-Structured Data? (1998) — 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_expressivity_limitations_2518ae5c,
  title = {expressivity limitations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-limitations/rdr_2518ae5c9e6245799d97028e1eaaefad},
  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_expressivity_limitations_2518ae5c_v1,
  title = {expressivity limitations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-limitations/rdr_2518ae5c9e6245799d97028e1eaaefad/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