System for reconstructing prior versions of indexes using records indicating changes between successive versions of the indexes

• US 5,347,653 A
• Filed: 06/28/1991
• Issued: 09/13/1994
• Est. Priority Date: 06/28/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Flynn, Rex A., Anick, Peter G.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Harrity, Paul
• Application Number:
  US07/722,696
• Time in Patent Office: 1,173 Days
• Field of Search: 395/425, 395/600, 395/800
• US Class Current: 707/695
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method and apparatus for providing an historical perspective into a database of information objects through an efficient method and apparatus for versioning information objects stored in a database as well as an index representative of the information objects is disclosed. The latest versions of each one of the information objects and each one of the entries in the index are maintained in the database. Partial earlier versions of each one of the information objects and each one of the index entries are stored with the latest versions. The partial versions contain only sufficient information about the differences between the earlier versions and the later ones so that any earlier version may be reconstructed. Identification tags are employed as unique identifiers for each one of the plurality of information objects and for different versions of the information objects. Through the exploitation of the relative time ordering of generated identification tags, an efficient index representation and method for performing historical queries is provided.

Claims

1. A computer implemented method for versioning a database which is stored in a memory, the database including a plurality of information objects and an index representative of the plurality of information objects, the index includes a plurality of index entries, each index entry identifying at least one of the plurality of information objects, the method comprising the steps of:

(a) maintaining a latest version of each one of the plurality of information objects in the database;

(b) maintaining a latest version of each one of the plurality of index entries in the database;

(c) maintaining in the database a prior version of each one of the plurality of information objects than has been changed, each prior version of each one of the plurality of information objects that has been changed being a representation of a portion of the prior version that represents a difference between the one of the plurality of information objects in a prior state and a later version of the one of the plurality of information objects;

(d) maintaining in the database a set of change records in each one of the plurality of index entries, each change record in the set of change records corresponding to a change that, has been made to one of the plurality of information objects, each change record in the set of change records comprising an indicator identifying a type of change made, a first identification tag identifying one of the plurality of information objects affected by the change and a second identification tag representative of a time that the change occurred; and

(e) processing the set of change records to create a version of the index at a pre-selected time.

2. The method according to claim 1 wherein the step of maintaining a prior version of each one of the plurality of information objects that has been changed comprises the step of maintaining an indication for each one of the plurality of information objects to represent the prior state of the one of the plurality of information objects, the indication comprising the second identification tag representative of the time that the change occurred and at least one field including information representative of the prior state of the one of the plurality of information objects prior to the change that occurred.

3. The method according to claim 1 wherein the step of maintaining a latest version of each one of the plurality of index entries further comprises the step of storing, for each one of the plurality of index entries, a set of the first identification tags in each one of the plurality of index entries, each set of the first identification nags identifying the information objects associated with an index entry.

4. The method according to claim 3 wherein the step of maintaining a latest version of each one of the plurality of information objects further comprises the step of storing, for each one of the plurality of information objects, the second identification tag representative of a time that the latest version was stored in the database.

5. The method according to claim 4 wherein the first and second identification tags are generated by a single identification tag generation subroutine.

6. A computer implemented method for recreating a prior version of an information object and an index entry in a versioned database which is stored in a memory, the database including a plurality of information objects and an index representative of the plurality of information objects, the index includes a plurality of index entries, the method comprising the steps of:

(a) maintaining latest versions of each one of the plurality of information objects and each one of the plurality index entries in the database;

(b) maintaining in the database portions of each one of the plurality of information objects that were updated, said portions being a representation of prior versions of each one of the plurality of information objects;

(c) maintaining a set of change records in each one of the plurality of index entries, each change record in the set of change records corresponding to a change that has been made to one of the plurality of information objects, each change record in the set of change records comprising an indicator identifying a type of change made and a first identification tag identifying one of the plurality of information objects affected by the change; and

(d) generating a prior version of each one of the plurality of index entries utilizing the latest versions of each one of the plurality of index entries and the set of change records.

7. The method of claim 6 further comprising the step of generating a prior version of each one of the plurality of information objects utilizing the latest versions of each one of the plurality of information objects and the portions of each one of the respective plurality of information objects that were updated.

8. A computer implemented method for recreating a prior version of an index entry in a versioned database which is stored in a memory, the prior version corresponding to a state of the index entry at a preselected earlier time, the database including a plurality of information objects and an index representative of the plurality of information objects, the index includes a plurality of index entries, each index entry identifying at least one of the plurality of information objects, the method comprising the steps of:

(a) assigning a first identification tag to one of the plurality of information objects when one of the plurality of information objects is created, the identification tag being utilized to identify the one of the plurality of information objects;

(b) assigning a second identification tag to a modification of the one of the plurality of information objects;

(c) storing the first and second identification tags with the one of the plurality of information objects;

