Queries and materialized views on probabilistic databases

We review in this paper some recent yet fundamental results on evaluating queries over probabilistic databases. While one can see this problem as a special instance of general purpose probabilis-tic inference, we describe in this paper two key database specific techniques that significantly reduce the complexity of query evalu-ation on probabilistic databases. The first is the separation of the query and the data: we show here that by doing so, one can identify queries whose data complexity is #P-hard, and queries whose data complexity is in PTIME. The second is the aggressive use of pre-viously computed query results (materialized views): in particular, by rewriting a query in terms of views, one can reduce its complex-ity from #P-complete to PTIME. We describe a notion of a partial representation for views, show how to validated it based on the view definition, then show how to use it during query evaluation.