Expressing negative conditions is a crucial feature of query languages for knowledge bases (KBs). Answering such queries over ontological KBs, however, is a very challenging task that becomes undecidable even for lightweight Description Logic (DL) ontologies. Such negative results hold even for Conjunctive Queries (CQs) equipped with basic forms of negative conditions such as the so-called safe negation or inequality atoms. One ontology language that is seemingly unaffected by these results is (the DL counterpart of) RDFS even if equipped with disjointness axioms. Answering CQs with inequalities over such ontologies is known to be Pi^p_2-complete, if the number of inequality atoms is unbounded, and NP-complete if we limit this number to one. Notably, these results leave open the cases of CQs with a fixed number greater than two of inequality atoms. Additionally, such a thorough analysis is missing for CQs with safe negation. In this paper, we embark in a refined analysis of the combined complexity of answering CQs with inequality atoms and safe negation over RDFS ontologies augmented with disjointness axioms. Firstly, we provide a unified Pi^p_2 query answering algorithm for the general problem. Secondly, we confirm the generally held conjecture according to which answering CQs with two inequality atoms over such ontologies is already Pi^p_2-hard. This result closes an important gap in the current literature and has an impact on the widely influential problem of query containment. Lastly, for CQs with safe negation, we prove a behavior similar to that of CQs with inequality atoms. Specifically, we show that answering CQs with at most one negated atom can be done in NP, while allowing at most two negated atoms is sufficient to obtain Pi^p_2-hardness.

We propose a semantic characterization for a simple and yet sufficiently expressive kind of Knowledge Graphs based on RDFS, which we call RKGs. In doing so, we address some of the issues deriving from the standard RDFS semantics and then proceed by defining a semantics for RKGs based on formal logic which is also able to properly capture the metamodeling capabilities of RDFS. We prove that RKGs, in general, do not exhibit a universal model, and thus query answering cannot rely on the well-known techniques based on the use of it. Then, by highlighting the connection between the lack of a universal model for an RKG and the presence of a form of indefiniteness in its elements, we introduce the class of definite RKGs, and prove that definiteness is both a sufficient and necessary condition for an RKG to admit a universal model. Also, based on such result, we propose an algorithm for query answering for both definite and general RKGs and we characterize the computational complexity for the two cases.