Attributed Logics for Reasoning over Knowledge Graphs

Maximilian MarxMaximilian Marx

Maximilian Marx
Attributed Logics for Reasoning over Knowledge Graphs
Phd thesis, Technische Universität Dresden, 2025-07-08

Details
Bibtex

KurzfassungAbstract
Ever since Google introduced their Knowledge Graph, interest in graph-based knowledge modelling and reasoning has increased. Public Knowledge Graphs such as Wikidata have become huge, sporting over 1.671.000 statements for more than 115.000.000 items; new graph query languages such as GQL and SQL/PGQ have recently been standardised. With such a wealth of machine-readable data, reasoning over these graphs – i.e., deducing new information from the information explicitly encoded in the graph – already poses a challenge. This is further complicated by the graph data models (i.e., how the information is encoded in the graphs). Wikidata, e.g., uses an intricate data model supporting annotations on statements that provide further context. However, most current and proposed reasoning formalisms for graph data lack facilities for dealing with these annotations.
Handling such annotations in reasoning has long been a focus in research for decades, from the study of Complex Values in the context of Database Theory, the use of annotations for provenance in database systems, over extensions of RDF graphs with various kinds of annotations to the continued evolution of the Property Graph model. Our work thus forms part of a long-standing tradition of lines of research.
In this thesis, we lay the theoretical foundation for overcoming this gap: we introduce the notion of attributed logics as an extension of First-Order Logic (FO), where we add annotations to facts and provide syntactic features for dealing with such annotations. An early result shows that this attributed FO (FO@) is strictly more expressive than FO. This is both encouraging – it shows that the additional features are warranted – and tragic at the same time – it also shows that no sound and complete deduction calculus for FO@ can exist. From there on, we focus on finding decidable fragments of FO@. We explore two different avenues: one based on Description Logics, and one based on the rule language Datalog.
Description Logics are a family of decidable logics that can be viewed as fragments of FO. They also form the theoretical underpinnings of OWL 2, the Web Ontology Language, a formalism for reasoning over RDF graphs. Equipping them with support for annotations is thus a very natural idea. Indeed, we investigate attributed version of several Description Logics, from lightweight ℰℒℋ over 𝒜ℒ𝒞ℋ up to the very expressive 𝒮ℛ𝒪ℐ𝒬 (the basis for OWL 2). For each of those, we show that reasoning over an attributed ontology can be performed by translating them into a (potentially exponentially larger) classical (i.e., non-attributed) ontology. Except for attributed 𝒮ℛ𝒪ℐ𝒬, this means that reasoning becomes exponentially more difficult when moving to attributed ontologies, but we identify sufficient conditions under which this blowup can be avoided and we recover the original complexity of the underlying Description Logic.
We find, however, that attributed Description Logics cannot express certain queries. Thus, we study an attributed version of the rule language Datalog, which we call MARPL. We establish that reasoning for MARPL is still decidable – even not any more difficult than for Datalog. However, the same is not true for the data complexity, where we consider the set of MARPL rules fixed and study complexity merely with respect to the size of the graph database: here, MARPL reasoning is again exponentially more difficult. On the flip side, this also means that a fixed MARPL program can express strictly more problems than a fixed Datalog program. This is a helpful property to have for reasoning over a Knowledge Graph, where, e.g., ontological rules might be encoded in the Graph (i.e., in the data): Wikidata, e.g., contains statements that certain properties are symmetric. We describe a reasoning algorithm, the MARS chase, for MARPL.
Yet, having to implement a whole new reasoning procedure (even if it is similar to existing techniques used for Datalog reasoning) to reason using MARPL programs is a much less satisfying situation when compared to the attributed Description Logics situation, where merely implementing the (syntactic) translation into classical ontologies already enables the use of existing reasoning tools. In search of a similar translation for MARPL, we first introduce and another variant of Datalog, Datalog with complex values (DatalogCV), that we will use as an intermediate language for our translation. We establish a translation from DatalogCV into Existential Rules (which extend Datalog with the ability to add new values to the domain), for which reasoning software exists. We show that reasoning for translations of DatalogCV programs is decidable, even though this is not generally true for arbitrary sets of Existential Rules. We further extend DatalogCV with stratified negation, and finally show that MARPL programs can be translated into DatalogCV. At last, practical MARPL reasoning is in reach!
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@phdthesis{M2025,
  author = {Maximilian Marx},
  title  = {Attributed Logics for Reasoning over Knowledge Graphs},
  school = {Technische Universit{\"{a}}t Dresden},
  year   = {2025}
}