Metraipolis › archive › dc_39b4566f70de

Provenance of HAVING Queries in Semirings with Monus — arXiv:2609.31246

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.31246
License (as archived)
CC0-1.0
Archived
2026-10-08T03:34:24.299Z
SHA-256 of the archived text
a1b680c5a4e0e0cf3162f5fe10951d7e82432e928a605a7164fbe382b67f6b05
Stable URL of this page
https://metraipolis.com/documento/dc_39b4566f70de

How to cite

Provenance of HAVING Queries in Semirings with Monus — arXiv:2609.31246 — arXiv (en), https://arxiv.org/abs/2609.31246 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_39b4566f70de (Metraipolis archive dc_39b4566f70de, sha256 a1b680c5a4e0e0cf3162f5fe10951d7e82432e928a605a7164fbe382b67f6b05)
BibTeX
@misc{dc39b4566f70de,
  title = {Provenance of HAVING Queries in Semirings with Monus — arXiv:2609.31246},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.31246},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_39b4566f70de; sha256 a1b680c5a4e0e0cf3162f5fe10951d7e82432e928a605a7164fbe382b67f6b05},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31246. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The semiring framework and its extensions form the basis of a rich collection of theoretical results and implementations for provenance tracking of database queries. Many real-world queries use aggregation and conditions on the aggregate values. Support for such queries has been proposed by introducing semimodule elements as aggregate values and formal comparisons between aggregate values as tuple annotations, which takes the approach outside the standard semiring framework. In this work, we show how to introduce a semantics for the provenance of such queries in arbitrary commutative semirings with monus (or m-semirings), without the need for additional operators. This semantics is shown to agree with the standard provenance of the aggregation-free self-join rewriting of HAVING COUNT(*) queries in semirings that are absorptive and where times distributes over monus. We derive algorithms for this semantics and implement them within the ProvSQL system, with viable performance on a real-world dataset for probabilistic query evaluation.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-28 in cs.DB).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2609.31246 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T03:11:41.435Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).