Martin Grohe

Probabilistic Query Evaluation with Bag Semantics

2022 · arXiv (Cornell University)

We study the complexity of evaluating queries on probabilistic databases under bag semantics. We focus on self-join free conjunctive queries, and probabilistic databases where occurrences of different facts are independent, which is the natural generalization …