Svoboda | Graniru | BBC Russia | Golosameriki | Facebook

Differential files: their application to the maintenance of large databases

Editor: David K. Hsiao Authors:

Dennis G. Severance,

Guy M. LohmanAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 1, Issue 3

Pages 256 - 267

https://doi.org/10.1145/320473.320484

Published: 01 September 1976 Publication History

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.

References

[1]

BLOOM, B.H. Space/time trade-offs in hash coding with allowable errors. Comm. ACM 13, 7 (July 1970), 422-426.

Digital Library

[2]

BRINCH I-IANSEN, P. Operating System Principles. Prentice-Hall, Englewood Cliffs, N.J., 1973, pp. 55-131.

Digital Library

[3]

BUCItHOLZ, W. File organization and addressing. IBM Systems J. 2 (June 1963), 80-111.

[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.

Digital Library

[5]

DAvis, G.B. Management Information Systems: Conceptual Foundaticns, Structure and Development. McGraw-Hill, New York, 1974, p. 278.

Digital Library

[6]

DRAKE, R.W., AND SMITH, J.L. Some techniques for file recovery. Australian Computer J. 3, 4 (Nov. 1971), 162-170.

[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.

[8]

INNOVATION DATA PROCESSING INC. Fast dump restore and data set functions, user documentation. Innovation Data Processing inc., Clifton, N.J., July 1973.

[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.

[10]

KNUTH, D.E. The Art of Computer Programming, VoW. 8: Sorting and Searching. Addison~ Wesley, Reading, Mass., 1973, pp. 561-562.

Digital Library

[11]

MAURER, W.D. An improved hash code for scatter storage. Comm. ACM 1i, 1 (Jan. 1968), 35-38.

Digital Library

[12]

RaPPAPORT, R.L. File structure design to facilitate on-line instantaneous updating. Proc. 1975 ACM SIGMOD Conf., pp. 1-14.

Digital 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.

[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.

Digital Library

[15]

SEVERANCE, D.G., AND DUItNE, R.A. Practitioner's guide to addressing algorithms. Comm. ACM I9, 6 (June 1976),314--326.

Digital Library

[16]

TURNBURKE, V.P., JR. Sequential data processing design. IBM Sysl. J. P (March 1963), 37--48.

[17]

YOURDON, E. Design of On-Line Computer Systems. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 340-353,515--542.

Digital Library

Cited By

Li YWang HLiu X(2024)One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate CountingProceedings of the ACM on Management of Data10.1145/36392702:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639270
Li MWang HDai HLi MChai CGu RChen FChen ZLi SLiu QChen G(2024)A Survey of Multi-Dimensional Indexes: Past and Future TrendsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336418336:8(3635-3655)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3364183
Wang CQiao JHuang XSong SHou HJiang TRui LWang JSun J(2023)Apache IoTDB: A Time Series Database for IoT ApplicationsProceedings of the ACM on Management of Data10.1145/35897751:2(1-27)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589775
Show More Cited By

Index Terms

Differential files: their application to the maintenance of large databases
1. Information systems
  1. Data management systems
  2. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Hashed file organization
        Indexed file organization

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 data

The 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 10130

In 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

Information & Contributors

Information

Published In

ACM Transactions on Database Systems Volume 1, Issue 3

Sept. 1976

87 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/320473

Editor:
David K. Hsiao
Ohio State Univ., Columbus

Issue’s Table of Contents

Copyright © 1976 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1976

Published in TODS Volume 1, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

319
Total Citations
View Citations
1,483
Total Downloads

Downloads (Last 12 months)180
Downloads (Last 6 weeks)24

Reflects downloads up to 24 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YWang HLiu X(2024)One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate CountingProceedings of the ACM on Management of Data10.1145/36392702:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639270
Li MWang HDai HLi MChai CGu RChen FChen ZLi SLiu QChen G(2024)A Survey of Multi-Dimensional Indexes: Past and Future TrendsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336418336:8(3635-3655)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3364183
Wang CQiao JHuang XSong SHou HJiang TRui LWang JSun J(2023)Apache IoTDB: A Time Series Database for IoT ApplicationsProceedings of the ACM on Management of Data10.1145/35897751:2(1-27)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589775
Mathieu CRajaraman RYoung NYousefi AMarx D(2021)Competitive data-structure dynamizationProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458199(2269-2287)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458199
Krishna SPatel NShasha DWies T(2021)Automated Verification of Concurrent Search StructuresSynthesis Lectures on Computer Science10.2200/S01089ED1V01Y202104CSL0139:1(1-188)Online publication date: 1-Jun-2021
https://doi.org/10.2200/S01089ED1V01Y202104CSL013
Patel NKrishna SShasha DWies T(2021)Verifying concurrent multicopy search structuresProceedings of the ACM on Programming Languages10.1145/34854905:OOPSLA(1-32)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485490
Wellenzohn KPopovic LBöhlen MHelmer S(2021)Inserting Keys into the Robust Content-and-Structure (RCAS) IndexAdvances in Databases and Information Systems10.1007/978-3-030-82472-3_10(121-135)Online publication date: 24-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-82472-3_10
Ding JNathan VAlizadeh MKraska T(2020)TsunamiProceedings of the VLDB Endowment10.14778/3425879.342588014:2(74-86)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.14778/3425879.3425880
Gelli FUricchio THe XBimbo AChua T(2020)Learning Visual Elements of Images for Discovery of Brand PostsACM Transactions on Multimedia Computing, Communications, and Applications10.1145/338541316:2(1-21)Online publication date: 22-May-2020
https://dl.acm.org/doi/10.1145/3385413
Zhou ZWu QYang YSun X(2020)Region-Level Visual Consistency Verification for Large-Scale Partial-Duplicate Image SearchACM Transactions on Multimedia Computing, Communications, and Applications10.1145/338358216:2(1-25)Online publication date: 22-May-2020
https://dl.acm.org/doi/10.1145/3383582
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents