Menu:

• Homepage
• People
• Group Blog
• Publications
• Education
• DB Colloquium
• DB Lunch
• Projects
• Cayuga
• Data Privacy
• DBToaster
• Games
• Hilda
• MayBMS
• Youtopia

MayBMS - A Probabilistic Database Management System

MAIN PAGE | DOWNLOAD | PUBLICATIONS

Overview Papers

• MayBMS: A System for Managing Large Uncertain and Probabilistic Databases [pdf]
  C. Koch. Chapter 6 of Charu Aggarwal, ed., Managing and Mining Uncertain Data, Springer-Verlag, 2009.
  • This is currently the best document giving an overview of the project.

Papers on the MayBMS2 System

• MayBMS: A Probabilistic Database Management System [pdf]
  Jiewen Huang, Lyublena Antova, Christoph Koch, Dan Olteanu. Proc. SIGMOD 2009. Demo paper.

• A Compositional Framework for Complex Queries over Uncertain Data [pdf]
  M. Goetz and C. Koch. Proc. ICDT 2009.

• SPROUT: Lazy vs. Eager Query Plans for Tuple-Independent Probabilistic Databases [pdf]
  D. Olteanu, J. Huang, C. Koch. Proc. ICDE, 2009. Long paper.
  
  • This paper shows how to find query plans that are more efficient than safe plans for hierarchical queries on tuple-independent databases. The paper also introduces a special operator for efficiently processing such plans.

• Conditioning Probabilistic Databases [arXiv:0803.2212]
  C. Koch and D. Olteanu. Proc. VLDB 2008.
  
  • This paper is the first to consider the problem of conditioning a probabilistic database outside of the context of graphical models. The core contribution is an exact confidence computation algorithm that seems to perform well in practice.

• Approximating Predicates and Expressive Queries on Probabilistic Databases [pdf]
  C. Koch. Proc. PODS 2008.
  • This paper shows that queries in our expressive compositional query language can be efficiently arbitrarily closely approximated.

• Fast and Simple Relational Processing of Uncertain Data [pdf]
  L. Antova, T. Jansen, C. Koch, D. Olteanu. Proc. ICDE 2008. Best paper runner-up.
  
  • This paper presents the representation system of MayBMS2 and the efficient SQL-only evaluation of a large fragment of our query language.

Papers on the MayBMS Query Language and on APIs

• A Compositional Query Algebra for Second-Order Logic and Uncertain Databases [pdf]
  C. Koch. Proc. ICDT 2009. Technical Report arXiv:0807.4620.
  
  • This paper proves that world-set algebra, (the nonprobabilistic version of) the core of the MayBMS query language, has exactly the same expressive power as second-order logic. It also provides some useful insights into query languages for uncertain databases in general.

• On APIs for Probabilistic Databases [pdf]
  L. Antova and C. Koch. Proc. MUD 2008.
  
  • This paper studies the challenge of defining an application programming interface for probabilistic databases. This is difficult because the goal of keeping the API independent from database internals (specifically, the representation system) clashes with the desire for efficiency.

• Query language support for incomplete information in the MayBMS system (Demonstration) [pdf]
  L. Antova, C. Koch, D. Olteanu. Proc. VLDB 2007.
  
  • This was a MayBMS2 demo, but the paper focuses on the query language of MayBMS. The PODS 2008 paper is a much better reference for (the algebraic version of) the language.

• From Complete to Incomplete Information and Back [pdf]
  L. Antova, C. Koch, D. Olteanu. Proc. SIGMOD 2007.
  
  • This paper presents the nonprobabilistic version of the MayBMS query language and studies its properties.

Papers on the MayBMS1 Prototype

Note: We are currently working on the second prototype of MayBMS -- MayBMS2 -- which is based on U-relations as the representation system (see our ICDE 2008 paper). The first prototype, MayBMS1, was based on world-set decompositions (WSDs). U-relations allow for more efficient query processing than WSDs and are more succinct.

• World-set Decompositions: Expressiveness and Efficient Algorithms [arxiv 0705.4442]
  L. Antova, C. Koch, D. Olteanu. Theoretical Computer Science 403 (2-3):265-284 (2008) Preliminary version in Proc. ICDT 2007.
  
  • This paper studies the theory of world-set decompositions. Of particular interest is the factorization algorithm, which does a form of minimization of representations.

• MayBMS: Managing Incomplete Information with Probabilistic World-Set Decompositions (Demonstration) [pdf]
  L. Antova, C. Koch, D. Olteanu. Proc. ICDE 2007. Demo Paper.
  
  • This was a demo of MayBMS1. The paper is the first to discuss world-set decompositions for representing probabilistic databases.

• 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information. [pdf]
  L. Antova, C. Koch, D. Olteanu. Proc. ICDE 2007. Technical Report INFOSYS-TR-2005-4.
  
  • This paper introduces world-set decompositions, the representation formalism of MayBMS1, and studies query evaluation on these representations. World-set decompositions are based on factorizations to exploit independence and, at least in their probabilistic form, can be thought of as shallow Bayesian Networks.

Posters

• SIGMOD 2009 Demo Poster. [pdf]
  (see companion paper above)
• MayBMS: A System for Managing Large Uncertain and Probabilistic Databases. [pdf]
  L. Antova, C. Koch, D. Olteanu. Best Poster Award at Spring'08 North East DB/IR Day, Columbia University, April 18, 2008.

© 2009 Cornell University