Metraipolis › archive › dc_02ff8f7961be

The Complexity of Computing Class Probabilities in BID Probabilistic Databases — arXiv:2609.21245

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21245
License (as archived)
CC0-1.0
Archived
2026-10-10T02:45:59.429Z
SHA-256 of the archived text
338d2199095121a2bdb43c81351d9a697bac69084300bb3f21c0ad49c7631515
Stable URL of this page
https://metraipolis.com/documento/dc_02ff8f7961be

How to cite

The Complexity of Computing Class Probabilities in BID Probabilistic Databases — arXiv:2609.21245 — arXiv (en), https://arxiv.org/abs/2609.21245 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_02ff8f7961be (Metraipolis archive dc_02ff8f7961be, sha256 338d2199095121a2bdb43c81351d9a697bac69084300bb3f21c0ad49c7631515)
BibTeX
@misc{dc02ff8f7961be,
  title = {The Complexity of Computing Class Probabilities in BID Probabilistic Databases — arXiv:2609.21245},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21245},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_02ff8f7961be; sha256 338d2199095121a2bdb43c81351d9a697bac69084300bb3f21c0ad49c7631515},
  year = {2026}
}

Archived text

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

We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the database realizes each feasible tuple type, the goal is to compute the probability of a class of worlds specified by a given tuple multiplicity vector, thus grouping together worlds with the same bag (multiset) of realized tuple types. For this problem, we prove $\#\mathsf{P}$-hardness even for very restricted and structured inputs. On the other hand, we show that it admits an FPRAS, as well as $\mathsf{XP}$-time algorithms parameterized by the number of tuple types and the treewidth of an incidence graph modeling the connections between blocks and tuples. Finally, we show that augmenting the problem with certain compatibility constraints between block realizations renders it $\#\mathsf{XLP}$- and $\#\mathsf{XALP}$-hard parameterized by pathwidth and treewidth respectively, ruling out $\mathsf{FPT}$ algorithms under standard assumptions. We leave as an open question whether this also holds in the absence of compatibility constraints.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.21245 — 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-10T02:29:42.998Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).