World-set Decompositions: Expressiveness and Efficient Algorithms

Computer Science – Databases

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

34 pages, 13 figures, extended version of ICDT'07 paper

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

World-set Decompositions: Expressiveness and Efficient Algorithms 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 World-set Decompositions: Expressiveness and Efficient Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and World-set Decompositions: Expressiveness and Efficient Algorithms will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-357992

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.