In the context of the Description Logic DL-Liteℛ≠, i.e., DL-Liteℛ 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 DL-Liteℛ 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 DL-Liteℛ≠ corresponding to RDFS 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≠,bs. 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≠,bs over DL-Liteℛ≠ ontologies is still in AC0 in data complexity.

Answering Conjunctive Queries with Inequalities in DL-Lite(R) / Cima, Gianluca; Lenzerini, Maurizio; Poggi, Antonella. - (2020), pp. 2782-2789. (Intervento presentato al convegno 34th AAAI Conference on Artificial Intelligence, AAAI 2020 tenutosi a New York; USA) [10.1609/aaai.v34i03.5666].

Answering Conjunctive Queries with Inequalities in DL-Lite(R)

Gianluca Cima
;
Maurizio Lenzerini;Antonella Poggi
2020

Abstract

In the context of the Description Logic DL-Liteℛ≠, i.e., DL-Liteℛ 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 DL-Liteℛ 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 DL-Liteℛ≠ corresponding to RDFS 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≠,bs. 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≠,bs over DL-Liteℛ≠ ontologies is still in AC0 in data complexity.
2020
34th AAAI Conference on Artificial Intelligence, AAAI 2020
ontologies; description logics; conjunctive query; inequalities; computational complexity
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Answering Conjunctive Queries with Inequalities in DL-Lite(R) / Cima, Gianluca; Lenzerini, Maurizio; Poggi, Antonella. - (2020), pp. 2782-2789. (Intervento presentato al convegno 34th AAAI Conference on Artificial Intelligence, AAAI 2020 tenutosi a New York; USA) [10.1609/aaai.v34i03.5666].
File allegati a questo prodotto
File Dimensione Formato  
Lenzerini_Answering-conjunctive-queries.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 540.35 kB
Formato Adobe PDF
540.35 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1422634
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact