Method and structure for relationally representing database objects

This application claims the benefit of U.S. Provisional Application No. 60/129,574, filed on Apr. 16, 1999, entitled “COMPLEX DATABASE STRUCTURE”, which is incorporated herein by reference.

This application also contains copyrighted material, Copyright 1999, Clarify Inc. The copyright owner has no objection to the reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever in the copyrighted material.

The present invention relates to a relational data structure corresponding to a complex hierarchy relationship. More particularly, the present invention relates to a relational data structure corresponding to elements or database objects to provide defining simultaneous multiple hierarchies and to provide simplified location and access to nodes in a hierarchy.

Databases are well-known in the art. Typically, databases store elements or objects that contain data and contain the relationship from one object to another. The database can then be queried by conventional Structured Query Language (“SQL”) to extract information including summary information therefrom.

An example of a database structure is a tree structure, which contains zero or more nodes that are linked together in a hierarchical fashion. The topmost node has been called the root. The root could have zero or more child nodes, connected by edges or links. The root is the parent node to its children. Each child node can in turn have zero or more children of its own. Nodes sharing the same parent are called siblings. Every node in a tree has exactly one parent node (except for the root, which has none), and all nodes in the tree are descendants of the root node. These relationships have set out that there is one and only one path from the root node to any other node in the tree.

There are a number of shortcomings of such database structures. For example, in order to process a summary level information of the data at a lower child level, object A level, such structures must be iteratively processed by summarizing the data from objects in the search path. This iteration for retrieval is inefficient and cumbersome. Further, such structures shown do not allow both single parent and multiple parent hierarchies. In addition, it does not support a graph database structure.

Thus, there is a need to overcome the foregoing difficulties of such database structure.

Provided is a method of creating a relational database having a plurality of objects, each having an associated data is disclosed. A first database table having a plurality of entries, with each entry representing an object with an associated data is formed. A second database table having a plurality of entries, each entry defining a relationship between the plurality of objects is also formed. As another aspect, the present invention relates to an article of manufacture in which a computer usable medium having a computer readable program code embodied therein is configured to cause a computer to execute the foregoing.

FIG. 1 is a schematic diagram showing a complex tree-like hierarchical database structure to which the present invention can represent.

FIG. 2 is a database table showing the relationship of the database objects along with the data stored in the database table.

FIG. 3 is a block level diagram of one embodiment of the present invention.

FIG. 4 is a schematic diagram of another embodiment of the present invention.

Referring to FIG. 1 , there is shown a hierarchical type of database structure. As is shown in FIG. 1 , object A or database element A has a direct relationship to objects B, C, D. As used hereinafter, elements B, C, D will be referred to as objects. Object B has objects E and F directly related thereto. Object C is directly related to object G. Object D is directly related to object H. The database structure shown in FIG. 1 is typically termed a tree structure and has a hierarchical relationship between objects A, B, C, D, E, F, G and H. Typically, the database structure shown in FIG. 1 can represent, for example, sales data. Thus, objects E, F, G and H can represent sales information in a certain locality. Objects B, C and D may be summaries of the sales in a certain region. Object A may then be a summary of a higher order region such as a country.

The relationship of the objects A-H in the structure is shown in FIG. 2 . Each object is represented as a row in a database table 8 . In one of the columns, the object is represented by a unique number. Thus, object A is assigned the number 0, object B is assigned the number 1, etc. In another column, the objects to which the particular object in that row has a direct relationship is so indicated. Thus, object A, having the number 0, has a direct relationship with objects B, C and D having the numbers 1, 2 and 3 respectively. Similarly, object B, having the number 1, has a direct relationship with objects E and F Z with numerical identifiers of 4 and 5 respectively. Similarly, object C, bears a direct relationship to object G having a numerical identifier of 6. Last but not least is object D having a direct relationship with object H having a numerical identifier of 7. In this manner, the relationship of each of the objects to one another is defined in this particular database table. Other columns in each of the rows stores the data associated with that particular object.

Referring to FIG. 3 there is shown a schematic diagram of the relationship of the database structure to implement the method and apparatus of the present invention. A first table of members 10 has a plurality of entries. Each entry is defined, e.g. by one row and comprises a database object along with its associated data. The first table 10 has a listing of only of each object and its associated data. Thus, for the hierarchical relationship shown in FIG. 1 , the table 10 contains entries for objects A-H and their associated data.

A second table of reporting relationships 20 is constructed. The second table 20 has a plurality of entries with each entry showing each of the relationships existing in the complex hierarchical structure to which the first table 10 relates. Thus, for example, for the hierarchical structure shown in FIG. 1 , there is the following relationship between the various database objects:

Parent Child A A A B A C A D A E A F A G A H B E B F C G D H

