Databases containing uncertain or incomplete information arise naturally in many data management scenarios. 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.  I introduce World-set Decompositions (WSDs), an approach to succinctly representing sets of possible worlds that is based on relational decomposition.  WSDs on one hand allow for natural reuse of relational storage, indexing and query processing techniques and on the other, admit efficient techniques for minimizing data representations and computing factored decompositions.  I will discuss foundational results on managing and transforming WSDs and give experimental evidence that WSDs form a scalable approach to representing large amounts of incomplete information. I also cover recently developed query language and probabilistic extensions that are now becoming part of MayBMS.