Browse Prior Art Database

Checkpointing on a Hierarchically Organized Data Base

IP.com Disclosure Number: IPCOM000044155D
Original Publication Date: 1984-Nov-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 4 page(s) / 60K

Publishing Venue

IBM

Related People

Arnold, RF: AUTHOR [+2]

Abstract

This invention relates to a method for execution of checkpointing on a hierarchically organized data base. The method steps comprise (a) maintaining a next free record counter; (b) upon modifying a given block by user action, renumbering all of the blocks in predecessor (parent) relation to the given block up to the root block; (c) writing all changed blocks to the storage system at the end of the checkpoint file (at the newly numbered locations) upon the occurrence of the checkpoint; and (d) updating the directory file to include a pointer to the just recorded group. The data base consists of nested lists containing a variable number of elements. The top of the data base is called the ROOT list which, in general, contains several list elements.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 4

Checkpointing on a Hierarchically Organized Data Base

This invention relates to a method for execution of checkpointing on a hierarchically organized data base. The method steps comprise (a) maintaining a next free record counter; (b) upon modifying a given block by user action, renumbering all of the blocks in predecessor (parent) relation to the given block up to the root block; (c) writing all changed blocks to the storage system at the end of the checkpoint file (at the newly numbered locations) upon the occurrence of the checkpoint; and (d) updating the directory file to include a pointer to the just recorded group. The data base consists of nested lists containing a variable number of elements. The top of the data base is called the ROOT list which, in general, contains several list elements. Each such list element is itself either a list of zero or more list elements, or is a primitive item (character string) which does not decompose. Each element of a list has a prefix which specifies the length of the element in bytes. For elements which are lists, the prefix length equals the combined lengths of the sub-elements of the list. For primitives, the prefix length is the length of the character string. The elements of a list are stored one after another, occupying adjacent strings of bytes, following the bytes of the list prefix, as illustrated below:

(Image Omitted)

During data base operations, new elements are added to the lists. These new elements are physically inserted in their proper position. That is, if a new list element needs to be inserted between list elements 2 and 3, then all data from list element 3 to the end are moved just enough to make space for the new element. (As will be demonstrated below, this data movement only occurs within relatively small segments of the overall data base and, hence, is not a performance factor.) As these operations proceed, the data base becomes too large to be contained entirely in main storage. To solve this problem, the following strategy is offered. An initial data base is generated and stored within the first record of a direct-access storage device (DASD) file. This file, called the CHECKPOINT FILE, is formatted to contain physical records which are all of the same length (fixed-length records). The initial data base is represented as a ROOT list containing zero sub-elements; therefore, it consists only of the length prefix. The remainder of this ROOT record is empty and is available to support the insertion of new list elements. A second DASD file, called the DIRECTORY, is formatted to contain directory records which point at records in the checkpoint file. The directory file, corresponding to the initial checkpoint file, contains two directory entries. The first entry points to the location of the record containing the ROOT list. The second entry points to the end of the checkpoint file. Since the initial data base consists of only one record, the first and second entries i...