Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization, and Updating.

Guy M. Lohman, John A. Muckstadt: Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization, and Updating. ACM Trans. Database Syst. 2(3): 209-222(1977)

@article{DBLP:journals/tods/LohmanM77,
  author    = {Guy M. Lohman and
               John A. Muckstadt},
  title     = {Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization,
               and Updating},
  journal   = {ACM Trans. Database Syst.},
  volume    = {2},
  number    = {3},
  year      = {1977},
  pages     = {209-222},
  ee        = {http://doi.acm.org/10.1145/320557.320558, db/journals/tods/LohmanM77.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Many database maintenance operations are performed periodically in batches, even in real-time systems. The purpose of this paper is to present a general model for determining the optimal frequency of these batch operations. Specifically, optimal backup, checkpointing, batch updating, and reorganization policies are derived. The approach used exploits inventory parallels by seeking the optimal number of items - rather than a time interval - to trigger a batch. The Renewal Reward Theorem is used to find the average long run costs for backup, recovery, and item storage, per unit time, which is then minimized to find the optimal backup policy. This approach permits far less restrictive assumptions about the update arrival process than did previous models, as well as inclusion of storage costs for the updates. The optimal checkpointing, batch updating, and reorganization policies are shown to be special cases of this optimal backup policy. The derivation of previous results as special cases of this model, and an example, demonstrate the generality of the methodology developed.

Copyright © 1977 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

Conference Abstract

Guy M. Lohman, John A. Muckstadt: Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization, and Updating (Abstract). SIGMOD Conference 1977: 157 BibTeX

References

[1]: K. Mani Chandy, James C. Browne, Charles W. Dissly, Werner R. Uhrig: Analytic Models for Rollback and Recovery Strategies in Data Base Systems. IEEE Trans. Software Eng. 1(1): 100-110(1975) BibTeX
[2]: ...
[3]: ...
[4]: ...
[5]: ...
[6]: ...
[7]: ...
[8]: ...
[9]: ...
[10]: ...
[11]: Ben Shneiderman: Optimum Data Base Reorganization Points. Commun. ACM 16(6): 362-365(1973) BibTeX
[12]: S. Bing Yao, K. Sundar Das, Toby J. Teorey: A Dynamic Database Reorganization Algorithm. ACM Trans. Database Syst. 1(2): 159-174(1976) BibTeX
[13]: John W. Young: A First Order Approximation to the Optimal Checkpoint Interval. Commun. ACM 17(9): 530-531(1974) BibTeX
[14]: ...

Referenced by

Jaideep Srivastava, C. V. Ramamoorthy: Efficient Algorithms for Maintenance of Large Database. ICDE 1988: 402-408
Stavros Christodoulakis: Analysis of Retrieval Performance for Records and Objects Using Optical Disk Technology. ACM Trans. Database Syst. 12(2): 137-169(1987)
Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: Improving the Differential File Technique via Batch Operations for Tree Structured File Organizations. ICDE 1986: 524-532
George P. Copeland, Setrag Khoshafian, Marc G. Smith, Patrick Valduriez: Buffering Schemes for Permanent Data. ICDE 1986: 214-221
Calton Pu: On-the-Fly, Incremental, Consistent Reading of Entire Databases. VLDB 1985: 369-375
Salvatore T. March, Gary D. Scudder: On the Selection of Efficient Record Segmentations and Backup Strategies for Large Shared Databases. ACM Trans. Database Syst. 9(3): 409-438(1984)
Daniel P. Heyman: Mathematical Models of Database Degradation. ACM Trans. Database Syst. 7(4): 615-631(1982)
Don S. Batory: Optimal File Designs and Reorganization Points. ACM Trans. Database Syst. 7(1): 60-81(1982)
Houtan Aghili, Dennis G. Severance: A Practical Guide to the Design of Differential Files for Recovery of On-Line Databases. ACM Trans. Database Syst. 7(4): 540-565(1982)
Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
Joel Arditi: An Optimized Backout Mechanism for Sequential Updates. VLDB 1979: 147-154
Daniel J. Rosenkrantz: Dynamic Database Dumping. SIGMOD Conference 1978: 3-8

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]