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.

This is joint work with Robert Fink.