Revisiting Conjunctive Query Entailment for S

Proceedings of the AAAI Conference on Artificial Intelligence 2026 Open access

Read full text
Authors: Yazmín Angélica Ibáñez-García, Jean Christoph Jung, Vincent Michielini, Filip Murlak
DOI: 10.1609/aaai.v40i23.38989
Cited by: 0

Abstract

We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic S, the extension of ALC with transitive roles. Contrary to what existing partial results suggested, we show that the problem is, in fact, 2ExpTime-complete; hardness already holds in the presence of two transitive roles and for Boolean conjunctive queries. We complement this result by showing that the problem remains in coNExpTime when the input query is rooted or is restricted to use at most one transitive role (but may use arbitrarily many non-transitive roles).

Fields of Study & Subjects

Semantic Web and Ontologies Logic Reasoning and Knowledge Advanced Database Systems and Queries

Publication details

Journal / source
Proceedings of the AAAI Conference on Artificial Intelligence
Volume
40
Issue
23
Pages
19152–19159
Publication date
14 March 2026
Language
EN