Multiset semantics in SPARQL, Relational Algebra and Datalog

Tracking #: 3678-4892

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

Responsible editor: 
Ruben Verborgh

Submission type: 
Full Paper
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.
Full PDF Version: 
Under Review