Metraipolis › archive › dc_5aaac01c35fc
How Can We Shrink the Family of Test Databases? Query Containment with Nulls and Comparisons — arXiv:2609.16218
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.16218
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T21:36:05.829Z
- SHA-256 of the archived text
02ec914e9ae8e9d51dafe3e24cdd2023d5cd0687f65f7c48aaeb300d31516a9b- Stable URL of this page
https://metraipolis.com/documento/dc_5aaac01c35fc
How to cite
How Can We Shrink the Family of Test Databases? Query Containment with Nulls and Comparisons — arXiv:2609.16218 — arXiv (en), https://arxiv.org/abs/2609.16218 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5aaac01c35fc (Metraipolis archive dc_5aaac01c35fc, sha256 02ec914e9ae8e9d51dafe3e24cdd2023d5cd0687f65f7c48aaeb300d31516a9b)
BibTeX
@misc{dc5aaac01c35fc,
title = {How Can We Shrink the Family of Test Databases? Query Containment with Nulls and Comparisons — arXiv:2609.16218},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.16218},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5aaac01c35fc; sha256 02ec914e9ae8e9d51dafe3e24cdd2023d5cd0687f65f7c48aaeb300d31516a9b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16218. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Query containment and equivalence drive database query optimization and rewriting. For plain conjunctive queries, both are decided by evaluating one query over a single canonical database of the other. This classical test breaks down in two settings that pervade real queries: databases with null values under SQL's three-valued semantics, and queries with order comparisons. In both, deciding containment is $\Pi_2^p$-complete, and the known characterizations replace it by an exponential family of test databases, leaving no practical route to certifying equivalence. We ask how the family of test databases can be shrunk. For conjunctive queries over databases with nulls, we shrink the family to one that is exponential only in a special set of variables, and place containment in NP when that set has constant size. For queries with comparisons, we construct canonical values that decide containment, and then shrink the family by decomposing the test into independent components and by splitting it along the order conflicts. Finally, we combine the two features, and prove that the number of test databases is fixed-parameter tractable in three local parameters of the two queries, with the null-only and comparison-only tests as special cases. Each test evaluates the containing query over a family of databases, an operation native to any database system. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DB). Categorie arXiv: Databases (cs.DB). Pagina del lavoro: https://arxiv.org/abs/2609.16218 — 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-15T21:30:45.884Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).