Revisiting Conjunctive Query Entailment for $\mathcal S$
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913100204081152 |
|---|---|
| author | Ibáñez-García, Yazmín Jung, Jean Christoph Michielini, Vincent Murlak, Filip |
| author_facet | Ibáñez-García, Yazmín Jung, Jean Christoph Michielini, Vincent Murlak, Filip |
| contents | We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic $\mathcal S$, the extension of $\mathcal{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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07933 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting Conjunctive Query Entailment for $\mathcal S$ Ibáñez-García, Yazmín Jung, Jean Christoph Michielini, Vincent Murlak, Filip Logic in Computer Science I.2.4; H.2.3 We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic $\mathcal S$, the extension of $\mathcal{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). |
| title | Revisiting Conjunctive Query Entailment for $\mathcal S$ |
| topic | Logic in Computer Science I.2.4; H.2.3 |
| url | https://arxiv.org/abs/2511.07933 |