Item

Abstract

Database systems often have to deal with incomplete information as the world they model is not always complete. This is a frequent case in data integration applications, scientific databases, or in scenarios where information is manually entered and constains errors or ambiguity. In the las couple of decades different formalisms have been proposed for representing incomplete information. These include, among other, the so called realtions with or-sets, tables with variables (v-tables) and conditional tables (c-tables). However, none of the current approaches for representing incomple information has satisfied the requirements for a powerful and effcient 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, as is the case for v-tables and realtions with or-sets, or the handling and processing of the data, e.g. for query evaluation, is intractable (as is the case for c-tables). In this thesis, e present a decomposition-based approach to addressing the problem of incompletely specified databases. we introduce world-set decompositions (WSDs), a space-efficient formalism for repreenting any finite set of possible worlds over relational algebra queries on WSDs. For each relational algebra operation we present an algorithm operting on WSDs. We also address the problem of data cleaning in the context of world set decompositions. We present a modified version of the existing Chase algorithm, which we use to remove inconsistent worlds in an incompletely specified database. We evaluate our techniques in a large census data scenario with data originating from the 1990 USA census and we show that data processing on WSDs is both scalable and efficient.