Temporally and spatially organized database

• US 5,794,242 A
• Filed: 04/08/1997
• Issued: 08/11/1998
• Est. Priority Date: 02/07/1995
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Green, Russell J., Davies, J. Christopher, Paxton, Alan J., Whitaker, Christopher
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): RONES, CHARLES
• Application Number:
  US08/835,553
• Time in Patent Office: 490 Days
• Field of Search: 395/792, 395/618, 395/613, 395/122, 348/433, 400/223, 707/10, 707/204
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

During operation of a computer system, index records and data records of a data structure are organized in a hierarchical manner, with index records being at a higher level of the hierarchy than the data records referenced by the index records. While the data structure is manipulated, the data records are stored in a random access memory. Modifications made to the data structure are chronologically written to a disk storage in a bottom-first/top-last order of the hierarchy for persistent storage as a database. A back-up copy of the database is made by storing the data and index records of the database in a top-first/bottom-last order on a sequentially readable media. A temporal and spatial view of a portion of the database can be obtained by accessing the index records and the data records of the database or the back-up media in the top-first/bottom last order.

Claims

1. An apparatus for maintaining records of a database in a memory of a computer system, comprising:

means for generating a plurality of records temporally in a chronological order;

means for storing the plurality of records at successive addresses of the memory according to the chronological order in which the plurality of records are generated; and

means for organizing the plurality of records stored at the successive addresses into a hierarchical data structure while maintaining the chronological order of the records at the successive addresses.

2. A computerized method for maintaining records of a database in a memory of a computer system, comprising the steps of:

generating a plurality of records temporally in a chronological order;

organizing the plurality of records in a hierarchical order in a data structure; and

storing the plurality of records at successive addresses of the memory while maintaining the hierarchical order of the records, the plurality of records being stored at the successive addresses of the memory according to the chronological order in which each record is generated.

3. The method of claim 2 wherein the step of storing writes records as a plurality of segments, the segments having monotonically increasing segment numbers according to the chronological and hierarchical order of the records of the data structure, each segment being a unit of data transfer.

4. The method of claim 2 further comprising:

supplying a logical selection criteria and a time-based selection criteria, the time-based selection criteria having a first time and a chronologically later second time;

reading the data structure in a reverse chronological order beginning at the second time and ending at the first time; and

while reading the data structure in the reverse chronological order, concurrently selecting data according to the logical selection criteria in a depth-last order.

5. The method as in claim 2 wherein the data structure has levels including a bottom level and a top level, the step of organizing includes a step of associating each record with a particular one of the levels, and the step of storing proceeds in a bottom level to top level order when storing the records.

6. The method as in claim 2 further comprising the steps of:

generating modified records temporally in the chronological order, each modified record being derived from a previously generated record in the data structure;

organizing the modified records in the hierarchical order in the data structure; and

storing the modified records at other successive addresses of the memory while maintaining the hierarchical order of the modified records, the modified records being stored at the other successive addresses of the memory according to the chronological order in which each modified record is generated.

7. The method as in claim 2 further comprising the steps of:

generating a new record temporally in the chronological order;

organizing the new record in the hierarchical order in the data structure; and

storing the new record at another successive address of the memory according to the chronological order in which the new record is generated while maintaining the hierarchical order.

8. The method as in claim 2 wherein the memory is a first memory and the record stored last in the chronological order is a root record of the data structure;

and further comprising the steps of;

reading records from the first memory in a reverse chronological order, proceeding from the root record to those records coupled to the root record by a logical path; and

writing the records read from the first memory to a second memory in the reverse chronological order in which the records are read so as to produce a back-up of the data structure.

9. The method as in claim 8 further comprising:

detecting a failure of the first memory;

reading the records from the second memory in the reverse chronological order in which the records are stored in the second memory; and

storing the records read from the second memory to successive addresses of the first memory in chronological order so as to restore the data structure.

10. The method as in claim 8 further comprising:

storing a first time associated with the creation of the backup of the data structure;

modifying the data structure until a second time, the second time being relatively later than the first time;

reading an incremental portion of the data structure from the first memory in the reverse chronological order beginning at the second time and ending at the first time; and

writing the incremental portion to a third memory in the reverse chronological order to create an incremental back-up.

11. The method as in claim 10 further comprising:

detecting a failure in the first memory;

reading, in the reverse chronological order, the records from the second memory and the incremental portion from the third memory; and

writing the records read from the third memory and the incremental portion to the first memory in the chronological order to restore the data structure.