(d) storing a latest version of an index entry as a set of first and second identification tags, wherein each one of the first identification tags in the set corresponds to an information object associated with the index entry at a most recent time in the database; and

(e) storing change information with the index entry for use in reconstructing the prior version of the index entry at the preselected earlier time;

(f) retrieving the latest version of the index entry; and

(g) processing the change information for each index entry having a second identification tag corresponding to a time later than or equal to the preselected earlier time to apply said change information against the latest version of the index entry retrieved in step (f) until the index entry is restored to its state at the preselected earlier time.

9. A computer implemented method for versioning a database which is stored in a memory, the database includes a plurality information objects and an index representative of the plurality of information objects, the method comprising the steps of:

(a) maintaining latest versions of each one of the plurality of information objects and the index in the database, the index including entries that identify one or more of the plurality of information objects;

(b) generating a first identification tag representative of the time that a latest version of one of the plurality of information objects is added to the database;

(c) storing the first identification tag with the latest version of the one of the plurality of information objects;

(d) maintaining portions of the one of the plurality of information objects and the index related to the one of the plurality of information objects that were updated in the database as encoded representations of the updates as prior versions of the one of the plurality of information objects and the index related to the one of the plurality of information objects;

(e) generating a plurality of second identification tags representative of the prior versions of the one of the plurality of information objects;

(f) storing the second identification tags with the respective prior versions of the one of the plurality of information objects;

(g) storing the second identification tags respective prior versions of the index; and

(h) processing the stored first identification tags and stored second identification tags to create a version of the database.

10. An information retrieval system comprising:

a memory system;

a database stored in the memory system, the database comprising a plurality of information objects and an index representative of the plurality of information objects, the index comprises a plurality of index entries, the database includes;

latest versions of each one of the plurality of information objects and each one of the plurality of index entries in the database,

a prior version of an information object, the prior version of an information object stored in the memory system and including an encoded representation of a change made to the information object, and

a prior version of an index entry, the prior version of an index entry stored in the memory system and including a set of change records, each change record in the set of change records corresponding to a change that has been made to one of the plurality of information objects, each change record in the set of change records comprising an indicator identifying a type of change made, a first identification tag identifying the one of the plurality of information objects affected by the change, and a second identification tag identifying a time the change made to the one of the plurality of information objects occurred; and

processing means for processing the set of change records to create a version of the index at a pre-selected time.

11. An information retrieval system comprising:

a memory system;

a database stored in the memory system, the database comprising a plurality of information objects and an index representative of the plurality of information objects; and

a computer coupled to the memory system, the computer includes;

means for assigning a first identification tag to an information object, the first identification tag identifying a plurality of versions of the information object,

means for assigning a second identification tag to a modification of the information object,

means for storing the first and second identification tags with a version of the information object associated with the modification,

means for storing a latest version of an index entry as a set of first and second identification tags, wherein each one of the first identification tags in the set corresponds to an information object associated with the index entry at a most recent time in the database,

means for storing change information with the index entry for use in reconstructing a prior version of the set of first and second identification tags, the prior version corresponding to a state of the database at a preselected earlier time; and

means for processing said change information to reconstruct a prior version of the set of first and second identification tags.

12. A computer implemented method for indexing a database stored in a memory, the database including one or more versions of a plurality of information objects and an index for accessing the plurality of information objects, the index comprising a plurality of index entries, the method comprising the steps of:

(a) storing a latest version of each one of the plurality of index entries identifying a set of information objects belonging to the index entry at a most recent time;

(b) storing change information with each one of the plurality of index entries for recreating a plurality of prior versions of the index entry, each of the plurality of prior versions of the index entry corresponding to the set of information objects belonging to the index entry at a prior time, the change information comprising;

a first identification tag to identify an information object affected by a change to the set of information objects belonging to the index entry,

a second identification tag representing the time that the change occurred, and

an indicator to identify a type of change made; and

processing the change information to create a version of the index at a preselected time.

13. A computer implemented method for versioning a database which is stored in a memory, the database including an objects database, the objects database including a plurality of information objects, and an index database, the index database including a plurality of index entries, each index entry identifying at least one of the plurality of information objects, the method comprising the steps of:

(a) maintaining a latest version of each one of the plurality of information objects in the objects database;

(b) maintaining a latest version of each one of the plurality of index entries in the index database;

(c) maintaining in the objects database a prior version of each one of the plurality of information objects that has been changed, each prior version of each one of the plurality of information objects that has been changed being a representation of the one of the plurality of information objects in a prior state;

(d) maintaining in the index database a set of change records in each one of the plurality of index entries, each change record in the set of change records corresponding to a change that has been made to one of the plurality of information objects, each change record in the set of change records comprising an indicator identifying a type of change made, a first identification tag identifying the one of the plurality of information objects affected by the change and a second identification tag representative of a time that the change occurred; and

(e) processing the set of change records in the index database to create a version of the index database at a preselected time.