hide
Free keywords:
-
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.
