Department of Computer, Control and Management Engineering

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.