TY - JOUR
AU - Cima, Gianluca
AU - Lenzerini, Maurizio
AU - Poggi, Antonella
PY - 2020/04/03
Y2 - 2024/02/28
TI - Answering Conjunctive Queries with Inequalities in <em>DL-Lite</em><sub>ℛ</sub>
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 03
SE - AAAI Technical Track: Knowledge Representation and Reasoning
DO - 10.1609/aaai.v34i03.5666
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5666
SP - 2782-2789
AB - <p>In the context of the Description Logic <em>DL-Lite</em><sub>ℛ</sub><sup>≠</sup>, i.e., <em>DL-Lite</em><sub>ℛ</sub> without UNA and with inequality axioms, we address the problem of adding to unions of conjunctive queries (UCQs) one of the simplest forms of negation, namely, inequality. It is well known that answering conjunctive queries with unrestricted inequalities over <em>DL-Lite</em><sub>ℛ</sub> ontologies is in general undecidable. Therefore, we explore two strategies for recovering decidability, and, hopefully, tractability. Firstly, we weaken the ontology language, and consider the variant of <em>DL-Lite</em><sub>ℛ</sub><sup>≠</sup> corresponding to <span style="font-variant: small-caps;">rdfs</span> enriched with both inequality and disjointness axioms. Secondly, we weaken the query language, by preventing inequalities to be applied to existentially quantified variables, thus obtaining the class of queries named UCQ<sup>≠,<i>b</i></sup>s. We prove that in the two cases, query answering is decidable, and we provide tight complexity bounds for the problem, both for data and combined complexity. Notably, the results show that answering UCQ<sup>≠,<i>b</i></sup>s over <em>DL-Lite</em><sub>ℛ</sub><sup>≠</sup> ontologies is still in AC<sup>0</sup> in data complexity.</p>
ER -