Circumscription is one of the main approaches for defining non-monotonic description logics (DLs). While the decidability and complexity of traditional reasoning tasks such as satisfiability of circumscribed DL knowledge bases (KBs) is well understood, for evaluating conjunctive queries (CQs) and unions thereof (UCQs), not even decidability had been established. In this paper, 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).
%0 Journal Article
%1 lutz2023querying
%A Lutz, Carsten
%A Manière, Quentin
%A Nolte, Robin
%D 2023
%I arXiv
%K Artificial_Intelligence_(cs.AI) Computational_Complexity_(cs.CC) FOS:_Computer_and_information_sciences Logic_in_Computer_Science_(cs.LO)
%R 10.48550/ARXIV.2306.04546
%T Querying Circumscribed Description Logic Knowledge Bases
%X Circumscription is one of the main approaches for defining non-monotonic description logics (DLs). While the decidability and complexity of traditional reasoning tasks such as satisfiability of circumscribed DL knowledge bases (KBs) is well understood, for evaluating conjunctive queries (CQs) and unions thereof (UCQs), not even decidability had been established. In this paper, 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).
@article{lutz2023querying,
abstract = {Circumscription is one of the main approaches for defining non-monotonic description logics (DLs). While the decidability and complexity of traditional reasoning tasks such as satisfiability of circumscribed DL knowledge bases (KBs) is well understood, for evaluating conjunctive queries (CQs) and unions thereof (UCQs), not even decidability had been established. In this paper, 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).},
added-at = {2024-10-02T13:52:45.000+0200},
archiveprefix = {arXiv},
author = {Lutz, Carsten and Manière, Quentin and Nolte, Robin},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/24d20b04f6237fc30ff43aafa836fb2de/scadsfct},
copyright = {Creative Commons Attribution Share Alike 4.0 International},
doi = {10.48550/ARXIV.2306.04546},
eprint = {2306.04546},
file = {:http\://arxiv.org/pdf/2306.04546v1:PDF},
interhash = {6d9a8b2b2557268ae7d0a3619170189c},
intrahash = {4d20b04f6237fc30ff43aafa836fb2de},
keywords = {Artificial_Intelligence_(cs.AI) Computational_Complexity_(cs.CC) FOS:_Computer_and_information_sciences Logic_in_Computer_Science_(cs.LO)},
month = jun,
primaryclass = {cs.AI},
publisher = {arXiv},
timestamp = {2024-10-02T13:52:45.000+0200},
title = {Querying Circumscribed Description Logic Knowledge Bases},
year = 2023
}