Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics
This work addresses gaps in the literature for query entailment in description logics, providing a unified approach that is incremental but with broad implications for the field.
The paper tackles the problem of worst-case optimal entailment of unions of conjunctive queries in locally-forward description logics by generalizing Lutz's spoiler technique, achieving ExpTime-completeness for querying in superlogics of ALC within ALCHbregQ.
We present a unified approach to (both finite and unrestricted) worst-case optimal entailment of (unions of) conjunctive queries (U)CQs in the wide class of "locally-forward" description logics. The main technique that we employ is a generalisation of Lutz's spoiler technique, originally developed for CQ entailment in ALCHQ. Our result closes numerous gaps present in the literature, most notably implying ExpTime-completeness of (U)CQ-querying for any superlogic of ALC contained in ALCHbregQ, and, as we believe, is abstract enough to be employed as a black-box in many new scenarios.