💻 computer science

Partially Finite Model Reasoning in Description Logics Extended Version

This paper introduces the concept of partially finite models in description logics to harmonize finite and infinite reasoning, proving that conjunctive query entailment for the logic S with a distinguished finite concept is decidable in 2-EXPTIME and demonstrating its application to query containment with closed predicates.

Original authors: Tomasz Gogacz, Filip Murlak, Marcin Przybyłko, Alexandra Rogova, Michał Skrzypczak

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tomasz Gogacz, Filip Murlak, Marcin Przybyłko, Alexandra Rogova, Michał Skrzypczak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery based on a set of clues (a Knowledge Base). Usually, when detectives work, they assume the world could be infinite. There could be an endless chain of suspects, an infinite number of alibis, and a never-ending timeline. This is called infinite model reasoning.

However, in the real world (like in a database or a specific case file), things are finite. You only have a limited number of people, a limited number of rooms, and a limited number of events. This is finite model reasoning.

The problem is that for some complex logic systems (specifically a type called Description Logics, or DLs), the answer to a question can change depending on whether you assume the world is infinite or finite. Sometimes, a clue proves a suspect is guilty in an infinite world, but in a finite world, the suspect is innocent because the "infinite chain" of evidence can't physically exist.

The New Idea: "Partially Finite" Reasoning

This paper introduces a middle ground called Partially Finite Model Reasoning.

Think of it like a detective who says: "I don't care if the rest of the universe is infinite, but I know for a fact that the suspects in this specific room must be a finite group."

