Hybrid database structure linking navigational fields having a hierarchial database structure to informational fields having a relational database structure

• US 5,295,261 A
• Filed: 07/27/1990
• Issued: 03/15/1994
• Est. Priority Date: 07/27/1990
• Status: Expired due to Term

• Current Assignee: Pacific Bell (AT&T, Inc.)
• Original Assignee: Pacific Bells Incorporated
• Inventors: Simonetti, Charles T.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Harrity, Paul
• Application Number:
  US07/558,618
• Time in Patent Office: 1,327 Days
• Field of Search: 395/600, 395/800, 364/419
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Improved database structure is described in which the fields of each database record are divided into two classes, navigational and informational data. The data in the navigational fields is stored in a topological map which may be viewed as a tree structure or the merger of two or more such tree structures. The informational data is preferably stored in a conventional relational database. Each leaf node in the topological map specifies a unique record in the relational database.

Claims

1. A method for converting organized data from a data record structure into a hybrid structure which allows for efficient storage and retrieval of the organized data by a digital computer, where the data record structure includes a plurality of records each divided into a plurality of fields, where each field of the plurality of fields stores data of a field type associated with the field and where the organized data in the data record structure is encompassed in the plurality of fields of the plurality of records, the method comprising the steps of:

separating the plurality of fields into navigational fields and informational fields, where geographic values encompassed in each navigational field of the data records are of a geographical class defined by the field type of said navigational field, wherein said separating step further comprises the steps of assigning to each said record of the plurality of fields a unique identifier, and adding a unique identifier field to the navigational fields and to the informational fields where each said record of said unique identifier field encompasses the unique identifier assigned to that record;

ordering said navigational fields into a plurality of distinct hierarchical data structures each comprising a plurality of node classes and links therebetween, where each said node class corresponds to a specific geographical class and each node in said node class corresponds to a distinct geographic value of said geographical class, where a node class lower in said hierarchical data structure represents a geographical class that is hierarchically subordinate to and wholly encompassed in the geographical classes represented by node classes higher in said hierarchical data structure, and where said links between said node classes indicate which geographic values listed in a lower node class are geographically encompassed in a geographic value listed in a higher node class immediately adjacent to and above said lower node class in said hierarchical data structure;

identifying among the plurality of distinct hierarchical data structures one of said distinct hierarchical data structures having at least one geographical class in common, where a distinct hierarchical data structure is one which is hierarchically independent from all other hierarchical data structures and which has at least one geographic class that is unique to that hierarchical data structure;

merging portions of said distinct hierarchical data structures having one or more geographic classes in common by linking said structures to a single node class for each said geographical class said structures have in command; and

creating for each said node class in the merged hierarchical data structure a table comprising an identifier describing the geographical class represented by the node class, an enumeration list encompassing the geographical values of said node class, and a plurality of linkage structures, where each linkage structure comprises an adjacent class identifier describing a geographical class immediately adjacent to and above said node class in said merged hierarchical data structure, and an adjacent link list, specifying for each first geographic value in said enumeration list, a second geographic value in an adjacent node class in which said first geographic value is geographically encompassed, and wherein the navigational field of a lowest geographical class includes said unique identifier thereby pointing to a corresponding one of said informational fields containing said same unique identifier.

2. The method of claim 1, wherein said step of ordering the navigational fields into a plurality of hierarchical data structures further comprises the steps of:

creating a lowest node class for each hierarchical data structure, where said lowest node class encompasses nodes representing the unique identifiers; and

linking said lowest node class to the node class lowest in the hierarchical data structure which encompasses geographic values to indicate a relationship between said geographic values and the records of said informational fields.

3. A method for converting organized data from a data record structure into a hybrid structure which allows for efficient storage and retrieval of the organized data by a digital computer, where the data record structure includes a plurality of records each divided into a plurality of fields, where each field of the plurality of fields stores data of a field type associated with the field and where the organized data in the data record structure is encompassed in the plurality of fields of the plurality of records, the method comprising the steps of:

separating the plurality of fields into navigational fields and informational fields, where values encompassed in each navigational field of the data records are of a class defined by the field type of said navigational field, wherein said separating step further comprises the steps of assigning to each said record of the plurality of fields a unique identifier, and adding a unique identifier field to the navigational fields and to the informational fields of a data record, where said unique identifier field encompasses the unique identifier assigned to that data record;

ordering said navigational fields into a plurality of distinct hierarchical data structures each comprising a plurality of node classes and links therebetween, where each said node class corresponds to a specific class of values and each node in said node class corresponds to a distinct value of said class, where a node class lower in said hierarchical data structure represents a class that is hierarchically subordinate to and wholly encompassed in the classes represented by node classes higher in said hierarchical data structure, and where said links between said node classes indicate which values listed in a lower node class are specifically related to a value listed in a higher node class immediately adjacent to and above said lower node class in said hierarchical data structure;

identifying among the plurality of distinct hierarchical data structures ones of said distinct hierarchical data structures having at least one class in common, where a distinct hierarchical data structure is one which is hierarchically independent from all other hierarchical data structures and which has at least one class that is unique to that hierarchical data structure;

merging portions of said distinct hierarchical data structures having one or more classes in common by linking said structures to a single node class for each class said structures have in common, where each said node in the merged node class represents the unique occurrence of a value encompassed in the common, yet unmerged node classes; and

creating for each said node class in the merged hierarchical data structure a table comprising an identifier describing the class represented by the node class, an enumeration list encompassing the values of said node class, and a plurality of linkage structures, where each linkage structure comprises an adjacent class identifier describing a class immediately adjacent to and above said node class in said merged hierarchical data structure, and an adjacent link list, specifying for each first value in said enumeration link, a second value in an adjacent node class to which said first value is related, and wherein the navigational field of a lowest class includes said unique identifier thereby pointing to a corresponding one of said informational fields containing said same unique identifier.

4. The method of claim 3, wherein said step of ordering the navigational fields into a plurality of hierarchical data structures further comprises the steps of:

creating a lowest node class for each hierarchical data structure, where said lowest node class encompasses nodes representing the unique identifiers; and

linking said lowest node class to the node class lowest in the hierarchical data structure which encompasses a class of specific values to indicate a relationship between said specific values and the records of said informational fields.