10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information

Details 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information

2006-06-16

arxiv.org/abs/cs/0606075v2

Computer Science

Databases

17 pages, 24 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-389965