Multiset semantics in SPARQL, Relational Algebra and Datalog

The paper studies and determines the algebraic and logic structure of the multiset semantics of the core patterns of SPARQL formed by AND, UNION, OPTIONAL, FILTER, MINUS and SELECT. We show that it conforms a robust fragment with the same expressive power of well-known logical and relational query languages, named Datalog and Relational Algebra. Indeed, we identify and develop a logical formalism for multisets, namely non-recursive Datalog with safe negation, with the extension to multiset developed by Mumick et al., and a multiset relational algebra (projection, selection, natural join, arithmetic union and except), based on the framework defined by Dayal et al., and prove that these three formalisms have the same expressive power viewed as query languages.