Data management method for representing hierarchical functional dependencies

• US 5,247,666 A
• Filed: 05/28/1991
• Issued: 09/21/1993
• Est. Priority Date: 05/28/1991
• Status: Expired due to Fees

• Current Assignee: Lia Buckwold
• Original Assignee: Fawnwood, Inc.
• Inventors: Buckwold, Jonathan Y.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US07/706,254
• Time in Patent Office: 847 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/575, 395/600, 395/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/212 with details for data modelling support

Abstract

A data management method for representing hierarchical functional dependencies. Data are modeled as assertions assigning values to attributes along a path of dependencies. Attributes are created by specifying their parents and are assigned identifiers which distinguish them from their siblings. Assertions are stored as storage sequences, which are identifiers corresponding to the attributes of a path alternating with values assigned to the attributes. Storage sequences are stored as indices of a hierarchical data structure. Application values are stored in the tree with predecessors, and deleted with dependents. Assertions are denoted by function assignments which assign values to function instances. Function instances may reference multiple values, and attributes may be created at any time. Data storage, access and deletion are efficient.

Claims

1. In a data processing system having processor means, memory means, and an executing application program that references application data comprising values of attributes, said application data stored in said memory means and accessed via said processor means,

a data management method for representing hierarchical functional dependencies of said application data, said hierarchical functional dependencies being relationship between attributes, said relationships defining, for a specified attribute, a path, a family and at most one parent, said path having as terminal attribute said specified attribute, said family being, when said specified attribute has no parent, the collection of all attributes having no parent, said family being, when said specified attribute has one parent, the collection of all attributes having said one parent,

said data management method comprising the steps of:

(a) generating a new attribute having a specified name and of a specified family,

said generating step (a) comprising the substeps of;

(a-0) storing said specified name in said memory means,

(a-1) computing a child identifier corresponding to said new attribute, said child identifier being distinct from the child identifiers corresponding to previously generated attributes of said specified family;

(a-2) storing said child identifier in said memory means;

(b) storing application data as a storage sequence,

said storage sequence comprising, in the order of a path, the child identifier and an asserted value of each attribute in said path;

(c) identifying a particular storage sequence which contains a desired particular application data by specifying the attribute of said particular application data and values of the attributes preceding said specified attribute in its path; and

(d) retrieving said particular application data from said particular storage sequence by retrieving at least a portion of said particular storage sequence for processing by said processor means.

2. The method of claim 1 wherein said values of attributes are character strings.

3. The method of claim 1 wherein said child identifier corresponding to said new attribute is a count of attributes of said specified family.

4. The method of claim 1 wherein said storing substep (a-2) stores a sequence of child identifiers corresponding to the path of said new attribute.

5. The method of claim 1 comprising the additional step of:

deleting, from said memory means, a specified storage sequence and each storage sequence sharing said specified storage sequence as a common initial sequence.

6. The method of claim 1 wherein said storage sequence comprising said child identifiers and said asserted values is a sequence of indices of a hierarchical data structure, each said child identifier and each said asserted value stored, individually, as one of said indices.

7. The method of claim 1 comprising the additional step of:

generating initial attributes by storing, in said memory means, initial storage sequences,

wherein said specified name of substep (a-0) and said child identifier of substep (a-2) are stored as values of said initial attributes.

8. In a data processing system having processor means, memory means, and an executing application program that references application data comprising values of attributes, said application data stored in said memory means and accessed via said processor means,

a data management method for representing hierarchical functional dependencies of said application data, said hierarchical functional dependencies being relationships between attributes, said relationships defining, for a specified attribute, a path, a family and at most one parent, said path having as terminal attribute said specified attribute, said family being, when said specified attribute has no parent, the collection of all attributes having no parent, said family being, when said specified attribute has one parent, the collection of all attributes having said one parent,

said data management method comprising the steps of:

(a) generating a new attribute having a specified name and of a specified family,

