Multiset Semantics in SPARQL,Relational Algebra,and Datalog

Abstract

The paper analyzes and characterizes the algebraic and logical structure of the multiset semantics for SPARQL patterns involving AND, UNION, FILTER, EXCEPT, and SELECT. To do this, we align SPARQL with two well-established query languages: Datalog and Relational Algebra. Specifically, we study (i) a version of nonrecursive Datalog with safe negation extended to support multisets, and (ii) a multiset relational algebra comprising projection, selection, natural join, arithmetic union, and except. We prove that these three formalisms are expressively equivalent under multiset semantics.

Keywords

query languages multisets bags SPARQL Datalog relational algebra

1. Introduction

Informally speaking, multisets are sets in which each element could occur multiple times, that is, the number of “copies” of each element matters. In the field of databases, the notion of multisets (also called “duplicates” or “bags”)¹ has been studied in several contexts, including programming languages (Breazu-Tannen & Subrahmanyam, 1991; Lloyd, 1998), bag languages (Albert, 1991; Colby & Libkin, 1997; Grumbach et al., 1996; Grumbach & Milo, 1996; Libkin & Wong, 1994, 1997), relational algebra (Console et al., 2022; Dayal, Goodman, & Katz, 1982; Klausner & Goodman, 1985), Datalog (Afrati et al., 2010; Bertossi, Gottlob, & Pichler, 2019; Cohen, 2009; Mumick et al., 1990a, 1990b), SQL (Guagliardo & Libkin, 2017; Ricciotti & Cheney, 2019), SPARQL (Angles & Gutiérrez, 2016; Geerts et al., 2016; Kaminski et al., 2016; Polleres & Wallner, 2013), and data integration (Hernich & Kolaitis, 2017).

The incorporation of multisets in query languages is essentially due to practical concerns: duplicate elimination is expensive, and duplicates might be required for some applications, for example, for aggregation. Although this design decision may be debatable (see, e.g., Date, 2006), today multisets are an established reality in database systems (Green, 2009; Lamperti et al., 2001).

The classical theory behind declarative query languages includes formalisms (relational algebra or relational calculus) that, for sets, have a clear and intuitive semantics for users, developers, and theoreticians (Abiteboul et al., 1995). The same cannot be said for their extensions to multisets, whose theory is complex (particularly the containment of queries), and their practical use is not always clear (Green, 2009). Worst, there exist several possible ways of extending set relational operators to multisets, which makes the study and design of multiset semantics for query languages challenging.

To illustrate the variety of possible semantics, we will show the different extensions to multisets of set operators found in the literature. Consider the following multiset relations: $R (W, X) = {[(a, b), (a, b), (a, d)]}$ , $S (W, X) = {[(a, b)]}$ and $T (Y, Z) = {[(b, c), (b, c)]}$ . For the first relation, $R$ is the name of the relation, $W$ and $X$ are the attributes that conform the schema of $R$ , $R$ contains three tuples, and the tuple $(a, b)$ is duplicated (i.e., its cardinality is $2$ ). A similar description can be given for the relations $S$ and $T$ . Note that $R$ and $S$ have the same attributes, while $T$ does not have attributes in common with $R$ and $S$ .

–
The selection returns the tuples satisfying a given condition but keeping cardinalities. For example, $σ_{X =^{'} b^{'}} (R)$ returns the multiset ${[(a, b), (a, b)]}$ with schema $(W, X)$ .
–
The Cartesian product results in the multiplication of the cardinalities. For example, $R \times T$ returns the multiset ${[(a, b, b, c)$ , $(a, b, b, c)$ , $(a, b, b, c)$ , $(a, b, b, c)$ , $(a, d, b, c)$ , $(a, d, b, c)]}$ with schema $(W, X, Y, Z)$ .
–
The join results in the multiplication of the cardinalities, as it is expressed as a Cartesian product followed by a selection. For example, $R ⋈_{X = Y} T$ returns the multiset ${[(a, b, b, c)$ , $(a, b, b, c)$ , $(a, b, b, c)$ , $(a, b, b, c)]}$ with schema $(W, X, Y, Z)$ .
–
The max-union takes the maximum number of occurrences of an element. For example, $R ⊔ S$ returns the multiset ${[(a, b)$ , $(a, b)$ , $(a, d)]}$ with schema $(W, X)$ .
–
The arithmetic union adds up cardinalities. For example, $R \cup S$ returns the multiset ${[(a, b)$ , $(a, b)$ , $(a, d)$ , $(a, b)]}$ with schema $(W, X)$ .
–
The min-intersection takes the minimum number of occurrences of each element in the intersection. For example, $R \cap S$ returns the multiset ${[(a, b)]}$ with schema $(W, X)$ .
–
The max-intersection returns the product of the cardinalities of each element in the intersection. For example, $R ⊓ S$ returns the multiset ${[(a, b)$ , $(a, b)]}$ with schema $(W, X)$ .
–
The arithmetic difference subtracts the cardinalities of the elements up to zero. For example $R - S$ returns the multiset ${[(a, b)$ , $(a, d)]}$ with schema $(W, X)$ .
–
The existential negation returns the elements in the first multiset that do not occur in the second one, and keeps the cardinalities of such elements in the first multiset. For example, the expression $R ∖ S$ returns the multiset ${[(a, d)]}$ with schema $(W, X)$ .
–
The projection reduces the number of attributes in each tuple, and gives rise to new cardinalities for the resulting tuples. For example $π_{W} (R)$ returns the multiset ${[(a)$ , $(a)$ , $(a)]}$ with schema $(W)$ .

Table 1 shows a summary of the above operators, and their corresponding implementation in SQL and SPARQL. Note that SQL can express all the operators, whereas SPARQL does not support max-union, min-intersection, and arithmetic difference. Also note that SPARQL uses the AND operator to implement the Cartesian product and max-intersection. The first case occurs because $R$ and $T$ do not have variables in common, and the second case occurs because $R$ and $S$ have the same set of variables.

Table 1.
Possible Ways of Extending Set Operators With Multiset Semantics in SQL and SPARQL.

Operation Operator Cardinality for $x$ SQL SPARQL

