Answering Expressive Conjunctive Queries over RDFS Knowledge Bases (Extended Abstract)

Answering conjunctive queries (CQs) equipped with basic forms of negation is a challenging task, which happens to be undecidable even for lightweight Description Logic (DL) ontologies. Interestingly, the DL counterpart of RDFS seems to be partially unaffected by those negative results, even when equipped with disjointness axioms. This paper summarises our recent work on this subject, where we present a refined complexity analysis of answering CQs with inequality atoms and safe negation posed over such ontologies. We introduce a unified Π𝑝2 algorithm for the general case; we prove that two inequality atoms already lead to Π𝑝2-hardness, and we show similar results for the case of safe negation: answering CQs with one negated atom is in NP, but two negated atoms are enough to reach Π𝑝2 -hardness. These results close key gaps in the literature and refine the complexity analysis of the query containment problem.