Logical reconstruction of RDFS knowledge graphs

Knowledge graphs are a central tool in Artificial Intelligence, data management, and the Semantic Web. Their relevance stems from their dual nature: on the one hand, they are graph-shaped mathematical structures, whose topology supports flexible representation, navigation, and pattern-based querying; on the other hand, their nodes and edges carry semantic information intended to represent entities, classes, properties, and relationships. This ability to combine structural and semantic aspects allows knowledge graphs to play a bridging role between different research areas, including databases, the Semantic Web, and Knowledge Representation and Reasoning. Knowledge graphs can be seen under different perspectives, each emphasizing a different aspect of their nature. From the graph database perspective, a knowledge graph is primarily an explicit graph-shaped data structure to be queried by pattern matching. From the Semantic Web perspective, RDF and RDFS provide standard languages for publishing and exchanging graph-shaped data. From the Knowledge Representation and Reasoning perspective, knowledge graphs are naturally seen as logical knowledge bases, typically expressed through Description Logics, whose meaning and reasoning are grounded in classical logic. Each of these perspectives presents advantages, but also significant limitations. Graph databases provide a simple and operational view of graph querying but they typically rely on a single explicit model and do not capture open-world semantic reasoning. Standard RDFS natively supports metamodeling, that is the possibility of modeling domain elements simultaneously playing different roles, e.g., as both a class and an individual. Despite this flexibility, its semantics does not capture the intended set-theoretic meaning of some of the core relations. Description Logics, on the other hand, provide a well-founded logical framework for knowledge representation and query answering, but they are usually characterized by a strict separation between individuals, classes, and roles, and thus do not directly capture the metamodeling behavior of RDFS. These observations motivate the need for a comprehensive unifying framework, grounded in classical logic, for evaluating and comparing the different scenarios in which KGs can be used, while providing logic-based semantics, reasoning algorithms under incomplete information, and complexity results. This thesis develops such a framework by taking RDFS as its starting point, as its lightweight, triple-based language combines graph structure, schema-level information, and native metamodeling capabilities. At the same time, it abstracts from features of the full RDF and RDFS standards that are not essential to the logical phenomena under investigation. The resulting formalism, called RDFS Knowledge Graphs (RKGs), preserves the graph-based flexibility of RDFS while providing a common setting in which different semantic readings can be compared. On the graph side, the thesis considers a single-model interpretation, the standard RDFS semantics, and the RKG Metamodeling Semantics (RKGMS). Under RKGMS, the reserved RDFS vocabulary is interpreted extensionally according to its intended set-theoretic meaning, while the same domain object may simultaneously play different semantic roles. On the query side, the thesis distinguishes a SPARQL-style semantics based on uniform groundings of query variables from the classical first-order semantics of existential variables. The thesis then studies the logical and computational consequences of these semantic choices. Under RKGMS, it defines a finite chase procedure and proves that it computes the deductive closure of an RKG. A central result is that RKGs do not always admit a universal model: this failure is characterized through a form of indefiniteness affecting classes and properties, and definiteness is shown to be exactly the condition under which the chase-induced structure is a universal model. The thesis also considers two different semantics for queries, i.e., the SPARQL-style semantics based on uniform groundings of query variables and the first-order query semantics of existential variables. The interaction between graph semantics and query semantics is analyzed through Boolean BGP entailment. In the fully logic-based setting, combining RKGMS with first-order query semantics, general RKGs require reasoning by cases over definite completions. Query entailment is coNP-complete in ontology complexity and $\Pi_2^p$-complete in combined complexity. The completion-based procedure is further encoded in positive disjunctive Datalog, where query entailment is reduced to skeptical reasoning over stable models. Finally, the thesis extends the framework with a reserved inequality predicate and studies its different interpretations. The extension affects satisfiability, homomorphisms, the existence of universal models, and query entailment, and provides a first step toward richer forms of negation. Overall, the thesis provides a logical reconstruction of RDFS knowledge graphs as semantic graph structures with metamodeling capabilities. It offers a systematic framework for understanding how different graph and query semantics affect model-theoretic properties, reasoning methods, and the computational behavior of query entailment.