Fall 2016

A Dichotomy for Queries with Negation in Probabilistic Databases

Wednesday, Oct. 5, 2016 10:00 am10:40 am

Add to Calendar


Calvin Lab Auditorium

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.