Metraipolis › archive › dc_f98bfc10760e

Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics — arXiv:2609.09978

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.09978
License (as archived)
CC0-1.0
Archived
2026-10-16T11:15:42.654Z
SHA-256 of the archived text
279472b8ffc11376ff6041079722b137daff2f527f55f29a28bf82f3bcd82405
Stable URL of this page
https://metraipolis.com/documento/dc_f98bfc10760e

How to cite

Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics — arXiv:2609.09978 — arXiv (en), https://arxiv.org/abs/2609.09978 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f98bfc10760e (Metraipolis archive dc_f98bfc10760e, sha256 279472b8ffc11376ff6041079722b137daff2f527f55f29a28bf82f3bcd82405)
BibTeX
@misc{dcf98bfc10760e,
  title = {Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics — arXiv:2609.09978},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09978},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f98bfc10760e; sha256 279472b8ffc11376ff6041079722b137daff2f527f55f29a28bf82f3bcd82405},
  year = {2026}
}

Archived text

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

Bounded SQL equivalence checkers search for a counter-example database of bounded size, and a search that comes back empty proves nothing. We supply missing theory: computable bounds $B$ such that agreement on all databases with at most $B$ tuples per relation implies equivalence. We work in the combined-semantics framework, which captures SQL's mix of duplicate-eliminating (DISTINCT) and duplicate-preserving computation over set-valued relations. For conjunctive queries we prove a bound linear in the query size for fixed multiset width: inequivalent queries already disagree on a database with at most $2^w |Q|$ tuples, where the width $w$ counts only the columns the queries actually read, independently of the total number of multiset variables. Declared keys shrink the bound to $2^{kw} |Q|$ for the smaller key-width $kw$, acyclic foreign keys leave it unchanged, and the result extends to several classes of queries with comparisons, for which equivalence had not previously been characterized. For these fragments, bounded search becomes a terminating, complete decision procedure.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-10 in cs.DB).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2609.09978 — 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-16T10:53:25.630Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).