Séminaire de Quentin Manière, Department of Computer Science, ScaDS.AI, Leipzig University, Germany
Querying Circumscribed Description Logic Knowledge Bases2 nov. 2023 - 14:00
Circumscription is one of the main approaches for defining non-monotonic description logics (DLs) and the decidability and complexity of traditional reasoning tasks, such as satisfiability of circumscribed DL knowledge bases (KBs), are well understood. For evaluating conjunctive queries (CQs) and unions thereof (UCQs), in contrast, not even decidability has been established. In our paper at KR this year, we prove decidability of (U)CQ evaluation on circumscribed DL KBs and obtain a rather complete picture of both the combined complexity and the data complexity for DLs ranging from ALCHIO via EL to various versions of DL-Lite. We also study the much simpler atomic queries (AQs).