PERFORMANCE ANALYSIS OF DYNAMIC FINITE VERSIONING SCHEMES - STORAGE COST VS OBSOLESCENCE

Dynamic finite versioning (DFV) schemes are an effective approach to c oncurrent transaction and query processing, where a finite number of c onsistent, but maybe slightly out-of-date, logical snapshots of the da tabase can be dynamically derived for query access. In DFV, the storag e 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 perfor mance of DFV, with emphasis on the trade-offs between the storage cost and obsolescence. We develop analytical models based on a renewal-pro cess approximation to evaluate the performance oi DFV using M greater than or equal to 2 snapshots. Asymptotic closed-form results for high query arrival rates are given for the case of two snapshots. Simulatio n is used to validate the analytical models and to evaluate the tradeo ffs between various strategies for advancing snapshots when M > 2. The results show that 1) the analytical models match closely with simulat ion; 2) both the storage cost and obsolescence are sensitive to the sn apshot-advancing strategies, especially for M > 2 snapshots; and 3) ge nerally speaking, increasing the number of snapshots demonstrates a tr ade-off between storage overhead and query obsolescence. For cases wit h skewed access or low update rates, a moderate increase in the number of snapshots beyond two can substantially reduce the obsolescence, wh ile 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 snapsh ots can be used to reduce the obsolescence to almost zero without incr easing the storage overhead.