  Uncertain information is commonplace in real-world data management scenarios.
The ability to represent large sets of possible instances (worlds) while
supporting efficient storage and processing is an important challenge in this
context. The recent formalism of world-set decompositions (WSDs) provides a
space-efficient representation for uncertain data that also supports scalable
processing. WSDs are complete for finite world-sets in that they can represent
any finite set of possible worlds. For possibly infinite world-sets, we show
that a natural generalization of WSDs precisely captures the expressive power
of c-tables. We then show that several important decision problems are
efficiently solvable on WSDs while they are NP-hard on c-tables. Finally, we
give a polynomial-time algorithm for factorizing WSDs, i.e. an efficient
algorithm for minimizing such representations.
