Multiset semantics in SPARQL, Relational Algebra and Datalog

Submitted by Daniel Hernandez on 06/05/2025 - 05:06

Tracking #: 3900-5114

This paper is currently under review
Authors: 
Renzo Angles
Claudio Gutierrez
Daniel Hernandez

Responsible editor: 
Ruben Verborgh

Submission type: 
Full Paper
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 non-recursive 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.
Full PDF Version: 
PDF icon swj3900.pdf
Previous Version: 
Multiset semantics in SPARQL, Relational Algebra and Datalog
Tags: 
Under Review