MayBMS: A Probabilistic Database Management System
Christoph Koch, Cornell University

Databases that contain uncertain data arise naturally in many data
management scenarios, such as Web information extraction, data
cleaning, data integration, sensor data management, and scientific
databases. There are currently no scalable systems for managing and
querying such databases.  In this talk I present MayBMS, a database
management system for efficiently managing and processing large
collections of uncertain data that is currently under development at
Cornell. MayBMS is based on a clean yet expressive query language that
captures many important use cases of probabilistic databases,
including what-if queries and the conditioning of databases using new
evidence. MayBMS employs a carefully designed succinct representation
system for probabilistic databases called U-relations, which nicely
unifies various approaches to representing uncertain data, such as
c-tables, relational, in particular vertical, decomposition, and
probabilistic graphical models.  U-relations allow for the natural
reuse of mature relational storage, indexing and query processing
techniques to build scalable probabilistic database systems. In
addition to the exact processing of probabilistic database queries on
U-relations, I discuss the efficient approximation of expressive,
compositional queries on probabilistic databases.