Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 1023-1032
Abstract
We study the problem of computing query results with confidence values in ULDBs: relational databases with uncertainty and lineage. ULDBs, which subsume probabilistic databases, offer an alternative decoupled method of computing confidence values: Instead of computing confidences during query processing, compute them afterwards based on lineage. This approach enables a wider space of query plans, and it permits selective computations when not all confidence values are needed. This paper develops a suite of algorithms and optimizations for a broad class of relational queries on ULDBs. We provide confidence computation algorithms for single data items, as well as efficient batch algorithms to compute confidences for an entire relation or database. All algorithms incorporate memoization to avoid redundant computations, and they have been implemented in the Trio prototype ULDB database system. Performance characteristics and scalability of the algorithms are demonstrated through experimental results over a large synthetic dataset.Keywords
This publication has 15 references indexed in Scilit:
- Representing and Querying Correlated Tuples in Probabilistic Databases2007
- DBNotes2005
- MYSTIQ2005
- An Annotation Management System for Relational Databases2004
- Lineage tracing for general data warehouse transformationsThe VLDB Journal, 2003
- On propagation of deletions and annotations through views2002
- Tracing the lineage of view data in a warehousing environmentACM Transactions on Database Systems, 2000
- A probabilistic relational algebra for the integration of information retrieval and database systemsACM Transactions on Information Systems, 1997
- On the representation and querying of sets of possible worldsTheoretical Computer Science, 1991
- Monte-Carlo algorithms for enumeration and reliability problems1983