In technical terms, the researchers give the system a "distinguished concept" (let's call it the "Finite Room"). They ask: "Does this query hold true in every possible scenario, as long as the people in the 'Finite Room' are a limited number?"

This is a hybrid approach. It keeps the flexibility of infinite worlds for most things but respects the hard limits of the real world for the specific parts that matter (like a closed list of employees or a fixed set of devices).

The Core Challenge: The "Infinite Chain" Trap

The paper uses a logic system called S (an extension of a basic logic called ALC) to test this. In this system, you can have rules that create infinite chains.

The Analogy:
Imagine a rule that says: "Every person in the 'Finite Room' must point to a 'Next Person', and that Next Person must point to another, forever."

In an infinite world: This is easy. You just keep adding new people forever.
In a finite world: You eventually run out of people. You have to loop back or merge people.

The tricky part is how you merge them.

Option A: Merge everyone into one single person. (This might accidentally make a query true that shouldn't be).
Option B: Merge people based on who they are connected to. (This is harder to calculate).

The paper shows that finding the "right" way to merge these infinite chains into a finite structure—without accidentally creating false answers—is incredibly complex.

The Solution: "Surgery" on the Model

The authors developed a sophisticated method to solve this, which they call "infinite model surgery."

Imagine you have a giant, tangled ball of yarn representing an infinite world. You need to cut it down to a manageable size, but you must keep the "Finite Room" small and ensure you don't accidentally tie two knots that shouldn't be tied.

Quasi-Unravelling: They take the infinite tangle and "unravel" it into a tree-like structure. However, they are careful not to duplicate the "Finite Room" people. If a person is in the Finite Room, they only get one copy. If they are outside, they can have many copies (like branches on a tree).
Elementary Interpretations: They build a special, compact "blueprint" (called an elementary interpretation) that represents these complex trees. It's like a schematic diagram that captures all the necessary connections without needing infinite space.
The "Blow-Up" Trick: To check if a query is true or false, they temporarily "blow up" the loops in their blueprint, making them huge. This helps them see if a query would work in a finite setting without getting stuck in an infinite loop.

The Result: How Hard Is It?

The paper proves that solving this "Partially Finite" problem is 2-ExpTime-complete.

What does that mean in plain English?
It means the problem is very hard (it takes a lot of computing power), but it is solvable.

It is just as hard as solving the problem for purely infinite worlds.
It is just as hard as solving it for purely finite worlds.
Crucially: Adding this "partially finite" constraint does not make the problem harder than it already was. You don't pay an extra "complexity tax" for this hybrid approach.

Real-World Application Mentioned

The paper mentions one specific application: Query Containment with Closed Predicates.

The Analogy:
Imagine you have two search queries. You want to know: "If I run Query A, will I always get a subset of the results from Query B?"
Usually, this assumes an open world (anything could exist). But sometimes, you want to assume a "Closed World" for certain things (e.g., "The list of employees is complete; no other employees exist").

The paper shows that you can solve this "Closed World" problem by turning it into a "Partially Finite" problem. If you can solve the partially finite version, you can solve the closed-predicate version.

Summary

The paper introduces a new way to reason about data that mixes infinite possibilities with finite reality. They proved that for a specific type of logic, this new method is just as computationally expensive as the old methods (very hard, but doable) and provides a powerful tool for handling "closed" lists of data in complex databases. They did this by inventing a way to surgically cut down infinite models into finite, manageable blueprints without losing the truth of the data.

1. Problem Statement

The paper addresses the gap between infinite model reasoning (standard in Description Logics, where models can be arbitrarily large) and finite model reasoning (standard in databases, where domains are finite). While many Description Logics (DLs) exhibit finite controllability (where query entailment is the same for finite and infinite models), others, such as $\mathcal{S}$ (an extension of $\mathcal{ALC}$ with transitive roles), do not. In these logics, a query might be entailed in all finite models but not in infinite ones, or vice versa.

The authors introduce Partially Finite Model Reasoning. In this hybrid mode:

A Knowledge Base (KB) is given along with a distinguished concept $F$ .
The reasoning task considers only models where the interpretation of $F$ is a finite set of individuals.
The rest of the model (elements not in $F$ ) may be infinite.
Goal: Decide if a Conjunctive Query (CQ) $Q$ is entailed by the KB under the constraint that $F$ is finite (denoted $K \models_F Q$ ).

This framework generalizes both standard entailment (where no concept is restricted) and finite entailment (where the entire domain is restricted). It also serves as a theoretical foundation for query containment with closed predicates, where certain predicates are assumed to have finite extensions.

2. Methodology

The authors develop a sophisticated proof technique to decide partially finite entailment for the logic $\mathcal{S}$ . The methodology involves several key steps:

A. Quasi-Unravelling

To handle infinite models while keeping the "finite" part ( $F$ ) manageable, the authors introduce quasi-unravelling.

Unlike standard unravelling (which creates a tree by duplicating every node), quasi-unravelling creates a tree-like structure where critical elements (those in $F$ ) are not duplicated.
Only non-critical elements are duplicated along paths. This ensures the resulting structure has a finite set of critical nodes, preserving the "partially finite" property while allowing the rest of the model to be tree-like for easier analysis.

B. Elementary Interpretations

The authors define a class of finite structures called elementary interpretations to serve as finite representations of potential countermodels. These are built hierarchically:

Singletons/Cycles/Critical Clusters: Basic building blocks.
Loop Trees: Trees formed by attaching loop trees to singletons or cycles (similar to cactuses).
Elementary Interpretations: Trees constructed by attaching loop trees and critical clusters.
The core insight is that any countermodel can be transformed into an elementary interpretation via quasi-unravelling without losing the property of being a countermodel.

C. Coloured Blocking and Quotients

To handle multiple transitive roles and ensure the existence of a finite countermodel with the required properties, the paper adapts the Coloured Blocking Theorem.

They define a $k$ -sparse coloring of critical elements.
Using an equivalence relation based on $k$ -neighbourhoods, they construct a quotient interpretation.
They prove that if a query is not satisfied in the original infinite model, it is also not satisfied in the quotient (which is partially finite), provided the coloring is sparse enough.

D. The "Blow-Up" and Decidability

To make the problem decidable, the authors replace the condition "the quasi-unravelling does not satisfy $Q$ " with a checkable condition on a blown-up version of the elementary interpretation ( $G_n$ ).

They "blow up" cycles in the elementary interpretation to length $2n+1$ (where $n$ is the number of variables in the query).
They prove that checking if the blown-up structure $G_n$ satisfies the query is equivalent to checking the quasi-unravelling for queries of size $n$ .
This allows the use of a type-elimination procedure (similar to automata-based approaches) to search for a witness (a countermodel) within a doubly exponential search space.

3. Key Contributions

Formalization of Partially Finite Reasoning: The paper initiates the systematic study of reasoning where only specific parts of a model are constrained to be finite.
Complexity Result for $\mathcal{S}$ : The authors prove that Partially Finite Query Entailment for $\mathcal{S}$ is 2-ExpTime-complete.
- This matches the complexity of both standard infinite entailment and finite entailment for $\mathcal{S}$ , showing that the hybrid mode does not increase computational complexity.
Novel Proof Techniques: The solution involves "infinite model surgery," combining quasi-unravelling, elementary interpretations, and coloured blocking in a way that goes beyond simply combining arguments for the finite and infinite cases.
Application to Closed Predicates: The paper demonstrates that query containment in the presence of closed predicates can be reduced to partially finite entailment. This provides a new complexity upper bound for the closed predicate problem in expressive DLs.

4. Results

Main Theorem (Theorem 16): Partially finite entailment of conjunctive queries for the logic $\mathcal{S}$ is 2-ExpTime-complete.
Witness Characterization: If a KB does not partially finite entail a query, there exists a "piecewise elementary" interpretation of bounded size (exponential in the KB size) whose quasi-unravelling serves as a countermodel.
Reduction: Query containment with closed predicates is solvable in Nondeterministic Polynomial Time (NP) given an oracle for partially finite entailment.

5. Significance

Bridging Theory and Practice: The work bridges the gap between the theoretical richness of infinite models (needed for expressive logics) and the practical constraints of finite domains (needed for database applications).
Handling Closed Predicates: Closed predicates (where the extension of a concept is known and finite) are crucial for database integration and ontology-mediated query answering. This paper provides a rigorous complexity-theoretic foundation for reasoning with them in expressive logics like $\mathcal{S}$ .
Scalability Insights: The complexity result (2-ExpTime) suggests that while the problem is hard, it is not undecidable, and the upper bounds align with existing systems (like SUMA) that use partial materialization strategies.
Future Directions: The authors suggest extending these techniques to other logics lacking finite controllability (e.g., $\mathcal{ALCIF}$ ) and other reasoning tasks like query containment and enumeration.

In summary, the paper successfully establishes that reasoning with "partially finite" constraints is computationally feasible and provides the necessary model-theoretic machinery to handle the divergence between finite and infinite models in expressive Description Logics.