|
|
|
@article{DBLP:journals/tods/Heyman82,
author = {Daniel P. Heyman},
title = {Mathematical Models of Database Degradation},
journal = {ACM Trans. Database Syst.},
volume = {7},
number = {4},
year = {1982},
pages = {615-631},
ee = {http://doi.acm.org/10.1145/319758.319771, db/journals/tods/Heyman82.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
As data are updated, the initial physical structure of a database is changed and retrieval of specific pieces of data becomes more time consuming. This phenomenon is called database degradation. In this paper two models of database degradation are described. Each model refers to a different aspect of the problem.
It is assumed that transactions are statistically independent and either add, delete, or update data. The fast model examines the time during which a block of data is filling up. The second model examines the overflows from a block of data, which essentially describes the buildup of disorganization. Analytical results are obtained for both models. In addition, several numerical examples are presented which show that the mean number of overtlows grows approximately linearly with time. This approximation is used to devise a simple formula for the optimal time to reorganize a stochastically growing database.
Copyright © 1982 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.