Database systems often have to deal with incomplete information as the
world they model is not always complete. None of the current approaches
for representing incomplete information has satisfied the requirements
for a powerful and efficient data management system, which is the reason
why none has found application in practice. All models 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 talk I will present a decomposition-based approach to addressing
the problem of incompletely specified databases. I will 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. I will study the problems of evaluating
relational algebra queries on WSDs. I will also address the problem of
data cleaning in the context of world-set decompositions.
I will conclude with experimental results from a large census data
scenario, which show that our model allows for efficient and scalable
data processing.