Selection $σ_{φ} (R)$ ${\begin{cases} R (x) & if x satisfies φ, \\ 0 & otherwise. \end{cases}$ SELECT * FROM $R$ WHERE $φ$ $R$ FILTER ( $φ$ )

Cartesian product $R \times T$ $R (x) \times T (x)$ $R$ CROSS JOIN $T$ $R$ AND $T$

Join $R ⋈_{φ} T$ $R (x) \times T (x)$ ( $R$ CROSS JOIN $T$ ) WHERE $φ$ ( $R$ AND $T$ ) FILTER ( $φ$ )

Max-union $R ⊔ S$ $max (R (x), S (x))$ ( $R$ UNION ALL $S$ ) EXCEPT ALL –

( $R$ INTERSECT ALL $S$ )

Arithmetic union $R \cup S$ $R (x) + S (x)$ $R$ UNION ALL $S$ $R$ UNION $S$

Min-intersection $R \cap S$ $min (R (x), S (x))$ $R$ INTERSECT ALL $S$ –

Max-intersection $R ⊓ S$ $S (x) \times S (x)$ $R$ NATURAL JOIN $S$ $R$ AND $S$

Arithmetic difference $R - S$ $max (0, R (x) - S (x))$ $R$ EXCEPT ALL $S$ –

Existential negation $R ∖ S$ ${\begin{cases} R (x) & if S (x) = 0, \\ 0 & otherwise. \end{cases}$ $\begin{array}{l} SELECT * FROM R \\ WHERE x NOT IN (S) \end{array}$ $R$ MINUS $S$

Projection $π_{A t t s} (R)$ $\sum_{t \in R, t [A t t s] = x} R (x)$ SELECT $A t t s$ FROM $R$ SELECT $A t t s$

Note. The table shows several extended relational algebra operations for multisets currently present (or possible to implement) in SQL and SPARQL. Let $R$ , $S$ , and $T$ be multiset relations satisfying that $R$ and $S$ have the same attributes, and $T$ does not have attributes in common with $R$ . The cardinality of an element $x$ in a relation $R$ is represented as $R (x)$ . Note that SPARQL works with multisets of bindings, whose corresponding schema is a set of variables.

The landscape of operators over multisets poses important challenges for integrating multisets in query languages. First, as shown in Table 1, some operators exhibit different semantics when applied to multisets. Second, while relational algebra and SQL support all the semantics listed, SPARQL and Datalog only support a subset. Third—and this is the main motivation for our research—it remains unclear whether there exists an optimal set of multiset operators for SPARQL, and if so, which one it is. To tackle these questions, it is essential to understand how formalisms that are “closed” with respect to SPARQL behave, and how their design and behavior can inform or be translated into SPARQL. In technical terms, this means analyzing the expressive power of SPARQL regarding multisets. To this end, we focus on two natural and well-studied reference points: relational algebra and Datalog. That is the aim of this article. Next, we review the existing literature about multisets.

Related Work. First, we consider the research works that define general algebras for manipulating bags. Albert (1991) extended typical set operations (union, intersection, difference, and Boolean selection) to bags, and demonstrated that some of the algebraic properties for sets fail for multisets. Grumbach et al. (1996) introduced a bag algebra, called BALG, that extends relational operations to handle duplicates. This paper shows that BALG is more expressive than standard relational algebra because it can count duplicates, but it still has low data complexity (LOGSPACE). Grumbach and Milo (1996) focused on designing bag algebras that are both expressive and computationally tractable. They introduce restricted forms of projection and join to maintain tractable data complexity. Libkin and Wong (1994, 1997) introduced BQL, a query language for handling bags and aggregate functions (sum, count, and avg.). They show that BQL is more expressive than traditional set-based languages, and show that after incorporating structural recursion to BQL, it is able to express all primitive recursive functions, significantly increasing its computational power. Ricciotti and Cheney (2019) explored how to mix set and bag semantics in query languages, addressing practical needs found in SQL (e.g., SELECT vs. SELECT DISTINCT). They propose a formal model that supports both semantics and allows translation between them.

The first attempt to extend the relational algebra to include multisets was made by Dayal et al. (1982). In this work, the authors introduced a multiset relational algebra (MRA; formed by the operators of projection, selection, join, max-union, arithmetic union, min-intersection, and arithmetic difference) and studied their algebraic properties. This work laid the groundwork for formalizing bag semantics in relational query languages. Klausner and Goodman (1985) provided a semantic framework for understanding the role of multirelations (relations with duplicates) at the conceptual level. The authors explain how any query language can be extended consistently to have full multirelational expressiveness. Afrati et al. (2010) studied query containment in relational databases under bag semantics and bag-set semantics (duplicates allowed in intermediate steps but not in the final output). The authors identify conditions under which containment is decidable and provide complexity results. Console et al. (2022) investigated fragments of bag relational algebra, focusing on their expressive power. The authors also study query answering over bags with nulls (i.e., under incomplete data).

Multisets have also been the subject of study in the context of Datalog, with various extensions proposed to support bag semantics. Mumick et al. (1990a) defined the Magic Sets transformation for optimizing recursive queries, and described how to adapt this technique to support duplicates. They also showed how to efficiently evaluate recursive queries under multiset semantics. In a subsequent work (Mumick et al., 1990b), Mumick et al. extended the Magic Sets technique to support duplicates and aggregate functions in recursive queries. The authors also studied the challenges of preserving correct bag semantics when applying recursion and aggregation. Cohen (2009) studied the problem of query equivalence under bag semantics. This work includes complexity results and demonstrates that equivalence checking is significantly harder under bag semantics. Mumick et al. (1990a) developed a translation of Datalog under bag semantics into warded Datalog $^{\pm}$ , a well-behaved extension under set semantics. The authors investigated the properties of the resulting Datalog $^{\pm}$ programs, the problem of deciding multiplicities, and the expressibility of some bag operations.

For SPARQL—the standard query language for RDF databases—Pérez et al. (2006) provided the first formal treatment of its multiset semantics. This work influenced the definition of SPARQL 1.0 (Prud’hommeaux & Seaborne, 2008) and SPARQL 1.1 (Harris & Seaborne, 2013), whose semantics are based on operations over multisets of mappings (although a database is a set of RDF triples). Schmidt et al. (2010) presented a formal framework for SPARQL query optimization, addressing both set and bag semantics. The authors analyzed the algebraic properties of SPARQL operations such as OPTIONAL, UNION, and FILTER under multisets, and introduced equivalence rules and normal forms for optimizing queries. Kaminski et al. (2016) presented a formal investigation of subqueries and aggregate functions in SPARQL 1.1, focusing on their semantics under multisets. The authors analyzed the expressive power of these constructs, showing that SPARQL 1.1 is strictly more expressive than SPARQL 1.0 due to these features.

Finally, we review research articles that present comparisons and translations among SPARQL, relational algebra, and Datalog. Cyganiak (2005) was among the first to translate a core fragment of SPARQL into relational algebra. Polleres (2007) proved the inclusion of the fragment of SPARQL patterns with safe filters into Datalog by providing a precise and correct set of rules. Schenk (2007) proposed a formal semantics for SPARQL based on Datalog, but concentrated on complexity more than expressiveness issues. Both Polleres and Schenk did not consider the multiset semantics of SPARQL in their translations. Angles and Gutiérrez (2008) studied the expressive power of SPARQL by providing a translation to nonrecursive safe Datalog with negation. Chebotko et al. (2009) addressed the problem of translating SPARQL queries into SQL while preserving bag semantics. The authors proposed a formal translation framework that captures the subtleties of OPTIONAL, UNION, and FILTER, and ensures that duplicates in the result sets are handled correctly when mapped to relational databases. Angles and Gutiérrez (2016) studied the multiset semantics of SPARQL patterns by translating its patterns into two languages: a version of MRA and multiset nonrecursive Datalog with safe negation. Angles et al. (2023) implemented the translation from SPARQL to Datalog within the Vadalog system (Bellomarini et al., 2018).

Objectives and Contributions. The main objective of this article is to examine the theoretical foundations of SPARQL’s multiset semantics. To do so, we compare it with classical algebraic and logical frameworks—specifically, Relational Algebra and Datalog. We focus on the SPARQL fragment built from AND, UNION, FILTER, EXCEPT, and SELECT, characterizing its structure and proving its expressive equivalence with corresponding fragments of Relational Algebra and Datalog.

The specific contributions of our research are as follows: (1)
Based on the work of Mumick et al. (1990b), who defined the multiset semantics for Datalog without negation, we defined a version called nonrecursive multiset Datalog with safe negation ( ${NRMD}^{\neg}$ ). The definition of ${NRMD}^{\neg}$ includes negation and follows a proof-theoretic semantics.
(2)
Based on the work of Dayal et al. (1982), who extended the relational algebra to include multiset relations, we defined a multiset relational algebra (MRA. The definition of MRA includes the operators of projection ( $π$ ), selection ( $σ$ ), natural join ( $⋈$ ), arithmetic union ( $\cup$ ), and filter difference ( $∖$ ), all of them working under multiset semantics.
(3)
We show the equivalence among the aforementioned SPARQL fragment, MRA, and ${NRMD}^{\neg}$ by providing translations for databases, queries, and answers. Table 2 shows a glimpse of these translations, whose details are developed in this paper.

Table 2.
Schema of Correspondences Among: SPARQL Graph Patterns, MRA Expressions, ${NRMD}^{\neg}$ Rules, and SQL Expressions.

SPARQL ${NRMD}^{\neg}$ MRA SQL

$SELECT X P_{1}$ $L \leftarrow L_{1}, null (X ∖ X_{1})$ $π_{X} (r_{1}) ⋈ null (X ∖ X_{1})$ $\begin{aligned} SELECT X \\ FROM r_{1} NATURAL\;JOIN null (X ∖ X_{1}) \end{aligned}$

$P_{1} FILTER X = a$ $L \leftarrow L_{1}, X = a$ $σ_{X = a} (r_{1})$ FROM $r_{1}$ WHERE $X = a$

$P_{1} AND P_{2}$ $\begin{aligned} L \leftarrow & v_{1} (L_{1}), v_{2} (L_{2}), \\ comp (v_{1}, v_{2}, X) \end{aligned}$ $\begin{aligned} π_{\bar{X}} (ρ_{v_{1}} (r_{1}) ⋈ ρ_{v_{2}} (r_{2}) ⋈ \\ comp (v_{2}, v_{2}, X)) \end{aligned}$ $\begin{aligned} SELECT X \\ FROM r_{1} NATURAL\;JOIN r_{2} NATURAL\;JOIN \\ comp (v_{2}, v_{2}, X) \end{aligned}$

$P_{1} UNION P_{2}$ $L \leftarrow L_{1}; L \leftarrow L_{2}$ $r_{1} ⊎ r_{2}$ $r_{1}$ UNION ALL $r_{2}$

$P_{1} EXCEPT P_{2}$ $L \leftarrow L_{1}, \neg L_{2}$ $r_{1} ∖ r_{2}$ $r_{1}$ EXCEPT $r_{2}$

Note. MRA = multiset relational algebra; ${NRMD}^{\neg}$ = nonrecursive Datalog with safe negation. The operator $EXCEPT$ is not part of SPARQL, but it replaces the standard operators $MINUS$ and $OPT$ without changing the expressiveness of the fragment. In MRA, $⊎$ is the arithmetic union and $∖$ is the multiset filter difference. SPARQL patterns are assumed normalized, that is, variables in the filter condition are in the schema of the filtered pattern, and operators $EXCEPT$ and $UNION$ assume operands with the same schema. $P_{1}$ and $P_{2}$ are SPARQL patterns that are associated with atoms $L_{1}$ and $L_{2}$ in the ${NRMD}^{\neg}$ translation, and relations $r_{1}$ and $r_{2}$ in the MRA translations, respectively.

This paper extends a previously published conference paper (Angles & Gutiérrez, 2016). Herein, we provide an extended discussion throughout. We extend the study to some operators that were introduced in version 1.1 of SPARQL after the publication of our previous work, and we extend the analysis to also consider bag semantics. Some of the additional contributions of this paper come from Hernández’s PhD thesis (Hernández, 2020).

The rest of the article is organized as follows. Section 2 presents basic concepts and notations. The SPARQL query language is defined in Section 3. ${NRMD}^{\neg}$ is defined in Section 4. The MRA is defined in Section 5. The equivalence between SPARQL and ${NRMD}^{\neg}$ is presented in Section 6. The equivalence between MRA and ${NRMD}^{\neg}$ is presented in Section 7. The equivalence between MRA and SPARQL is presented in Section 8. Conclusions are presented in Section 9.
2. Preliminaries

Operation	Operator	Cardinality for $x$	SQL	SPARQL
Selection	$σ_{φ} (R)$	${\begin{cases} R (x) & if x satisfies φ, \\ 0 & otherwise. \end{cases}$	SELECT * FROM $R$ WHERE $φ$	$R$ FILTER ( $φ$ )
Cartesian product	$R \times T$	$R (x) \times T (x)$	$R$ CROSS JOIN $T$	$R$ AND $T$
Join	$R ⋈_{φ} T$	$R (x) \times T (x)$	( $R$ CROSS JOIN $T$ ) WHERE $φ$	( $R$ AND $T$ ) FILTER ( $φ$ )
Max-union	$R ⊔ S$	$max (R (x), S (x))$	( $R$ UNION ALL $S$ ) EXCEPT ALL	–
			( $R$ INTERSECT ALL $S$ )
Arithmetic union	$R \cup S$	$R (x) + S (x)$	$R$ UNION ALL $S$	$R$ UNION $S$
Min-intersection	$R \cap S$	$min (R (x), S (x))$	$R$ INTERSECT ALL $S$	–
Max-intersection	$R ⊓ S$	$S (x) \times S (x)$	$R$ NATURAL JOIN $S$	$R$ AND $S$
Arithmetic difference	$R - S$	$max (0, R (x) - S (x))$	$R$ EXCEPT ALL $S$	–
Existential negation	$R ∖ S$	${\begin{cases} R (x) & if S (x) = 0, \\ 0 & otherwise. \end{cases}$	$\begin{array}{l} SELECT * FROM R \\ WHERE x NOT IN (S) \end{array}$	$R$ MINUS $S$
Projection	$π_{A t t s} (R)$	$\sum_{t \in R, t [A t t s] = x} R (x)$	SELECT $A t t s$ FROM $R$	SELECT $A t t s$

SPARQL	${NRMD}^{\neg}$	MRA	SQL
$SELECT X P_{1}$	$L \leftarrow L_{1}, null (X ∖ X_{1})$	$π_{X} (r_{1}) ⋈ null (X ∖ X_{1})$	$\begin{aligned} SELECT X \\ FROM r_{1} NATURAL\;JOIN null (X ∖ X_{1}) \end{aligned}$
$P_{1} FILTER X = a$	$L \leftarrow L_{1}, X = a$	$σ_{X = a} (r_{1})$	FROM $r_{1}$ WHERE $X = a$
$P_{1} AND P_{2}$	$\begin{aligned} L \leftarrow & v_{1} (L_{1}), v_{2} (L_{2}), \\ comp (v_{1}, v_{2}, X) \end{aligned}$	$\begin{aligned} π_{\bar{X}} (ρ_{v_{1}} (r_{1}) ⋈ ρ_{v_{2}} (r_{2}) ⋈ \\ comp (v_{2}, v_{2}, X)) \end{aligned}$	$\begin{aligned} SELECT X \\ FROM r_{1} NATURAL\;JOIN r_{2} NATURAL\;JOIN \\ comp (v_{2}, v_{2}, X) \end{aligned}$
$P_{1} UNION P_{2}$	$L \leftarrow L_{1}; L \leftarrow L_{2}$	$r_{1} ⊎ r_{2}$	$r_{1}$ UNION ALL $r_{2}$
$P_{1} EXCEPT P_{2}$	$L \leftarrow L_{1}, \neg L_{2}$	$r_{1} ∖ r_{2}$	$r_{1}$ EXCEPT $r_{2}$

This section provides the concepts and formal notation we will follow regarding multisets and the expressive power of query languages.

2.1. Multisets

Informally, a multiset is an unordered collection of elements where each element may occur more than once. Formally, a multiset is a tuple $M = (S, card)$ , where $S$ is the underlying set of $M$ (containing the distinct elements), and $card : S \to N^{+}$ is a function that defines the cardinality in $M$ of each element $a \in S$ . We write $set (M) = S$ to denote that the underlying set of $M$ is $S$ . Given a positive natural number $n$ , $card (a, M) = n$ denotes $a \in set (M)$ and the cardinality of $a$ in $M$ is $n$ , and is usually written as $(a, n) \in M$ . Abusing notation, we write $card (a, M) = 0$ if $a \notin set (M)$ and $a \in M$ when $card (a, M) \geq 1$ . In what follows, we will prefer these formal notions over the informal and intuitive ${[a, a, a, b]}$ .

When dealing with multisets, formally describing each “copy” of an element is challenging. The notion of colored set (Mumick et al., 1990b) is a formalism to do this. Indeed, assuming that the set of colors is $N^{+}$ , the colored set of a multiset $M$ , denoted $coloring (M)$ , is the set ${⟨ a, i ⟩ ∣ a \in set (M) and 1 \leq i \leq card (a, M)}$ . In the contrary direction, we write ${coloring}^{- 1} (C)$ for the multiset $M$ with $set (M) = set (C)$ and defined by a colored set $C$ when forgetting the colors, that is, when for every element $a \in set (M)$ , $card (a, M)$ is the number of colored copies of $a$ in $C$ . Abusing notation, we write ${coloring}^{- 1} (⟨ a, i ⟩) = a$ .

Example 1
Let $A$ be the set ${a, b, c}$ , $M$ be a multiset with $set (M) = A$ , $card (a, M) = 1$ , $card (b, M) = 2$ , and $card (c, M) = 3$ . Then, $coloring (M)$ is the colored set $C = {⟨ a, 1 ⟩, ⟨ b, 1 ⟩, ⟨ b, 2 ⟩, ⟨ c, 1 ⟩, ⟨ c, 2 ⟩, ⟨ c, 3 ⟩}$ .
2.2. Comparing the Expressive Power of Query Languages

Next, we present the notion of query language and two notions of expressive power used in this paper.

Definition 1 Query language

A query language $L$ is a quadruple $(Q, D, S, Eval)$ , where $Q$ is the set of queries in $L$ , $D$ is the set of databases in $L$ , $S$ is the set of query answers in $L$ , and $Eval : Q \times D \to S$ is the query evaluation function of $L$ .

Let $L = (Q, D, S, Eval)$ be a query language. Two queries $Q_{1}, Q_{2} \in Q$ are said to be equivalent, denoted $Q_{1} \equiv Q_{2}$ , if for every database $D \in D$ , it holds that $Eval (Q_{1}, D) = Eval (Q_{2}, D)$ , that is, they return the same query answer for all input databases.

Given a query language $(Q, D, S, Eval)$ , a query $Q \in Q$ determines a function $q : D \to S$ defined as $q (D) = Eval (Q, D)$ , called the query function of $Q$ . Two queries $Q_{1}$ and $Q_{2}$ are thus equivalent, denoted $Q_{1} \equiv Q_{2}$ , if they determine the same query function.

In this context, the expressive power of a query language $L$ is understood as the set of all query functions that are expressible by $L$ . Abiteboul et al. (1995) summarizes how this notion is used to compare the expressive power of relational algebra, Datalog, and relational calculus. In the context of SPARQL, Zhang and den Bussche (2014), Kontchakov and Kostylev (2016), and Angles and Gutierrez (2016) use this notion to compare different fragments of SPARQL.

The query languages studied in this paper do not satisfy the aforementioned property of having a common set of databases and query answers. Thus, we need an extended version of the notion of expressive power as in Definition 2 below.

Definition 2 Generalized expressive power

Given two query languages $L_{1} = (Q_{1}, D_{1}, S_{1}, {Eval}_{1})$ and $L_{2} = (Q_{2}, D_{2}, S_{2}, {Eval}_{2})$ , we say that $L_{1}$ is contained in $L_{2}$ if and only if there exist functions $g : D_{1} \to D_{2}$ (called the database translation), $f : Q_{1} \to Q_{2}$ (called the query translation), and $h : S_{2} \to S_{1}$ (called the query answer translation), such that for every $Q \in Q_{1}$ and database $D \in D_{1}$ it holds that

{Eval}_{1} (Q, D) = h ({Eval}_{2} (f (Q), g (D))) .

If that is the case, we say that the triple

(f, g, h)

is a simulation of

L_{1}

L_{2}

. We say that the languages

L_{1}

and

L_{2}

have the same expressive power, denoted

L_{1} ≅ L_{2}

, if and only if

L_{1}

is contained in

L_{2}

and

L_{2}

is contained in

L_{1}

The above definition of generalized expressive power is implicit in the translations by Polleres (2007), Angles and Gutiérrez (2008, 2016), and Polleres and Wallner (2013).

Observe that the extended notion defined above defines a partial order: the containment relation on the equivalence classes over the relation $≅$ . In fact, reflexivity and antisymmetry follow directly from the definition, while transitivity is shown in Figure 1.

Figure 1.

Transitivity of language containment. The figure represents three languages $L_{i} = (Q_{i}, D_{i}, S_{i}, {Eval}_{i}),$ where $i \in {1, 2, 3}$ . The containment of a language $L_{i}$ in $L_{i + 1}$ is given by the simulation $(f_{i, i + 1}, g_{i, i + 1}, h_{i, i + 1})$ . The transitive containment of $L_{1}$ in $L_{3}$ is given by the simulation $(f_{12} \circ f_{23}, g_{12} \circ g_{23}, h_{23} \circ h_{12}),$ where $\circ$ denotes the composition of functions (e.g., $g_{12} \circ g_{23}$ denotes the function from $D_{1}$ to $D_{3}$ that results from composing $g_{12}$ and $g_{23}$ ).

2.3. Comparing SPARQL,

{NRMD}^{\neg}

, and MRA

In the remainder of this paper, we define three families of query languages: ${NRMD}^{\neg}$ , MRA, and a core fragment of SPARQL. After defining these languages, we present simulations that show the equivalence among these three families of query languages. These simulations are depicted in Figure 2.

Figure 2.

The triangle of simulations among SPARQL, ${NRMD}^{\neg}$ , and MRA described in this paper. The query languages are identified by numbers, and $T_{i j}$ denotes the simulation of language $i$ using language $j$ . Note. ${NRMD}^{\neg}$ = nonrecursive multiset Datalog with safe negation; MRA = multiset relational algebra.

3. Multiset SPARQL

SPARQL (Harris & Seaborne, 2013; Prud’hommeaux & Seaborne, 2008) is the standard query language for RDF. In this paper, we study a fragment of SPARQL, the “relational core,” described by Angles and Gutiérrez (2016), which considers the operators FILTER, SELECT, AND, UNION, and EXCEPT. This fragment captures the graph pattern queries in SPARQL essentially. In fact, it has been proved (Angles & Gutiérrez, 2016; Kontchakov & Kostylev, 2016) that it is mutually expressible with the standard-core consisting of the operators FILTER, SELECT, AND, UNION, OPTIONAL, and MINUS. (In what follows, when speaking of “SPARQL” we will mean this fragment.)

3.1. RDF Graphs

Assume two disjoint infinite sets $I$ and $L$ , called IRIs and literals, respectively. An RDF term is an element in the set $T = I \cup L$ . An RDF triple is a triple $(s, p, o) \in I \times I \times T$ where $s$ is called the subject, $p$ is called the predicate, and $o$ is called the object. An RDF graph (just graph from now on) is a set of RDF triples. Given a graph $G$ , the function $terms (G)$ returns the RDF terms that occur in $G$ , that is, $terms (G)$ = ${s ∣ (s, p, o) \in G}$ $\cup$ ${p ∣ (s, p, o) \in G}$ $\cup$ ${o ∣ (s, p, o) \in G}$ The union of graphs, $G_{1} \cup G_{2}$ , is the theoretical union of their sets of triples.

A SPARQL database will be a set of RDF triples.

Note: In addition to $I$ and $L$ , SPARQL admits as terms anonymous resources called blank nodes. In this paper, we do not include them to help focus on the issues arising from multisets. Avoiding blank nodes does not affect the results presented in this paper. Indeed, in SPARQL, blank nodes in the data can be consistently replaced by IRIs and produce equivalent query results, and blank nodes in queries can be replaced by fresh variables without changing the semantics of the query (Hogan et al., 2014).

3.2. SPARQL Syntax

Assume the existence of an infinite set $V$ of variables disjoint from $T$ (RDF terms). A filter condition is defined recursively as follows: (i) If $? X, ? Y \in V$ and $c \in T$ then $(? X = c)$ , $(? X = ? Y)$ and $bound (? X)$ are atomic filter conditions; (ii) If $φ_{1}$ , $φ_{2}$ are filter conditions then $(φ_{1} \land φ_{2})$ , $(φ_{1} \lor φ_{2})$ and $\neg φ_{1}$ are complex filter conditions. We denote by $var (φ)$ the set of variables occurring in $φ$ .

A SPARQL pattern is defined recursively as follows:

–
A triple from $(I \cup V) \times (I \cup V) \times (I \cup L \cup V)$ is a pattern called a triple pattern. We will assume that a triple pattern has at least one variable.
–
If $P_{1}$ and $P_{2}$ are patterns then $(P_{1} AND P_{2})$ , $(P_{1} UNION P_{2})$ , and $(P_{1} EXCEPT P_{2})$ are patterns.
–
If $P$ is a pattern and $φ$ is a filter condition, then $(P FILTER φ)$ is a pattern.
–
If $W$ is a set of variables and $P_{1}$ is a pattern, then $(SELECT W P_{1})$ is a pattern.

3.3. SPARQL Semantics

A solution mapping (or just mapping from now on) is a partial function $μ : V \to T$ where the domain of $μ$ , denoted $dom (μ)$ , is the subset of $V$ where $μ$ is defined. We write $μ_{\emptyset}$ to denote the mapping with empty domain (i.e., $dom (μ_{\emptyset}) = \emptyset$ ). Given $? X \in V$ and $c \in T$ , we write $μ (? X) = c$ to denote that $μ$ maps the variable $? X$ to the term $c$ . Given a finite set of variables $W$ , the restriction of a mapping $μ$ to $W$ , denoted $μ_{| W}$ , is a mapping $μ^{'}$ that satisfies $dom (μ^{'}) = W \cap dom (μ)$ and $μ^{'} (? X) = μ (? X)$ when $? X \in dom (μ^{'})$ . Two solution mappings $μ_{1}, μ_{2}$ are compatible, denoted $μ_{1} \sim μ_{2}$ , when for all $? X \in dom (μ_{1}) \cap dom (μ_{2})$ they satisfy $μ_{1} (? X) = μ_{2} (? X)$ , that is, when $μ_{1} \cup μ_{2}$ is also a mapping. Note that two mappings with disjoint domains are always compatible.

Let $Ω$ be a multiset of solution mappings. The domain of variables in $Ω$ , denoted $dom (Ω)$ , is defined as the set union of the domains of the variables that occur in the solution mappings of $Ω$ . Given a mapping $μ$ , the cardinality of $μ$ in $Ω$ will be denoted as $card (μ, Ω)$ . If $μ \notin Ω$ then $card (μ, Ω) = 0$ .

The evaluation of a filter condition $φ$ under a mapping $μ$ , denoted $μ (φ)$ , is defined in a three-valued logic with values $true$ , $false$ and $error$ . We say that $μ$ satisfies $φ$ when $μ (φ) = true$ . The semantics of $μ (φ)$ is defined recursively as follows:

–
If $φ$ is $? X = c$ and $c \in T$ , then: (a) If $? X \in dom (μ)$ then $μ (φ) = true$ when $μ (? X) = c$ and $μ (φ) = false$ otherwise; (b) If $? X \notin dom (μ)$ then $μ (φ) = error$ .
–
If $φ$ is $? X = ? Y$ and $? X, ? Y \in dom (μ)$ , then $μ (φ) = true$ when $μ (? X) = μ (? Y)$ , and $μ (φ) = false$ otherwise. If $? X \notin dom (μ)$ or $? Y \notin dom (μ)$ then $μ (φ) = error$ .
–
If $φ$ is $bound (? X)$ and $? X \in dom (μ)$ then $μ (φ) = true$ ; otherwise $μ (φ) = false$ .
–
If $φ$ is a complex filter condition, then it is evaluated following the three-valued logic shown in Table 3.

Table 3.
Evaluation of Complex Filter Conditions (Prud’hommeaux & Seaborne, 2008, § 17.2), where $μ$ is a Solution Mapping, and $φ_{1}$ , $φ_{2}$ are Filter Conditions.

$μ (φ_{1})$ $μ (φ_{2})$ $μ (φ_{1}) \land μ (φ_{2})$ $μ (φ_{1}) \lor μ (φ_{2})$

true true true true

true false false true

true error error true

false true false true

false false false false

false error false error

error true error true

error false false error

error error error error

$μ (φ_{1})$ $\neg (μ (φ_{1}))$

true false

false true

error error

The evaluation of a pattern $P$ on a graph $G$ is defined as a function $⟦ P ⟧_{G}$ , which returns a multiset of mappings. Let $P_{1}, P_{2}$ be SPARQL patterns, $φ$ be a filter condition, and $W$ be a set of variables. For simplicity of reading, denote $M = ⟦ P ⟧_{G}$ , $M_{1} = ⟦ P_{1} ⟧_{G}$ , and $M_{2} = ⟦ P_{2} ⟧_{G}$ . The evaluation $⟦ P ⟧_{G}$ is defined recursively as follows:

–
If $P$ is a triple pattern $t$ then $set (M) = {μ ∣ dom (μ) = var (t), μ (t) \in G}$ , where $μ (t)$ is the triple obtained by replacing the variables in $t$ according to $μ$ , and $card (μ, M) = 1$ .
–
If $P$ is $(P_{1} AND P_{2})$ then $set (M) = {μ_{1} \cup μ_{2} ∣ μ_{1} \in M_{1}, μ_{2} \in M_{2}, and μ_{1} \sim μ_{2}}$ and $card (μ, M) = \sum_{μ = μ_{1} \cup μ_{2}} card (μ_{1}, M_{1}) \times card (μ_{2}, M_{2})$ .
–
If $P$ is $(P_{1} UNION P_{2})$ then $set (M) = {μ ∣ μ \in M_{1} \lor μ \in M_{2}}$ and $card (μ, M) = card (μ, M_{1}) + card (μ, M_{2})$ .
–
If $P$ is $(P_{1} EXCEPT P_{2})$ then $set (M) = {μ ∣ μ \in M_{1}, μ \notin M_{2}}$ and $card (μ, M) = card (μ, M_{1})$ .
–
If $P$ is $(P_{1} FILTER φ)$ then $set (M) = {μ ∣ μ \in M_{1}, μ (φ) = true}$ and $card (μ, M) = card (μ, M_{1})$ .
–
If $P$ is $(SELECT W P_{1})$ then $set (M) = {μ^{'} ∣ μ^{'} = μ_{| W} \land μ \in M_{1}}$ and $card (μ^{'}, M) = \sum_{μ^{'} = μ_{| W}} card (μ, M_{1})$ .

To facilitate the translation from SPARQL to relational algebra and Datalog, we use the difference operator $EXCEPT$ in SPARQL, called SetMinus by Kontchakov and Kostylev (2016). Kontchakov and Kostylev (2016) proved that, over this fragment, the operator $EXCEPT$ and the pair of standard operators ${MINUS, OPTIONAL}$ are mutually expressible.
3.4. Normalization of SPARQL Patterns

$μ (φ_{1})$	$μ (φ_{2})$	$μ (φ_{1}) \land μ (φ_{2})$	$μ (φ_{1}) \lor μ (φ_{2})$
true	true	true	true
true	false	false	true
true	error	error	true
false	true	false	true
false	false	false	false
false	error	false	error
error	true	error	true
error	false	false	error
error	error	error	error
$μ (φ_{1})$	$\neg (μ (φ_{1}))$
true	false
false	true
error	error

The solution mappings of a SPARQL pattern $P$ may have different domains. To translate SPARQL to languages built upon relations, we require representing multisets of mappings as relations whose tuples have the same set of attributes. This set of attributes has to contain all variables that can appear in the solution mappings of $P$ . The SPARQL specification (Harris & Seaborne, 2013) defines a finite set of variables, called in-scope, that include all variables of a SPARQL pattern $P$ that can occur in the solution mappings of $P$ . To complete the relation, unbound values need to be denoted with a distinguished constant of the target language.

Example 2
Assume a pattern $P$ with in-scope variables $? X$ , $? Y$ , and $? Z$ that returns the multiset of mappings $Ω = {[{? X \mapsto a}, {? X \mapsto b, ? Y \mapsto c}, {? Y \mapsto d}]}$ . Since all variables in the solution mappings are ensured to be in-scope variables of $P$ , we can represent this multiset of mappings as the following relation ( $⊥$ denotes the distinguished constant to denote unbound values):
$[\begin{matrix} ? X & ? Y & ? Z \\ a & ⊥ & ⊥ \\ b & c & ⊥ \\ ⊥ & d & ⊥ \end{matrix}]$
.

In-scope variables are defined as follows. Let $P_{1}$ , $P_{2}$ , and $P_{3}$ be patterns, $φ$ be a filter condition, and $W$ be a set of variables. The set of in-scope variables of a pattern $P$ , denoted $inScope (P)$ , is defined recursively as follows:
If $P$ is a triple pattern, then $inScope (P)$ is the set of variables occurring in $P$ .

If $P$ is $(P_{1} AND P_{2})$ or $(P_{1} UNION P_{2})$ then $inScope (P) = inScope (P_{1}) \cup inScope (P_{2})$ ;

If $P$ is $(P_{1} FILTER φ)$ or $(P_{1} EXCEPT P_{2})$ then $inScope (P) = inScope (P_{1})$ ;

If $P$ is $(SELECT W P_{1})$ then $inScope (P) = W$ .

So far, we have described how to translate the results of SPARQL queries to relations. However, languages built upon relations have some restrictions that make a straightforward translation of the SPARQL operations difficult. The relational selection operation requires all attributes in the selection formula to be attributes of the relation; the relational union is done over relations of the same schema; and the relational difference requires all variables in the subtrahend to be instanced in the minuend. Conversely, SPARQL does not have these restrictions. We next present a normal form to simplify the translation from SPARQL to relational languages by satisfying the constraints of the target languages.
Definition 3 SPARQL normal form

A pattern $P$ is said to be in normalized or in normal form if the following conditions hold:

For every subpattern $(P_{1} FILTER φ)$ in $P$ it holds that $var (φ) \subseteq inScope (P_{1})$ ;

For every subpattern $(P_{1} UNION P_{2})$ in $P$ it holds that $inScope (P_{1}) = inScope (P_{2})$ ;

For every subpattern $(P_{1} EXCEPT P_{2})$ in $P$ it holds that $inScope (P_{1}) = inScope (P_{2})$ .

Lemma 1
Every SPARQL query (in the fragment described in Section 3.2) can be rewritten as an equivalent normalized SPARQL query.
Proof.
The conditions that make a pattern normalized refer to restrictions on the in-scope variables of patterns. Patterns that are not normalized include at least one subpattern that has either the form $(P_{1} FILTER φ)$ , $(P_{2} UNION P_{3})$ , or $(P_{2} EXCEPT P_{3})$ , where $φ$ contains a variable $? X \notin inScope (P_{1})$ , and $inScope (P_{2}) \neq inScope (P_{3})$ . We next present a method to normalize these patterns.

Given a pattern $P$ , and a finite set of variables $X$ , $P \equiv (SELECT (inScope (P) \cup X) P)$ . Indeed, a mapping $μ$ is a solution of the pattern $(SELECT (inScope (P) \cup X) P)$ if and only there exists a solution mapping $μ^{'}$ of pattern $P$ such that $μ = μ^{'} |_{inScope (P) \cup X}$ . By the definition of the in-scope variables, $dom (μ^{'}) \subseteq inScope (P)$ . Then, $dom (μ^{'}) \subseteq inScope (P) \cup X$ . Then, $μ = μ^{'}$ . Hence, $P \equiv (SELECT (inScope (P) \cup X) P)$ .

Let $P_{1}^{'}$ , $P_{2}^{'}$ , and $P_{3}^{'}$ be the patterns defined as follows:
$\begin{aligned} P_{1}^{'} & = (SELECT (inScope (P_{1}) \cup var (φ)) P_{1}), \\ P_{2}^{'} & = (SELECT (inScope (P_{2}) \cup inScope (P_{3})) P_{2}), \\ P_{3}^{'} & = (SELECT (inScope (P_{2}) \cup inScope (P_{3})) P_{3}) . \end{aligned}$
Since $P_{1}^{'} \equiv P_{1}$ , $P_{2}^{'} \equiv P_{2}$ , and $P_{3}^{'} \equiv P_{3}$ , the following equivalences hold:
$\begin{aligned} (P_{1} FILTER φ) \equiv (P_{1}^{'} FILTER φ), \\ (P_{2} UNION P_{3}) \equiv (P_{2}^{'} UNION P_{3}^{'}), \\ (P_{2} EXCEPT P_{3}) \equiv (P_{2}^{'} EXCEPT P_{3}^{'}) . \end{aligned}$
Unlike the patterns on the left side of these equivalences, the patterns on the right side are normalized. Indeed, by the definition of the $inScope$ function, $var (φ) \subseteq inScope (P_{1}^{'})$ and $inScope (P_{2}^{'}) = inScope (P_{3}^{'})$ . Hence, these equivalences can be used to normalize SPARQL patterns.
Example 3
Let $P$ be the pattern $(P_{1} UNION P_{2})$ where $P_{1}$ is the triple pattern $(? X, is, person)$ and $P_{2}$ is the triple pattern $(? X, email, ? Y)$ , and $G$ be the RDF graph that includes the triples $(a, is, person)$ and $(a, email, a @ ex . org)$ . The pattern $P$ is not in normal form because variable $? Y$ is in $inScope (P_{2})$ , but not in $inScope (P_{1})$ . The normal form of the pattern $P$ is a pattern $P^{'}$ that results from replacing $P_{1}$ by the pattern $P_{1}^{'} = (SELECT ? X ? Y (? X, is, person))$ . The patterns $P$ and $P^{'}$ are equivalent because the patterns $P_{1}$ and $P_{1}^{'}$ return the same multiset of solution mappings $Ω_{1} = {[{? X \mapsto a}]}$ . Note that variable $? Y$ is not in the solutions of $P_{1}$ nor $P_{1}^{'}$ . However, variable $? Y$ is in $inScope (P_{1}^{'})$ but not in $inScope (P_{1})$ . Using the in-scope variables of the patterns to translate the results of patterns $P_{1}$ and $P_{1}^{'}$ as relations, we get the respective relations
$[\begin{matrix} ? X \\ a \end{matrix}] and [\begin{matrix} ? X & ? Y \\ a & ⊥ \end{matrix}] .$
Although both relations represent the same multiset of mappings, just the second relation has the same attributes as the result of pattern $P_{2}$ , and thus can be operated with the relational union.
4. Nonrecursive Multiset Datalog With Safe Negation ( ${NRMD}^{\neg}$ )

This section presents an extension of Datalog to support multiset semantics. Based on the work of Mumick et al. (1990b), a database is defined to allow duplicate facts, and the evaluation of a fact is given by the number of different proofs for that fact. We extended Mumick’s formalism in Angles and Gutiérrez (2016) to provide a more complete formalism including negation, which we call ${MD}^{\neg}$ . Furthermore, we follow the work of Bertossi et al. (2019) for the semantics of ${MD}^{\neg}$ . We call ${NRMD}^{\neg}$ to the fragment of ${MD}^{\neg}$ restricted to nonrecursive queries.

4.1. ${NRMD}^{\neg}$ Syntax

Assume three disjoint sets: variables, constants, and predicate names. A term is either a variable or a constant. An atom is an expression $p (t_{1}, \dots, t_{n}),$ where $p$ is a predicate name and each $t_{i}$ is a term. An equality expression will be represented by an atom of the form $eq (t_{1}, t_{2})$ . A literal is either an atom (i.e., a positive literal $A$ ) or the negation of an atom (i.e., a negative literal $\neg A$ ). Given a literal $L$ , we use $var (L)$ to denote the variables in $L$ . A Horn Clause, or simply clause, is an expression containing at most one positive literal. There are three types of clauses, named facts, rules, and goals.

A fact is a positive literal that does not contain any variables. A ${MD}^{\neg}$ Database is a finite multiset of facts. The vocabulary of an ${MD}^{\neg}$ database $D$ is a pair $(P, α),$ where $P$ is the set of predicate names occurring in the facts of $D$ , and $α$ is a function defining the arity of each predicate name in $P$ , that is, if $p (c_{1}, \dots, c_{n}) \in D$ then $α (p) = n$ . The predicate names occurring in $D$ are called extensional.

A program $Π$ is a finite set of rules. A rule is an expression $L_{n + 1} \leftarrow L_{1}, \dots, L_{n},$ where $L_{n + 1}$ is a positive literal with no constants called the head, and $L_{1}, \dots, L_{n}$ ( $n \geq 1$ ) is a set of literals called the body. The predicate names occurring in the head of the rules of $Π$ are called intensional.

A variable $X$ occurs positively in a rule $R$ if and only if $X$ occurs in a positive literal in the body of $R$ . A rule $R$ is said to be safe if all its variables occur positively. Additionally, we will assume that every literal in the body of a rule has at least one variable. A program is safe if all its rules are safe. A ${MD}^{\neg}$ program is a safe program.

The dependency graph of a program $Π$ is a digraph $(N, E)$ where the set of nodes $N$ is the set of predicates names that occur in the literals of $Π$ , and there is an edge $(p_{1}, p_{2})$ in $E$ if there is a rule in $Π$ whose body contains the predicate name $p_{1}$ , and whose head contains the predicate name $p_{2}$ . A program is said to be nonrecursive if its dependency graph is acyclic. An ${NRMD}^{\neg}$ program is an ${MD}^{\neg}$ that is nonrecursive.

A goal clause is an atom without constants. An ${MD}^{\neg}$ query is a pair $(L, Π),$ where $L$ is a goal clause, and $Π$ is an ${MD}^{\neg}$ program. An ${NRMD}^{\neg}$ query is an ${MD}^{\neg}$ query $(L, Π)$ such that $Π$ is nonrecursive. An ${NRMD}^{\neg}$ database is an ${MD}^{\neg}$ database. We assume that extensional and intensional predicate symbols are disjoint; in particular, a predicate cannot appear both as a fact in the database and as the head of a rule.

4.2. ${NRMD}^{\neg}$ Semantics

We follow the formalisms by Mumick et al. (1990b) and Bertossi et al. (2019) that use a proof-theoretic semantics for ${NRMD}^{\neg}$ programs. The semantics is based on the notions of “substitution” and “derivation tree.”

A substitution is a partial function $θ$ from variables to constants. Given a literal $L$ (positive or negative), and a substitution $θ$ , we write $θ (L)$ to denote the literal $L^{'}$ obtained by replacing all variables $x$ occurring in $L$ with $θ (x)$ . Informally, the answer for a query $(L, Π)$ , where $Π$ is an ${NRMD}^{\neg}$ program, over a database $D$ , will be a multiset of substitutions with the same domain, each obtained from one proof showing that this substitution works. We will use the notion of “colored set” (Mumick et al., 1990b) to identify the different copies of an element, as introduced in Section 2.1.

The notion of “derivation tree” (Mumick et al., 1990b) will be used to count the number of proofs for an atom. Formally, a Derivation Tree is a connected, undirected graph, with no cycles, represented as a tuple $T = (N, E, L, ϵ, λ)$ where $N$ is a set of nodes, $E$ is a set of edges, $L$ is a set of labels (for nodes and edges), $ϵ : E \to N \times N$ is a total function that assigns a pair of nodes to each edge, and $λ : (N \cup E) \to L$ is a total function that assigns a label to each node and edge. The function $root (T)$ will be used to obtain the root node of $T$ .

Let $R$ be a rule of the form $L_{n + 1} \leftarrow L_{1}, \dots, L_{m}, L_{m + 1}, \dots, L_{n},$ where $L_{1}, \dots, L_{m}$ are positive literals, and $L_{m + 1}, \dots, L_{n}$ are negative literals, $DT$ be a set of derivation trees, and $ST = (T_{1}, \dots, T_{m})$ be a sequence of derivation trees that satisfy that every derivation tree in ST is also in DT. We say that DT matches $R$ with ST, denoted $DT ⊨^{ST} R$ , if there is a substitution $θ$ satisfying: (i) for every positive literal $L_{i} \in R$ it applies that $θ (L_{i}) = root (T_{i}),$ where $T_{i} \in ST$ ; and (ii) for every negative literal $L_{j} \in$ it applies that DT does not contain a derivation tree whose root node has the label $θ (L_{j})$ .

Assume that $DT ⊨^{ST} R$ where $ST = (T_{1}, \dots, T_{m})$ , $T_{1} = (N_{1}, E_{1}, L_{1}, ϵ_{1}, λ_{1})$ , $\dots$ , and $T_{m} = (N_{m}, E_{m}, L_{m}, ϵ_{m}, λ_{m})$ . The derivation tree $T_{R} = (N_{R}, E_{R}, L_{R}, ϵ_{R}, λ_{R})$ for the rule $R$ is defined as follows: $N_{R} = {n_{r}} \cup N_{1} \cup \dots \cup N_{m}$ , $E_{R} = {e_{1}, \dots, e_{m}} \cup E_{1} \cup \dots \cup E_{m}$ , $L_{R} = {R, θ (L_{n + 1})} \cup L_{1} \cup \dots \cup L_{m}$ , every assignment in $ϵ_{i}$ is also in $ϵ_{R}$ , $ϵ_{R} (e_{1}) = (n_{r}, root (T_{1}))$ , $\dots$ , $ϵ_{R} (e_{m}) = (n_{r}, root (T_{m}))$ , every assignment in $λ_{i}$ is also in $λ_{R}$ , $λ_{R} (n_{r}) = θ (L_{n + 1})$ , and $λ_{R} (e_{1}) = R$ .

Let $D$ be an ${NRMD}^{\neg}$ database and $Π$ an ${NRMD}^{\neg}$ program. The set of derivation trees of $Π$ with respect to $D$ , denoted $dt (Π, D)$ , is defined as follows:

For every fact $F \in D$ of the form $p (t_{i}, \dots, t_{n})$ , and for every colored copy $⟨ p (t_{i}, \dots, t_{n}), i ⟩$ , it applies that $dt (Π, D)$ contains a derivation tree $T_{F}^{i} = (N_{F}^{i}, E_{F}^{i}, L_{F}^{i}, ϵ_{F}^{i}, λ_{F}^{i}),$ where $N_{F}^{i} = {n_{1}, n_{2}}$ , $E_{F}^{i} = {e_{1}}$ , $L_{F}^{i} = {p (t_{i}, \dots, t_{n}), ⟨ p (t_{i}, \dots, t_{n}), i ⟩, F}$ , $ϵ_{F}^{i} (e_{1}) = (n_{1}, n_{2})$ , $λ_{F}^{i} (n_{1}) = p (t_{i}, \dots, t_{n})$ , $λ_{F}^{i} (n_{2}) = ⟨ p (t_{i}, \dots, t_{n}), i ⟩$ , and $λ_{F}^{i} (e_{1}) = F$ .

Assume that DT is the set of derivation trees obtained for the facts in $D$ as defined above. Given a rule $R$ in $Π$ and a sequence of derivation trees ST satisfying $DT ⊨^{ST} R$ , the derivation tree for $R$ is added to DT. This process is repeated for every rule $R$ in $Π$ , until no more derivation trees are generated. Finally, $dt (Π, D) = DT$ .

Let $Π$ be an ${NRMD}^{\neg}$ program, $D$ be an ${NRMD}^{\neg}$ database and $F$ be a fact. A derivation tree $T \in dt (Π, D)$ is said to be a proof for the fact $F$ if the label of the root node is $F$ . The multiset of atoms of $Π$ in $D$ , denoted $atoms (Π, D)$ , is the multiset of facts $F$ such that there is a proof for $F$ in $dt (Π, D)$ , and the cardinality of $F$ in $atoms (Π, D)$ is the number of proofs of $F$ . Figure 3 shows the derivation trees that are proofs of the facts derived from an example ${NRMD}^{\neg}$ program. The facts $r (a)$ , $p (a)$ , and $q (a)$ belong to $atoms (Π, D)$ with cardinalities 2, 2, and 4.

Figure 3.

Example of derivation trees. Let $D$ be a nonrecursive multiset Datalog with safe negation ( ${NRMD}^{\neg}$ ) database, $F = r (a)$ be a fact in $D$ with $card (F, D) = 2$ , $Π = {R, S}$ be an ${NRMD}^{\neg}$ program where $R$ is the rule $q (X) \leftarrow r (X), p (X)$ and $S$ is the rule $p (X) \leftarrow r (X)$ . This figure shows the derivation trees of $Π$ with respect to $D$ .

The ${NRMD}^{\neg}$ query language over a vocabulary $τ$ is the query language $(Q, D, S, ⟦ \cdot ⟧_{\cdot})$ where:

$Q$ is the set of ${NRMD}^{\neg}$ queries over $τ$ ;

$D$ is the set of ${NRMD}^{\neg}$ databases over $τ$ ;

$S$ is the set of ${NRMD}^{\neg}$ query answers (i.e., pairs $(V, M)$ , where $V$ is a set of variables and $M$ is a multiset of substitutions $θ$ with $dom (θ) = V$ ); and

$⟦ \cdot ⟧$ is the function that receives an ${NRMD}^{\neg}$ query $(L, Π)$ and an ${NRMD}^{\neg}$ database $D$ , and returns an ${NRMD}^{\neg}$ query answer $(V, M)$ , where $V = var (L)$ , $set (M) = {θ ∣ θ (L) \in atoms (Π, D) and dom (θ) = V}$ , and $card (θ, M) = card (θ (L), atoms (Π, D))$ .

Observe that the domain of the query answer for a query $(L, Π)$ is $var (L)$ . Abusing notation, we will say that it is also the domain of the query $(L, Π)$ , denoted $dom ((L, Π)) = var (L)$ .

The multiset Datalog query language presented here, ${NRMD}^{\neg}$ , differs from the version proposed by Bertossi et al. (2019) in that we do not allow recursive programs nor constants in the head of rules. These restrictions permit us to match the expressive power of the SPARQL fragment studied here.

4.3. Normalization of

{NRMD}^{\neg}

Programs

To simplify the translations from

{NRMD}^{\neg}

to SPARQL and

M R A

, we assume that every

{NRMD}^{\neg}

query is normalized into a query that contains only rules of the three following types:

Next, we show the feasibility of this normalization.

Lemma 2
Every ${NRMD}^{\neg}$ query is equivalent to a normalized ${NRMD}^{\neg}$ query.
Proof.
We provide a normalization algorithm that replaces every rule in the query by a set of rules that do not change the semantics of the query. Given an ${NRMD}^{\neg}$ query $(L, Π)$ , every rule $R \in Π$ has the form
$p (\bar{X}) \leftarrow A_{1}, \dots, A_{m}, \neg B_{1}, \dots, \neg B_{n},$
where $A_{1}, \dots, A_{m}$ are positive literals, and $\neg B_{1}, \dots, \neg B_{n}$ are negative literals. For $1 \leq i \leq m$ , let ${\bar{Y}}_{i}$ be the set of variables that consists of the variables occurring in the atoms $A_{1}, \dots, A_{i}$ . Then, we replace rule $R$ by the minimal set of rules $Π_{R}$ that includes the following rules:
Rules $R_{i}^{A}$ , for $2 \leq i \leq m$ , defined recursively as follows: (a)
$R_{2}^{A} = q_{2}^{A} ({\bar{Y}}_{2}) \leftarrow A_{1}, A_{2}$ .
(b)
$R_{i}^{A} = q_{i}^{A} ({\bar{Y}}_{i}) \leftarrow q_{i - 1}^{A} ({\bar{Y}}_{i - 1}), A_{i}$ .

Rules $R_{j}^{B}$ and $R_{j}^{B^{'}}$ for $1 \leq j \leq n$ , defined recursively as follows: (a)
$R_{0}^{B} = r_{0}^{B} ({\bar{Y}}_{m}) \leftarrow q_{m}^{A} ({\bar{Y}}_{m})$ ,
(b)
$R_{j}^{B} = r_{j}^{B} ({\bar{Y}}_{m}) \leftarrow r_{j - 1}^{B} ({\bar{Y}}_{m}), \neg B_{j}^{'} ({\bar{Y}}_{m})$ ,
(c)
$R_{j}^{B^{'}} = B_{j}^{'} ({\bar{Y}}_{m}) \leftarrow r_{j - 1}^{B} ({\bar{Y}}_{m}), B_{j}$ .

A rule $R^{'} = p (\bar{X}) \leftarrow r_{n}^{B} ({\bar{Y}}_{m}) .$
Let $(L, Π^{'})$ be the query resulting from replacing rule $R$ with the rules in $Π_{R}$ . It is clear that the program is normal (recall that the original program is safe). Need to show that both programs are equivalent, that is, that the solutions of query $(p (\bar{X}), Π)$ after the replacement are the same and have the same cardinalities. These two conditions follow from Claim 3 in the Appendix.
5. Multiset Relational Algebra (MRA)

The MRA used in this paper is based on the semantics defined by Dayal et al. (1982). This algebra considers the operations of selection, projection, natural join, and arithmetic union. Additionally, we include operators for renaming and filter difference (or “except”).

5.1. Multiset Relations

Assume that $N, A, C$ are disjoint infinite sets, where $N$ is the domain of relation names, $A$ is the domain of attributes, and $C$ is the domain of constants or values.

A relation schema is given by a relation name $R \in N$ and a set of attributes ${A_{1}, \dots, A_{n}}$ , where $A_{i} \in A$ for $1 \leq i \leq n$ . To simplify the notation, we will use the relation name $R$ to denote the relation schema, and $\hat{R}$ to denote the attributes of $R$ . A relational database schema is a finite set of relation schemas.

A tuple over a relation schema $R$ with attributes $\hat{R} = {A_{1}, \dots, A_{n}}$ is a total mapping $t$ from $\hat{R}$ to $C$ . The value of tuple $t$ on an attribute $A_{i} \in \hat{R}$ will be denoted as $t (A_{i})$ . Given a set of attributes $U \subseteq \hat{R}$ and a tuple $t$ , we write $t [U]$ to denote the tuple $t^{'}$ with attributes $U$ such that $t^{'} (A) = t (A)$ for every attribute $A \in U$ .

A multiset relation $r$ over a relation schema $R$ is a multiset of tuples over $\hat{R}$ . We write $\hat{r}$ to denote the relation schema $R$ , where the multiset relation $r$ is defined. Given a tuple $t \in r$ , we will use $card (t, r)$ to denote the cardinality of tuple $t$ in $r$ .

A relational database schema is a set of relation schemas. Given a relational database schema $T = {R_{1}, \dots, R_{n}}$ , a multiset relational database over $T$ is a set of multiset relations ${r_{1}, \dots, r_{n}}$ , where each relation $r_{i}$ is defined over the schema $R_{i}$ . Sometimes we will write MRA database, emphasizing that the multiset relational database is in the context of MRA.

Let $r_{1}, r_{2}$ be two multiset relations, and $t_{1} \in r_{1}$ and $t_{2} \in r_{2}$ be tuples. We say that $t_{1}$ and $t_{2}$ are compatible, denoted $t_{1} \sim t_{2}$ , if (i) for every attribute $A \in {\hat{r}}_{1} \cap {\hat{r}}_{2}$ it holds that $t_{1} (A) = t_{2} (A)$ , or (ii) ${\hat{r}}_{1} \cap {\hat{r}}_{2} = \emptyset$ . If $t_{1}$ and $t_{2}$ are compatible, then the merge of them, denoted $t_{1} \cup t_{2}$ , is the tuple $t$ with attributes ${\hat{r}}_{1} \cup {\hat{r}}_{2}$ , where $t (A) = t_{1} (A)$ for each attribute $A \in {\hat{r}}_{1}$ , and $t (B) = t_{2} (B)$ for each attribute $B \in {\hat{r}}_{2} ∖ {\hat{r}}_{1}$ .

5.2. Syntax of MRA

The MRA defined in this paper includes the operators of selection ( $σ$ ), projection ( $π$ ), renaming ( $ρ$ ), join ( $⋈$ ), union ( $\cup$ ), and except ( $∖$ ). Next, we describe the syntax of MRA expressions containing the above operators.

A selection formula $ψ$ is a Boolean combination of equality expressions of the form $x = y$ , where $x, y \in A \cup C$ . We define an MRA expression $E$ over a relational database schema $T$ , and the attributes of $E$ , denoted $\hat{E}$ , by mutual recursion as follows:

–
A relation name $R \in T$ is an MRA expression $E$ , and $\hat{E} = \hat{R}$ .
–
If $E_{1}$ is an MRA expression and $ψ$ is a selection formula where the attributes occurring in $ψ$ are included in ${\hat{E}}_{1}$ , then $σ_{ψ} (E_{1})$ is an MRA expression $E$ , and $\hat{E} = {\hat{E}}_{1}$ .
–
If $E_{1}$ is an MRA expression and $S \subseteq {\hat{E}}_{1}$ is a set of attributes, them $π_{S} (E_{1})$ is an MRA expression $E$ , and $\hat{E} = S$ .
–
If $E_{1}$ is an MRA expression, $A \in {\hat{E}}_{1}$ and $B \in A$ are attributes, then $ρ_{A / B} (E_{1})$ is an MRA expression $E$ , and $\hat{E} = ({\hat{E}}_{1} ∖ A) \cup B$ .
–
If $E_{1}$ and $E_{2}$ are MRA expressions, then $(E_{1} ⋈ E_{2})$ is an MRA expression $E$ , and $\hat{E} = {\hat{E}}_{1} \cup {\hat{E}}_{2}$ .
–
If $E_{1}$ and $E_{2}$ are MRA expressions and ${\hat{E}}_{1} = {\hat{E}}_{2}$ , then $(E_{1} ∖ E_{2})$ is an MRA expression $E$ , and $\hat{E} = {\hat{E}}_{1}$ .
–
If $E_{1}$ and $E_{2}$ are MRA expressions and ${\hat{E}}_{1} = {\hat{E}}_{2}$ , then $(E_{1} \cup E_{2})$ is an MRA expression $E$ , and $\hat{E} = {\hat{E}}_{1}$ .

Note that a selection operation $σ_{ψ} (E_{1})$ requires that attributes in the selection formula $ψ$ be attributes of the MRA expression $E_{1}$ ; the projection operation $π_{S} (E_{1})$ requires that $S$ be a subset of the attributes of the MRA expression $E_{1}$ ; and that the union $E_{1} \cup E_{2}$ and difference $E_{1} ∖ E_{2}$ expressions require that expressions $E_{1}$ and $E_{2}$ have the same set of attributes.
5.3. Semantics of MRA

Given a selection formula $ψ$ and a tuple $t$ over a relation schema $R$ , we will use $t ⊨ ψ$ to denote that $t$ satisfies $ψ$ , and its evaluation is given as follows:

If $ψ$ is $A = B$ , where $A, B \in \hat{R}$ are attributes, then $t ⊨ ψ$ iff $t (A) = t (B)$ .

If $ψ$ is $A = c$ , where $A \in \hat{R}$ is an attribute and $c \in C$ is a constant, then $t ⊨ ψ$ iff $t (A) = c$ .

If $ψ$ is $c_{1} = c_{2}$ , where $c_{1}, c_{2} \in C$ are constants, then $t ⊨ ψ$ iff $c_{1}$ is the same constant as $c_{2}$ .

If $ψ$ is $ψ_{1} \land ψ_{2}$ , then $t ⊨ ψ$ iff $t ⊨ ψ_{1}$ and $t ⊨ ψ_{2}$ .

If $ψ$ is $ψ_{1} \lor ψ_{2}$ , then $t ⊨ ψ$ iff $t ⊨ ψ_{1}$ or $t ⊨ ψ_{2}$ .

If $ψ$ is $\neg ψ_{1}$ , then $t ⊨ ψ$ iff $t ⊨ ψ_{1}$ does not hold.

Now, the evaluation of an MRA expression $E$ over a multiset relational database $D$ (of the same schema as $E$ ) is defined as a function $Eval (E, D)$ that returns a multiset relation $r$ with the same schema as $E$ .

Let $D$ be an MRA database over a schema $T$ and $E, E_{1}, E_{2}$ be MRA expressions over $T$ . The evaluation of $Eval (E, D)$ is the multiset relation $r$ defined recursively as follows (assume that $Eval (E_{1}, D) = r_{1}$ , and $Eval (E_{2}, D) = r_{2}$ ):

–
If $E$ is a relation name $R_{1} \in T$ , then $r$ is the relation for the relation name $R_{1}$ in the database $D$ .
–
If $E$ is $σ_{ψ} (E_{1})$ then $set (r) = {t ∣ t \in r_{1} and t ⊨ ψ}$ and $card (t, r) = card (t, r_{1})$ .
–
If $E$ is $π_{S} (E_{1})$ then $set (r) = {t^{'} ∣ t^{'} = t [S] and t \in r_{1}}$ and $card (t^{'}, r) = \sum_{t with t [S] = t^{'}} card (t, r_{1})$ .
–
If $E$ is $ρ_{A / B} (E_{1})$ then $r$ is the result from renaming in $r_{1}$ the attribute $A$ as $B$ .
–
If $E$ is $(E_{1} ⋈ E_{2})$ then $set (r) = {t_{1} \cup t_{2} ∣ t_{1} \in r_{1}, t_{2} \in r_{2}, and t_{1} \sim t_{2}}$ and $card (t_{1} \cup t_{2}, r) = card (t_{1}, r_{1}) \times card (t_{2}, r_{2})$ .
–
If $E$ is $(E_{1} \cup E_{2})$ then $set (r) = {t ∣ t \in r_{1} or t \in r_{2}}$ and $card (t, r) = card (t, r_{1}) + card (t, r_{2})$ .
–
If $E$ is $(E_{1} ∖ E_{2})$ then $set (r) = {t ∣ t \in r_{1} and t \notin r_{2}}$ and $card (t, r) = card (t, r_{1})$ .

Hence, in MRA, the set of queries is the set of MRA expressions, the set of databases is the set of multiset relational databases, the set of results is the set of multiset relations, and the evaluation procedure is the aforementioned function $Eval$ .
6. Equivalence Between SPARQL and ${NRMD}^{\neg}$

This section presents the simulations that prove that SPARQL and ${NRMD}^{\neg}$ have the same expressive power. Specifically, we show that SPARQL can be simulated by ${NRMD}^{\neg}$ (Section 6.1), and ${NRMD}^{\neg}$ can be simulated by SPARQL (Section 6.2).

6.1. From SPARQL to ${NRMD}^{\neg}$

This section shows that SPARQL can be simulated by ${NRMD}^{\neg}$ . To support this, we describe the following translation functions:

–
function $f_{12}$ that translates SPARQL queries into ${NRMD}^{\neg}$ queries;
–
function $g_{12}$ that translates SPARQL databases into ${NRMD}^{\neg}$ databases; and
–
function $h_{12}$ that translates ${NRMD}^{\neg}$ query answers into SPARQL query answers.

6.1.1. Translating Databases From SPARQL to ${NRMD}^{\neg}$

Recall that a SPARQL database is a set of RDF triples, and an ${NRMD}^{\neg}$ database is a multiset of facts. Given this, the basic idea is to translate each RDF triple into a Datalog atom. Additionally, we create an atom to encode all RDF terms, and an atom to encode the unbound value.

Definition 4 Function $g_{12}$

Let $⊥$ be an RDF term that will exclusively be used to encode the unbounded value. Let $(P, α)$ be a Datalog vocabulary where $P = {term, eq, comp, triple, null}$ and $α (term) = 1$ , $α (eq) = 2$ , $α (comp) = 3$ , $α (triple) = 3$ , and $α (null) = 1$ . Given an RDF graph $G$ , the function $g_{12} (G)$ returns an ${NRMD}^{\neg}$ database $D$ with vocabulary $(P, α)$ , where the multiset of facts in $D$ is defined as follows:

–
for each RDF term $t$ in $terms (G)$ (i.e., the set of terms in $G$ ) , $D$ contains the facts $term (t)$ , $eq (t, t)$ , $comp (t, t, t)$ , $comp (t, ⊥, t)$ , $comp (⊥, t, t)$ ;
–
for each RDF triple $(s, p, o) \in G$ , $D$ contains the fact $triple (s, p, o)$ ;
–
$D$ contains the fact $comp (⊥, ⊥, ⊥)$ ;
–
$D$ contains the fact $null (⊥) \in D$ .

Intuitively: a fact of the form $term (t)$ is used to represent that $t$ is an RDF term; a fact of the form $eq (t, t)$ is used to represent the equality of the RDF term $t$ ; for each term $t$ in $G$ , the notion of compatible is represented by the facts $comp (t, t, t)$ , $comp (t, ⊥, t)$ , and $comp (⊥, t, t)$ ; a fact of the form $triple (s, p, o)$ is used to represent an RDF triple $(s, p, o)$ .
Example 4
Let $G$ be the RDF graph defined as follows:
$G = {\begin{aligned} (A l i c e, l i v e s I n, S a n t i a g o), (A l i c e, k n o w s, B o b), (B o b, l i v e s I n, S a n t i a g o), (B o b, k n o w s, C a r o l), \\ (C a r o l, l i v e s I n, L i m a)} . \end{aligned}$
The translation of the above RDF triples into Datalog facts is given as follows:
$g_{12} (G) = {[\begin{aligned} term (A l i c e), eq (A l i c e, A l i c e), \\ comp (A l i c e, A l i c e, A l i c e), comp (A l i c e, ⊥, A l i c e), comp (⊥, A l i c e, A l i c e), \\ ⋮ \\ term (L i m a), eq (L i m a, L i m a), \\ comp (L i m a, L i m a, L i m a), comp (L i m a, ⊥, L i m a), comp (⊥, L i m a, L i m a), \\ triple (A l i c e, l i v e s I n, S a n t i a g o), triple (A l i c e, k n o w s, B o b), triple (B o b, l i v e s I n, S a n t i a g o), \\ triple (B o b, k n o w s, C a r o l), triple (C a r o l, l i v e s I n, L i m a), \\ comp (⊥, ⊥, ⊥), \\ null (⊥) \\ ]} . \end{aligned}$

6.1.2. Translating Queries From SPARQL to ${NRMD}^{\neg}$

In general terms, any SPARQL graph pattern can be translated into a set of ${NRMD}^{\neg}$ rules. However, there are some subtleties that need to be discussed before presenting the general translation rules.

An initial issue is the translation of a filter graph pattern $P = (P_{1} FILTER φ)$ , where $φ$ is a complex filter condition. In order to simplify the translation to Datalog, we need to transform $P$ into a collection of filter graph patterns where every filter condition is an atomic filter condition.

Consider the following equivalences:

\begin{aligned} (P_{1} FILTER φ_{1} \land φ_{2}) \equiv ((P_{1} FILTER φ_{1}) FILTER φ_{2}) . \end{aligned}

(1)

\begin{aligned} (P_{1} FILTER φ_{1} \lor φ_{2}) \equiv (P_{1} FILTER φ_{1}) UNION (P_{1} FILTER φ_{2}) . \end{aligned}

(2)

\begin{aligned} (P_{1} FILTER \neg (φ_{1})) \equiv (P_{1} EXCEPT (P_{1} FILTER φ_{1})) . \end{aligned}

(3)

Intuitively, these equivalences seem to be true, since similar equivalences are valid in set relational algebra, namely

σ_{φ_{1} \land φ_{2}} (R) = σ_{φ_{1}} (σ_{φ_{2}} (R))

σ_{φ_{1} \lor φ_{2}} (R) = σ_{φ_{1}} (R) \cup σ_{φ_{2}} (R)

, and

σ_{\neg φ_{1}} (R) = R ∖ σ_{φ_{1}} (R)

. Under set semantics, these three equivalences are valid. However, under bag semantics, just equivalence (1) is valid, and equivalences (2) and (3) present problems. Let us analyze them and provide valid equivalences.

–

To see why equivalence (2) is not valid, consider the case where for a solution $μ$ of the pattern $P_{1}$ , the evaluation of formulas $φ_{1}$ and $φ_{2}$ is true. Then, $μ$ is a solution of the queries in both sides of equivalence (2). However, the cardinality differs. Indeed, the cardinality of $μ$ for the query on the right side is twice the cardinality for the query on the left side. Hence, equivalence (2) is valid for set semantics but not for bag semantics.

–

To see why equivalence (3) is not valid, consider the case where for a solution mapping $μ$ of the pattern $P_{1}$ , formula $φ_{1}$ produces an error. Then, formula $\neg φ_{1}$ also produces an error, and hence $μ$ is not a solution to the query on the left side. On the other hand, since $μ$ is a solution mapping for $P_{1}$ but not a solution to the pattern $(P_{1} FILTER φ_{1})$ , $μ$ is a solution mapping to the query on the right side. Hence, this equivalency is not valid because the queries do not have the same solution mappings.

Intuitively, equivalence (2) is no longer valid when we change from set semantics to bag semantics, whereas equivalence (3) is no longer valid when we change from two-valued logic to three-valued logic. In the following, we show how to solve these problems.

Lemma 3 Rewriting of disjoint filter conditions

We say that two filter conditions $φ_{1}$ and $φ_{2}$ are disjoint, if for every mapping $μ$ it does not hold that $μ (φ_{1})$ and $μ (φ_{2})$ are simultaneously $true$ . Equivalence (2) is true when $φ_{1}$ and $φ_{2}$ are disjoint.

Proof.
Given that $φ_{1}$ and $φ_{2}$ are disjoint, it applies that $μ (φ_{1})$ is $true$ when $μ (φ_{2})$ is not $true$ (and vice versa). So, it holds that $μ (φ_{1} \lor φ_{2}) = true$ if and only if $μ (φ_{1}) = true$ or $μ (φ_{2}) = true$ , and the cardinality of $μ$ on the left-hand side is the sum of the cardinalities of $μ$ in each of the terms of the right-hand side.

Now, consider the following equivalence:
$\begin{aligned} (P_{1} FILTER φ_{1} \lor φ_{2}) \equiv & (P_{1} FILTER φ_{1} \land \neg φ_{2}) UNION \\ (P_{1} FILTER \neg φ_{1} \land φ_{2}) UNION \\ (P_{1} FILTER φ_{1} \land φ_{2}) . \end{aligned}$
(4)

Equivalence (4) solves one of the problems of equivalence (2), but it still has problems in evaluating formulas with errors. In order to solve them, we introduce the notion of “error filter condition.”
Definition 5 Error filter condition

Let $φ$ , $φ_{1},$ and $φ_{2}$ be filter conditions. The function $Error (φ)$ returns a filter condition defined recursively as follows:

–
if $φ$ is $bound (? X)$ then $Error (φ) = false;$
–
if $φ$ is $? X = a$ then $Error (φ) = \neg bound (? X)$ ;
–
if $φ$ is $? X = ? Y$ then $Error (φ)$ = $(\neg bound (? X) \land bound (? Y))$ $\lor$ $(bound (? X) \land \neg bound (? Y))$ $\lor$ $(\neg bound (? X) \land \neg bound (? Y))$ ;
–
if $φ$ is $φ_{1} \land φ_{2}$ then $Error (φ)$ = $(φ_{1} \land Error (φ_{2}))$ $\lor$ $(Error (φ_{1}) \land φ_{2})$ $\lor$ $(Error (φ_{1}) \land Error (φ_{2}))$ ;
–
if $φ$ is $φ_{1} \lor φ_{2}$ then $Error (φ)$ = $(\neg φ_{1} \land Error (φ_{2}))$ $\lor$ $(Error (φ_{1}) \land \neg φ_{2})$ $\lor$ $(Error (φ_{1}) \land Error (φ_{2}))$ ;
–
if $φ$ is $\neg φ_{1}$ then $Error (φ)$ = $Error (φ_{1})$ .

Lemma 4
For every filter condition $φ$ and mapping $μ$ it holds that $μ (φ) = error$ if and only if $μ (Error (φ)) = true$ .
Proof.
This lemma is proved by induction on the structure of the filter condition (see Claim 1 in the Appendix).
Example 5
Let $φ$ be the filter condition $L \lor \neg L$ , where $L$ is the equality $? X = a$ . According to Definition 5, $Error (φ)$ will be the filter condition $(\neg L \land Error (\neg L)) \lor (Error (L) \land \neg \neg L) \lor (Error (L) \land Error (\neg L))$ . Since $\neg \neg L$ is equivalent to $L$ and $Error (\neg L)$ is equivalent to $Error (L)$ , then $Error (φ)$ is equivalent to $(\neg L \land Error (L)) \lor (Error (L) \land L) \lor (Error (L))$ , which is equivalent to $(φ \land Error (L)) \lor (Error (L))$ , and then, equivalent to $Error (L)$ . According to Definition 5, we conclude that $Error (φ)$ is equivalent to $\neg bound (? X)$ .

There are three possible values for variable $? X$ in a mapping $μ$ , namely $μ (? X) = a$ , $μ (? X) = b$ (for a term $b \neq a$ ), and variable $? X$ is unbound in $μ$ (denoted $μ (? X) = ⊥$ ). The following table shows the values for $μ (φ)$ and $μ (Error (φ))$ for these three cases.

As defined by Lemma 4, the filter condition $φ$ produces error for mappings $μ$ , where $μ (Error (φ)) = true$ , and $μ (Error (φ))$ is either $true$ or $false$ .

Now we present an equivalence for the disjunction that works in all cases.
Lemma 5 Disjunction rewriting

Given two filter conditions $φ_{1}$ and $φ_{2}$ , and a pattern $P$ , the following equivalence holds for bag semantics:

\begin{aligned} (P FILTER φ_{1} \lor φ_{2}) \equiv & (P FILTER φ_{1} \land φ_{2}) UNION \\ (P FILTER φ_{1} \land \neg φ_{2}) UNION \\ (P FILTER \neg φ_{1} \land φ_{2}) UNION \\ (P FILTER φ_{1} \land Error (φ_{2})) UNION \\ (P FILTER Error (φ_{1}) \land φ_{2}) . \end{aligned}

(5)

Proof.

Since $φ \lor \neg φ \lor Error (φ)$ is a tautology for every filter condition $φ$ , the following equivalences hold:

\begin{aligned} φ_{1} & \equiv φ_{1} \land (φ_{2} \lor \neg φ_{2} \lor Error (φ_{2})) \equiv (φ_{1} \land φ_{2}) \lor (φ_{1} \land \neg φ_{2}) \lor (φ_{1} \land Error (φ_{2})), \\ φ_{2} & \equiv φ_{2} \land (φ_{1} \lor \neg φ_{1} \lor Error (φ_{1})) \equiv (φ_{2} \land φ_{1}) \lor (φ_{2} \land \neg φ_{1}) \lor (φ_{2} \land Error (φ_{1})) . \end{aligned}

Hence, the following equivalence holds:

\begin{aligned} φ_{1} \lor φ_{2} & \equiv (φ_{1} \land φ_{2}) \lor (φ_{1} \land \neg φ_{2}) \lor (\neg φ_{1} \land φ_{2}) \lor (φ_{1} \land Error (φ_{2})) \lor (Error (φ_{1}) \land φ_{2}) . \end{aligned}

Since all filter conditions in the disjunction of the right side of this equivalence are disjoint, by Lemma 3, we got equivalence (5).

Finally, we provide a translation for filter graph patterns that have a negation. Under two-valued logic, the evaluation of a pattern $P$ of the form $(P_{1} FILTER \neg φ)$ may be understood as “all solutions $μ$ of $P_{1}$ except those where $μ (φ)$ is true.” Under three-valued logic, the evaluation of $P$ means “all solutions $μ$ of $P$ except those where $μ (φ)$ is true or $μ (φ)$ is error.” Thus, according to the latter meaning, we have:

Lemma 6 Negation rewriting

Given a filter condition $φ$ , and a pattern $P_{1}$ , the following equivalence holds:

(P_{1} FILTER \neg φ) \equiv ((P_{1} EXCEPT (P_{1} FILTER φ)) EXCEPT (P_{1} FILTER Error (φ))) .

(6)

Proof.

The equivalence follows from the fact that the filter discards from the solutions of $P$ those solutions $μ$ such that $μ (φ)$ is $false$ or $error$ .

Now we are ready to present the effectiveness of rewriting that allows for the reduction of complex filter conditions.

Definition 6 Reduction of complex filter conditions

Given a pattern $(P_{1} FILTER φ)$ , the filter-reduced pattern of it is the pattern that results of applying recursively the equivalences (1), (5), and (6) until in the resulting patterns only occur atomic formulas (i.e., no logical connectives).

Lemma 7
Given a pattern $(P_{1} FILTER φ)$ , the procedure to reduce complex filter conditions described in Definition 6 produces a pattern equivalent to the original and with no logical connectives in filter conditions.
Proof.
This lemma is proved by induction on the structure of the filter condition in the pattern. The base case consists of a filter condition $φ$ without logical connectives. The case where $φ$ is $φ_{1} \land φ_{2}$ is straightforward. The pattern $(P FILTER φ)$ can be reduced to the pattern $((P FILTER φ_{1}) FILTER φ_{2})$ , and the inductive hypothesis can be applied on $φ_{1}$ and $φ_{2}$ . The cases where $φ$ is $φ_{1} \lor φ_{2}$ or $\neg φ_{1}$ are more involved because the application of the respective equivalences eliminates a logical connective from $φ$ but adds new logical connectives to the resulting filter conditions. The proof for the cases involving disjunction or negation follows from Claim 2 in the Appendix.

Translation of SPARQL Graph Patterns Into Datalog Rules

The translation essentially follows the idea presented by Polleres (2007), adapted to multisets by Angles and Gutiérrez (2016), and improved by Hernández (2020). Specifically, we cover the following issues:
It considers the cases where a filter condition is evaluated as an error. Some solutions are lost when these cases are not considered.

It considers that the equality $X = Y$ must be evaluated as true only if $X$ and $Y$ are bound. The translation is fixed by using the literal $eq (X, Y)$ instead of a built-in equality $X = Y$ . Since atom $eq (X, Y)$ is true only if $X$ and $Y$ are terms in the database, the translation of the filter-condition $X = Y$ is not evaluated as true when $X$ and $Y$ are unbound.

Given a SPARQL graph pattern $P$ , the function $δ (P)$ is introduced to transform $P$ into a set of ${NRMD}^{\neg}$ rules. The definition of function $δ$ is given by the translation rules presented in Table 4. Note that this function implies a recursive translation of graph patterns into Datalog rules, as well as the generation of fresh predicates. To do this, the application of function $δ$ over a graph $P$ will be based on exploring the parse tree of $P$ .

Table 4.
Definition of Function $δ (P)$ Which Allows to Translate a SPARQL Graph Pattern $P$ Into a set of ${NRMD}^{\neg}$ Rules.

Graph pattern $P$ $δ (P)$ where $\dots$

$(x_{1}, x_{2}, x_{3})$ $p (\bar{P}) \leftarrow t r i p l e (x_{1}, x_{2}, x_{3})$ ; $\bar{P}$ contains the variables in the set ${x_{1}, x_{2}, x_{3}}$ .

$(P_{1} AND P_{2})$ $p (\bar{P})$ $\leftarrow$ $ν_{1} (p_{1} ({\bar{P}}_{1}))$ , $ν_{2} (p_{2} ({\bar{P}}_{2}))$ , ${comp (ν_{1} (X), ν_{2} (X), X) ∣ X \in {\bar{P}}_{1} \cap {\bar{P}}_{2}}$ ; $δ (P_{1})$ ; $δ (P_{2})$ Assume that $ν_{1}$ and $ν_{2}$ are functions with the same domain ${\bar{P}}_{1} \cap {\bar{P}}_{2}$ and with different range. Given a literal $L$ , the function $ν_{i} (L)$ returns a copy of $L$ where the variables have been renamed according to $v_{i}$ .

$(P_{1} UNION P_{2})$ $p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1})$ ; $p (\bar{P}) \leftarrow p_{2} ({\bar{P}}_{2})$ ; $δ (P_{1})$ ; $δ (P_{2})$ $\bar{P}$ , ${\bar{P}}_{1}$ and ${\bar{P}}_{2}$ contain the same variables.

$(P_{1} EXCEPT P_{2})$ $p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), \neg p_{2} ({\bar{P}}_{2})$ ; $δ (P_{1})$ ; $δ (P_{2})$ $\bar{P}$ and ${\bar{P}}_{1}$ contain the same variables.

$(P_{1} FILTER x_{1} = x_{2})$ $p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), eq (x_{1}, x_{2})$ ; $δ (P_{1})$ $\bar{P}$ and ${\bar{P}}_{1}$ contain the same variables.

$(P_{1} FILTER bound (? X))$ $p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), term (? X)$ ; $δ (P_{1})$ $\bar{P}$ and $\bar{P_{1}}$ contain the same variables.

$(SELECT W P_{1})$ $p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), null (x_{1}), \dots, null (x_{n})$ ; $δ (P_{1})$ $\bar{P} = W$ , and $x_{1}, \dots, x_{n}$ are the variables that are in $W$ but not in $inScope (P_{1})$ .

Note. ${NRMD}^{\neg}$ = nonrecursive Datalog with safe negation. Given a graph pattern $P$ , the function $\bar{P}$ returns the variables of $P$ in lexicographical order. Note that $p_{i}$ is a fresh predicate name used to codify the graph pattern $P_{i}$ .

A parse tree for a graph pattern $P$ is an ordered rooted tree whose internal nodes represent the graph pattern operators in $P$ (i.e., AND, UNION, EXCEPT, FILTER, and SELECT), and whose leaves represent the triple patterns of $P$ . Additionally, we will assume that the nodes will be enumerated using a postorder traversal of the tree, that is, for any node $n$ , first visit the left subtree, then visit the right subtree, and finally visit the node $n$ itself.

Given a graph pattern $P$ and its parse tree $T$ , the execution of the function $δ$ consists of applying the rules shown in Table 4 to each node in $T$ , following their enumeration. Next, we present an example of this procedure.
Example 6
Let $Q$ be the following SPARQL query asking for all people, the place where they live, and optionally the people they know:
$\begin{aligned} ( & ((? p e r s o n, l i v e s I n, ? s o m e w h e r e) AND (? p e r s o n, k n o w s, ? s o m e b o d y)) \\ UNION \\ \begin{aligned} ( & (? p e r s o n, l i v e s I n, ? s o m e w h e r e) EXCEPT \\ \begin{aligned} ( & SELECT ? p e r s o n ? s o m e w h e r e \\ WHERE ((? p e r s o n, l i v e s I n, ? s o m e w h e r e) AND (? p e r s o n, k n o w s, ? s o m e b o d y))))) . \end{aligned} \end{aligned} \end{aligned}$
This SPARQL query is not normalized because both sides of the $UNION$ operator have different variables. To normalize this query, we replace the right-hand operand of the $UNION$ pattern by a $SELECT$ clause, and include the projection variables $? p e r s o n$ , $? s o m e w h e r e$ , and $? s o m e b o d y$ . The resulting normalized query is the following:
$\begin{aligned} ( & ((? p e r s o n, l i v e s I n, ? s o m e w h e r e) AND (? p e r s o n, k n o w s, ? s o m e b o d y)) \\ UNION \\ \begin{aligned} ( & SELECT ? p e r s o n ? s o m e w h e r e ? s o m e b o d y \\ WHERE \begin{aligned} ( & (? p e r s o n, l i v e s I n, ? s o m e w h e r e) EXCEPT \\ \begin{aligned} ( & SELECT ? p e r s o n ? s o m e w h e r e \\ WHERE ((? p e r s o n, l i v e s I n, ? s o m e w h e r e) AND (? p e r s o n, k n o w s, ? s o m e b o d y)))))) . \end{aligned} \end{aligned} \end{aligned} \end{aligned}$

Assume that $P$ is the normalized SPARQL graph pattern presented above, and $T$ is the parse tree of $P$ shown in Figure 4. Hence, the application of the function $δ (P)$ results in the following Datalog rules:
$\begin{aligned} p_{1} (? p e r s o n, ? s o m e w h e r e) \leftarrow triple (? p e r s o n, l i v e s I n, ? s o m e w h e r e) \\ p_{2} (? p e r s o n, ? s o m e b o d y) \leftarrow triple (? p e r s o n, k n o w s, ? s o m e b o d y) \\ p_{3} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \leftarrow p_{1} (? p e r s o n_{1}, ? s o m e w h e r e), p_{2} (? p e r s o n_{2}, ? s o m e b o d y), \\ comp (? p e r s o n_{1}, ? p e r s o n_{2}, ? p e r s o n) \\ p_{4} (? p e r s o n, ? s o m e w h e r e) \leftarrow triple (? p e r s o n, l i v e s I n, ? s o m e w h e r e) \\ p_{5} (? p e r s o n, ? s o m e w h e r e) \leftarrow triple (? p e r s o n, l i v e s I n, s o m e w h e r e) \\ p_{6} (? p e r s o n, ? s o m e b o d y) \leftarrow triple (? p e r s o n, k n o w s, ? s o m e b o d y) \\ p_{7} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \leftarrow p_{5} (? p e r s o n_{1}, ? s o m e w h e r e), p_{6} (? p e r s o n_{2}, ? s o m e b o d y), \\ comp (? p e r s o n_{1}, ? p e r s o n_{2}, ? p e r s o n) \\ p_{8} (? p e r s o n, ? s o m e w h e r e) \leftarrow p_{7} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \\ p_{9} (? p e r s o n, ? s o m e w h e r e) \leftarrow p_{4} (? p e r s o n, ? s o m e w h e r e), \neg p_{8} (? p e r s o n, ? s o m e w h e r e) \\ p_{10} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \leftarrow p_{9} (? p e r s o n, ? s o m e w h e r e), null (? s o m e b o d y) \\ p_{11} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \leftarrow p_{3} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \\ p_{11} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \leftarrow p_{10} (? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y) \end{aligned}$

Figure 4.
Parse tree of the normalized SPARQL graph pattern presented in Example 6. Each node represents a graph pattern, and each edge represents a composition relationship between graph patterns. The nodes were enumerated using a post-order traversal of the tree. In this figure: $P_{1}$ is the triple pattern $(? p e r s o n, l i v e s I n, ? s o m e w h e r e)$ , $P_{2}$ is $(? p e r s o n, k n o w s, ? s o m e b o d y)$ , $P_{3}$ is $(? p e r s o n, l i v e s I n, ? s o m e w h e r e)$ , $P_{4}$ is $(? p e r s o n, l i v e s I n, ? s o m e w h e r e)$ , and $P_{5}$ is $(? p e r s o n, k n o w s, ? s o m e b o d y)$ .

Note that the predicate names are enumerated according to the parse tree shown in Figure 4. In this sense: the rule $p_{1} (\dots) \leftarrow \dots$ encodes the triple pattern $P_{1}$ ; the same applies for the predicated names $p_{2}$ , $p_{4}$ , $p_{5}$ , and $p_{6}$ ; the rule $p_{3} (\dots) \leftarrow \dots$ encodes the pattern $(P_{1} AND P_{2})$ ; the rule $p_{7} (\dots) \leftarrow \dots$ encodes the pattern $(P_{5} AND P_{6})$ ; the rule $p_{8} (\dots) \leftarrow \dots$ encodes the pattern $(SELECT ? p e r s o n, ? s o m e w h e r e WHERE P_{7})$ ; the rule $p_{9} (\dots) \leftarrow \dots$ encodes the pattern $(P_{4} EXCEPT P_{8})$ ; the rule $p_{10} (\dots) \leftarrow \dots$ encodes the pattern $(SELECT ? p e r s o n, ? s o m e w h e r e, ? s o m e b o d y WHERE P_{9})$ ; finally, the two rules with predicate name $p_{11}$ encode the graph pattern $(P_{3} UNION P_{10})$ .

Based on the function $δ$ , we define a general method to transform SPARQL queries into ${NRMD}^{\neg}$ queries.
Definition 7 Function $f_{12}$

Graph pattern $P$	$δ (P)$	where $\dots$
$(x_{1}, x_{2}, x_{3})$	$p (\bar{P}) \leftarrow t r i p l e (x_{1}, x_{2}, x_{3})$ ;	$\bar{P}$ contains the variables in the set ${x_{1}, x_{2}, x_{3}}$ .
$(P_{1} AND P_{2})$	$p (\bar{P})$ $\leftarrow$ $ν_{1} (p_{1} ({\bar{P}}_{1}))$ , $ν_{2} (p_{2} ({\bar{P}}_{2}))$ , ${comp (ν_{1} (X), ν_{2} (X), X) ∣ X \in {\bar{P}}_{1} \cap {\bar{P}}_{2}}$ ; $δ (P_{1})$ ; $δ (P_{2})$	Assume that $ν_{1}$ and $ν_{2}$ are functions with the same domain ${\bar{P}}_{1} \cap {\bar{P}}_{2}$ and with different range. Given a literal $L$ , the function $ν_{i} (L)$ returns a copy of $L$ where the variables have been renamed according to $v_{i}$ .
$(P_{1} UNION P_{2})$	$p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1})$ ; $p (\bar{P}) \leftarrow p_{2} ({\bar{P}}_{2})$ ; $δ (P_{1})$ ; $δ (P_{2})$	$\bar{P}$ , ${\bar{P}}_{1}$ and ${\bar{P}}_{2}$ contain the same variables.
$(P_{1} EXCEPT P_{2})$	$p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), \neg p_{2} ({\bar{P}}_{2})$ ; $δ (P_{1})$ ; $δ (P_{2})$	$\bar{P}$ and ${\bar{P}}_{1}$ contain the same variables.
$(P_{1} FILTER x_{1} = x_{2})$	$p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), eq (x_{1}, x_{2})$ ; $δ (P_{1})$	$\bar{P}$ and ${\bar{P}}_{1}$ contain the same variables.
$(P_{1} FILTER bound (? X))$	$p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), term (? X)$ ; $δ (P_{1})$	$\bar{P}$ and $\bar{P_{1}}$ contain the same variables.
$(SELECT W P_{1})$	$p (\bar{P}) \leftarrow p_{1} ({\bar{P}}_{1}), null (x_{1}), \dots, null (x_{n})$ ; $δ (P_{1})$	$\bar{P} = W$ , and $x_{1}, \dots, x_{n}$ are the variables that are in $W$ but not in $inScope (P_{1})$ .

Given a SPARQL query $Q$ , the function $f_{12} (P)$ returns an ${NRMD}^{\neg}$ query $(L, Π)$ , where $L$ is the goal atom $p (\bar{P})$ and $Π$ is a Datalog program containing the rules produced by $δ (Q)$ (note that $Q$ is a graph pattern).

6.1.3. Translating Query Answers From ${NRMD}^{\neg}$ to SPARQL

Recall that an ${NRMD}^{\neg}$ query answer is a pair $(V, M)$ , where $V$ is a set of variables and $M$ is a multiset of substitutions. Additionally, a SPARQL query answer is a multiset of solution mappings $Ω$ .

The main difference between a multiset of substitutions $M$ and a multiset of solution mappings $Ω$ is the representation of null values. Given a substitution $θ$ and a variable $? X \in dom (θ)$ , a null value is represented with the assignment $θ (? X) = ⊥$ . On the other hand, for a solution mapping $μ$ , a null value for $? X$ is represented by not including $? X$ in the domain of $μ$ . Given a Datalog substitution $θ$ , the function $NotNull (θ)$ returns a SPARQL solution mapping $μ$ defined as follows: (i) $dom (μ) = {x \in dom (θ) ∣ θ (x) \neq ⊥}$ , that is, the variables of $μ$ are the variables in $θ$ whose assignment is not $⊥$ ; and (ii) for every variable $? X \in dom (θ)$ , if $θ (? X) \neq ⊥$ then $μ (? X) = θ (? X)$ . Hence, every value different from $⊥$ is translated into an unbound variable in the corresponding solution mapping.

Definition 8 Function $h_{12}$

Given a multiset of Datalog substitutions $Θ$ , the function $h_{12} (Θ)$ returns a multiset of SPARQL solution mappings $Ω$ defined as follows: $set (Ω) = {NotNull (θ) ∣ θ \in set (Θ)}$ ; and, for each substitution $θ \in set (Θ)$ , it applies that $card (NotNull (θ), Ω) = card (θ, Θ)$ . In other words, the cardinality of each solution mapping $NotNull (θ)$ in $Ω$ is defined as the number of colored copies $⟨ θ, i ⟩$ occurring in $coloring (Θ)$ .

Lemma 8
SPARQL can be simulated by ${NRMD}^{\neg}$ .
Proof.
We need to show that, using the functions defined above, $(f_{12}, g_{12}, h_{12})$ is a simulation of SPARQL in ${NRMD}^{\neg}$ . The proof is in the Claim 4 of the Appendix.
6.2. From ${NRMD}^{\neg}$ to SPARQL

This section shows that ${NRMD}^{\neg}$ can be simulated by SPARQL. To support this, we describe the following translation functions:

–
$f_{21}$ is the function that translates ${NRMD}^{\neg}$ queries into SPARQL queries;
–
$g_{21}$ is the function that translates ${NRMD}^{\neg}$ databases into SPARQL databases; and
–
$h_{21}$ is the function that translates SPARQL query answers into ${NRMD}^{\neg}$ query answers.

6.2.1. Translating Databases From ${NRMD}^{\neg}$ to SPARQL

In general terms, a fact $p (c_{1}, \dots, c_{n})$ can be translated into a set of triples of the form $(u, α_{i}, c_{i})$ , where $u$ is a fresh IRI that identifies the fact, and $α_{i}$ is a reserved IRI which allows to describe that constant $c_{i}$ is in the position $i$ of the fact². Also recall that the semantics of ${NRMD}^{\neg}$ relies on the notion of a colored set of a multiset (see Section 4.2), which is the set containing the colored copies of the element of the multiset. This idea is formalized next.

In what follows, we will assume that $A = {α_{0}, α_{1} \dots}$ is an enumerable set of special IRIs used to codify positions in Datalog atoms, $NULL$ is a special IRI, and any Datalog constant $c$ and name of predicate $p$ has an equivalent RDF IRI term (excluding the aforementioned special IRIs) that we will denote with the same symbol $c$ and $p$ .

Definition 9 Function $g_{21}$

Assume that the ${NRMD}^{\neg}$ database $D$ contains $n$ copies of a fact $F$ (namely $p (c_{1}, \dots, c_{n})$ ), and the $coloring (D)$ contains the colored copies $⟨ F, 1 ⟩$ , …, $⟨ F, n ⟩$ of fact $F$ . For each colored copy $⟨ F, i ⟩$ of $F$ , we assume the existence of a fresh IRI $u_{⟨ F, i ⟩}$ , which we use to identify the colored copy. Similarly, the subscript $_{⟨ F, i ⟩}$ is used to identify the colored copy of a constant or a predicate.

Then the function $g_{21}$ applied to the multiset of ${NRMD}^{\neg}$ facts $D$ , returns a set of RDF triples (i.e., an RDF graph) defined as

g_{21} (D) = {(N U L L, N U L L, N U L L)} ⋃_{⟨ F, i ⟩ \in coloring (D)} {(u_{⟨ F, i ⟩}, α_{0}, p_{⟨ F, i ⟩}), (u_{⟨ F, i ⟩}, α_{1}, (c_{1})_{⟨ F, i ⟩}), \dots, (u_{⟨ F, i ⟩}, α_{n}, (c_{n})_{⟨ F, i ⟩})} .

Example 7
Let $D$ be the following ${NRMD}^{\neg}$ database:
$D = {[p (a, b), p (a, b), p (a, c), q (b, d, a), q (b, e, a)]} .$
Note that the fact $p (a, b)$ occurs twice in the multiset $D$ , so we need to generate the colored copies for this fact, namely, $⟨ p (a, b), 1 ⟩$ and $⟨ p (a, b), 2 ⟩$ . In contrast, the fact $p (a, b)$ occurs once, so we just generate a simple colored copy, that is, $⟨ p (a, c), 1 ⟩$ . Then the data are translated for SPARQL as follows:
$\begin{aligned} g_{21} (D) = & {(N U L L, N U L L, N U L L), \\ (u_{⟨ p (a, b), 1 ⟩}, α_{0}, p), (u_{⟨ p (a, b), 1 ⟩}, α_{1}, a), (u_{⟨ p (a, b), 1 ⟩}, α_{2}, b), \\ (u_{⟨ p (a, b), 2 ⟩}, α_{0}, p), (u_{⟨ p (a, b), 2 ⟩}, α_{1}, a), (u_{⟨ p (a, b), 2 ⟩}, α_{2}, b), \\ (u_{⟨ p (a, c), 1 ⟩}, α_{0}, p), (u_{⟨ p (a, c), 1 ⟩}, α_{1}, a), (u_{⟨ p (a, c), 1 ⟩}, α_{2}, c), \\ (u_{⟨ p (b, d, a), 1 ⟩}, α_{0}, q), (u_{⟨ p (b, d, a), 1 ⟩}, α_{1}, b), (u_{⟨ p (b, d, a), 1 ⟩}, α_{2}, d), (u_{⟨ p (b, d, a), 1 ⟩}, α_{3}, a), \\ (u_{⟨ p (b, e, a), 1 ⟩}, α_{0}, q), (u_{⟨ p (b, e, a), 1 ⟩}, α_{1}, b), (u_{⟨ p (b, e, a), 1 ⟩}, α_{2}, d), (u_{⟨ p (b, e, a), 1 ⟩}, α_{3}, a)} . \end{aligned}$

Intuitively, the SPARQL database corresponding to the ${NRMD}^{\neg}$ database $D$ consists of a set of triples that describe each of the facts, and the inclusion of triple $(NULL, NULL, NULL)$ allows us to ensure that the SPARQL database is not empty. The need for this additional triple is explained next when describing the translation from ${NRMD}^{\neg}$ queries to SPARQL.
6.2.2. Translating Queries From ${NRMD}^{\neg}$ to SPARQL

A notable difference between ${NRMD}^{\neg}$ and SPARQL is the way both languages define the scope of variables. In ${NRMD}^{\neg}$ , all variables in a rule are universally quantified, and they are not in the scope of the query. On the other hand, variables in a SPARQL query are divided into in-scope and non-in-scope (see Subsection 3.4). To see this difference, consider the ${NRMD}^{\neg}$ query $(q (X, Y), Π)$ , where the program $Π$ consists of the single rule $R = q (Y, Z) \leftarrow p (X, Z, Y)$ . Notice that the variables in the goal of the query do not correspond to the variables in the head of the rule $R$ . To simplify the translation, we rename variables in rules according to the goal of the query.

In this case, we rewrite $R$ as the rule $R^{'} = q (X, Y) \leftarrow p (Z, Y, X)$ . Formally, given a literal $L = q (X_{1}, \dots, X_{n})$ and a rule $R$ whose head is $q (Y_{1}, \dots, Y_{n})$ , the renamed rule of $R$ with respect to $L$ , denoted $vr (R, L)$ , is the rule $R^{'}$ that results from $R$ by consistently renaming each variable $Y_{i}$ as $X_{i}$ , for $1 \leq i \leq n$ .

Let $L$ be a positive literal $p (X_{1}, \dots, X_{n})$ and $Π$ be a normalized ${NRMD}^{\neg}$ program. We define the function $gp (L, Π)$ , which translates $L$ into a SPARQL graph pattern. The function $gp$ is defined recursively as follows:

If predicate name $p$ does not occur in the head of any rule of $Π$ (i.e., $p$ is extensional), then $gp (L, Π)$ returns

SELECT \bar{X} ((? Y, α_{0}, p) AND (? Y, α_{1}, ? X_{1}) AND \dots AND (? Y, α_{n}, ? X_{n})),

where

\bar{X} = var (L)

and

? Y

is a fresh variable.

Otherwise, if $p$ occurs in the head of the rules ${R_{1}, \dots, R_{n}}$ in $Π$ (i.e., $p$ is intentional), then $gp (L, Π)$ returns:

(T (vr (R_{1}, L)) UNION \dots UNION T (vr (R_{n}, L))),

where the operator

T (R)

is defined as follows:

–
If $R$ is a projection rule $L \leftarrow L_{1}$ then $T (R)$ is $(SELECT \bar{X} P_{1})$ where $\bar{X} = var (L)$ and $P_{1} = gp (L_{1}, Π)$ .
–
If $R$ is a join rule $L \leftarrow L_{1}, L_{2}$ then $T (R)$ is $(P_{1} AND P_{2})$ where $P_{1} = gp (L_{1}, Π)$ and $P_{2} = gp (L_{2}, Π)$ .
–
If $R$ is a negation rule $L \leftarrow L_{1}, \neg L_{2}$ then $T (R)$ is $(P_{1} EXCEPT P_{2})$ where $P_{1} = gp (L_{1}, Π)$ and $P_{2} = gp (L_{2}, Π)$ .

Note that, if there is just one rule $R_{1}$ , then $gp (L, Π)$ can be reduced to $T (R_{1})$ (no need to rename variables).

Example 8
Consider the ${NRMD}^{\neg}$ query $(q (X), Π)$ where program $Π$ consists of the rule $q (X) \leftarrow p (X, Y)$ . Then, $gp (q (X), Π)$ is the SPARQL query
$SELECT ? X ((? U, α_{0}, p) AND (? U, α_{1}, ? X) AND (? U, α_{2}, ? Y)) .$

The function $gp$ is not enough to translate ${NRMD}^{\neg}$ queries to SPARQL queries. Recall that an ${NRMD}^{\neg}$ query answer is a pair $(V, M)$ where $V$ is a set of ${NRMD}^{\neg}$ variables and $M$ is a set of ${NRMD}^{\neg}$ substitutions, and a SPARQL query answer is a multiset $Ω$ of SPARQL mappings. To conclude the translation, we need to define a function that, given a SPARQL query answer $Ω$ , returns an ${NRMD}^{\neg}$ query answer $(V, M)$ . The issue is that we cannot compute the set $V$ when the multiset $Ω$ is empty. For example, an empty ${NRMD}^{\neg}$ database $D$ is translated as the SPARQL database consisting of the set of triples ${(NULL, NULL, NULL)}$ (see Subsection 6.2.1). The evaluation of the query $gp (q (X), Π)$ in Example 8 returns an empty multiset of mappings, $Ω$ , where the query answer to the ${NRMD}^{\neg}$ query $(q (X), Π)$ is a pair $({X}, M)$ such that $M$ is an empty multiset of solutions. Hence, the SPARQL query answer $Ω$ does not contain the information needed to generate the set of variables ${X}$ in the answer of the ${NRMD}^{\neg}$ query.

To solve the aforementioned issue of having an empty SPARQL query answer, we can extend the function $gp$ with a query that introduces the variables of the query. This is done using the additional triple $(NULL, NULL, NULL)$ we introduced in the translation. Given a set of ${NRMD}^{\neg}$ variables $V = {X_{1}, \dots, X_{n}}$ we write $VarQuery (V)$ to denote the SPARQL pattern $(NULL, NULL, ? X_{1}) AND \dots AND (NULL, NULL, ? X_{n})$ . The translation of an ${NRMD}^{\neg}$ query is then the union of the graph patterns computed by the functions $gp$ and $VarQuery$ .
Definition 10 Function $f_{21}$

Given an ${NRMD}^{\neg}$ query $Q = (L, Π)$ , the function $f_{21} (Q)$ returns a SPARQL graph pattern $(gp (L, Π) UNION VarQuery (var (L)))$ .

Example 9
Consider the ${NRMD}^{\neg}$ query $(q (X), Π)$ in Example 8. Then, $f_{21} ((q (X), Π))$ is the following SPARQL graph pattern:
$(SELECT ? X ((? U, α_{0}, p) AND (? U, α_{1}, ? X) AND (? U, α_{2}, ? X))) UNION (N U L L, N U L L, ? X) .$
The result of evaluating the ${NRMD}^{\neg}$ query on an empty set of facts $D$ is the pair $({X}, M)$ , where $M$ is an empty multiset of ${NRMD}^{\neg}$ substitutions, whereas the result of evaluating the graph pattern $f_{21} ((q (X), Π))$ on the SPARQL database $g_{21} (D) = {(NULL, NULL, NULL)}$ is the SPARQL query answer $Ω = {{? X \mapsto NULL}}$ . Intuitively, the mapping ${? X \mapsto NULL}$ does not codify an ${NRMD}^{\neg}$ substitution, but the variables in the domain of ${NRMD}^{\neg}$ substitutions.
6.2.3. Translating Query Answers From SPARQL to ${NRMD}^{\neg}$

Recall that a SPARQL query answer is a multiset of solution mappings, and an ${NRMD}^{\neg}$ query answer is a pair $(V, M)$ (where $V$ is a set of variables and $M$ is a multiset of substitutions). Since a SPARQL solution mapping can be seen as an ${NRMD}^{\neg}$ substitution, the translation from SPARQL mappings to ${NRMD}^{\neg}$ substitutions does not require modifications, except for the mapping ${? X_{1} \mapsto NULL, \dots, ? X_{n} \mapsto NULL}$ , which is used to codify the solution variables.

Definition 11 Function $h_{21}$

Let $Ω$ be a multiset of SPARQL solution mappings that includes a mapping $μ_{V \mapsto NULL}$ with cardinality 1 where $dom (μ_{V \mapsto NULL}) = V$ and $μ (? X) = NULL$ for every variable $? X \in dom (μ_{V \mapsto NULL})$ , and for every mapping $μ^{'} \in Ω$ it holds that $dom (μ^{'}) = V$ . The ${NRMD}^{\neg}$ solution for $Ω$ , denoted $h_{21} (Ω)$ , is the pair $(V, M)$ where $M$ is the multiset of substitutions $θ$ defined as follows:

Given a SPARQL mapping $μ = {? X_{1} \mapsto c_{1}, \dots, ? X_{n} \mapsto c_{n}}$ the corresponding ${NRMD}^{\neg}$ substitution for mapping $μ$ is the substitution $θ_{μ} = {X_{1} \mapsto c_{1}, \dots, X_{n} \mapsto c_{n}}$ , where the ${NRMD}^{\neg}$ variable $X_{i}$ corresponds to the SPARQL variable $? X_{i}$ .

$set (M) = {θ_{μ} ∣ μ \in Ω ∖ {μ_{V \mapsto NULL}}}$ .

$card (θ_{μ}, M) = card (μ, Ω)$ .

Lemma 9
${NRMD}^{\neg}$ can be simulated by SPARQL.
Proof.
This is a long but straightforward induction on Datalog queries using as a hypothesis that $(f_{21}, g_{21}, h_{21})$ is a simulation of ${NRMD}^{\neg}$ in SPARQL. The details of this proof are in the Appendix (Claim 5).
6.3. SPARQL and ${NRMD}^{\neg}$ Have the Same Expressive Power

Putting together the simulations among SPARQL and ${NRMD}^{\neg}$ stated in this section, we get the following theorem:

Theorem 1
SPARQL and ${NRMD}^{\neg}$ have the same expressive power.
Proof.
The claim is based on the simulation of SPARQL with ${NRMD}^{\neg}$ (Lemma 8) and the simulation of ${NRMD}^{\neg}$ with MRA (Lemma 9).
7. Equivalence Between MRA and ${NRMD}^{\neg}$

This section presents the simulations that prove that MRA and ${NRMD}^{\neg}$ have the same expressive power. Specifically, we show that MRA can be simulated by ${NRMD}^{\neg}$ (Section 7.1), and ${NRMD}^{\neg}$ can be simulated by MRA (Section 7.2).

7.1. From MRA to ${NRMD}^{\neg}$

This section shows that MRA can be simulated by ${NRMD}^{\neg}$ . To support this, we describe the following translation functions:

–
$f_{32}$ is the function that translates MRA queries into ${NRMD}^{\neg}$ queries;
–
$g_{32}$ is the function that translates MRA databases into ${NRMD}^{\neg}$ databases; and
–
$h_{32}$ is the function that translates ${NRMD}^{\neg}$ query answers into MRA query answers.

7.1.1. Translating Databases From MRA to ${NRMD}^{\neg}$

Recall that an MRA database is a set of relations (where each relation is a multiset of tuples), and an ${NRMD}^{\neg}$ database is a multiset of facts. First, we define a method to translate an MRA relation into a multiset of facts. Then, we define a method to translate a set of MRA relations into a multiset of ${NRMD}^{\neg}$ facts.

Assume the existence of functions that map: MRA relation names to ${NRMD}^{\neg}$ predicate names, MRA attributes to ${NRMD}^{\neg}$ variables, and MRA constants to ${NRMD}^{\neg}$ constants. Given a relation schema $R$ , we write $\vec{R}$ to denote a tuple containing the attributes of $R$ in lexicographical order.

Given a multiset relation $r$ , defined over a relation schema $R$ , with $\vec{R} = (A_{1}, \dots, A_{n})$ , the function $Σ (r)$ returns a multiset of Datalog facts defined as follows: for each tuple $t$ in $r$ , $Σ (r)$ contains a fact $f$ of the form $p (c_{1}, \dots, c_{n})$ , where $p$ is the image of $R$ , every $c_{i}$ is $t (A_{i})$ , and the cardinality of $f$ in $Σ (r)$ is given by the cardinality of $t$ in $r$ .

Definition 12 Function $g_{32}$

Given an MRA database $D$ , the function $g_{32}$ returns a multiset of ${NRMD}^{\neg}$ facts $D^{'}$ defined as follows:

For each MRA relation $r$ in $D$ , $D^{'}$ contains the facts returned by $Σ (r)$ .

For each constant $c$ in $D$ , $D^{'}$ contains a fact $eq (c, c)$ .

Example 10
Let $D$ be an MRA dataset consisting of two relations $r$ and $s$ with respective relation schemas $R$ and $S$ with $\vec{R} = (A_{1}, A_{2})$ and $\vec{S} = (A_{1}, A_{3})$ , and defined as follows:
$\begin{aligned} r & = {[{A_{1} \mapsto a_{1}, A_{2} \mapsto a_{2}}, {A_{1} \mapsto a_{1}, A_{2} \mapsto a_{2}}, {A_{1} \mapsto a_{1}, A_{2} \mapsto a_{3}}]}, \\ s & = {[{A_{1} \mapsto a_{1}, A_{3} \mapsto a_{4}}]} . \end{aligned}$
Then, the corresponding ${NRMD}^{\neg}$ dataset is the following:
$g_{32} (D) = {[p_{R} (a_{1}, a_{2}), p_{R} (a_{1}, a_{2}), p_{R} (a_{1}, a_{3}), p_{S} (a_{1}, a_{4}), eq (a_{1}, a_{1}), eq (a_{2}, a_{2}), eq (a_{3}, a_{3}), eq (a_{4}, a_{4})]},$
where predicates $p_{R}$ and $p_{S}$ are the corresponding images for the relation schemas $R$ and $S$ .

Note that the multiset of Datalog facts $D^{'}$ is defined over the vocabulary that includes as predicate names all the relation names in $D$ , and as the arity of the predicate name $R$ , the number of attributes of the relation name $R$ .
7.1.2. Translating Queries From MRA to ${NRMD}^{\neg}$

Recall that an MRA query is a relational algebra expression, and an ${NRMD}^{\neg}$ query is a set of rules.

First, we need to provide a recursive method to reduce MRA selection formulas into atomic formulas. Such a method is based on the following equivalences where $E$ is an MRA expression, and $ψ$ , $ψ_{1}$ , and $ψ_{2}$ are selection formulas:

\begin{aligned} σ_{ψ_{1} \land ψ_{2}} (E) & \equiv σ_{ψ_{2}} (σ_{ψ_{1}} (E)), \end{aligned}

(7)

\begin{aligned} σ_{ψ_{1} \lor ψ_{2}} (E) & \equiv σ_{ψ_{1} \land \neg ψ_{2}} (E) \cup σ_{\neg ψ_{1} \land ψ_{2}} (E) \cup σ_{ψ_{1} \land ψ_{2}} (E), \end{aligned}

(8)

\begin{aligned} σ_{\neg ψ} (E) & \equiv E ∖ σ_{ψ} (E) . \end{aligned}

(9)

The proof of the validity of the above equivalences follows directly from the semantics of the selection operator. In particular, equivalence (8) is rather involved because it separates the disjunction into a union of three disjoint multiset relations in order to preserve the cardinality of each solution. Using the above equivalence, we get the following lemma.

Lemma 10

For every MRA expression $E$ , there exists an equivalent MRA expression $E^{'}$ satisfying that all selection formulas in $E^{'}$ are atomic.

Proof.

The proof follows from induction in the number $k$ of Boolean connectives in selection formulas occurring in an MRA expression $E$ . The base case is $k = 0$ , and thus all selection formulas are atomic. If $k > 0$ , then the expression includes a selection expression whose formula has either the form $ψ_{1} \land ψ_{2}$ , $\neg ψ$ , or $ψ_{1} \lor ψ_{2}$ . In the first two cases, equivalences (7) and (9) reduce by one of the Boolean connectives of the expression. In the third case, the consecutive application of equivalences (8), (7), and (9) (in that order) reduces by one the number of Boolean connectives. Hence, we produce an equivalent query with $k - 1$ Boolean connectives.

Definition 13 Function

f_{32}

Let

Q

be an MRA query (i.e., an MRA expression), where selection formulas are atomic (i.e., have no Boolean connectives). The function

f_{32} (Q)

returns an

{NRMD}^{\neg}

query

(L, Π)

, where

L

is a goal clause of the form

q (\vec{Q})

where

q

is a predicate name corresponding to

Q

\vec{Q}

are the variables corresponding to the attributes in the schema

\hat{Q}

(sorted in lexicographical order), and

Π

is a set of

{NRMD}^{\neg}

rules (i.e., an

{NRMD}^{\neg}

program) created by applying recursively the rules shown in Table 5.

Table 5.
Definition of Function $Γ$ Which Translates an MRA Expression Into a set of Datalog Rules.

MRA expression $E_{0}$	$Γ (E_{0})$	where $\dots$
$R$	$q_{0} ({\bar{A}}_{0}) \leftarrow R (\vec{R})$	${\bar{A}}_{0} = \vec{R}$
$(E_{1} ⋈ E_{2})$	$q_{0} ({\bar{A}}_{0}) \leftarrow q_{1} ({\bar{A}}_{1}), q_{2} ({\bar{A}}_{2})$ ; $Γ (E_{1})$ ; $Γ (E_{2})$	${\bar{A}}_{0} = {\bar{A}}_{1} \cup {\bar{A}}_{2}$
$(E_{1} \cup E_{2})$	$q_{0} ({\bar{A}}_{0}) \leftarrow q_{1} ({\bar{A}}_{1})$ ; $q_{0} ({\bar{A}}_{0}) \leftarrow q_{2} ({\bar{A}}_{2})$ ; $Γ (E_{1})$ ; $Γ (E_{2})$	${\bar{A}}_{0} = {\bar{A}}_{1} = {\bar{A}}_{2}$
$(E_{1} ∖ E_{2})$	$q_{0} ({\bar{A}}_{0}) \leftarrow q_{1} ({\bar{A}}_{1}), \neg q_{2} ({\bar{A}}_{2})$ ; $Γ (E_{1})$ ; $Γ (E_{2})$	${\bar{A}}_{0} = {\bar{A}}_{1}$
$π_{S} (E_{1})$	$q_{0} ({\bar{A}}_{0}) \leftarrow q_{1} ({\bar{A}}_{1})$ ; $Γ (E_{1})$	${\bar{A}}_{0} = S$
$ρ_{A / B} (E_{1})$	$q_{0} ({\bar{A}}_{0}) \leftarrow q_{1} ({\bar{A}}_{1}), eq (A, B)$ ; $Γ (E_{1})$	${\bar{A}}_{0} = ({\bar{A}}_{1} ∖ {A}) \cup {B}$
$σ_{A = B} (E_{1})$	$q_{0} ({\bar{A}}_{0}) \leftarrow q_{1} ({\bar{A}}_{1}), eq (A, B)$ ; $Γ (E_{1})$	$\bar{A_{0}} = {\bar{A}}_{1}$

Note. MRA = multiset relational algebra. Given an MRA expression $E$ , the recursive function $Γ (E)$ returns a set of ${NRMD}^{\neg}$ rules, where $q_{i} (\bar{A})$ is a positive literal related to the MRA expression $E_{i}$ , $q_{i}$ is a fresh predicate name, $\bar{A_{i}}$ denotes a set of variables, $\vec{R}$ denotes the attributes in schema $\hat{R}$ , sorted in lexicographical order.

Note that function $f_{32}$ assigns a fresh predicate name to each operation in query $Q$ by following a nondeterministic approach. Although it is not difficult to define deterministic ways (e.g., in the translation from SPARQL to ${NRMD}^{\neg}$ ), we omit how intentional predicate names are assigned.

7.1.3. Translating Query Answers From

{NRMD}^{\neg}

to MRA

Recall that an ${NRMD}^{\neg}$ query answer is a pair $(V, M)$ , where $V$ is a set of variables and $M$ is a multiset of ${NRMD}^{\neg}$ substitutions. On the other hand, an MRA query answer is a multiset relation. Next, we define a function $h_{32}$ , which translates an ${NRMD}^{\neg}$ query answer into an MRA query answer.

Definition 14 Function $h_{32}$

Given an ${NRMD}^{\neg}$ query answer $A = (V, M)$ , the function $h_{32} (A)$ returns a multiset relation $r$ , where the schema of $r$ is given by the set of attributes $V$ (assume a simple transformation of variables to attribute names); for each substitution $θ$ in $M$ , there is a tuple $t$ in $r$ satisfying that $t (X) = θ (X)$ for every attribute $X \in \hat{R}$ , and $card (t, r) = card (θ, M)$ .

Lemma 11
MRA can be simulated by ${NRMD}^{\neg}$ .
Proof.
Let $f_{32}$ , $g_{32}$ , and $h_{32}$ be the functions described in Definitions 12, 14, and 13, respectively. The proof of this theorem follows from the claim that $(f_{32}$ , $g_{32}$ , $h_{32})$ simulates MRA in ${NRMD}^{\neg}$ by using induction in the structure of queries. The proof of this claim is in the Appendix (Claim 6).
7.2. From ${NRMD}^{\neg}$ to MRA

This section shows that ${NRMD}^{\neg}$ can be simulated by MRA. To support this, we describe the following translation functions:

$f_{23}$ is the function that translates ${NRMD}^{\neg}$ queries into MRA queries;

$g_{23}$ is the function that translates ${NRMD}^{\neg}$ databases into MRA databases; and

$h_{23}$ is the function that translates MRA query answers into ${NRMD}^{\neg}$ query answers.

7.2.1. Translating Databases From ${NRMD}^{\neg}$ to MRA

Recall that a database in ${NRMD}^{\neg}$ is a multiset of facts, and a database in MRA is a set of relations (where each relation is a multiset of tuples). First, we define a method to translate a multiset of facts with the same predicate name into a relation $r$ . Let $M$ be a multiset of ${NRMD}^{\neg}$ facts having the same predicate name, that is, every fact in $M$ has the form $p (t_{1}, \dots, t_{n})$ . The function $ψ (M)$ returns an MRA relation $r$ , where the relation schema $\hat{r}$ of $r$ is given by the relation name $p$ and the set of attributes ${A_{1}, \dots, A_{n}}$ , where each attribute name has the form $a t t_i$ with $1 \leq i \leq n$ ; for each fact $p (t_{1}, \dots, t_{n})$ in $M$ there is a tuples $t$ in $r$ satisfying that $t (A_{i}) = t_{i}$ .

Next, we define function $g_{23}$ , which allows translating a multiset of facts into a set of relations.

Definition 15 Function $g_{23}$

Let $M$ be a multiset of ${NRMD}^{\neg}$ facts $M$ (i.e., an ${NRMD}^{\neg}$ database), and ${p_{1}, \dots, p_{n}}$ are the predicate names in $M$ . The function $g_{23} (M)$ returns a set of relations (i.e., an MRA database) ${r_{1}, \dots, r_{n}}$ , where $r_{i} = ψ (M_{i})$ such that $M_{i}$ is the subset of ${NRMD}^{\neg}$ facts of $M$ having the predicate name $p_{i}$ .

Example 11
Let $M$ be the multiset of ${NRMD}^{\neg}$ facts defined as follows:
$M = {[p_{1} (c_{1}, c_{2}), p_{1} (c_{1}, c_{2}), p_{1} (c_{1}, c_{3}), p_{2} (c_{1}, c_{4})]} .$
Then, the corresponding MRA dataset $g_{23} (M)$ consists of the following relations $r_{1}$ and $r_{2}$ , over relation schemas $R_{1}$ and $R_{2}$ , and with attributes $\hat{R_{1}} = {A_{1}, A_{2}}$ and $\hat{R_{2}} = {B_{1}, B_{2}}$ :
$\begin{aligned} r_{1} & = {[{A_{1} \mapsto c_{1}, A_{2} \mapsto c_{2}}, {A_{1} \mapsto c_{1}, A_{2} \mapsto c_{2}}, {A_{1} \mapsto c_{1}, A_{2} \mapsto c_{3}}]}, \\ r_{2} & = {[{B_{1} \mapsto c_{1}, B_{2} \mapsto c_{4}}]} . \end{aligned}$

7.2.2. Translating Queries From ${NRMD}^{\neg}$ to MRA

Recall that an ${NRMD}^{\neg}$ query is a set of rules, and an MRA query is a relational algebra expression.

Let $Π$ be a normalized ${NRMD}^{\neg}$ program. We define, by mutual recursion, functions $δ_{1} (L, Π)$ and $δ_{2} (r, Π)$ to translate (respectively) literals and rules into MRA expressions.

Given a literal $L$ in $Π$ of the form $p (X_{1}, \dots, X_{n})$ , the function $δ_{1} (L, Π)$ is defined as follows:

If predicate name $p$ does not occur in the head of any rule of $Π$ , then $δ_{1} (L, Π)$ returns the MRA expression $ρ_{A_{1} / X_{1}} (\dots ρ_{A_{n} / X_{n}} (R) \dots)$ , where $R$ is the relation name associated with $p$ ;

Otherwise, if $p$ occurs in the head of the rules ${r_{1}, \dots, r_{m}}$ in $Π$ , then $δ_{1} (L, Π)$ returns the MRA expression $(E_{1} \cup (E_{2} \cup (\dots E_{m}) \dots)$ , where each $E_{i}$ is an MRA expression returned by $δ_{2} (r_{i}, Π)$ .

Given a rule $r$ in $Π$ , the function $δ_{2} (r, Π)$ is defined as follows:

–
If $r$ is a projection rule $L_{0} \leftarrow L_{1}$ then $δ_{2} (r, Π)$ returns the MRA expression $π_{S} (E)$ , where $S$ is the set of variables $var (L_{0})$ and $E$ is the MRA expression returned by $δ_{1} (L_{1}, Π)$ .
–
If $r$ is a join rule $L_{0} \leftarrow L_{1}, L_{2}$ then $δ_{2} (r, Π)$ returns the MRA expression $(E_{1} ⋈ E_{2})$ , where $E_{1}$ and $E_{2}$ are the MRA expressions returned by $δ_{1} (L_{1}, Π)$ and $δ_{1} (L_{2}, Π)$ , respectively.
–
If $r$ is a negation rule $L_{0} \leftarrow L_{1}, \neg L_{2}$ then $δ_{2} (r, Π)$ returns the MRA expression $(E_{1} ∖ E_{2})$ , where $E_{1}$ and $E_{2}$ are the MRA expressions returned by $δ_{1} (L_{1}, Π)$ and $δ_{1} (L_{2}, Π)$ , respectively.

Definition 16 Function $f_{23}$

Given a normalized ${NRMD}^{\neg}$ query $Q = (L, Π)$ , where $L$ is the goal clause, and $Π$ an ${NRMD}^{\neg}$ program, the function $f_{23} (Q)$ returns an MRA query defined by $δ_{1} (L, Π)$ .

7.2.3. Translating Query Answers From MRA to ${NRMD}^{\neg}$

Recall that an MRA query answer is a multiset relation, and an ${NRMD}^{\neg}$ query answer is a pair $(V, M)$ , where $V$ is a set of variables, and $M$ is a multiset of substitutions. Since an MRA tuple can be seen (interpreted) also as a Datalog substitution, the translation from MRA tuples to Datalog substitutions requires essentially no modifications. Next, we define a function $h_{23}$ , which transforms an MRA query answer into an ${NRMD}^{\neg}$ query answer.

Definition 17 Function $h_{23}$

Given an MRA relation $R$ with schema $\hat{R} = {A_{1}, \dots, A_{n}}$ , the function $h_{23} (R)$ returns an ${NRMD}^{\neg}$ query answer $A = (V, M)$ , where $V$ is a set of variables ${X_{1}, \dots, X_{n}}$ where variable $X_{i}$ corresponds to attribute $A_{i}$ (assume a simple transformation of attribute names to variable names); and, for each tuple $t$ in $R$ , there is a substitution $θ$ in $M$ satisfying that $θ (X_{i}) = t (A_{i})$ for every attribute $A_{i} \in \hat{R}$ , and $card (θ, M) = card (t, R)$ .

Lemma 12
${NRMD}^{\neg}$ can be simulated by MRA.
Proof.
This is a long but straightforward induction on Datalog queries using as a hypothesis that $(f_{23}, g_{23}, h_{23})$ is a simulation of ${NRMD}^{\neg}$ in MRA. The details of this proof are in the Appendix (Claim 7).
7.3. MRA and ${NRMD}^{\neg}$ Have the Same Expressive Power

Putting together the simulations among MRA and ${NRMD}^{\neg}$ stated in this section, we get the following theorem:

Theorem 2
MRA and ${NRMD}^{\neg}$ have the same expressive power.
Proof.
The claim is based on the simulation of MRA with ${NRMD}^{\neg}$ (Lemma 11) and the simulation of ${NRMD}^{\neg}$ with MRA (Lemma 12).
8. Equivalence Between MRA and SPARQL

This section presents the simulations that prove that MRA and SPARQL have the same expressive power. Specifically, we show that MRA can be simulated by SPARQL (Section 8.1), and SPARQL can be simulated by MRA (Section 8.2).

8.1. From MRA to SPARQL

This section shows that MRA can be simulated by SPARQL. To support this, we describe the following translation functions:

–
$f_{31}$ is the function that translates MRA queries into SPARQL queries;
–
$g_{31}$ is the function that translates MRA databases into SPARQL databases; and
–
$h_{31}$ is the function that translates SPARQL query answers into MRA query answers.

8.1.1. Translating Databases From MRA to SPARQL

Recall that an MRA database is a set of relations (where each relation is a multiset of tuples), and a SPARQL database is a set of triples.

Assume the existence of functions that map relation names to IRIs, relation attributes to IRIs, and tuples to IRIs.

Let $r$ be a multiset relation, $t$ be a tuple in $r$ and ${t^{1}, \dots, t^{n}}$ be the set of colored copies of $t$ , where $n = card (t, r)$ . The function $β (t, r)$ returns a set of RDF triples defined as follows: for each copy $t^{i}$ of $t$ , $β (t, r)$ contains a triple $(i r i_t^{i}, i r i_b, i r i_r)$ where $i r i_t^{i}$ is an IRI which identifies the tuple $t^{i}$ , $i r i_r$ is an IRI which identifies the relation $r$ , and $i r i_b$ is an IRI which describes that $i r i_t^{i}$ is a tuple of $i r i_r$ ; and, for each attribute $A$ in $\hat{r}$ , $β (t, r)$ contains a triple of the form $(i r i_t^{i}, i r i_A, l i t_A)$ , where $i r i_A$ is an IRI which identifies the attribute $A$ , and $l i t_A$ is a literal equivalent to the value $t (A)$ . Hence, for each copy of a tuple $t$ , we create a set of RDF triples.

Definition 18 Function $g_{31}$

Given an MRA database $D$ , the function $g_{31} (D)$ returns a set of RDF triples $D^{'}$ defined as follows:

–
For each multiset relation $r$ in $D$ , and for each tuple $t$ in $r$ , $D^{'}$ contains the RDF triples returned by $β (t, r)$ ;
–
$D^{'}$ contains a triple $(NULL, NULL, NULL)$ , where $NULL$ is a special IRI. Like in the simulation of ${NRMD}^{\neg}$ with SPARQL, the simulation of MRA with SPARQL uses this special triple to retrieve the variables that are attributes of the MRA query answer.

Example 12
Let $D$ be an MRA dataset consisting of two relations $r$ and $s$ with respective relation schemas $R$ and $S$ with $\vec{R} = (A_{1}, A_{2})$ and $\vec{S} = (A_{1}, A_{3})$ , and defined as follows:
$\begin{aligned} r & = {[{A_{1} \mapsto a_{1}, A_{2} \mapsto a_{2}}, {A_{1} \mapsto a_{1}, A_{2} \mapsto a_{2}}, {A_{1} \mapsto a_{1}, A_{2} \mapsto a_{3}}]}, \\ s & = {[{A_{1} \mapsto a_{1}, A_{3} \mapsto a_{4}}]} . \end{aligned}$
Then, the corresponding SPARQL dataset is the following:
$\begin{aligned} g_{31} = & {(u_{1}^{1}, i r i_b, i r i_r), (u_{1}^{1}, i r i_A_{1}, l i t_A_{a_{1}}), (u_{1}^{1}, i r i_A_{2}, l i t_A_{a_{2}}), \\ (u_{1}^{2}, i r i_b, i r i_r), (u_{1}^{2}, i r i_A_{1}, l i t_A_{a_{1}}), (u_{1}^{2}, i r i_A_{2}, l i t_A_{a_{2}}), \\ (u_{2}^{1}, i r i_b, i r i_r), (u_{2}^{1}, i r i_A_{1}, l i t_A_{a_{1}}), (u_{2}^{1}, i r i_A_{2}, l i t_A_{a_{3}}), \\ (v_{1}^{1}, i r i_b, i r i_s), (v_{1}^{1}, i r i_A_{1}, l i t_A_{a_{1}}), (v_{1}^{1}, i r i_A_{3}, l i t_A_{a_{4}}), \\ (N U L L, N U L L, N U L L)}, \end{aligned}$
where $u_{1}^{1}$ , $u_{1}^{2}$ , and $u_{2}^{1}$ correspond to the IRIs for the tuples in the multiset relation $r$ and $v_{1}^{1}$ corresponds to the IRI of the tuple in the multiset relation $s$ .
8.1.2. Translating Queries From MRA to SPARQL

Recall that an MRA query is a relational algebra expression and a SPARQL query is a graph pattern.

First, consider the following issue. A query answer in MRA is a multiset relation $r$ over a set of attributes $\hat{r}$ , whereas a query answer in SPARQL does not specify a set of variables for which solutions are defined. For example, the evaluation of the triple pattern $(? X, ? Y, ? Z)$ over an empty RDF graph results in an empty multiset $Ω$ . The reference to the variables is not carried in the SPARQL answer. Like with the simulation of ${NRMD}^{\neg}$ with SPARQL, we need to define a SPARQL pattern to retrieve the answer variables.

Given an MRA expression $E$ , with attributes $\hat{E} = {X_{1}, \dots, X_{n}}$ , we write $AttrQuery (E)$ to denote the SPARQL pattern $(NULL, NULL, ? X_{1}) AND \dots AND (NULL, NULL, ? X_{n}),$ where, for $1 \leq i \leq n$ , variable $? X_{i}$ is the corresponding SPARQL variable for the MRA attribute $X_{i}$ .

Example 13
Consider the MRA expression $r ⋈ s$ where $\hat{r} = {X, Y}$ and $\hat{s} = {Y, Z}$ . Then, $AttrQuery (E) = (NULL, NULL, ? X) AND (NULL, NULL, ? Y) AND (NULL, NULL, ? Z)$ , where $? X$ , $? Y$ , and $? Z$ are the corresponding SPARQL variables for attributes $X$ , $Y$ , and $Z$ .

Recall that an MRA query is an MRA expression, and a SPARQL query is a SPARQL graph pattern. We will show that every type of MRA expression can be translated to a specific type of SPARQL graph pattern. Table 6 shows the translation rules that are the basis for the following definition.

Table 6.
Definition of Function $Υ$ Which Translates an MRA Expression Into a SPARQL Pattern.

MRA expression $E$ SPARQL pattern $Υ (E)$ where $\dots$

$R$ ( $SELECT$ $? X_{1} \dots ? X_{n}$ $i r i_{r}$ is the IRI that identifies $R$ , $? Y$ is a variable used to match every tuple of $R$ ,

$((? Y, i r i_b, i r i_r)$ $AND ((? Y, {iri_A}_{1}, ? X_{1})$ $AND (\dots AND (? Y, {iri_A}_{2}, ? X_{n}) \dots)$ and $? X_{i}$ is a variable that corresponds to the attribute $A_{i}$ in schema $\hat{R}$ .

$(E_{1} ⋈ E_{2})$ $(P_{1} AND P_{2})$ $P_{1} = Υ (E_{1})$ and $P_{2} = Υ (E_{2})$ .

$(E_{1} \cup E_{2})$ $(P_{1} UNION P_{2})$ $P_{1} = Υ (E_{1})$ and $P_{2} = Υ (E_{2})$ .

$(E_{1} ∖ E_{2})$ $(P_{1} EXCEPT P_{2})$ $P_{1} = Υ (E_{1})$ and $P_{2} = Υ (E_{2})$ .

$π_{S} (E_{1})$ $(SELECT W P_{1})$ $P_{1} = Υ (E_{1})$ and $W$ is the set of variables corresponding to the attributes in $S$ .

$ρ_{A / B} (E_{1})$ ${subs}_{? X / ? Y} (P_{1})$ $P_{1} = Υ (E_{1})$ , $? X$ is the variable that corresponds to attribute $A$ , $? Y$ is the variable that corresponds to attribute $B$ , and ${subs}_{? X / ? Y} (P_{1})$ denotes the renaming of variable $? X$ with variable $? Y$ in the SPARQL query $P_{1}$ (see Appendix A).

$σ_{ψ} (E_{1})$ $(P_{1} FILTER φ)$ $P_{1} = Υ (E_{1})$ , and $φ$ is a filter condition equivalent to the selection condition $ψ$ .

Note. MRA = multiset relational algebra.

Definition 19 Function $f_{31}$

MRA expression $E$	SPARQL pattern $Υ (E)$	where $\dots$
$R$	( $SELECT$ $? X_{1} \dots ? X_{n}$	$i r i_{r}$ is the IRI that identifies $R$ , $? Y$ is a variable used to match every tuple of $R$ ,
	$((? Y, i r i_b, i r i_r)$ $AND ((? Y, {iri_A}_{1}, ? X_{1})$ $AND (\dots AND (? Y, {iri_A}_{2}, ? X_{n}) \dots)$	and $? X_{i}$ is a variable that corresponds to the attribute $A_{i}$ in schema $\hat{R}$ .
$(E_{1} ⋈ E_{2})$	$(P_{1} AND P_{2})$	$P_{1} = Υ (E_{1})$ and $P_{2} = Υ (E_{2})$ .
$(E_{1} \cup E_{2})$	$(P_{1} UNION P_{2})$	$P_{1} = Υ (E_{1})$ and $P_{2} = Υ (E_{2})$ .
$(E_{1} ∖ E_{2})$	$(P_{1} EXCEPT P_{2})$	$P_{1} = Υ (E_{1})$ and $P_{2} = Υ (E_{2})$ .
$π_{S} (E_{1})$	$(SELECT W P_{1})$	$P_{1} = Υ (E_{1})$ and $W$ is the set of variables corresponding to the attributes in $S$ .
$ρ_{A / B} (E_{1})$	${subs}_{? X / ? Y} (P_{1})$	$P_{1} = Υ (E_{1})$ , $? X$ is the variable that corresponds to attribute $A$ , $? Y$ is the variable that corresponds to attribute $B$ , and ${subs}_{? X / ? Y} (P_{1})$ denotes the renaming of variable $? X$ with variable $? Y$ in the SPARQL query $P_{1}$ (see Appendix A).
$σ_{ψ} (E_{1})$	$(P_{1} FILTER φ)$	$P_{1} = Υ (E_{1})$ , and $φ$ is a filter condition equivalent to the selection condition $ψ$ .

Given an MRA expression $E$ , the function $f_{31}$ returns a SPARQL graph pattern defined by $(Υ (E) UNION AttrQuery (E))$ .

Example 14
Consider the MRA expression $E = R ⋈ S$ where $\hat{R} = {A, B}$ and $\hat{S} = {B, C}$ . Then the corresponding SPARQL query $f_{31} (E)$ is the following:
$f_{31} (E) = \begin{aligned} ( & \begin{aligned} ( & (SELECT {{? X}_{A}, {? X}_{B}} WHERE ({? Y}_{1}, iri_A, {? X}_{A}) AND ({? Y}_{1}, iri_B, {? X}_{B})) AND \\ (SELECT {{? X}_{B}, {? X}_{C}} WHERE ({? Y}_{1}, iri_B, {? X}_{B}) AND ({? Y}_{1}, iri_C, {? X}_{C}))) UNION \end{aligned} \\ ((N U L L, N U L L, {? X}_{A}) AND (N U L L, N U L L, {? X}_{A}) AND (N U L L, N U L L, {? X}_{A}))) . \end{aligned}$
If $R = {[{A \mapsto a, B \mapsto b}, {A \mapsto a, B \mapsto b}]}$ and $S = {[{B \mapsto b, C \mapsto c}]}$ , the answer to the SPARQL query over the corresponding translation of the MRA database $D$ to an RDF graph is the following multiset:
$⟦ f_{31} E ⟧_{g_{31} (D)} = {[\begin{aligned} {{? X}_{A} \mapsto a, {? X}_{B} \mapsto b, {? X}_{C} \mapsto c}, \\ {{? X}_{A} \mapsto a, {? X}_{B} \mapsto b, {? X}_{C} \mapsto c}, \\ {{? X}_{A} \mapsto N U L L, {? X}_{B} \mapsto N U L L, {? X}_{C} \mapsto N U L L}]} . \end{aligned}$
Otherwise, if $R$ is empty then:
$⟦ f_{31} E ⟧_{g_{31} (D)} = {[\begin{aligned} {{? X}_{A} \mapsto N U L L, {? X}_{B} \mapsto N U L L, {? X}_{C} \mapsto N U L L}]} . \end{aligned}$
Whereas the first two SPARQL mappings ${{? X}_{A} \mapsto a, {? X}_{B} \mapsto b, {? X}_{C} \mapsto c}$ correspond are duplicates of the same MRA answer, ${A \mapsto a, B \mapsto b, C \mapsto c}$ , the last mapping does not correspond to an answer, but encodes the attributes of the MRA query. By encoding the attributes of the MRA query, we can reconstruct the result MRA relation even in the case it is empty.
8.1.3. Translating Query Answers From SPARQL to MRA

Recall that a query answer in SPARQL is a multiset of mappings, and a query answer in MRA is a multiset relation (i.e., a multiset of tuples). Intuitively, a multiset of mappings $Ω$ can be transformed into an MRA relation $r$ where the attributes in $\hat{r}$ are the variables in the domain of $Ω$ . This notion is defined next.

Definition 20 Function $h_{31}$

Let $Ω$ be a multiset of mappings with $dom (μ) = V$ for every mapping $μ \in Ω$ , and that includes the mapping $μ_{V \mapsto NULL}$ with $dom (μ_{V \mapsto NULL}) = V$ , $μ_{V \mapsto NULL} (? X) = NULL$ for every variable $? X \in V$ . The function $h_{31} (Ω)$ returns a multiset relation $r$ where:

–
For each variable $? X \in V$ , the schema $\hat{r}$ includes the MRA attribute $A$ corresponding to variable $? X$ .
–
The tuple $t_{μ}$ corresponding to a mapping $μ$ with $dom (μ) = V$ is the tuple with attributes $\hat{r}$ such that $t (A) = μ (? X)$ , for each MRA attribute $A \in \hat{r}$ corresponding to a variable $? X \in V$ .
–
$set (r) = {t_{μ} ∣ μ \in set (Ω) ∖ {μ_{V \mapsto NULL}}}$ .
–
$card (t_{μ}, r) = card (μ, Ω)$ .

Lemma 13
MRA can be simulated in SPARQL.
Proof.
Let $f_{31}, g_{31}, h_{31}$ denote, respectively, the functions stated in Definitions 19, 18, and 20. The proof of this theorem follows from the claim that $(f_{31}, g_{31}, h_{31})$ simulates MRA in SPARQL by using induction in the structure of queries. The proof of this claim is in the Appendix (Claim 8).
8.2. From SPARQL to MRA

This section shows that SPARQL can be simulated by MRA. To support this, we describe the following translation functions:

–
$f_{13}$ is the function that translates SPARQL queries into MRA queries;
–
$g_{13}$ is the function that translates SPARQL databases into MRA databases; and
–
$h_{13}$ is the function that translates MRA query answers into SPARQL query answers.

The translation presented here is inspired by the one presented by Cyganiak (2005). However, unlike Cyganiak, we do not use null values with the SQL semantics. Instead, we use a special constant, denoted $⊥$ , used to codify unbound values.
8.2.1. Translating Databases From SPARQL to MRA

Recall that a SPARQL database is a set of RDF triples, and an MRA database is a set of multiset relations. The translation of a set of RDF triples $G$ will produce three multiset relations (without duplicates): $Trip$ , which codifies the RDF triples in $G$ ; $Null$ , introduced to manage the unbound values of SPARQL; and $Comp$ , introduced to simulate the notion of compatibility between mappings.

Definition 21 Function $g_{13}$

Let $⊥$ be a special constant. Given a set of RDF triples $G$ , the function $g_{13} (G)$ returns a multiset relational database $D^{'}$ containing the multiset relations $Trip$ , $Null$ , and $Comp$ defined as follows:

$\hat{Trip} = {S, P, O}$ , $set (Trip) = {{S \mapsto s, P \mapsto p, O \mapsto o} ∣ (s, p, o) \in G}$ , and $card (t, Trip) = 1$ for every tuple $t \in set (Trip)$ .

$\hat{Null} = {N}$ , $set (Null) = {{N \mapsto ⊥}}$ , and $card ({N \mapsto ⊥}, Null) = 1$ .

$\hat{Comp} = {A_{1}, A_{2}, A}$ , $set (Comp)$ includes the tuple ${A_{1} \mapsto ⊥, A_{2} \mapsto ⊥, A \mapsto ⊥}$ and all tuples of the form ${A_{1} \mapsto a, A_{2} \mapsto a, A \mapsto a}$ , ${A_{1} \mapsto ⊥, A_{2} \mapsto a, A \mapsto a}$ , and ${A_{1} \mapsto a, A_{2} \mapsto ⊥, A \mapsto a}$ where $a$ is an RDF term in $G$ , and $card (t, Comp) = 1$ for every tuple $t \in set (Comp)$ .

Example 15
Let $G$ be the RDF graph defined as follows:
$G = {\begin{aligned} (A l i c e, l i v e s I n, S a n t i a g o), (A l i c e, k n o w s, B o b), \\ (B o b, l i v e s I n, S a n t i a g o), (B o b, k n o w s, C a r o l), \\ (C a r o l, l i v e s I n, L i m a)} . \end{aligned}$
Then the data are translated for MRA as the database $g_{13} (G)$ with the multiset relations $Trip$ , $Null$ , and $Comp$ defined as follows:
$\begin{aligned} Trip & = \begin{aligned} {[ & {S \mapsto A l i c e, P \mapsto l i v e s I n, O \mapsto S a n t i a g o}, {S \mapsto A l i c e, P \mapsto k n o w s, O \mapsto B o b}, \\ {S \mapsto B o b, P \mapsto l i v e s I n, O \mapsto S a n t i a g o}, {S \mapsto B o b, P \mapsto k n o w s, O \mapsto C a r o l}, \\ {S \mapsto C a r o l, P \mapsto l i v e s I n, O \mapsto L i m a}]}, \end{aligned} \\ Null & = {[{N \mapsto ⊥}]}, \\ Comp & = \begin{aligned} {[ & {A_{1} \mapsto ⊥, A_{2} \mapsto ⊥, A_{3} \mapsto ⊥}, \\ {A_{1} \mapsto A l i c e, A_{2} \mapsto A l i c e, A_{3} \mapsto A l i c e}, \\ {A_{1} \mapsto A l i c e, A_{2} \mapsto ⊥, A_{3} \mapsto A l i c e}, \\ {A_{1} \mapsto ⊥, A_{2} \mapsto A l i c e, A_{3} \mapsto A l i c e}, \\ {A_{1} \mapsto l i v e s I n, A_{2} \mapsto l i v e s I n, A_{3} \mapsto l i v e s I n}, \\ {A_{1} \mapsto l i v e s I n, A_{2} \mapsto ⊥, A_{3} \mapsto l i v e s I n}, \\ {A_{1} \mapsto ⊥, A_{2} \mapsto l i v e s I n, A_{3} \mapsto l i v e s I n}, \\ ⋮ \\ {A_{1} \mapsto L i m a, A_{2} \mapsto L i m a, A_{3} \mapsto L i m a}, \\ {A_{1} \mapsto L i m a, A_{2} \mapsto ⊥, A_{3} \mapsto L i m a}, \\ {A_{1} \mapsto ⊥, A_{2} \mapsto L i m a, A_{3} \mapsto L i m a}]} . \end{aligned} \end{aligned}$

8.2.2. Translating Queries From SPARQL to MRA

Recall that a SPARQL query is a graph pattern, and an MRA query is a relational algebra expression. First, we define the function $Λ$ which allows translating an RDF triple pattern into an MRA expression.

Assume that $a$ , $b$ , $c$ are RDF terms, and $? X$ , $? Y$ , $? Z$ are variables. Recall that $Trip$ is a multiset relation that is obtained from a set of RDF triples, where $\hat{Trip} = {S, P, O}$ is the schema of $Trip$ . Given a triple pattern $T$ , the function $Λ (T)$ returns an MRA expression defined as follows³ :

–
if $T$ is $(? X, b, c)$ then $Λ (T)$ returns $π_{? X} (ρ_{S / ? X} (σ_{P = b \land O = c} (Trip)))$ ;
–
if $T$ is $(a, ? Y, c)$ then $Λ (T)$ returns $π_{? Y} (ρ_{P / ? Y} (σ_{S = a \land O = c} (Trip)))$ ;
–
if $T$ is $(a, b, ? Z)$ then $Λ (T)$ returns $π_{? Z} (ρ_{O / ? Z} (σ_{S = a \land P = b} (Trip)))$ ;
–
if $T$ is $(? X, ? Y, c)$ then $Λ (T)$ returns $π_{? X, ? Y} (ρ_{P / ? Y} (ρ_{S / ? X} (σ_{O = c} (Trip))))$ ;
–
if $T$ is $(? X, b, ? Z)$ then $Λ (T)$ returns $π_{? X, ? Z} (ρ_{O / ? Z} (ρ_{S / ? X} (σ_{P = b} (Trip))))$ ;
–
if $T$ is $(a, ? Y, ? Z)$ then $Λ (T)$ returns $π_{? Y, ? Z} (ρ_{O / ? Z} (ρ_{P / ? Y} (σ_{S = a} (Trip))))$ ;
–
if $T$ is $(? X, ? Y, ? Z)$ then $Λ (T)$ returns $π_{? X, ? Y, ? Z} (ρ_{O / ? Z} (ρ_{P / ? Y} (ρ_{S / ? X} (Trip))))$ ;
–
if $T$ is $(? X, ? X, c)$ then $Λ (T)$ returns $π_{? X} (ρ_{S / ? X} (σ_{S = P \land O = c} (Trip)))$ ;
–
if $T$ is $(? X, b, ? X)$ then $Λ (T)$ returns $π_{? X} (ρ_{S / ? X} (σ_{P = b \land S = O} (Trip)))$ .
–
if $T$ is $(a, ? X, ? X)$ then $Λ (T)$ returns $π_{? X} (ρ_{P / ? X} (σ_{S = a \land P = O} (Trip)))$ ; and
–
if $T$ is $(? X, ? X, ? X)$ then $Λ (T)$ returns $π_{? X} (ρ_{S / ? X} (σ_{S = P \land P = O} (Trip)))$ .

Second, we define a function $γ$ that allows translating a SPARQL filter condition into an MRA selection condition. Like in the translation from SPARQL to ${NRMD}^{\neg}$ , it is not necessary to translate complex filter conditions (SPARQL) to complex selection formulas (MRA) because SPARQL queries can be normalized to avoid logical connectives.

Given an atomic filter condition $φ$ , the function $γ (φ)$ is defined recursively as follows: –
If $φ$ is $? X = c$ then $γ (φ)$ is $(\neg (X = ⊥) \land X = c)$ where $X$ is the attribute name corresponding to variable $? X$ .
–
If $φ$ is $? X = ? Y$ then $γ (φ)$ is $((\neg (X = ⊥) \land \neg (Y = ⊥)) \land X = Y)$ where $X$ and $Y$ are the attribute names corresponding to variables $? X$ and $? Y$ , respectively.
–
If $φ$ is $bound (X)$ then $γ (φ)$ is $\neg (X = ⊥)$ where $X$ is the attribute name corresponding to variable $? X$ .

In Definition 21, we introduced the relation named $Comp$ to simulate the compatibility between mappings. For example, to simulate the SPARQL query $Q = (P_{1} AND P_{2})$ we need to ensure that check if two pairs of mappings $μ_{1} \in ⟦ P_{1} ⟧_{G}$ and $μ_{2} \in ⟦ P_{2} ⟧_{G}$ are compatible, and if they are compatible, return the mapping $μ = μ_{1} \cup μ_{2}$ resulting from joining them. To explain how this operation is simulated with MRA, let $inScope (P_{1}) \cap inScope (P_{2}) = {? X}$ and tuples $t_{1}$ and $t_{2}$ correspond to mappings $μ_{1}$ and $μ_{2}$ . To be compatible, either both mappings map variable $? X$ to the same value, or at least for one of the mappings, variable $? X$ is unbound. For tuples, an unbound variable $? X$ is represented with an attribute value $⊥$ (e.g., $t (X) = ⊥$ ). Then, to check if tuples $t_{1}$ and $t_{2}$ are compatible, we need to rename the attribute name $X$ corresponding to variable $? X$ as two attributes, namely $X_{1}$ and $X_{2}$ and check if there exists a tuple $t_{3}$ in the result of query $ρ_{A_{1} / X_{1}} (ρ_{A_{2} / X_{2}} (Comp))$ that agrees with tuples $t_{1}$ and $t_{2}$ (i.e., $t_{3} (X_{1}) = t_{1} (X)$ and $t_{3} (X_{2}) = t_{2} (X)$ ) or agrees with either $t_{1}$ or $t_{2}$ whereas for the other tuple the value is $⊥$ (e.g., $t_{3} (X_{1}) = t_{1} (X)$ and $t_{2} (X_{2}) = ⊥$ ). We recover the renamed attribute $X$ for the attribute $A$ in the relation named $Comp$ . That is, for the compatibility, we use the MRA expression $ρ_{A / X} (ρ_{A_{1} / X_{1}} (ρ_{A_{2} / X_{2}} (Comp)))$ which is generalized as follows for multiple common variables in the scope of patterns $P_{1}$ and $P_{3}$ .

Let $X$ be a finite set of attribute names, and $ν_{1}$ and $ν_{2}$ be two bijective functions that map each attribute $X \in X$ to two different sets of attributes (i.e., the ranges of $ν_{1}$ and $ν_{2}$ are disjoint). Then, we write $Comp (ν_{1}, ν_{2}, X)$ to denote the join of MRA expressions of the form $ρ_{A / X} (ρ_{A_{1} / ν_{1} (X)} (ρ_{A_{2} / ν_{2} (X)} (Comp)))$ , for every attribute name $X \in X$ .

Let $E$ be an MRA expression, and $X = {X_{1}, \dots, X_{n}}$ be a subset of the attribute names in $\hat{E}$ , and $ν$ a bijective function that maps each attribute name in $X$ to a fresh attribute name (i.e., $ν (X) \notin \hat{E}$ ). We call $ν (E)$ the MRA expression that renames each attribute name $X \in X$ with $ν (X)$ . That is, $ν (E) = ρ_{X_{1} / ν (X_{1})} (\dots ρ_{X_{n} / ν (X_{n})} (E) \dots)$ .

Given two MRA expressions $E_{1}$ and $E_{2}$ , assume two bijective functions $ν_{1}$ and $ν_{2}$ that map each attribute $X \in {\hat{E}}_{1} \cap {\hat{E}}_{2}$ to two fresh attributes (i.e., $ν_{1} (X), ν_{2} (X) \notin {\hat{E}}_{1} \cup {\hat{E}}_{2}$ ), and satisfy $range (ν_{1}) \cap range (ν_{2}) = \emptyset$ . Then, we define the MRA operation $E_{1} * E_{2}$ in terms of existing MRA operators as follows:
$E_{1} * E_{2} = π_{{\hat{E}}_{1} \cup {\hat{E}}_{2}} (Comp (ν_{1}, ν_{2}, {\hat{E}}_{1} \cap {\hat{E}}_{2}) ⋈ ν_{1} (E_{1}) ⋈ ν_{2} (E_{2})) .$
Notice that the attribute names in the ranges of functions $μ_{1}$ and $μ_{2}$ in the definition of expression $E_{1} * E_{2}$ do not matter because they are not in the schema of the multiset that results from expression $E_{1} * E_{2}$ .

To translate SPARQL queries $Q$ of the form $(SELECT X P)$ where the set of variables $X$ include a variable that is not in the scope of $P$ , we need to generate values $⊥$ to fill the tuples returned by the translated query. For example, if $inScope (P) = {? X}$ and $X = {? X, ? Y}$ , then the MRA expression $E$ that corresponds to the SPARQL pattern $P$ can be extended with an attribute name $Y$ by joining $E$ with the MRA relation $ρ_{N / Y} (Null)$ . Given a set $Y = {Y_{1}, \dots, Y_{n}}$ of attribute names, we define the MRA expression $Δ (Y)$ as $ρ_{N / Y_{1}} (Null) ⋈ \dots ⋈ ρ_{N / Y_{n}} (Null)$ .

Next, we present the translation of SPARQL queries to MRA queries.
Definition 22 Function $f_{13}$

The translation rules in Table 7 define the function

f_{13}

from normalized graph patterns whose filter conditions have no Boolean connectives to MRA queries.

Table 7.
Definition of the Function $f_{13}$ , Which Takes a Normalized SPARQL Pattern $P$ as Input (Without Logical Connectives in Filter Conditions) and Returns an MRA Query.

SPARQL pattern $P$	MRA query $f_{13} (P)$	where $\dots$
$(s, p, o)$	$Λ (s, p, o)$
$(P_{1} AND P_{2})$	$(f_{13} (P_{1}) * f_{13} (P_{2}))$
$(P_{1} UNION P_{2})$	$(f_{13} (P_{1}) \cup f_{13} (P_{2}))$
$(P_{1} EXCEPT P_{2})$	$(f_{13} (P_{1}) ∖ f_{13} (P_{2}))$
$(SELECT inScope (P) P_{1})$	$π_{A} (f_{13} (P_{1}) ⋈ Δ_{B})$	$A$ is the set of attribute names corresponding to the variables in set $inScope (P)$ and $B$ is the set of attribute names that correspond to variables that are in set $inScope (P) ∖ inScope (P_{1})$ .
$(P_{1} FILTER φ)$	$σ_{γ (φ)} (f_{13} (P_{1}))$

Note. MRA = multiset relational algebra.

Example 16

Let $Q$ be the following SPARQL query asking for all people, the place where they live, and optionally the people they know (notice that this query is already normalized as we discussed in Example 6).

\begin{aligned} ( & ((? p e r s o n, l i v e s I n, ? s o m e w h e r e) AND (? p e r s o n, k n o w s, ? s o m e b o d y)) \\ UNION \\ \begin{aligned} ( & SELECT ? p e r s o n ? s o m e w h e r e ? s o m e b o d y \\ WHERE \begin{aligned} ( & (? p e r s o n, l i v e s I n, ? s o m e w h e r e) EXCEPT \\ \begin{aligned} ( & SELECT ? p e r s o n ? s o m e w h e r e \\ WHERE ((? p e r s o n, l i v e s I n, ? s o m e w h e r e) AND (? p e r s o n, k n o w s, ? s o m e b o d y)))))) . \end{aligned} \end{aligned} \end{aligned} \end{aligned}

Then, the corresponding query

f_{13} (Q)

is the query

(q (X), Π)

, where

Π

is defined as follows:

\begin{aligned} (Λ (? p e r s o n, l i v e s I n, ? s o m e w h e r e) * Λ (? p e r s o n, k n o w s, ? s o m e b o d y)) \cup \\ \begin{aligned} ( & \begin{aligned} ( & π_{P e r s o n} (Λ (? p e r s o n, l i v e s I n, ? s o m e w h e r e)) ∖ \\ π_{P e r s o n} (Λ (? p e r s o n, l i v e s I n, ? s o m e w h e r e) * Λ (? p e r s o n, k n o w s, ? s o m e b o d y))) ⋈ \end{aligned} \\ ρ_{N / S o m e b o d y} (Null)), \end{aligned} \end{aligned}

where the MRA attributes

P e r s o n

and

S o m e b o d y

correspond to the SPARQL variables

? p e r s o n

and

? s o m e b o d y

8.2.3. Translating Query Answers From MRA to SPARQL

Recall that an MRA query answer is a multiset of tuples, and a SPARQL query answer is a multiset of solution mappings. Next, we define the function $h_{31}$ that transforms MRA query answers into ${NRMD}^{\neg}$ query answers.

Intuitively, the translation of an MRA tuple $t$ as a SPARQL solution mapping $μ$ consists of removing from tuple $t$ every attribute whose value is $⊥$ , and viewing the result tuple as a SPARQL mapping $μ$ . For example, the result of translating a tuple $t$ with $\hat{t} = {X, Y}$ , $t (X) = a$ , and $t (Y) = ⊥$ , is the SPARQL mapping $μ = {? X \mapsto a}$ . Recall that we write $? X$ to denote the corresponding SPARQL variable for an MRA attribute $X$ .

Definition 23 Function $h_{31}$

Given an MRA tuple $t$ , we write $f_{31} (t)$ to denote the SPARQL mapping $μ$ such that: (1) $μ (? X) = t (X)$ if $X \in \hat{t}$ and $t (X) \neq ⊥$ , and (2) variable $? Y$ is not in $dom (μ)$ if $Y \notin \hat{t}$ or $t (Y) = ⊥$ . Abusing notation, $f_{31} (r)$ is also the function that receives an MRA relation $r$ and returns the multiset $Ω$ of SPARQL mappings where $set (Ω) = {μ ∣ there exist t \in r such that f_{31} (t) = μ}$ and the cardinality of mapping $f_{31} (t)$ in $Ω$ is the cardinality of tuple $t$ in $r$ .

Lemma 14
SPARQL can be simulated by MRA.
Proof.
This is a long but straightforward induction on the structure of SPARQL queries using as a hypothesis that $(f_{13}, g_{13}, h_{13})$ is a simulation of SPARQL by MRA. The details of this proof are in the Appendix (Claim 9).
8.3. MRA and SPARQL Have the Same Expressive Power

Putting together the simulations among MRA and SPARQL stated in this section, we get the following theorem:

Theorem 3
MRA and SPARQL have the same expressive power.
Proof.
The claim is based on the simulation of MRA with SPARQL (Lemma 13) and the simulation of SPARQL with MRA (Lemma 14).
9. Conclusions

We studied the algebraic and logic structure of the multiset semantics of the core SPARQL patterns, and compared it to the classical and well-studied formalisms of MRA and multiset Datalog. Our motivation was to shed light on the underlying theoretical structure of the multiset features of SPARQL that could help improve future designs and implementations. In this regard, the main discoveries of this research are: (1) the core fragment of SPARQL patterns matches precisely the multiset semantics of Datalog as defined by Mumick et al. (1990b); and (2) this logical structure corresponds to a simple multiset algebra, namely the MRA. These correspondences, besides showing a nice parallel to the one exhibited by classical set relational algebra and relational calculus, and thus transferring theoretical guarantees from these well-studied formalisms, could help to give new insights into possible optimizations and future extensions of SPARQL.

We think there are a couple of lessons learned in the investigation of the multiset features of SPARQL. First, contrary to the rather chaotic variety of multiset operators in SQL, it is interesting to observe that the SPARQL design comprises a more coherent body of multiset operators. We suggest that this asset should be considered and curated by designers in order to try to keep this clean design in future extensions of SPARQL. Second, there is a challenging goal for query language designers that work with multisets: given the diversity of multiset extensions for each of the classical set operators, it is not evident at all from a theoretical perspective how to develop a logically coherent formalism that could integrate all or most of them.

Our study shows that there are fragments that behave coherently, but that operators do not fit in this schema, when available (not always), have to be accessed in a very ad-hoc manner. Last but not least, this study shows (and adds evidence of) the complexities and challenges that the introduction of multisets brings to query languages, exemplified here in the case of SPARQL. Many more use cases are needed in order to match the theoretical restrictions and recommendations (e.g., as studied in this paper), and real-life use cases that, to the best of our knowledge, do not yet have a good systematization.

Footnotes

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: R. Angles was supported by ANID FONDECYT Chile through grant 1221727. D. Hernández was supported by the German Research Foundation, Deutsche Forschungsgemeinschaft (DFG), grant SFB-1574-471687386. This work was partly funded by ANID - Millennium Science Initiative Program—Code ICN17_002.

Declaration of Conflicting Interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

ORCID iDs

Renzo Angles

Claudio Gutierrez

Daniel Hernández

Notes

Appendix A. Variable renaming in SPARQL

This appendix section defines function $subs (\cdot, \cdot)$ , which renames SPARQL variables. This function is used to simulate the MRA operator renaming $ρ_{A / B}$ (see Table 6). Note that function $subs (\cdot, \cdot)$ is not an additional algebraic operation but an operation over expressions (i.e., a query rewriting). Intuitively, given an MRA query $Q$ , a SPARQL pattern $P$ that simulates $Q$ , a renaming of MRA attributes $A / B$ and a renaming of variables $? X / ? Y$ where $? X$ and $? Y$ are the corresponding variables for attributes $A$ and $B$ , the query rewriting ${subs}_{? X / ? Y} (P)$ simulates the MRA query $ρ_{A, B} (Q)$ . To this end, SPARQL variables are renamed in the pattern, instead of renaming query result attributes as MRA does.

Appendix B. Proof of Claims

References

Abiteboul

Hull

Vianu

(1995). Foundations of databases. Addison-Wesley.

Afrati

F. N.

Damigos

Gergatsoulis

(2010). Query containment under bag and bag-set semantics. Information Processing Letters, 110(10), 360–369. https://doi.org/10.1016/j.ipl.2010.02.017

Albert

(1991). Algebraic properties of bag data types. In Proceedings of the international conference on very large data bases (VLDB) (pp. 211–219). Morgan Kaufmann Publishers Inc. https://dl.acm.org/doi/10.5555/645917.672310

Angles

Gottlob

Pavlović

Pichler

Sallinger

(2023). SparqLog: A system for efficient evaluation of SPARQL 1.1 queries via Datalog. Proceeding of VLDB Endowment, 16(13), 4240–4253. https://doi.org/10.14778/3625054.3625061

Angles

Gutiérrez

(2008). The Expressive Power of SPARQL. In Proceedings of the international semantic web conference (ISWC), LNCS (Vol. 5318, pp. 114–129). Springer. https://doi.org/10.1007/978-3-540-88564-1_8

Angles

Gutiérrez

(2016). The multiset semantics of SPARQL patterns. In 15th international semantic web conference (ISWC), LNCS (Vol. 9981, pp. 20–36). Springer. https://doi.org/10.1007/978-3-319-46523-4_2

Angles

Gutierrez

(2016). Negation in SPARQL. In Alberto Mendelzon international workshop on foundations of data management (AMW). https://ceur-ws.org/Vol-1644/paper11.pdf.

Bellomarini

Sallinger

Gottlob

(2018). The Vadalog system: Datalog-based reasoning for knowledge graphs. Proceeding of VLDB Endowment, 11(9), 975–987. https://doi.org/10.14778/3213880.3213888

Bertossi

Gottlob

Pichler

(2019). Datalog: Bag semantics via set semantics. In International conference on database theory (ICDT) (Vol. 127, pp. 16:1–16:19). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ICDT.2019.16

10.

Breazu-Tannen

Subrahmanyam

(1991). Logical and computational aspects of programming with sets/bags/lists. In Automata, languages and programming (pp. 60–75). Springer.

11.

Chebotko

Fotouhi

(2009). Semantics preserving SPARQL-to-SQL translation. Data & Knowledge Engineering, 68(10), 973–1000. https://doi.org/10.1016/j.datak.2009.04.001

12.

Cohen

(2009). Equivalence of queries that are sensitive to multiplicities. The VLDB Journal, 18(3), 765–785. https://doi.org/10.1007/s00778-008-0122-1

13.

Colby

L. S.

Libkin

(1997). Tractable iteration mechanisms for bag languages. In International conference on database theory (ICDT), LNCS (Vol. 1186, pp. 461–475). Springer. https://doi.org/10.1007/3-540-62222-5_64

14.

Console

Guagliardo

Libkin

(2022). Fragments of bag relational algebra: Expressiveness and certain answers. Information Systems, 105, 101604. https://doi.org/10.1016/j.is.2020.101604

15.

Cyganiak

(2005). A relational algebra for SPARQL. Technical Report HPL-2005-170, HP Labs.

16.

Date

C. J.

(2006). Date on database: Writings 2000–2006. APress.

17.

Dayal

Goodman

Katz

R. H.

(1982). An extended relational algebra with control over duplicate elimination. In Proceedings of the symposium on principles of database systems (PODS) (pp. 117–123). ACM. https://doi.org/10.1145/588111.588132

18.

Geerts

Unger

Karvounarakis

Fundulaki

Christophides

(2016). Algebraic structures for capturing the provenance of SPARQL queries. Journal of ACM, 63(1), 1–63. https://doi.org/10.1145/2810037

19.

Green

T. J.

(2009). Bag semantics. In Encyclopedia of database systems (pp. 201–206).

20.

Grumbach

Libkin

Milo

Wong

(1996). Query languages for bags: Expressive power and complexity. SIGACT News, 27(2), 30–44. https://doi.org/10.1145/235767.235770

21.

Grumbach

Milo

(1996). Towards tractable algebras for bags. Journal of Computer and System Sciences, 52(3), 570–588. https://doi.org/10.1006/jcss.1996.0042

22.

Guagliardo

Libkin

(2017). A formal semantics of SQL queries, its validation, and applications. Proceeding of VLDB Endowment, 11(1), 27–39. https://doi.org/10.14778/3151113.3151116

23.

Harris

Seaborne

(2013). SPARQL 1.1 Query Language – W3C Recommendation. http://www.w3.org/TR/2013/REC-sparql11-query-20130321/.

24.

Hernández

(2020). The problem of incomplete data in SPARQL. PhD dissertation, Universidad de Chile—Faculty of Physical and Mathematical Sciences, Santiago, Chile. https://repositorio.uchile.cl/handle/2250/178033.

25.

Hernich

Kolaitis

P. G.

(2017). Foundations of information integration under bag semantics. In 32nd annual ACM/IEEE symposium on logic in computer science (LICS) (pp. 1–12). IEEE. https://doi.org/10.1109/LICS.2017.8005104

26.

Hogan

Arenas

Mallea

Polleres

(2014). Everything you always wanted to know about blank nodes. Journal of Web Semantics, 27–28(August–October), 42–69. https://doi.org/10.1016/j.websem.2014.06.004

27.

Kaminski

Kostylev

E. V.

Grau

B. C.

(2016). Semantics and expressive power of subqueries and aggregates in SPARQL 1.1. In Proceedings of the international conference on world wide web (WWW) (pp. 227–238). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE. https://doi.org/10.1145/2872427.2883022

28.

Klausner

Goodman

(1985). Multirelations – semantics and languages. In Proceedings of international conference on very large data bases (VLDBs) (pp. 251–258). ACM. https://dl.acm.org/doi/10.5555/1286760.1286783.

29.

Kontchakov

Kostylev

E. V.

(2016). On expressibility of non-monotone operators in SPARQL. In International conference on the principles of knowledge representation and reasoning (pp. 369–378). AAAI Press. https://dl.acm.org/doi/10.5555/3032027.3032071.

30.

Lamperti

Melchiori

Zanella

(2001). On multisets in database systems. In Proceedings of the workshop on multiset processing (pp. 147–216). ACM. https://dl.acm.org/doi/10.5555/647269.721839.

31.

Libkin

Wong

(1994). Some properties of query languages for bags. In Proceedings of the international workshop on database programming languages (DBPL) – object models and languages (pp. 97–114). ACM. https://doi.org/10.1007/978-1-4471-3564-7_7

32.

Libkin

Wong

(1997). Query languages for bags and aggregate functions. Journal of Computer and System Sciences, 55(2), 241–272. https://doi.org/10.1006/jcss.1997.1523

33.

Lloyd

J. W.

(1998). Programming with multisets. Technical report, University of Bristol.

34.

Melton

Simon

A. R.

(2002). SQL:1999. Understanding relational language components. Morgan Kaufmann Publishers.

35.

Mumick

I. S.

Finkelstein

S. J.

Pirahesh

Ramakrishnan

(1990a). Magic is relevant. SIGMOD Record, 19(2), 247–258. https://doi.org/10.1145/93605.98734

36.

Mumick

I. S.

Pirahesh

Ramakrishnan

(1990b). The magic of duplicates and aggregates. In Proceedings of the international conference on very large data bases (pp. 264–277). Morgan Kaufmann Publishers Inc. https://dl.acm.org/doi/10.5555/94362.94426

37.

Pérez

Arenas

Gutierrez

(2006). Semantics of SPARQL. Technical Report TR/DCC-2006-17, Department of Computer Science, University of Chile.

38.

Polleres

(2007). From SPARQL to rules (and back). In Proceedings of the 16th international world wide web conference (WWW) (pp. 787–796). ACM. https://doi.org/10.1145/1242572.1242679

39.

Polleres

Wallner

J. P.

(2013). On the relation between SPARQL1.1 and answer set programming. Journal of Applied Non-Classical Logics, 23(1–2), 159–212. https://doi.org/10.1080/11663081.2013.798992

40.

Prud’hommeaux

Seaborne

(2008). SPARQL query language for RDF. W3C recommendation. http://www.w3.org/TR/2008/REC-115-sparql-query-20080115/

41.

Ricciotti

Cheney

(2019). Mixing set and bag semantics. In Proceedings of 17th ACM SIGPLAN international symposium on database programming languages (DBPL) (pp. 70–73). ACM. https://doi.org/10.1145/3315507.3330202

42.

Schenk

(2007). A SPARQL semantics based on Datalog. In Annual German conference on advances in artificial intelligence (Vol. 4667, pp. 160–174). Springer. https://doi.org/10.1007/978-3-540-74565-5_14

43.

Schmidt

Meier

Lausen

(2010). Foundations of SPARQL query optimization. In Proceedings of the international conference on database theory (pp. 4–33). ACM. https://doi.org/10.1145/1804669.1804675

44.

Zhang

den Bussche

J. V.

(2014). On the primitivity of operators in SPARQL. Information Processing Letters, 114(9), 480–485. https://doi.org/10.1016/j.ipl.2014.03.014

Multiset Semantics in SPARQL,Relational Algebra,and Datalog

Abstract

Keywords

1. Introduction

2.1. Multisets

Definition 1 Query language

Definition 2 Generalized expressive power

3.1. RDF Graphs

3.2. SPARQL Syntax

4.1. NRMD ¬ Syntax

4.2. NRMD ¬ Semantics

5.1. Multiset Relations

5.2. Syntax of MRA

6.1. From SPARQL to NRMD ¬

– function f 12 that translates SPARQL queries into NRMD ¬ queries; – function g 12 that translates SPARQL databases into NRMD ¬ databases; and – function h 12 that translates NRMD ¬ query answers into SPARQL query answers. 6.1.1. Translating Databases From SPARQL to NRMD ¬

Definition 4 Function g 12

Translation of SPARQL Graph Patterns Into Datalog Rules

6.1.3. Translating Query Answers From NRMD ¬ to SPARQL

Definition 8 Function h 12

Lemma 8 SPARQL can be simulated by NRMD ¬ . Proof. We need to show that, using the functions defined above, ( f 12 , g 12 , h 12 ) is a simulation of SPARQL in NRMD ¬ . The proof is in the Claim 4 of the Appendix. 6.2. From NRMD ¬ to SPARQL

Definition 9 Function g 21

Definition 11 Function h 21

Theorem 1 SPARQL and NRMD ¬ have the same expressive power. Proof. The claim is based on the simulation of SPARQL with NRMD ¬ (Lemma 8) and the simulation of NRMD ¬ with MRA (Lemma 9). 7. Equivalence Between MRA and NRMD ¬

7.1. From MRA to NRMD ¬

– f 32 is the function that translates MRA queries into NRMD ¬ queries; – g 32 is the function that translates MRA databases into NRMD ¬ databases; and – h 32 is the function that translates NRMD ¬ query answers into MRA query answers. 7.1.1. Translating Databases From MRA to NRMD ¬

Definition 12 Function g 32

Table 5. Definition of Function Γ Which Translates an MRA Expression Into a set of Datalog Rules.

Definition 14 Function h 32

7.2.1. Translating Databases From NRMD ¬ to MRA

Definition 15 Function g 23

7.2.3. Translating Query Answers From MRA to NRMD ¬

Definition 17 Function h 23

Theorem 2 MRA and NRMD ¬ have the same expressive power. Proof. The claim is based on the simulation of MRA with NRMD ¬ (Lemma 11) and the simulation of NRMD ¬ with MRA (Lemma 12). 8. Equivalence Between MRA and SPARQL

8.1. From MRA to SPARQL

– f 31 is the function that translates MRA queries into SPARQL queries; – g 31 is the function that translates MRA databases into SPARQL databases; and – h 31 is the function that translates SPARQL query answers into MRA query answers. 8.1.1. Translating Databases From MRA to SPARQL

Definition 18 Function g 31

Definition 20 Function h 31

Definition 21 Function g 13

Table 7. Definition of the Function f 13 , Which Takes a Normalized SPARQL Pattern P as Input (Without Logical Connectives in Filter Conditions) and Returns an MRA Query.

Definition 23 Function h 31

Theorem 3 MRA and SPARQL have the same expressive power. Proof. The claim is based on the simulation of MRA with SPARQL (Lemma 13) and the simulation of SPARQL with MRA (Lemma 14). 9. Conclusions

Footnotes

Funding

Declaration of Conflicting Interests

ORCID iDs

Notes

Appendix A. Variable renaming in SPARQL

Appendix B. Proof of Claims

References

4.1. ${NRMD}^{\neg}$ Syntax

4.2. ${NRMD}^{\neg}$ Semantics

6.1. From SPARQL to ${NRMD}^{\neg}$

Definition 4 Function $g_{12}$

6.1.3. Translating Query Answers From ${NRMD}^{\neg}$ to SPARQL

Definition 8 Function $h_{12}$

Lemma 8
SPARQL can be simulated by ${NRMD}^{\neg}$ .
Proof.
We need to show that, using the functions defined above, $(f_{12}, g_{12}, h_{12})$ is a simulation of SPARQL in ${NRMD}^{\neg}$ . The proof is in the Claim 4 of the Appendix.
6.2. From ${NRMD}^{\neg}$ to SPARQL

Definition 9 Function $g_{21}$

Definition 11 Function $h_{21}$

Theorem 1
SPARQL and ${NRMD}^{\neg}$ have the same expressive power.
Proof.
The claim is based on the simulation of SPARQL with ${NRMD}^{\neg}$ (Lemma 8) and the simulation of ${NRMD}^{\neg}$ with MRA (Lemma 9).
7. Equivalence Between MRA and ${NRMD}^{\neg}$

7.1. From MRA to ${NRMD}^{\neg}$

Definition 12 Function $g_{32}$

Table 5.
Definition of Function $Γ$ Which Translates an MRA Expression Into a set of Datalog Rules.

Definition 14 Function $h_{32}$

7.2.1. Translating Databases From ${NRMD}^{\neg}$ to MRA

Definition 15 Function $g_{23}$

7.2.3. Translating Query Answers From MRA to ${NRMD}^{\neg}$

Definition 17 Function $h_{23}$

Theorem 2
MRA and ${NRMD}^{\neg}$ have the same expressive power.
Proof.
The claim is based on the simulation of MRA with ${NRMD}^{\neg}$ (Lemma 11) and the simulation of ${NRMD}^{\neg}$ with MRA (Lemma 12).
8. Equivalence Between MRA and SPARQL

Definition 18 Function $g_{31}$

Definition 20 Function $h_{31}$

Definition 21 Function $g_{13}$

Table 7.
Definition of the Function $f_{13}$ , Which Takes a Normalized SPARQL Pattern $P$ as Input (Without Logical Connectives in Filter Conditions) and Returns an MRA Query.

Definition 23 Function $h_{31}$

Theorem 3
MRA and SPARQL have the same expressive power.
Proof.
The claim is based on the simulation of MRA with SPARQL (Lemma 13) and the simulation of SPARQL with MRA (Lemma 14).
9. Conclusions