# Finite Query Answering in Expressive Description Logics with Transitive Roles

arXiv: https://arxiv.org/abs/1808.03130 · HTML: https://mlsanity.com/paper/1808.03130/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2018.

## Built on by (most cited first, 4 of 4)

- [Fitting Description Logic Ontologies to ABox and Query Examples](https://mlsanity.com/paper/2508.08007/) (2025)
- [On the complexity of finding set repairs for data-graphs](https://mlsanity.com/paper/2206.07504/) (2022)
- [Finite Entailment of UCRPQs over ALC Ontologies](https://mlsanity.com/paper/2204.14261/) (2022)
- [Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models](https://mlsanity.com/paper/2604.26976/) (2026)

## Abstract (arXiv)

We study the problem of finite ontology mediated query answering (FOMQA), the variant of OMQA where the represented world is assumed to be finite, and thus only finite models of the ontology are considered. We adopt the most typical setting with unions of conjunctive queries and ontologies expressed in description logics (DLs). The study of FOMQA is relevant in settings that are not finitely controllable. This is the case not only for DLs without the finite model property, but also for those allowing transitive role declarations. When transitive roles are allowed, evaluating queries is challenging: FOMQA is undecidable for SHOIF and only known to be decidable for the Horn fragment of ALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI, SOF, and SIF. Our approach is to characterise models relevant for deciding finite query entailment. Relying on a certain regularity of these models, we develop automata-based decision procedures with optimal complexity bounds.