Computing class probabilities in complex probabilistic databases is hard
The Complexity of Computing Class Probabilities in BID Probabilistic Databases
Data Structures and Algorithms
Summary
The paper studies how hard it is to calculate the chance of certain combinations of data appearing together in a special kind of uncertain database called a BID probabilistic database. The authors show that even in simple cases, this calculation is very difficult (#P-hard). However, they also present some ways to approximate the answer or solve it efficiently when the data follows certain patterns. Adding extra rules about how data blocks can combine makes the problem even harder and rules out fast exact solutions under common assumptions.
What this means in practice
- •For database engineers: Understand limits on exact probability computations in BID database query optimization under independence assumptions.
- •For probabilistic modelers: Use approximation schemes and parameterized algorithms to estimate class probabilities when exact computation is infeasible.
A theory result. No direct application yet.
Authors
Sotiris Kanellopoulos, Ioannis Koutras, Aris Pagourtzis
Abstract
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.