Thumbnail
Access Restriction
Subscribed

Author Das Sarma, A. ♦ Theobald, M. ♦ Widom, J.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Relational databases ♦ Query processing ♦ Database systems ♦ Space exploration ♦ Uncertainty ♦ Prototypes ♦ Scalability ♦ Cleaning ♦ Data mining
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.
Description Author affiliation: Stanford Univ., Stanford, CA (Das Sarma, A.; Theobald, M.; Widom, J.)
ISBN 9781424418367
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-04-07
Publisher Place Mexico
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 4.43 MB
Page Count 10
Starting Page 1023
Ending Page 1032


Source: IEEE Xplore Digital Library