💻 computer science

Multiset semantics in SPARQL, Relational Algebra and Datalog

This paper establishes the expressive equivalence between SPARQL's multiset semantics, multiset-extended non-recursive Datalog with safe negation, and a multiset relational algebra by characterizing their shared algebraic and logical structures for core query operators.

Original authors: Renzo Angles, Claudio Gutierrez, Daniel Hernández

Published 2026-05-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Renzo Angles, Claudio Gutierrez, Daniel Hernández

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive library where books aren't just unique items on a shelf, but piles of identical copies. Sometimes you want to know how many copies of a specific book you have, not just if you have one. In the world of databases, this concept is called a multiset (or a "bag"). Unlike a standard set where duplicates are thrown away, a multiset keeps track of every single copy.

This paper is a deep dive into SPARQL, the language used to ask questions about data on the Semantic Web (like the internet's giant knowledge graph). The authors, Angles, Gutierrez, and Hernández, wanted to understand exactly how SPARQL handles these "bags of data" and whether its logic holds up against two other famous, well-tested mathematical frameworks: Relational Algebra (the math behind SQL databases) and Datalog (a logic-based programming language).

Here is the breakdown of their findings using simple analogies:

1. The Problem: The "Bag" Confusion

Imagine you are a chef.

Set Semantics (The Old Way): You ask for "apples." The kitchen gives you one apple. If you ask again, they give you another. But if you ask for "apples" and they give you two, the system might say, "No, that's just one type of fruit," and ignore the second one.
Multiset Semantics (The Real World): You ask for "apples." The kitchen gives you a bag. If there are two apples in the bag, you get two apples. The count matters.

The authors found that while SQL (the language for traditional databases) has a chaotic mix of ways to handle these counts (some operations add them up, some take the maximum, some subtract them), SPARQL has a surprisingly clean and consistent set of rules for handling them. However, nobody had mathematically proven why SPARQL's rules worked so well or how they compared to the "gold standards" of database theory.

2. The Three Languages in the Ring

The authors set up a "triathlon" to see if three different languages could do the exact same job with the same precision:

SPARQL: The star of the show, used for web data.
NRMD¬ (Non-Recursive Multiset Datalog with Safe Negation): Think of this as a logic puzzle solver. It builds answers step-by-step using rules, but it doesn't allow for infinite loops (non-recursive) and handles "not" statements carefully (safe negation).
MRA (Multiset Relational Algebra): This is the math toolkit. It's like a set of mechanical operations (like a blender, a sieve, or a scale) that you can apply to bags of data to mix, filter, and count them.

3. The Big Discovery: They Are All the Same

The core claim of the paper is that these three languages are mathematically equivalent.

Think of it like three different translators speaking three different languages (Spanish, French, and German). The authors proved that if you take a complex instruction written in SPARQL, you can translate it perfectly into Datalog, and then translate that into Relational Algebra, and you will get the exact same result every time. No information is lost, and no "bag" of data is accidentally emptied or filled with extra copies.

The Translation: They built a "dictionary" (translation functions) that converts SPARQL queries into Datalog rules and Relational Algebra expressions.
The Proof: They showed that for every operation SPARQL can do (like combining two lists of results, filtering out bad data, or counting duplicates), there is a matching operation in the other two languages that does the exact same thing with the exact same counts.

4. Why This Matters (According to the Paper)

The authors don't claim this will immediately fix a specific software bug or create a new medical app. Instead, they focus on the theoretical foundation:

Validation: It proves that SPARQL isn't just a "hacky" language; it has a solid, rigorous mathematical backbone that matches established theories.
Consistency: They found that SPARQL's design is actually more coherent than SQL's. While SQL has many different ways to handle duplicates (which can be confusing), SPARQL's core operators form a clean, logical system.
Future Design: By understanding that SPARQL is equivalent to these simpler, well-studied math models, future designers can build better tools and optimizations for SPARQL. It's like realizing that a complex machine is actually just a combination of simple, reliable gears.

Summary

In short, this paper is a mathematical proof that SPARQL's way of handling duplicate data is perfectly aligned with the best theories of database math. The authors built a bridge between the web's query language (SPARQL), logic programming (Datalog), and algebraic math (Relational Algebra), showing that they are all just different ways of describing the same underlying reality. This gives us confidence that SPARQL is robust, predictable, and theoretically sound.

1. Problem Statement

The paper addresses the theoretical foundations of multiset (bag) semantics in the context of the SPARQL query language for RDF databases. While multisets (allowing duplicate elements) are a standard feature in modern database systems (like SQL) due to practical needs (e.g., aggregation, avoiding expensive duplicate elimination), their theoretical treatment in declarative query languages is complex.

Key challenges identified include:

Semantic Variability: There is no single consensus on how to extend set-based operators (Union, Intersection, Difference) to multisets. Different operators exist (e.g., arithmetic union vs. max-union, arithmetic difference vs. existential negation).
Expressive Power Gap: It is unclear whether the specific subset of multiset operators supported by SPARQL (AND, UNION, FILTER, EXCEPT, SELECT) constitutes an optimal or coherent set.
Lack of Formal Equivalence: There is a need to rigorously characterize the expressive power of SPARQL's multiset semantics by comparing it against established formalisms: Relational Algebra and Datalog.

2. Methodology

The authors employ a comparative formal analysis to establish expressive equivalence between three distinct formalisms under multiset semantics:

SPARQL: Specifically, the "relational core" fragment involving AND, UNION, FILTER, EXCEPT, and SELECT.
NRMD¬ (Non-Recursive Multiset Datalog with Safe Negation): A logical formalism extending Datalog to support multisets and safe negation, based on proof-theoretic semantics (counting derivation trees).
MRA (Multiset Relational Algebra): An algebraic formalism extending standard Relational Algebra with multiset operators (Projection, Selection, Natural Join, Arithmetic Union, Filter Difference).

The Core Approach:
The authors define simulations (translations) between these languages to prove they have the same expressive power. This involves defining three functions for each pair of languages $(L_1, L_2)$ :

$g$ : Database translation (converting data structures).
$f$ : Query translation (converting query syntax).
$h$ : Answer translation (converting result sets).

They prove that $L_1$ is contained in $L_2$ and vice versa, establishing $L_1 \equiv L_2$ .

Key Technical Challenges Addressed:

Handling Nulls/Unbound Values: SPARQL mappings have partial domains (unbound variables), whereas relational tuples and Datalog substitutions are total. The authors introduce a special constant ( $\bot$ or NULL) to represent unbound values in the target languages.
Three-Valued Logic in Filters: SPARQL uses three-valued logic (True, False, Error) for filters. The authors developed specific rewriting rules to handle OR and NOT in filters under bag semantics, ensuring that "Error" conditions are correctly propagated and do not inflate cardinalities incorrectly.
Normalization: They define normal forms for SPARQL patterns and Datalog rules to ensure that variables in sub-patterns are properly scoped before translation.

3. Key Contributions

A. Definition of Formalisms

NRMD¬: The authors define a version of Datalog that supports multisets and safe negation, restricted to non-recursive programs to match SPARQL's capabilities. They utilize "colored sets" to track the cardinality of facts (proofs).
MRA: They define a Multiset Relational Algebra comprising:
- $\pi$ (Projection): Summing cardinalities of projected tuples.
- $\sigma$ (Selection): Filtering while preserving cardinality.
- $\bowtie$ (Natural Join): Multiplying cardinalities of compatible tuples.
- $\cup$ (Arithmetic Union): Adding cardinalities.
- $\setminus$ (Filter Difference): Subtracting cardinalities (clamped at zero).

B. Translation Mechanisms

The paper provides rigorous algorithms for translating between the three languages:

SPARQL $\leftrightarrow$ NRMD¬:
- SPARQL to Datalog: Triple patterns become atoms; AND becomes joins; UNION becomes multiple rules; EXCEPT becomes negation; FILTER conditions are rewritten to handle 3-valued logic and errors explicitly.
- Datalog to SPARQL: Facts are encoded as RDF triples with unique identifiers to preserve duplicates; rules are translated into graph patterns using AND, UNION, and EXCEPT.
MRA $\leftrightarrow$ NRMD¬:
- Standard relational operations are mapped to Datalog rules (e.g., Join $\to$ Rule body conjunction).
- Datalog rules are mapped to algebraic expressions (e.g., Negation $\to$ Set Difference).
SPARQL $\leftrightarrow$ MRA:
- SPARQL patterns are translated into algebraic expressions using a special Comp relation to simulate the compatibility check of solution mappings (handling partial domains).
- Algebraic expressions are translated back to SPARQL patterns, using NULL triples to reconstruct variable schemas for empty results.

C. Proof of Expressive Equivalence

The central theoretical result is the Triangle of Equivalence:
$\text{SPARQL} \equiv \text{NRMD}^\neg \equiv \text{MRA}$
The authors prove that the core fragment of SPARQL (with multisets) is expressively equivalent to both Non-Recursive Multiset Datalog with Safe Negation and Multiset Relational Algebra.

4. Results

Characterization of SPARQL: The study reveals that the multiset semantics of the core SPARQL fragment is not arbitrary but corresponds precisely to a well-defined logical and algebraic structure.
Operator Coherence: Unlike SQL, which supports a chaotic variety of multiset operators (max-union, min-intersection, arithmetic difference, etc.), SPARQL's design is shown to be a coherent subset. It supports arithmetic union and filter difference but lacks max-union and min-intersection.
Handling of "Error" States: The paper successfully formalizes how SPARQL's 3-valued logic (specifically the Error state in filters) interacts with multiset cardinality, showing that standard set-algebra equivalences (like De Morgan's laws for unions) do not hold directly in bag semantics without specific rewriting.

5. Significance and Implications

Theoretical Foundation: This work provides the first rigorous algebraic and logical characterization of SPARQL's multiset semantics, bridging the gap between the semantic web (RDF/SPARQL) and classical database theory (Relational Algebra/Datalog).
Optimization Potential: By establishing equivalence with MRA and NRMD¬, the authors suggest that optimization techniques developed for Datalog (e.g., Magic Sets) and Relational Algebra (e.g., join reordering, pushdown of selections) can be adapted for SPARQL engines to improve performance on bag-based queries.
Design Guidance: The results suggest that future extensions to SPARQL should aim to maintain the coherence of its current operator set. Adding operators that fall outside this "coherent" algebraic structure (like max-union) might introduce theoretical inconsistencies or require ad-hoc handling.
Standardization: The work clarifies the behavior of EXCEPT (SetMinus) and OPTIONAL in the presence of duplicates, providing a solid basis for query optimization and equivalence checking in SPARQL 1.1 and beyond.

In summary, the paper demonstrates that SPARQL's multiset semantics, while complex, is mathematically robust and equivalent to established formalisms, offering a path toward more efficient and theoretically sound implementations of SPARQL query engines.