Maintaining databases by means of hierarchical genealogical table

• US 5,467,471 A
• Filed: 03/10/1993
• Issued: 11/14/1995
• Est. Priority Date: 03/10/1993
• Status: Expired due to Fees

• Current Assignee: Dpc&C Incorporated
• Original Assignee: Dpc&C Incorporated
• Inventors: Bader, David A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US08/029,268
• Time in Patent Office: 979 Days
• Field of Search: 395/600, 395/700, 395/500, 395/425, 364/419.07
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

The present invention describes a system and method for maintaining databases. An ordered genealogy table is provided for implying hierarchical relations on an as-needed basis. The invention further provides relational search capabilities to a hierarchical database. The invention also allows a database that is maintained on a computer system in a hierarchical structure to be converted into a database that is maintained in a relational structure, and vice versa. In addition, the invention may be used with currently existing hierarchical and relational databases. The invention provides a plurality of records; a unique identifier for each of the records; a database for maintaining the records; and a table which contains one or more table entries, wherein each table entry contains a genealogy including the unique identifier of a particular record and the unique identifiers of any records that can be considered ancestors of that particular record in a hierarchy, and wherein the table entries are sorted in collating sequence according to their genealogies.

Claims

1. A system for maintaining a database in a computer, comprising:

a. a plurality of records maintained in a database;

b. a table creater configured to arrange a subset of the plurality of records into an hierarchical table;

c. each record in the table having a unique identifier and a plurality of pointers configured to point to adjacent records in the hierarchical table; and

d. an indexer configured to point to at least one unique identifier in the table.

2. The system of claim 1, wherein the pointers further comprise at least one of:

a. an owner pointer configured to point to a parent record in an immediately higher level in the hierarchical table, and records in a highest level of the hierarchical table having no owner pointer; and

b. a subordinate pointer configured to point to a subordinate record in an immediately lower level in the hierarchical table, and records in a lowest level of the hierarchical table having no subordinate pointer.

3. The system of claim 1, wherein the pointers further comprise at least one of:

a. a next record pointer configured to point to a next record in a same level of the record'"'"'s hierarchical table and a record being alone in the level having the next record pointer point to itself; and

b. a previous record pointer configured to point to a previous record in a same level of the record'"'"'s hierarchical table, and a record being alone in the level having the previous record pointer point to itself.

4. The system of claim 1, wherein the pointers further comprise a first record pointer configured to point to a first record in a same level of the record'"'"'s hierarchical table, and a record being alone in the level having the first record pointer point to itself.

5. The system of claim 1, wherein the indexer is configured to selectively point to at least one record based on a selected keyword.

6. A method for searching records maintained in a computer database, comprising the steps of:

a. hierarchically arranging an ordered genealogy including records in the database meeting a criteria of a user selected search;

b. creating an array comprising all records satisfying the criteria and genealogical families of said records, the array indicating which records satisfy the criteria;

c. comparing a current genealogical family in the array with an immediate prior genealogical family in the array;

d. determining if an inequality exists between the current and prior families;

e. if an inequality is determined to exist, performing a correcting routine;

f. if either one of (i) no inequality exists and (ii) the correcting routine is completed, continuing the steps of comparing and determining until all records in the array are checked; and

g. identifying all records satisfying the search.

7. The method of claim 6, wherein the step of creating an ordered genealogy table further comprises the steps of:

a. searching the database for a record satisfying the criteria;

b. retrieving a record meeting the criteria;

c. constructing a genealogical entry for the retrieved record;

d. inserting the genealogical entry into the table;

e. continuing searching if all records have not been searched; and

f. repeating steps a through e until the database has been searched for all criteria of the search.

8. The method of claim 6, wherein the step of creating an array further includes a first step of initializing the array to indicate that no record satisfies the criteria.

9. The method of claim 6, wherein the step of creating an array further includes indicating that all records subordinate to the record satisfying the criteria also satisfy the criteria.

10. The method of claim 6, wherein the step of determining if an inequality exists includes determining if an inequality exists in at least one of (i) a search criteria number and (ii) a record identifier.

11. The method of claim 6, wherein the step of performing the correcting routine further comprises the steps of:

a performing breaking logic on the family;

b. then performing clearing logic on the family;

c. then performing propagation logic on the family; and

d. then performing a set process on the family.

12. The method of claim 11, wherein the array is arranged in a plurality of columns and the step of performing the breaking logic further comprises applying Boolean logic of the search on each column of the array to determine an entry satisfying all criteria of the search.

13. The method of claim 11, wherein the step of performing the clearing logic comprises the steps of:

a. determining a record in the current family where a point of difference from the prior family occurs;

b. setting the record where the point of difference occurs to indicate that the criteria is not satisfied; and

c. setting all records in the family subordinate to the record where the point of difference occurs to indicate that the criteria is not satisfied.

14. The method of claim 11, wherein the step of performing the propagation logic further comprises:

a. doing nothing if either one of (i) a point of difference occurs at a highest level of the current family and (ii) no point of difference exists between the current and prior families, otherwise;

b. determining in the current genealogical family a level immediately above the level at which the point of difference occurs;

c. determining if the record in the level immediately above satisfies the criteria;

d. if the record satisfies the criteria setting all subordinate levels in the family to indicate that the criteria is satisfied; and

e. if the record does not satisfy the criteria, setting all subordinate levels in the family to indicate that the criteria is not satisfied.

15. The method of claim 11, wherein the set process comprises setting a record at a lowest level in the current family and all subordinate levels in the family to indicate that the criteria is satisfied.