An Algebraic Foundation for Knowledge Graph Construction

Sitt Min Oo, Olaf Hartig · 2025

Read An Algebraic Foundation for Knowledge Graph Construction by Sitt Min Oo, Olaf Hartig (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10385.txt.

Introduction

Sitt Min Oo and Olaf Hartig gave knowledge graph building a formal algebra in 2025. For over a decade, declarative mapping languages have been used to build knowledge graphs from mismatched data sources, and tools implementing them work well in practice. Yet the languages never received a solid formal base, so nobody could prove an implementation correct, engines quietly diverged from one another. And basic questions such as expressive power had no rigorous answer.

The authors define a language-agnostic algebra that captures what mapping definitions mean. As concrete payoffs, they show the popular mapping language RML translates into the algebra, which simultaneously fixes RML's formal semantics for the first time. And they prove a set of algebra-based rewriting rules. Those rules let an engine rewrite a mapping plan into an equivalent cheaper one with a guarantee of correctness, the kind of optimization data store systems have enjoyed for decades.

Catalog record

CREATORSitt Min Oo, Olaf Hartig
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-10385

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Algebraic Foundation for Knowledge Graph Construction Thanks: This is an extended version of a research paper accepted for the 22nd Extended Semantic Web Conference (ESWC 2025). The extension consists of a few additional equivalences in Section 6.1 and the complete content of Section 6.2 , which are not included in the version prepared for the conference proceedings. Sitt Min Oo, Olaf Hartig Abstract Although they exist since more than ten years already, have attracted diverse implementations, and have been used successfully in a significant number of applications, declarative mapping languages for constructing knowledge graphs from heterogeneous types of data sources still lack a solid formal foundation. This makes it impossible to introduce implementation and optimization techniques that are provably correct and, in fact, has led to discrepancies between different implementations. Moreover, it precludes studying fundamental properties of different languages (e.g., expressive power). To address this gap, this paper introduces a language-agnostic algebra for capturing mapping definitions. As further contributions, we show that the popular mapping language RML can be translated into our algebra (by which we also provide a formal definition of the semantics of RML) and we prove several algebraic rewriting rules that can be used to optimize mapping plans based on our algebra. (Extended Version) 1 Introduction Knowledge graphs (KGs) are often created or populated by extracting and transforming data from other sources of structured or semi-structured data. One approach to this end is to employ a mapping engine for which the desired mapping from the source data to the KG can be specified using a declarative language. This approach has gained traction in recent years, with applications across diverse domains such as COVID research [ 17 ] , railway networks [ 16 ] , and incident management in ICT systems [ 22 ] . To provide a basis for this approach, several declarative mapping languages, in particular for RDF-based KGs, have been proposed, including languages that focus only on a single type of input data sources (e.g., R2RML for relational databases [ 21 ] ) and, more interestingly, also languages designed for multiple types of input data sources [ 23 ] . The latter can be classified further into mapping-focused extensions of query languages and dedicated languages designed solely for the declarative description of mappings. So far, most of these mapping languages—in particular, the dedicated ones—are defined only informally. Yet, such an informal definition can easily lead to discrepancies between different implementations. For instance, for RML [ 4 , 5 ] , which has several implementations [ 1 , 6 , 9 , 20 , 18 ] , the introduction of conformance tests [ 8 ] has revealed various cases in which different implementations fail such a test [ 7 ] . It may be argued that the developers of these implementations interpreted the informal definition of the language differently. Without a formal definition it is impossible to introduce implementation and optimization techniques that are provably correct, or to properly compare languages or language features in terms of fundamental properties, such as their expressive power. Therefore, the goal of our work in this paper is to provide a formal foundation for such declarative mapping languages. Especially, instead of focusing on a single specific language, we aim for a more general formalization approach. Our main contribution is a language-agnostic algebra to capture definitions of mappings from heterogeneous types of data sources to RDF-based KGs. The basis of this mapping algebra is a variation of the relational data model (Section 3 ), for which we define five types of operators that can be arbitrarily combined into algebra expressions (Section 4 ). Due to its language-agnostic nature, the algebra can serve as a foundation to various mapping languages formally. As our second contribution, we demonstrate this benefit by providing an algorithm that translates mappings defined using RML into our algebra (Section 5 ). Through this algorithm, we show not only that our algebra is at least as expressive as RML, but we also provide a formal definition of the semantics of RML. To the best of our knowledge, this is the first formal approach to capture the RML semantics. Another important value of having an algebra that captures declarative mapping definitions is that it may be used as the basis of a systematic and well-defined approach to plan and to optimize the execution of KG construction processes in mapping engines. Related to this option, we make our third contribution: We show several algebraic equivalences which can be used as rewriting rules to optimize mapping plans that are based on our algebra (Section 6 ). 2 Related Work As mentioned above, declarative mapping languages for KG construction can be classified into languages that are extensions of other types of languages (mainly, query languages), with XSPARQL [ 2 ] , SPARQL-Generate [ 11 ] , and Facade-X [ 3 ] being examples of such “repurposed mapping languages” [ 23 ] , and “dedicated mapping languages” [ 23 ] that have been created specifically for the purpose of KG construction, with R2RML [ 21 ] and RML [ 4 ] as examples. Given our focus on formal approaches to capture such languages, for the repurposed ones we notice they can rely on the formalization of their underlying language. For instance, XSPARQL combines the semantics of XQuery and SPARQL for mapping between XML and RDF data [ 2 ] , and to also support relational databases, the authors extend their work by utilizing the semantics of relational algebra [ 12 ] . Similarly, the formalization of SPARQL-Generate [ 11 ] builds on the algebra-based formalization of SPARQL and, thus, is similar in spirit to our approach, which we see as more relevant for dedicated mapping languages. When considering dedicated mapping languages, to the best of our knowledge, only R2RML has a formally defined semantics. That is, Sequeda et al. [ 19 ] provide such a formalization by means of 57 Datalog rules. As this definition is for R2RML, it is limited to mappings from relational databases to RDF, whereas our formalization in this paper can capture mappings of different types of sources of structured and semi-structured data. Moreover, we argue that an algebraic formalization such as ours has the additional advantage that it can also be utilized to represent a form of logical execution plans in mapping engines. Besides R2RML, a few studies with formalizations related to RML have been published in recent years [ 9 , 14 ] . Iglesias et al. formalize RML-based mapping processes based on Horn clauses [ 9 ] , where the focus of this formalization is to define optimization techniques presented by the authors. Lastly, an initial study to capture the semantics of mappings in a language-agnostic manner through algebraic mapping operators [ 14 ] has a very similar goal as our work in this paper. Yet, in contrast to our work, the authors do not cover all aspects of popular dedicated mapping language such as RML (e.g., joining data from multiple sources) and several of their definitions remain informal or rely on undefined concepts. 3 Data Model This section introduces the data model based on which our mapping algebra is defined. Hence, this model captures the

Read the complete text