Dennis G. Severance
Abstract
The representation of a collection of data in terms of its differences from some preestablished point of reference is a basic storage compaction technique which finds wide applicability. This paper describes a differential database representation which is shown to be an efficient method for storing large and volatile databases. The technique confines database modifications to a relatively small area of physical storage and as a result offers two significant operational advantages. First, because the “reference point” for the database is inherently static, it can be simply and efficiently stored. Second, since all modifications to the database are physically localized, the process of backup and the process of recovery are relatively fast and inexpensive.
- 1 BLOOM, B.H. Space/time trade-offs in hash coding with allowable errors. Comm. ACM 13, 7 (July 1970), 422-426. Google Scholar
Digital Library
- 2 BRINCH I-IANSEN, P. Operating System Principles. Prentice-Hall, Englewood Cliffs, N.J., 1973, pp. 55-131. Google ScholarDigital Library
- 3 BUCItHOLZ, W. File organization and addressing. IBM Systems J. 2 (June 1963), 80-111.Google Scholar
- 4 CHANDY, K.M., BROWNE, J.C., DISSLY, C.W., AND UHRIG, W.R. Analytic models for rollback and recovery strategies in data base systems. IEEE Trans. Software Eng. SE-I, 1 (March 1975), 100-110.Google ScholarDigital Library
- 5 DAvis, G.B. Management Information Systems: Conceptual Foundaticns, Structure and Development. McGraw-Hill, New York, 1974, p. 278. Google ScholarDigital Library
- 6 DRAKE, R.W., AND SMITH, J.L. Some techniques for file recovery. Australian Computer J. 3, 4 (Nov. 1971), 162-170.Google Scholar
- 7 IBM CORP. Introduction to IBM direct-access storage devices and organization methods GC20-1649-8. IBM Corp., White Plains, N.Y., Feb. 1974, pp. 20-33.Google Scholar
- 8 INNOVATION DATA PROCESSING INC. Fast dump restore and data set functions, user documentation. Innovation Data Processing inc., Clifton, N.J., July 1973.Google Scholar
- 9 KIN(I, P.F., AND COLLM~YER, A.J. Database sharing--an efficient mechanism for supporting concurrent processes. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 271-275.Google Scholar
- 10 KNUTH, D.E. The Art of Computer Programming, VoW. 8: Sorting and Searching. Addison~ Wesley, Reading, Mass., 1973, pp. 561-562. Google ScholarDigital Library
- 11 MAURER, W.D. An improved hash code for scatter storage. Comm. ACM 1i, 1 (Jan. 1968), 35-38. Google ScholarDigital Library
- 12 RaPPAPORT, R.L. File structure design to facilitate on-line instantaneous updating. Proc. 1975 ACM SIGMOD Conf., pp. 1-14. Google ScholarDigital Library
- 13 ROYCROFT, A.J. Techniques for handling variable length logical records on IBM direct access storage devices. Proc. FILE68 Int. Seminar on File Org., Copenhagen, 1968, pp. 701-720.Google Scholar
- 14 SXYANI, H.H. Restart and recovery in transaction-oriented information processing system. Proc. 1974 ACM SIGMOD Workshop on Data Description, Access, and Control, May 1974, pp. 351-366. Google ScholarDigital Library
- 15 SEVERANCE, D.G., AND DUItNE, R.A. Practitioner's guide to addressing algorithms. Comm. ACM I9, 6 (June 1976),314--326. Google ScholarDigital Library
- 16 TURNBURKE, V.P., JR. Sequential data processing design. IBM Sysl. J. P (March 1963), 37--48.Google Scholar
- 17 YOURDON, E. Design of On-Line Computer Systems. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 340-353,515--542. Google ScholarDigital Library
Index Terms
- Differential files: their application to the maintenance of large databases
Recommendations
A practical guide to the design of differential files for recovery of on-line databases
The concept of a differential file has previously been proposed as an efficient means of collecting database updates for on-line systems. This paper studies the problem of database backup and recovery for such systems, and presents an analytic model of ...
Differential files: their application to the maintenance of large data bases
SIGMOD '76: Proceedings of the 1976 ACM SIGMOD international conference on Management of dataThe representation of a collection of data in terms of its differences from some pre-established point of reference is a basic compaction technique which finds wide applicability. This paper describes a differential database representation which is ...
Differential Erasure Codes for Efficient Archival of Versioned Data in Cloud Storage Systems
Transactions on Large-Scale Data- and Knowledge-Centered Systems XXX - Volume 10130In this paper, we study the problem of storing an archive of versioned data in a reliable and efficient manner. The proposed technique is relevant in cloud settings, where, because of the huge volume of data to be stored, distributed scale-out storage ...
Comments