Open for all UnRAVeL Members: Christoph Standke: Probabilistic Query Evaluation with Bag Semantics

Friday, January 21, 2022, 10:00am

Location: Online Session

Speaker: Christoph Standke



Typically, probabilistic databases (PDBs) are probability distributions over the subsets of a finite set of facts. The problem of evaluating a query on such set-PDBs, known as probabilistic query evaluation, is well-understood for unions of conjunctive queries (UCQs): it is either in polynomial time, or #P-hard (Dalvi and Suciu, JACM 2012). However, many practical implementations of relational databases use a bag semantics that allows multiple copies of a fact. For this reason, we study the query evaluation problem over PDBs with bag semantics (bag PDBs). As we will see, this setting differs substantially from the set-version.

This talk will give an introduction to probabilistic query evaluation.

We start by reviewing the case of set-PDBs and then present current results on querying bag-PDBs. This is joint work with Martin Grohe and Peter Lindner.