Multiset semantics in SPARQL, Relational Algebra and Datalog
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914524226912256 |
|---|---|
| author | Angles, Renzo Gutierrez, Claudio Hernández, Daniel |
| author_facet | Angles, Renzo Gutierrez, Claudio Hernández, Daniel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00417 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Multiset semantics in SPARQL, Relational Algebra and Datalog Angles, Renzo Gutierrez, Claudio Hernández, Daniel Databases Logic in Computer Science 68P15, 68N17 H.2.3; F.4.1; H.2.4 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. |
| title | Multiset semantics in SPARQL, Relational Algebra and Datalog |
| topic | Databases Logic in Computer Science 68P15, 68N17 H.2.3; F.4.1; H.2.4 |
| url | https://arxiv.org/abs/2605.00417 |