Abstract

Christoph Koch: Managing large amounts of incomplete information

In this talk I will discuss some of the issues involved in managing large sets of uncertain data. I will focus on the view of incomplete information as sets of possible worlds, but will also briefly address models of probabilistic databases. Most of the talk will address so-called _representation_systems_ for relational database query languages, and will look at how to get them to scale. I will present our own recent notion of _world-set_decompositions_ and their query evaluation and minimization problems, and will compare them to previous approaches such as c-tables and Trio. I will present both foundational results on WSDs and give experimental evidence that these form a scalable approach to representing large amounts of incomplete information.