Since there are twelve possible relationships between the database objects of FIG. 1 , twelve rows or entries are established. Each entry identifies the parent of that relationship and its associated child. Further, each entry indicates whether that relationship is a direct (“0”) or indirect (“1”) relationship. Thus for the parent-child relationships of A-B, A-C, A-D, these are direct relationships. For the parent child relationships of A-E, A-F, A-G and A-H, these are indirect relationships. Similarly, for the relationships of B-E, B-F, B-G, and B-H, these are direct relationships. In each entry is an indication of the databases structure to which this relationship represents. Thus, for example, the twelve entries relate to the hierarchical structure shown in FIG. 1 , and has the relationship of the present invention can be very flexible, the database objects shown in FIG. 1 , may be rearranged and have a different relationship. In that event, if, for example, in the second database structural relationship, object E represented by the numerical identifier 4 reports directly to object A, and if it is desired to represent that relationship, in the same table that representation can be set forth with a “Sum Obj” of “2” showing that it represents a different hierarchical structure.

A third table of hierarchy 30 is a summary of all the various possible database structural relationships to which the elements from second table 20 can be summarized. Thus, each row in the third table 30 represents a hierarchy and is a summary of the data in the rows in the second table 20 having rows identified with the identifier “1”, in the “Sum Obj” column. An identifier 2 in a row in third table 30 would summarize the relationships from those rows in which there is a column entry labeled “2” for “Sum Obj”, and would represent a different hierarchy. Thus, the first row in third table 30 is a summary of the data in which the objects have the relationship shown in FIG. 1 .

The operation of the database structure shown in FIG. 3 will now be described. First, given any node in any hierarchy, one can retrieve the nodes that report to that node with a SQL statement and executed with one round trip. Thus, if it is desired, for example, to determine the data summarized into object B at data node identified as 1, one has to do is summarize all the data in which node 1 (object B) is listed as the parent in second table 20 , retrieving the identification of the child that reports to that node and summarizing the data from the first table 10 .

Similarly, to obtain a summary of the data at node 0 or database object A, then the second table 20 is accessed and the entries in which 0 (object A) is the parent are referenced and the data is retrieved from the associated child from the first table 10 and summarize those. Therefore, retrieval of a node of the objects that report to it can be achieved by a SQL statement providing expeditious searches.

Second, an advantage of the present invention is that it allows definition of simultaneous multiple hierarchies on the database tables without having to use dedicated database relations for any of the hierarchies. As previously discussed, it is possible, for example, for the database objects shown in FIG. 1 to have the relationship shown in FIG. 1 . It is also possible for those same database objects to have a different relationship in which object E reports directly to object A. This example is shown in FIG. 3 wherein the same database objects in first database table 10 are shown in hierarchical relationship of 1 (under the “Sum Obj” column) and also the same relationship is established with a second hierarchical structure in which a 2 appears in the “Sum Obj” column. Thus, without the need to use dedicated database relationships for any of the hierarchies, one can establish simultaneous multiple hierarchies on the same database objects.

Third, with the present invention where the relationship is separate and apart from the underlying data, single parent and multiple parent hierarchies can also be defined. FIG. 1 shows a structural relationship of a single parent hierarchy. A multiple parent hierarchy would be, for example, with the structural relationship of FIG. 1 inverted in which objects E, F, G, and H are the parents and the children are B, C, D, and A. Database object B would have multiple parents reporting to both database object E and database object F. Establishing such a relationship in the database structural relationship of the present invention is simply a matter of defining the appropriate database object under the column of parent and the appropriate database object under the column of child. Such a structure would support both tree and graph type structures.

From the foregoing, it can be seen that with the relationship defined separately from the underlying data, and with the definition of each parent and child, execution of retrieval of information from the database structure is extremely efficient and fast. Moreover, for example, if the hierarchy is to change, the definition change reformats the hierarchy by modifying the second table 20 , accordingly. In contrast, in the database table 8 , one must change the database table in which the data is also present. In the present invention, where the data is separate from the relationship, data integrity during maintenance can be preserved. Further, the functions of data entry and data maintenance can be separated.

Referring to FIG. 4 there is shown yet another embodiment of the present invention. As before, a first table 10 stores each of the database objects and their associated data. A second table 20 stores each of the relationships in a parent-child definition for the hierarchy to which the database objects stored in first table 10 represents. As previously discussed, second table 20 may store relationships representing more than one complex hierarchy relationship to which the database objects of first table 10 represent. Similar to FIG. 3 , each row of a third table 30 represents a different complex hierarchy structure to which the database objects stored in the first table 10 represent.

The difference between the database structure relationship shown in FIG. 4 and that shown in FIG. 3 is that there is an intermediate fourth table 40 between the second table 20 and the third table 30 . Each row in the fourth table 40 relates to a row in the third table 30 to a row in the second table 20 . For example, in accounting, this may be termed a sub-total. Thus, for example, each row in the fourth table (“a Sub-Total”) 40 may relate a row in third table 30 (“a Grand Summary”) to the rows in the second table 20 .

In the preferred embodiment the method of the present invention is practiced by a computer operating a computer readable program stored on a computer usable medium, such as a disc drive. The pertinent portion of the method of the present invention can be practiced by the following code, written in Clarify® Basic, a language that can be executed under any of the following operating systems: Microsoft NT, Sun Solaris, HP Unix, and AIX (IBM). The relevant objects are table rollup (one row for the hierarchy description), table loc_rol_itm (all the “reports to” parent child rows), and table_inv_locatn (the objects being rolled up into this particular hierarchy). As an example, note the database relation from rollup to table_cycle_count. This allows a particular inventory cycle count to be tied to a particular rollup of inventory locations.