Multiset semantics in SPARQL, Relational Algebra and Datalog
Provides a formal foundation for multiset semantics in SPARQL by aligning it with well-understood query languages, benefiting the semantic web and database communities.
The paper proves that SPARQL with AND, UNION, FILTER, EXCEPT, and SELECT under multiset semantics is expressively equivalent to multiset versions of non-recursive Datalog with safe negation and multiset relational algebra.
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.