  Current systems and formalisms for representing incomplete information
generally suffer from at least one of two weaknesses. Either they are not
strong enough for representing results of simple queries, or the handling and
processing of the data, e.g. for query evaluation, is intractable.
  In this paper, we present a decomposition-based approach to addressing this
problem. We introduce world-set decompositions (WSDs), a space-efficient
formalism for representing any finite set of possible worlds over relational
databases. WSDs are therefore a strong representation system for any relational
query language. We study the problem of efficiently evaluating relational
algebra queries on sets of worlds represented by WSDs. We also evaluate our
technique experimentally in a large census data scenario and show that it is
both scalable and efficient.
