Prof. Wolfgang Gatterbauer, Carnegie Mellon University
Wednesday December 4, 2013
3:00 pm - 5317 Sennott Square
(Hosted by Panos K. Chrysanthis)
Oblivious Bounds on The Probability of Boolean Functions and The Connection To Query Ecaluation Over Probabilistic Databases
ABSTRACT
We develop upper and lower bounds for the probability of Boolean functions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. We call this approach dissociation and give an exact characterization of optimal oblivious bounds, i.e. when the new probabilities are chosen independent of the probabilities of all other variables. Our motivation comes from the weighted model counting problem (or, equivalently, the problem of computing the probability of a Boolean function), which is #P-hard in general. By performing several dissociations, one can transform a Boolean formula whose probability is difficult to compute, into one whose probability is easy to compute, and which is guaranteed to provide an upper or lower bound on the probability of the original formula by choosing appropriate probabilities for the dissociated variables. Our new bounds shed light on the connection between previous relaxation-based and model-based approximations and unify them as concrete choices in a larger design space. In the second part of the talk, we focus on the problem of query evaluation over probabilistic databases. We show how our theory allows a standard relational database management system (DBMS) to both upper and lower bound hard probabilistic queries in guaranteed polynomial time.
BIOGRAPHY OF SPEAKER
Wolfgang Gatterbauer is an Assistant Professor in the Tepper School of Business at Carnegie Mellon University. His main research interests center around uncertain and inconsistent data management, provenance models and networked data. Before joining CMU, he spent 4 years as PostDoc in the database research group of University of Washington after receiving his PhD from Vienna University of Technology, where he worked in the area of web data extraction.
PROJECT PAGE AND PAPERS:http://lapushdb.com