Stanford InfoLab Publication Server

Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data

Olston, C. and Widom, J. (2000) Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data. Technical Report. Stanford.

WarningThere is a more recent version of this item available.



Strict consistency of replicated data is infeasible or not required by many distributed applications, so current systems often permit stale replication, in which cached copies of data values are allowed to become out of date. Queries over cached data return an answer quickly, but the stale answer may be unboundedly imprecise. Alternatively, queries over remote master data return a precise answer, but with potentially poor performance. To bridge the gap between these two extremes, we propose a new class of replication systems called TRAPP (Tradeoff in Replication Precision and Performance). TRAPP systems give each user fine-grained control over the tradeoff between precision and performance: Caches store ranges that are guaranteed to bound the current data values, instead of storing stale exact values. Users supply a quantitative precision constraint along with each query. To answer a query, TRAPP systems automatically select a combination of locally cached bounds and exact master data stored remotely to deliver a bounded answer consisting of a range that is no wider than the specified precision constraint, that is guaranteed to contain the precise answer, and that is computed as quickly as possible. This paper defines the architecture of TRAPP replication systems and covers some mechanics of caching data ranges. It then focuses on queries with aggregation, presenting optimization algorithms for answering queries with precision constraints, and reporting on performance experiments that demonstrate the fine-grained control of the precision-performance tradeoff offered by TRAPP systems

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:TRAPP, bounded aggregation, replication
Subjects:Computer Science > Distributed Systems
Related URLs:Project Homepage
ID Code:437
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:27 Dec 2008 15:13

Available Versions of this Item

Download statistics

Repository Staff Only: item control page