Home » Publication » 19278

Dettaglio pubblicazione

2019, Proceedings of the 32nd International Workshop on Description Logics, Pages - (volume: 2373)

On queries with inequalities in DL-LiteR≠ (04b Atto di convegno in volume)

Cima G., Croce Federico, Lenzerini M., Poggi A., Toccacieli E.

It is well-known that answering conjunctive queries with inequalities (CQ≠s) over DL-LiteR ontologies is in general undecidable. In this paper we consider the subclass of CQ≠s, called CQ≠,bs, where inequalities involve only distinguished variables or individuals. In particular, we tackle the problem of answering C≠,bs and unions thereof (UC≠,bs s) over DL-LiteR≠ ontologies, where DL-LiteR≠ corresponds to DL-LiteR without the Unique Name Assumption, and with the possibility of asserting inequalities between individuals, as in OWL 2 QL. As a first contribution, we show that answering CQ≠,bs over DL-LiteR≠ ontologies has the same computational complexity as the UCQ case over DL-LiteR, i.e., it is in AC0 in data complexity, in PTIME in TBox complexity, and NP-complete in combined complexity. We then deal with the UCQ≠b case, and prove that answering UCQ=≠b over DL-LiteR≠ ontologies is still in AC0 in data complexity and in PTIME in TBox complexity, but is Π2p-hard in combined complexity.
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma