Dichotomy for Queries with Negation in Probabilistic Databases

Dan Olteanu ( University of Oxford )

In this talk I will discuss a complexity dichotomy for exact query evaluation in probabilistic databases, where each record in the database is an independent probabilistic event. I will show that the data complexity of any relational algebra query, which has no repeating relation symbols and disjunction but may have negation, is either polynomial time or #P-hard, and the tractable queries can be recognised efficiently.

Joint work with Robert Fink.