RDFS Knowledge Graphs Through the Lens of Logic: Semantics and Query Answering

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.