Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
World-Set Decompositions: Expressiveness and Efficient Algorithms
verfasst von : Lyublena Antova, Christoph Koch, Dan Olteanu
Erschienen in: Database Theory – ICDT 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Uncertain information is commonplace in real-world data management scenarios. An important challenge in this context is the ability to represent large sets of possible instances (worlds) while supporting efficient storage and processing. 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 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.