How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC

Bartosz BednarczykBartosz Bednarczyk, Sebastian RudolphSebastian Rudolph

Bartosz Bednarczyk, Sebastian Rudolph
How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC
Journal of Artificial Intelligence Research, 78:385–458, November 2023

Details
Bibtex

KurzfassungAbstract
It is commonly known that the conjunctive query entailment problem for certain ex- tensions of (the well-known ontology language) ALC is computationally harder than their knowledge base satisfiability problem while for others the complexities coincide, both under the standard and the finite-model semantics. We expose a uniform principle behind this divide by identifying a wide class of (finitely) locally-forward description logics, for which we prove that (finite) query entailment problem can be solved by a reduction to exponentially many calls of the (finite) knowledge base satisfiability problem. Consequently, our algorithm yields tight ExpTime upper bounds for locally-forward logics with ExpTime-complete knowledge base satisfiability problem, including logics between ALC and μALCHbregQ (and more), as well as ALCSCC with global cardinality constraints, for which the complexity of querying remained open. Moreover, to make our technique applicable in future research, we provide easy-to-check sufficient conditions for a logic to be locally-forward based on several novel versions of the model-theoretic notion of unravellings. Together with existing results, this provides a nearly complete classification of the “benign” vs. “malign” primitive modelling features extending ALC, missing out only the Self operator. We then show a rather surprising result, namely that the conjunctive entailment problem for ALCSelf is exponentially harder than for ALC. This places the seemingly innocuous Self operator among the “malign” modelling features, like inverses, transitivity or nominals.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@article{BR2023,
  author  = {Bartosz Bednarczyk and Sebastian Rudolph},
  title   = {How to Tell Easy from Hard: Complexities of Conjunctive Query
             Entailment in Extensions of {ALC}},
  journal = {Journal of Artificial Intelligence Research},
  volume  = {78},
  year    = {2023},
  month   = {November},
  pages   = {385{\textendash}458},
  doi     = {https://doi.org/10.1613/jair.1.14482}
}