Distributed object computer system with hierarchical name space versioning

• US 5,897,636 A
• Filed: 07/11/1996
• Issued: 04/27/1999
• Est. Priority Date: 07/11/1996
• Status: Expired due to Term

• Current Assignee: Tantau Software, Inc. (Constellation Software Incorporated)
• Original Assignee: Tandem
• Inventors: Kaeser, Reto
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/678,791
• Time in Patent Office: 1,020 Days
• Field of Search: 707/10, 707/100, 707/103, 707/8, 707/200, 707/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention is a method and apparatus for providing a hierarchical networked database which supports multiple versions of the same underlying data. Structurally, the present invention is based on hierarchical tree-like structure known which includes one or more nodes connected by labeled branches. Any node in the tree may be reached by specifying a sequence of names which correspond to the branch labels between the root node and the desired node. The root node contains one or more name/attribute pairs which define an initial revision. Each descendent node inherits the revision defined by its ancestors and forms a new revision by including the changed name/attribute pairs which differ from the inherited revision. In this way, a particular revision is defined to be the changed name/attribute pairs contained in a node and the most recent instance of each unchanged name/attribute pair contained in the node'"'"'s ancestors.

Claims

1. A method for providing a hierarchical networked database which supports multiple versions of the same underlying data, the method comprising the steps of:

providing one or more name/attribute pairs, the name/attribute pairs defining an initial version;

storing the name/attribute pairs of the initial version in the root node of a tree-like data structure;

creating one or more revisions to the initial version, each revision including one or more changed name/attribute pairs;

storing the changed name/attribute pairs of each revision in a separate node; and

storing each node in the tree-like data structure as a descendent of the root node.

2. A method as recited in claim 1 further comprising the steps of:

choosing a node in the tree-like data structure;

making a revision to the name/attribute pairs contained in the node and its ancestors, the revision including one or more changed name/attribute pairs;

storing the changed name/attribute pairs of the revision in a node; and

storing the node in the tree-like data structure as a descendent of the node.

3. A method as recited in claim 2 further comprising the steps of:

choosing a second node in the tree-like data structure; and

associating a variant with the second node, a variant being a symbolic name.

4. A method as recited in claim 2 further comprising the steps of:

choosing a second node in the tree-like data structure, the second chosen node being associated with a variant, the second chosen node having one or more descendent nodes;

removing the association between the second chosen node and the variant;

associating the variant with a third chosen node in the tree-like data structure; and

re-linking each descendent node of the second chosen node to be a descendent node of the third chosen node.

5. A method as recited in claim 2 further comprising the steps of:

choosing a second node in the tree-like data structure;

creating a revision chain list, the revision chain list being a linked list which includes, in order, the second chosen node and each ancestor of the second chosen node.

6. A method as recited in claim 5 further comprising the step of providing the contents of a revision by traversing the revision chain list and returning the first instance of each name/attribute pair contained in a node in the revision chain list.

7. An apparatus for manipulating a hierarchical networked database which supports multiple versions of the same underlying data, the apparatus comprising:

a first computer executable means for creating the root node of a tree-like data structure, the root node containing one or more name/attribute pairs defining an initial revision;

a second computer executable means for creating one or more descended nodes, each descendent node inheriting the revision associated with the parent of the descendent node, each descendent node containing one or more changed name/attribute pairs, the changed name/attribute pairs contained in each node in combination with the revision inherited by the descendent node defining a new revision associated with the descendent node.

8. An apparatus as recited in claim 7 which further comprises a third computer executable means for associating a variant with a chosen node in the tree-like data structure.

9. An apparatus as recited in claim 8 which further comprises:

a fourth computer executable means for removing the association between the variant and the chosen node, and associating the variant with a second chosen node in the tree-like data structure; and

a fifth computer executable means for re-linking each descendent node of the chosen node to be a descendent node of the second chosen node.

10. An apparatus as recited in claim 9 which further comprises a sixth computer executable means for creating a revision chain list, the revision chain list being a linked list which includes, in order, a chosen node and each ancestor of the chosen node.

11. An apparatus as recited in claim 10 which further comprises a seventh computer executable means for providing the contents of a revision by traversing the revision chain list and returning the first instance of each name/attribute pair contained in a node in the revision chain list.