Performance Analysis of Dynamic Finite Versioning Schemes: Storage Cost vs. Obsolescence
Journal
IEEE Transactions on Knowledge and Data Engineering
Journal Volume
8
Journal Issue
6
Pages
985-1001
Date Issued
1996
Date
1996
Author(s)
Abstract
Dynamic finite versioning (DFV) schemes are an effective approach to concurrent transaction and query processing, where a finite number of consistent, but maybe slightly out-of-date, logical snapshots of the database can be dynamically derived for query access. In DFV, the storage overhead for keeping additional versions of changed data to support the logical snapshots and the amount of obsolescence faced by queries are two major performance issues. In this paper, we analyze the performance of DFV, with emphasis on the trade-offs between the storage cost and obsolescence. We develop analytical models based on a renewal-process approximation to evaluate the performance of DFV using M ≥ 2 snapshots. Asymptotic closed-form results for high query arrival rates are given for the case of two snapshots. Simulation is used to validate the analytical models and to evaluate the trade-offs between various strategies for advancing snapshots when M > 2. The results show that 1) the analytical models match closely with simulation; 2) both the storage cost and obsolescence are sensitive to the snapshot-advancing strategies, especially for M > 2 snapshots; and 3) generally speaking, increasing the number of snapshots demonstrates a trade-off between storage overhead and query obsolescence. For cases with skewed access or low update rates, a moderate increase in the number of snapshots beyond two can substantially reduce the obsolescence, while the storage overhead may increase only slightly, or even decrease in some cases. Such a reduction in obsolescence is more significant as the coefficient of variation of the query length distribution becomes larger. Moreover, for very low update rates, a large number of snapshots can be used to reduce the obsolescence to almost zero without increasing the storage overhead. ©1996 IEEE.
Subjects
Analytical modeling; Concurrent transaction and query processing; Dynamic finite versioning; Multiple versions; Renewal process; Transaction processing; Two-moment approximation
Other Subjects
Approximation theory; Computer simulation; Concurrency control; Data processing; Decision support systems; Mathematical models; Concurrent transaction; Dynamic finite versioning; Multiple versions; Query processing; Renewal process; Transaction processing; Two moment approximation; Database systems
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
08.pdf
Size
1.98 MB
Format
Adobe PDF
Checksum
(MD5):ea27804bb194be7e286159674f4f4eae