Declarative knowledge graph construction has matured to the point where state of the art techniques are focusing on optimizing the mapping processes. However, these optimization techniques use the syntax of the mapping language without considering the impact of the semantics. As a result, it is dificult to compare diferent engines fairly due to the obscurity in their semantic diferences. In this poster paper, we propose an initial set of algebraic mapping operators to define the operational semantics of mapping processes, and provide a first step towards a theoretical foundation for mapping languages. We translated a series of RML documents to algebraic mapping operators to show the feasibility of our approach. We believe that further pursuing these initial results will lead to greater interoperability of mapping engines and languages, intensify requirements analysis for the upcoming RML standardization work, and an improved developer experience for all current and future mapping engines.
CEUR ceur-ws.org
Several mapping engines exist to generate RDF Knowledge Graphs (KG) from heterogeneous
data sources [
In the domain of knowledge graph querying, algebraic operators form the foundation for
the query semantics through formalization [
CEUR interoperability of mapping engines.
There are solutions which provide an ontology for representing the diferent mapping
languages [
In this poster paper, we introduce an initial set of algebraic mapping operators and define their semantics. We apply this initial set to RML. We translated a series of RML documents to algebraic mapping operators to validate our approach.
We first introduce terminologies. For our initial work, we reuse some of the terminologies from SPARQL algebra, allowing us to align our mapping algebra with SPARQL algebra in the future to study expressiveness. We can reuse following definitions. A solution mapping is a partial function mapping from , a set of variables, to Τ, a set of terms, provided ∩ Τ = ∅ . Τ = ∪ ∪ where , , and are disjoint, infinite sets of IRIs, blank nodes, and literals respectively.
Mapping languages enable users to fragment the generated data into diferent data sinks (e.g. multiple files or web sockets). In order to future proof the mapping algebra, we need to introduce the fragment. A fragment, ∈ , is a grouping of the multiset of solution mappings. It can be seen as a generic sink: a file , a database, or a logical fragment such as a specific social context, e.g. information about a person only known by friends.
A mapping tuple is the core of our mapping algebra; a partial function which maps fragments to multiset of solution mappings: ∶ → Ω with Ω a multiset of solution mappings. A multiset of mapping tuples is . This mapping of fragments to multiset of solution mappings enable us to group solution mappings based on some abstract concept. For example, we could have mapping tuples where solution mappings are grouped according to some social context (e.g. personal information and friend’s information) (Table 1). Currently, grouping solution mappings according to fragments can not be achieved with SPARQL’s definition of group algebra. 1 2 3
Alice Joe 26 john.doe@example.com susan.sue@example.com alice.joe@example.com
We now define the initial set of algebraic mapping operators computing on : Source, Project, Extend, and Serialize. We do not yet include the fragmentation operator where could be recursively fragmented nor the join operator. The algebraic mapping operators take as input Source operator The Source operator is needed to generate the mapping tuples from heterogeneous data sources used in the downstream operators for mapping. The source operator is the leaf node operator in the mapping plan and does not have as input.
Given a configuration, , a source operator generates a multi-set, , of mapping tuples, ’s, where a default fragment 0 is mapped to a multiset of solution mappings Ω. ∈ Ω is generated by flattening the data records which are derived by iterating over the data source. For example, derived from a CSV row is a partial function from the headers of the CSV to the corresponding data values in the CSV row. We define: 0 = a default fragment lfattened data record } 0 → Ω} Project operator The Project operator restricts the variables in the solution mapping, needed to eficiently process the mapping tuples. For example, RML’s single iteration of CSV contains all columns for a data record, but implicitly projects the required references for the mapping process. It is similar to the SPARQL algebra counterpart. Let { 0, … , } ∈ , be a set of projection attributes. We define:
Project( , P) = restricted to attribute variables in P Project(Ω, P) = {Project( , P) ∣ ∈ Ω} Project( , P) = → Project(Ω, P)
Project( , P) = {Project( , P) ∣ ∈ } and produces as output unless otherwise stated. 1–5 (1) (2) (3) Extend operator The Extend operator derives new attributes for a solution mapping. For example, to include body mass index (BMI) of a person in the output, we derive the BMI from the height and weight attributes of a person. In RML, this is equivalent to the template and constant Term Maps, where new values, not existing in the data records, are generated. The Extend operator derives a value, by executing an expression on the solution mapping, and coupled it to new variable not in the domain of the solution mapping. If evaluating the expression causes an error and the variable is not in the domain of the solution mapping, the extend operator behaves like an identity operator. It is undefined if the variable restriction is violated. We define:
Extend( , v, expr) = ∪ {( , ) ∣ ∉ Extend(Ω, v, expr) = {Extend( , v, expr) ∣ ∈ Ω} Extend( , v, expr) = → Extend(Ω, v, expr) Extend( , v, expr) = {Extend( , v, expr) ∣ ∈ } dom( ) and value = expr( )} Serialize operator The Serialize operator serializes the mapping tuples into the specified format. This is the core functionality of mapping engines: to generate data in a specific format from some data. For example, RML defines the data format implicitly using the Term Maps. The Serialize operator is the root node operator.
The Serialize operator generates data in a specific data format by replacing query variables in the template with the values from the input solution mappings. Each solution mapping generates one data item in the specified format. Given a string template . We define: Serialize(Ω, ) = { () ∣ ∈ Ω, () = Serialize( , ) = → Serialize(Ω, ) Serialize( , ) = {Serialize( , ) ∣ ∈ } variables in substituted with } (4)
We implemented these proposed semantics in a proof-of-concept algebra interpreter for RML mapping rules: https://github.com/s-minoo/meamer-rs . We translated several RML documents (without joins) to a tree of mapping algebraic operators: a mapping plan. This provides an initial validation of our proposed semantics, and showcases its potential: multiple mapping plans of diferent complexity are translated, allowing for inspection and optimization proposals.
This poster paper presents an initial set of algebraic mapping operators (Source, Project, Extend, Serialize) and proof-of-concept implementation which can already be used to describe a subset of mapping processes represented in RML. The generated mapping plans show the potential to define optimization rules based on the semantics and not syntax of the mapping language. Furthermore, working with algebraic mapping operators enables us to “rewrite” the mapping plan, generated using the algebraic mapping operators, to optimize the mapping process. For example, we could push the Projection operator close to the Source operator, to filter out unnecessary data unused in the output, to reduce memory usage during the knowledge graph construction.
As future work, we plan to extend and refine the algebraic operators, to be used as a theoretical foundation for mapping languages. We plan to provide a generic mapping framework: the reference implementation of these algebraic operators. Users could use this framework to easily create a mapping engine using their choice of mapping language. Finally, we plan to conduct an empirical study on the existing mapping optimization techniques and translate them to optimization rules using these algebraic operators.
The described research activities were supported by SolidLab Vlaanderen (Flemish Government, EWI and RRF project VV023/10), and the imec ICON project BoB (Agentschap Innoveren en Ondernemen project nr. HBC.2021.0658).