said generating step (a) comprising the substeps of;

(a-0) storing said specified name in said memory means,

(a-1) computing a child identifier corresponding to said new attribute, said child identifier being distinct from the child identifiers corresponding to previously generated attributes of said specified family;

(a-2) storing said child identifier in said memory means;

(b) storing application data as a storage sequence,

said storage sequence comprising an address sequence followed by one significant value,

said address sequence encoding a partial assertion,

said partial assertion having an associated path,

said partial assertion assigning to each non-terminal attribute of said associated path, an asserted value,

said address sequence comprising, in the order of said associated path, the child identifier and asserted value of each non-terminal attribute of said associated path, said one significant value being an asserted value of the terminal attribute of said associated path;

(c) identifying a particular storage sequence which contains a desired particular application data by specifying the attribute of said particular application data and values of the attributes preceding said specified attribute in its path; and

(d) retrieving said particular application data from said particular storage sequence by retrieving at least a portion of said particular storage sequence for processing by said processor means.

9. The method of claim 8 comprising the additional step of:

translating a formal expression to a storage address,

said formal expression encoding a partial assertion,

said storage address defining locations, in said memory means, of referenced values, each of said referenced values being the significant value of a storage sequence, the address sequence of said storage sequence encoding said partial assertion.

10. The method of claim 9 wherein said formal expression is a function instance,

said function instance having one name and zero or more arguments,

said name being the name of the terminal attribute of the associated path of said partial assertion,

said arguments comprising the asserted values assigned by said partial assertion.

11. The method of claim 9 comprising the additional step of:

retrieving, from said memory means, one of said referenced values located at a specified storage address.

12. The method of claim 9 comprising the additional step of:

deleting from said memory means a specified value located at a specified storage address.

13. The method cf claim 12 comprising the additional step of:

deleting from said memory means all referenced values located at a specified storage address.

14. The method of claim 9 comprising the additional step of:

inserting a specified value, into said memory means, at a specified storage address.

15. The method of claim 14 comprising the additional step of:

inserting at a specified storage address, a sequence of child identifiers corresponding to the path of a specified attribute.

16. The method of claim 15 comprising the additional step of:

inserting, at a specified storage address, a count of attributes of a specified family.

17. In a data processing system having processor means, memory means, and an executing application program that references application data comprising values of attributes, said application data stored in said memory means and accessed via said processor means,

a data management method for representing hierarchical functional dependencies of said application data, said hierarchical functional dependencies being relationships between attributes, said relationships defining, for a specified attribute, a path, a family and at most one parent, said path having as terminal attribute said specified attribute, said family being, when said specified attribute has no parent, the collection of all attributes having no parent, said family being, when said specified attribute has one parent, the collection of all attributes having said one parent,

said data management method comprising the steps of:

(a) generating a new attribute having a specified name and of a specified family,

said generating step (a) comprising the substeps of;

(a-0) storing said specified name in said memory means,

(a-1) computing a child identifier corresponding to said new attribute, said child identifier being distinct from the child identifiers corresponding to previously generated attributes of said specified family;

(a-2) storing said child identifier in said memory means;

(b) expressing application data as a function assignment,

said function assignment having one name, one significant value, and zero or more arguments,

said function assignment assigning one asserted value to each attribute of an associated path,

said name being the name of the terminal attribute of said associated path,

said significant value being said asserted value assigned to said terminal attribute,

said arguments being said asserted values assigned to the non-terminal attributes of said associated path;

(c) storing application data as a storage sequence,

said storage sequence encoding a function assignment,

said storage sequence comprising, in the order of said associated path of said function assignment, the child identifier and asserted value of each attribute in said associated path;

(d) identifying a particular storage sequence which contains a desired particular application data by specifying the attribute of said particular application data and values of the attributes preceding said specified attribute in its path;

(e) retrieving said particular application data from said particular storage sequence by retrieving at least a portion of said particular storage sequence for processing by said processor means.