Optimal garbage collection policies for a database with random threshold level
Takashi Satow, Kazumi Yasui, Toshio Nakagawa · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1996
Abstract When a database is updated, it is difficult to avoid divided accumulations of data in storage areas by adding and deleting them. Such divided accumulations decrease access efficiency; hence, efficient maintenance is needed to meet the requirement of high‐quality service to users. However, maintenance costs must also be kept low. However, if the operating time of a database is specified, economical and planned maintenance to guarantee that high‐quality services can be implemented. This paper considers the following stochastic model: A database is updated in accordance with a stochastic process and garbage is generated in the time between updatings, causing fragmentation in storage areas. Maintenance costs increase when accumulated garbage exceeds a threshold level. That is, to remove fragmentation from storage areas, garbage collection is made at time T or at the N‐th update. the expected cost rate of this model is obtained and optimal time T* and number N*, which minimize it, are derived. Furthermore, numerical examples are given and some discussions for these examples are presented.