[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2007-15 | ||
| Submitted on | 21st of March 2007 | ||
| Author | Das Sarma, Anish; Theobald, Martin; Widom, Jennifer | ||
| Title | Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases | ||
| Date of publication | 21st of March 2007 | ||
| Citation | Das Sarma, Anish; Theobald, Martin; Widom, Jennifer. Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases, | ||
| Number of pages | 14 | ||
| Language | English | ||
| Project | Database Group | ||
| Type | Technical Report | ||
| Subject group | Query processing | ||
| Abstract | We study the problem of computing query results with confidence values in {\em ULDBs}: relational databases with {\em uncertainty} and {\em lineage}. ULDBs, which subsume {\em probabilistic databases}, offer an alternative {\em 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 {\em Trio} prototype ULDB database system. Performance characteristics and scalability of the algorithms are demonstrated through experimental results over a large synthetic dataset. | ||
| Contact address | anish@cs.stanford.edu | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]