This extended abstract summarises our recent investigation on RDFS-based Knowledge Graphs (RKGs). Inspired by previous work on equipping DLs with a semantics adequate for metamodeling, we provide a formal semantics for RKGs based on classical logic. We show that, surprisingly, under the newly defined semantics, RKGs do not admit, in general, a universal model. Also, we introduce the notions of definite and indefinite RKGs and show that being definite is both a suficient and necessary condition for an RKG to admit a universal model, thus singling out the source of incompleteness that causes the lack of a universal model for indefinite RKGs. Finally, we characterize the complexity of the query answering problem for both definite and indefinite RKGs.
the RDFS standard semantics, also referred to as intensional semantics (see, e.g., [
Definition 1. Given a set of IRIs I, a set of IRIs R = {type, subClassOf, subPropertyOf, domain, range, Resource, Class, Property} ⊆ I, and a set of symbols B denoting blank nodes (we assume the symbols in B to start with “_"), an RKG is a set of triples of the form ⟨s p o⟩, where s,p,o ∈ I ∪ B.
Note that RKGs comprise a subset of the RDFS vocabulary, do not contain any literals, and possibly include blank nodes in predicate position.
Example 1. The following set of triples represents a valid RKG: {⟨_1 teachesTo Alice⟩, ⟨teachesTo range Student⟩, ⟨teachesTo domain Professor⟩, ⟨Professor subClassOf Person⟩, ⟨Professor type FacultyRole⟩, ⟨FacultyRole _2 Role⟩}.
The semantics of RKGs is defined by resorting to the notion of interpretation, where an interpretation ℐ for an RKG is a pair ⟨, · ℐ ⟩, where is called interpretation structure of ℐ, and · ℐ is the interpretation function of ℐ. In particular, is a triple ⟨∆ , · , · ⟩, such that ∆ is a non-empty set of objects, called the domain of ℐ, while · and · are partial functions. Intuitively, · (resp., · ) is defined for those domain objects that play the role of class (resp., property) in and determines their extension as a class (resp., property). The interpretation function maps every IRI appearing in a graph into an object in ∆ . All symbols from the set R are interpreted according to their intended set-theory meaning. As an example, (subClassOfℐ ) = {(1, 2)|1, 2 ∈ ∆ and 1 ⊆ 2 }. Blank nodes are dealt with by means of an assignment function ℐ such that, if is an IRI, then ℐ () = ℐ , while if is a blank node, then ℐ () = (for some ∈ ∆ ). We say that an interpretation ℐ for satisfies a triple ⟨ a b c ⟩ under ℐ , denoted (ℐ, ℐ ) |= ⟨ a b c ⟩, if ( ℐ (a), ℐ (c)) ∈ ℐ (b) . If an interpretation ℐ satisfies every triple of , denoted ℐ |= , ℐ is called a model of . We denote by () the set of models of . Definition 2. Let ℐ be an interpretation for an RKG with domain ∆ and be a query containing the set of IRIs I and the set of blank nodes B. A query homomorphism from to ℐ is a total function Ψ : I ∪B → ∆ , such that for every ∈ I, Ψ( ) = ℐ , and for every ⟨1 2 3⟩ ∈ , (Ψ( 1), Ψ( 3)) ∈ Ψ( 2) .
Intuitively, ℐ |= if and only if there exists a query homomorphism from to ℐ. Definition 3. An RKG entails a query , denoted |= , if there exists a query homomorphism from to ℐ for every ℐ ∈ ().
Analogously to what we have done in Definition 2, it is possible to define the notion of homomorphism from an interpretation ℐ to an interpretation . Also, as usual, we say that a model ℐ is a universal model of an RKG if, for every model of , there exists a homomorphism from ℐ to . Although RDFS is generally considered a “lightweight" language, and such languages typically admit a universal model that can be exploited for answering queries and for other reasoning tasks, we have the following surprising result.
Proposition 1. There exists an RKG such that no interpretation of is a universal model.
To illustrate the significance of the above result, consider the RKG = {⟨a R b⟩,⟨b R a⟩,⟨t type b⟩, ⟨a type Class⟩}, and the query : {⟨_x R _y⟩, ⟨_z type _y⟩,⟨_x subClassOf b⟩}. One can verify that entails , since in every model of it is possible to find an assignment satisfying the query. In particular, in every model of where the class is empty (which can be codified as being a subclass of every class in ), the assignment {_ ← ℐ , _ ← ℐ , _ ← ℐ } makes the query true, while in all models where is non-empty, the assignment {_ ← ℐ , _ ← ℐ , _ ← ℐ }, with being any instance of , does so. This shows that we have to reason by cases, since there exists no assignment for the variables , , which makes the query true in every model of . Note, indeed, that would not be entailed by if we adopted the standard SPARQL semantics based on the RDFS entailment regime.
The above case derives from a form of indefiniteness inherent to some RKGs. We singled out the source of such indefiniteness, and we defined two disjoint classes of RKGs, characterized by diferent properties. Intuitively, given an RKG and a class in , we say that is definite if either it contains instances in every model of or it is a subset of every class in . A class that is not definite is called indefinite . An analogous definition holds for definite and indefinite properties. A graph containing indefinite elements is an indefinite RKG.
Answering queries posed over definite RKGs can be done by means of the so-called chase procedure [16], which can be applied to RKGs and which allows one to obtain a structure from which it is possible to obtain a universal model for the given RKG, similarly to what happens for several lightweight ontology languages [17].
Proposition 2. Query entailment in definite RKGs can be done in polynomial time.
Since indefinite RKGs do not admit a universal model (see Proposition 1), for such RKGs query entailment requires using techniques based on reasoning by cases. The algorithm that we propose works as follows. Given an indefinite RKG , it guesses a set of indefinite classes and properties, and it generates a new RKG ′ (called a completion of ) obtained from by making each guessed class and property definite by providing them with new instances, while the non-guessed ones are made definite by adding triples that make them subsets of every class and every property, respectively. By guessing all possible combinations of indefinite classes and properties, query entailment for an RKG and a query can be solved by checking if there exists at least one completion that makes the query false. If that is the case, then we can conclude that ̸|= . On the contrary, if such a graph does not exist, then we can conclude that |= . Thus, it is possible to solve the query entailment problem for general RKGs in Π 2 with respect to the size of the entire input. By means of a reduction from the satisfiability problem for 2-QBF formulas, we also provide a matching lower bound for the query entailment problem.
Future developments of the framework proposed in this paper ideally involve the use of epistemic logic, as a tool to capture diferent interpretations for the semantics of queries [ 18], and the extension of both the graph and the query languages with forms of negation [19, 20, 21].
This work has been supported by MUR under the PNRR project FAIR (PE0000013). This work has been carried out while Roberto Maria Delfino was enrolled in the Italian National Doctorate on Artificial Intelligence run by Sapienza University of Rome.
During the preparation of this work, the author(s) used OpenAI ChatGPT-4 in order to: Grammar and spelling check; Paraphrase and reword. After using these tool(s)/service(s), the author(s) reviewed and edited the content as needed and take(s) full responsibility for the publication’s content. [12] S. Munoz, J. Pérez, C. Gutierrez, Simple and eficient minimal RDFS, Journal of web semantics 7 (2009) 220–234. [13] F. Goasdoué, I. Manolescu, A. Roatiş, Eficient query answering against dynamic RDF databases, in: Proceedings of the 16th International Conference on Extending Database Technology, 2013, pp. 299–310. [14] M. W. Chekol, J. Euzenat, P. Genevès, N. Layaïda, SPARQL query containment under RDFS entailment regime, in: International Joint Conference on Automated Reasoning, Springer, 2012, pp. 134–148. [15] M. Buron, F. Goasdoué, I. Manolescu, M.-L. Mugnier, Reformulation-based query answering for RDF graphs with RDFS ontologies, in: The Semantic Web: 16th International Conference, ESWC 2019, Portorož, Slovenia, June 2–6, 2019, Proceedings 16, Springer, 2019, pp. 19–35. [16] S. Greco, C. Molinaro, F. Spezzano, Incomplete Data and Data Dependencies in Relational Databases, Synthesis Lectures on Data Management, Morgan & Claypool Publishers, 2012. URL: https://doi. org/10.2200/S00435ED1V01Y201207DTM029. doi:10.2200/S00435ED1V01Y201207DTM029. [17] D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Tractable reasoning and eficient query answering in description logics: The DL-Lite family, Journal of Automated reasoning 39 (2007) 385–429. [18] R. Fagin, J. Y. Halpern, Y. Moses, M. Vardi, Reasoning about knowledge, MIT press, 2004. [19] V. Gutiérrez-Basulto, Y. A. Ibáñez-García, R. Kontchakov, E. V. Kostylev, Queries with negation and inequalities over lightweight ontologies 35 (2015) 184–202. [20] G. Cima, M. Lenzerini, A. Poggi, Answering conjunctive queries with inequalities in DL-Lite, 2020, pp. 2782–2789. [21] G. Cima, M. Console, R. M. Delfino, M. Lenzerini, A. Poggi, Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases, Proceedings of the AAAI Conference on Artificial Intelligence 39 (2025) 14824–14831. URL: https://ojs.aaai.org/index.php/AAAI/article/ view/33625. doi:10.1609/aaai.v39i14.33625.