Efficient Indexing Of Hierarchical Relational Database Records CROSS REFERENCE TO RELATED APPLICATIONS [0001] This application claims the benefit of U. S. Provisional Application No.

60/544,015, entitled"Efficient Indexing Of Hierarchical Relational database Entries", filed February 11,2004, which is incorporated by reference herein.

BACKGROUND Field of the Invention [0002] This invention relates in general to storing hierarchical data structures in relational databases, and more particularly, to efficient indexing of hierarchical data structures in relational databases.

Background Art [0003] Hierarchical data structures, such tree data structures, are commonly used to represent data. Tree data structures are made of nodes, which can contain both data to be stored and pointers to other nodes in the tree. The terms"hierarchical data structure","tree data structure"and"tree"are used interchangeably throughout this disclosure. Nodes in a tree structure are in an ancestor-child relationship. A root node is the topmost node that has no ancestor nodes. A tree structure also has leaf nodes and internal nodes. An internal node is a node that has one or more child nodes. A leaf node has no children. All children of the same node are siblings. Referring now Fig. 1, an exemplary tree data structure 160 is shown.

In Fig. 1, node"Alpha"is a root node that has the following three children:"Bravo", "Charlie", and"Juliet". Since Bravo, Charlie, and Juliet are children of the same parent, Alpha, these nodes are siblings (or'peers'). In the tree structure shown in Fig. 1, each node is identified by its unique ID (OID), the unique ID of its parent (ParentOID), and its sequential number among siblings (Peer Sequence).

[0004] It has become commonplace to represent hierarchical data structures in relational databases. An example of a relational database representation of the tree structure illustrated in Fig. 1 is shown below in Table 1.

Table 1: Database Representation of Tree Data Structure 160 OID Parent OID Peer Sequence LEVEL DATA 100 NULL 1 1 Alpha 200 100 1 2 Bravo 300 100 2 2 Charlie 400 200 1 3 Delta 600 300 1 3 Echo 500 300 2 3 Foxtrot 700 500 1 4 Golf 800 500 2 4 Hotel 900 700 1 5 India 1000 100 3 2 Juliet [0005] Table 1 stores a plurality of records. Each record is associated with a node in the tree data structure and includes a plurality of fields. An exemplary record shown in Table 1 includes a DATA field that stores data associated with a particular node in the data structure, and OID, Parent-OID, Peer-Sequence, and Level fields.

[0006] The OID field stores a unique object ID of a given node. An object ID can be any value that uniquely identifies the node. In a preferred embodiment, OID is a numeric value.

[0007] The ParentOID field stores a pointer or reference to the parent of the node.

When the node is a root node, it has no parent. In one implementation, the value of ParentOID for the root node is NULL or a null-like value, such as zero.

[0008] The Peer-Sequence field stores an index value identifying the sequential order of a node relative to its siblings. Peer-Sequence can be any value capable of being transformed into a constant-width string. In a preferred embodiment, Peer-Sequence can be any numeric value. The Peer-Sequence of the first node among siblings of the same parent can also indicate the interval by which Peer Sequence of a subsequent sibling will be incremented. For example, if the numeric Peer-Sequence value of the first sibling is"10", Peer-Sequence for each subsequent sibling node is incremented by"10".

[0009] The LEVEL field stores the sequential number of the level at which the node is located in the hierarchy. A hierarchical data structure can include any number of levels. The value of LEVEL is derived from the position of the node in the hierarchy.

[0010] The DATA field stores the value of the data associated with a given node. It could actually represent a collection of fields associated with each node.

[0011] A database user often needs to examine relationships across multiple levels of the tree hierarchy or needs to identify the next node following a given node in the hierarchy.

One of the largest drawbacks of a relational database is its inability to handle queries efficiently. For example, to answer a question like"Is India a descendant of Charlie ?" in the tree data structure shown in Fig. 1, one would have to perform a pointer chain traversal by iteratively traversing nodes in the tree data structure using a reference to the parent node.

This process involves issuing several queries or joins within one query to find out if the PARENTOID of India is the OID of Charlie, or if the PARENTOID of the PARENTOID of India is the OID of Charlie, etc. until the top of the hierarchy is reached. Below are sample SQL queries that need to be executed to perform the pointer-chain traversal of a data structure.

Now = India While (up. PARENTOID is not null) and (up. PARENTOID <> Charlie. OID) Do { select up.PARENT_OID from A_TREE now, A_TREE up where up.OID = now. PARENTOID ; up = now } If up.PARENT_OID is null, India is NOT a descendent of Charlie, otherwise it is.

[0012] This query is executed multiple times until a match is found or the root node in the tree structure is reached. To search more efficiently, one query that combines the previous queries can be issued. The problems with the above solution are that they either require an iterative series of queries of unknown length or a single complex and inefficient query.

[0013] Often, it is desirable to represent a tree data structure in a tree display similar to a computer directory tree structure, showing the hierarchy of the nodes, such as the one shown below: Alpha +Bravo ++Delta +Charlie ++Echo ++Foxtrot +++Golf ++++India +++Hotel +Juliet [0014] In this example, the'+'signs prefixing the DATA name indicate that a given node is an immediate child of the nearest preceding node in the data structure with fewer (or no)'+'signs. The existing solutions for ordering a hierarchical data structure have been left for programmers since this type of ordering cannot be accomplished with a single SQL query.

[0015] Accordingly, there is a need for a mechanism that provides for more efficient traversal of hierarchical data structures and avoids the complexities of prior art techniques.

DISCLOSURE OF THE INVENTION [0016] The above need is met by a sorting construct (TREE SORT), which is an index added to a relational database that stores hierarchical data structures. Adding the sorting construct provides for efficient use of sorting-type functions of the structured query language (SQL) to traverse among multiple levels of hierarchical data structures.

[0017] According to one embodiment of the present invention, to generate the TREE SORT construct, a hierarchical data structure is traversed, starting from the root node.

A TREE SORT value for a root node is generated by transforming a Peer-Sequence value of the root node to a left-justified string of a given width. Peer Sequence values identify a sequential order of nodes that have the same parent in a hierarchical data structure.

Peer-Sequence values are monotonically increasing among the children of the same parent.

[0018] According to an embodiment of the present invention, TREE SORT values for other nodes in tree data structure are generated as follows: Peer Sequence values for children nodes are transformed to a left-justified substring of characters of a given width, and a TREE SORT value of the parent node is prepended to the left of the generated substring of the transformed Peer Sequence value. The resulting TREE SORT value for a given node, other than the root node, includes the following components: a leading substring that represents a TREE SORT value of the parent node and the transformed Peer-Sequence value for that node. Thus, the TREE SORT value represents the chain of Peer Sequence values starting from the root node of the tree data structure and going down to the specific node.

[0019] Importantly, the generated TREE SORT values are ordered according to the same collating sequence as Peer-Sequence values. A collating sequence is an ordering system that determines whether a particular character sorts higher, lower, or the same as another. Thus, if a Peer Sequence of node A is ordered before a Peer-Sequence of the node B, the transformed value of the Peer-Sequence of node A is ordered before the transformed value of the Peer Sequence for node B.

[0020] In a preferred embodiment of the present invention, the generated TREE SORT values are of a STRING data type. As a result, the present invention advantageously uses SQL string-type functions, such as SORT (ORDER BY) and LIKE, to efficiently traverse across multiple levels of a hierarchical data structure. When a tree data structure is sorted according to a TREE SORT construct, descendant nodes of a particular node have TREE SORT values that sort after the common ancestor's TREE SORT value. This observation allows the system to execute efficient queries to, for example, identify ancestors or descendants of a given node, or the next node in the hierarchy, and yet to avoid traversing across multiple levels of a hierarchical data structure using a pointer-chain traversal.

BRIEF DESCRIPTION OF THE DRAWINGS [0021] FIGURE 1 is an exemplary hierarchical tree data structure.

[0022] FIGURE 2 is a block diagram of a system for providing efficient indexing of hierarchical data in relational databases according to an embodiment of the present invention.

[0023] FIGURE 3 is a flow diagram of the steps performed by the present invention.

[0024] The figures depict embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 1. System Architecture Overview [0025] Fig. 2 is a block diagram of system 200 for providing efficient indexing of hierarchical data in relational databases according to an embodiment of the present invention.

System 200 includes a data store 220, a sorting construct generation engine 240, and a database engine 260.

[0026] Data store 220 holds database having records. In one embodiment, when system 200 is implemented in a healthcare environment, data store 220 maintains medical records.

Data store 220 can be implemented, for example, as a relational database management system (RDMBS), and queries to the data store 220 are accomplished via SQL. An example of a relational database representation of the tree structure illustrated in Fig. 1 was shown in Table 1.

[0027] Sorting construct generation engine 240 is adapted to generate sorting constructs TREE SORT using transformed Peer-Sequence values according to an algorithm, which will be described in greater detail in the"Methods of Operation"section. Peer-Sequence values represent a sequential ordering among siblings of the node having the same parent. Briefly, the generated TREE SORT is an ordered construct of a fixed width ordered according to the same system as the transformed Peer Sequence values. In a preferred embodiment, TREE SORT construct is of a STRING data type. Using a TREE SORT construct allows system 200 to efficiently sort and retrieve data in a hierarchical data structure.

[0028] Database engine 260 is adapted to use generated TREE SORT constructs to execute efficient queries on data store 220. Operations performed by database engine 260 will be described in more detail below in the"Methods of Operation"section.

[0029] In one embodiment, engines 220,240, and 260 are implemented as modules. As used herein, the term"module"refers to computer program code adapted to provide the functionality attributed to the module. The program code is embodied in a random access memory (RAM), a read-only memory (ROM) or other media.

2. Methods of Operation Generation of TREE SORT construct [0030] As was previously described, engine 240 generates TREE SORT constructs using Peer-Sequence values. At this point, it is beneficial to describe the Peer-Sequence value and its transformed value in greater detail.

[0031] As indicated earlier, a Peer-Sequence value represents a sequential ordering of siblings of the same node. The Peer-Sequence value can be any value capable of being transformed into a fixed-length string having a given width. Peer-Sequence values are monotonically increasing among children of a given parent. A given instance of engine 240 will transform Peer Sequence into a fixed-length value that maintains the same ordering among its peers, but is of a sortable and concatenable data type. Transformed Peer Sequence values are capable of being ordered according an ordering system that determines whether a particular character sorts higher, lower, or the same as another. Such an ordering is referred to as"collating sequence". In one embodiment, transformed Peer-Sequence values are ordered according to the American Standard Code for Information Interchange (ASCII). In another embodiment, both the Peer Sequence and the transformed Peer Sequence are ASCII.

In another embodiment, transformed Peer Sequence values are ordered according to the Unicode system. As was previously described, the Peer-Sequence value of the first node among siblings of the same parent can indicate the default interval by which the Peer-Sequence value of a subsequent sibling will be incremented. For example, if the Peer Sequence of the first sibling is"10", the Peer-Sequence value for each subsequent sibling node is incremented by"10".

[0032] Referring now to Fig. 3, a flow diagram of a method for generating a TREE SORT construct is described. At this point, it is beneficial to describe properties of the TREE SORT construct. In a preferred embodiment, a TREE SORT construct is defined as a STRING data type. The STRING data type can be of a CHARACTER (CHAR) and CHARACTER VARYING (VARCHAR) data type. If TREE SORT is of a CHAR data type, a fixed number of characters are allocated for the TREE SORT field that stores a TREE SORT value. If the length of the TREE SORT value is shorter than the fixed length of the allocated TREE SORT field, in one implementation, the remaining characters of the TREE SORT value are filled, to the right of the generated value, with characters that sort before text characters and digital characters. In one implementation, the remaining characters are filled with blank characters.

[0033] In another implementation, when TREE SORT is of a VARCHAR data type, a maximum length of the TREE SORT field is specified. The length of the TREE SORT construct (LENGTH) is a product of a given width and the maximum number of levels (MAX_LEVEL) in the hierarchy. For example, if the width is 2 and the maximum number of levels is 15, the LENGTH of the TREE SORT construct is 30. Alternatively, in another implementation, if the transformed Peer-Sequence value of the root node is not included in the TREE SORT to avoid redundancy, the length of the TREE SORT construct is a product of the (MAXLEVEL-1) and width. For example, a width of 3 and a length of 120 would result in a table that could support up to 41 hierarchical levels. The width indicates the number of children that any given node can have. For example, a width of 3 indicates that a given node can have up to 999 immediate children (if each transformed Peer-Sequence value is expressed only using digit characters); a width of 2 indicates that a given node can have up to 99 children.

[0034] Continuing with the description of Fig. 3, at step 310, to generate a TREE SORT construct, the method traverses the hierarchical data structure, such as the one shown in Fig. 1, from the root node. To determine whether the node is the root node, the method determines whether the node has a parent. To this end, in one embodiment, the method determines whether the Parent JDID of the node is NULL.

[0035] In one implementation, the method converts 320 the Peer-Sequence value of the root node to a left-justified substring of characters of a given width. If TREE SORT field is defined as a CHAR data type, and the length of the transformed substring is shorter than the specified fixed length of the field, the method adds suffix padding characters that sort before text characters and digital characters when an SQL-like function is applied.

[0036] The following example will illustrate the implementation of this method. In the following example, WIDTH = 2, MAXLEVEL=5, LENGTH = WIDTH x MAXLEVEL= 2x5=10, and INTERVAL = 1. First, the root node, Alpha, is identified as the node that has no parent node. In one implementation, the ParentOID of the root node= NULL. This node is indexed by OID=100. The Peer-Sequence value for this node is"1." [0037] According to the method, in one implementation, the Peer Sequence value"1" is converted to a left-justified substring of characters of WIDTH=2. In one implementation, if the TREE SORT field is of a CHAR data type, characters that sort before text and digital characters are added to the right of the generated substring since the length of the transformed value is shorter than the fixed length (10) of the TREE SORT field. In this example, the transformed Peer Sequence string value is"01", and the generated TREE-SORT construct is "Olxxxxxxxx", wherein"x"represents a character that sorts before text and digital characters and that is being added to the transformed Peer-Sequence values to make the length of the construct equal to the fixed length of the TREE SORT field. In one implementation, "x"is a blank character (space).

[0038] The process then generates 320 TREE SORT of the children of the root node.

To this end, the process identifies nodes having their Parent-OlD equal to the OID of the root node. The process then generates the TREE SORT for the children nodes in the following manner : [0039] 1. The process converts 330 Peer-Sequence values for children nodes to a left- justified substring of characters of a given width; [0040] 2. The process then concatenates 340 the TREE SORT of the root node with the generated substring of the transformed Peer-Sequence value. The process continues 350 until TREE SORT values for all nodes in the tree are generated. In one implementation, the process uses the PREPEND function to add the TREE SORT of the root node to the left of the transformed Peer Sequence value for the child node.

[0041] Continuing with the same example, the process generates a TREE SORT for all children of that node. As shown in Fig. 1, Alpha node has the following children: Bravo, Charlie, and Juliet. The process converts the Peer-Sequence of Bravo to"01", Peer-Sequence of Charlie to"02", and Peer_Sequence of Juliet to"03." [0042] The process then prepends the TREE SORT value for Alpha (the parent node of Bravo, Charlie, and Juliet) to the left of the TREE SORT for each of these nodes. As a result, the generated TREE SORT for nodes Bravo, Charlie, and Juliet are "0101", "0102", and"0103"respectively.

[0043] Continuing with the same example, Bravo, Charlie, and Julie have their own set of children, each with its own set of Peer-Sequence values. For example, Delta is a child of Bravo. The Peer-Sequence value of Delta is "1", The transformed Peer-Sequence of Delta is"Ol". The TREE SORT of Delta is determined by prepending the TREE SORT of its immediate parent, Bravo, with the transformed value of "01". As a result, the generated TREE SORT for Delta is"010101".

[0044] Table 2 illustrates a relational database representation of the hierarchical data structure shown in Fig. 1 that includes a TREE SORT field. In Table 2, the WIDTH of the generated TREE SORT is 2. Peer-Sequence values start at 1 and have an interval of 1 for each subsequent child of a given parent.

Table 2. Relational Database Representation of a Hierarchical Data Structure After Adding TREE SORT construct OID Parent OID Peer Sequence Level TREE SORT DATA 100 none 1 1 '01' Alpha 200 100 1 2 '0101' Bravo 300 100 2 2'0102'Charlie 400 200 1 3'010101'Delta 600 300 1 3 '010201' Echo 500 300 2 3'010202'Foxtrot 700 500 1 4'01020201'Golf 800 500 2 4'01020202'Hotel 900 700 1 5'0102020101'India 1000 100 3 2'0103'Juliet [0045] Thus, as shown in Table 2, in a preferred embodiment, a TREE SORT construct of the root node (Alpha) in the hierarchical data structure includes a leading substring that represents a transformed Peer Sequence value. A TREE SORT value of the nodes other than the root node includes the following components: a leading substring that represents a TREE SORT value of the parent node, and the transformed Peer-Sequence value for that node. Thus, a TREE SORT construct for a particular node represents the chain of Peer Sequence values starting from the root of the tree structure and going down to the specific node.

[0046] Importantly, the generated TREE SORT values are ordered according to the same collating sequence as the transformed Peer Sequence values so that if Peer Sequence value A is ordered before Peer Sequence value B, the transformed value of the Peer-Sequence value A sorts before the transformed value of the Peer-Sequence value B. In a preferred embodiment of the present invention, TREE SORT values and Peer Sequence values are ordered according to the collating sequence defined by the ASCII system.

According to the ASCII collating system, smaller numeric characters are sorted before greater numeric characters; text characters are sorted in alphabetical order; and blank symbols are sorted before all numeric and text characters. One skilled in the art would understand that Peer Sequence values can be sorted according to any other system in which any subsequent value is increasing monotonically.

[0047] In other implementations, to avoid redundancy, the TREE SORT value of all the nodes omits from the TREE SORT value the string portion that would have been derived from the root node's Peer Sequence.

[0048] Since in the preferred embodiment, the generated TREE SORT values are of a STRING data type, the present invention advantageously uses SQL string-type functions, such as SORT (ORDER BY) and LIKE, to traverse across multiple levels of a hierarchical data structure. As was previously indicated, a TREE SORT value for a given node, other than a root node, includes a leading substring that represents a TREE SORT value for a parent node and the transformed Peer-Sequence value for that node. When a tree data structure is sorted according to a TREE SORT construct, descendant nodes of a particular node have a TREE SORT that sorts after the TREE SORT value of their common parent node. A node is a common parent for two child nodes if Parent-OlD for these nodes equal to OID of that parent.

[0049] The following example will illustrate the described concept. Continuing with the example illustrated in Table 2, TREE SORT of Bravo is"0101". TREE SORT of Delta (Bravo's child) is"010101. "In this example, TREE SORT values are ordered according to the collating sequence of the ASCII system. As was previously noted, TREE SORT of Delta comprises the following components: TREE SORT of Bravo"0101"and transformed Peer Sequence value of Delta"01". Similarly, TREE SORT of Juliet comprises TREE SORT of Bravo,"0101", and transformed Peer-Sequence of Juliet,"03". When an SQL SORT (ORDER BY) query is issued, the TREE SORT of Alpha ("O1") sorts before TREE SORT of Bravo,"0101", since characters that are added to the right of TREE_SORT of Alpha are sorted before numeric and text characters. Accordingly,"01"is sorted before "0101." [0050] Similarly, TREE SORT of Bravo, "0101", sorts before TREE SORT of Juliet, "010103"because characters added to TREE SORT of Bravo are sorted before numeric and text characters added to "0101." Tree Display Ordering [0051] As was previously described, often, a database user wants to produce a tree display of a hierarchical data structure. Existing solutions for accomplishing this task have been left for programmers since producing a tree display of a hierarchical data structure could not be accomplished with a single query with the given definition.

[0052] The present invention has overcome the limitations of the existing solutions by issuing a query that sorts elements of a hierarchical data structure according to TREE SORT constructs. The TREE SORT allows the following simple query to produce a tree display of a hierarchical data structure: Select Case When LEVEL = 1 Then DATA Else concat (Substring ('+++++++++', 1, LEVEL-1), DATA) End, TREE SORT From A TREE Order by TREE SORT [0053] The above query performed on the example illustrated in Table 2 will produce the following output: Alpha 01 +Bravo 0101 ++Delta 010101 +Charlie 0102 ++Echo 010201 ++Foxtrot 010202 +++Golf 01020201 ++++India 0102020101 <BR> +++Hotel'01020202'<BR> +Juliet'0103' [0054] The'+'sign prefixing the DATA indicates that a given node is a child of the preceding node with fewer or no +'signs. In the display list, descendant nodes of a given node have a TREE SORT that sorts after the TREE SORT of a common parent. Thus, descendants of Charlie, such as Golf and Hotel, sort after their common parent Foxtrot.

Examining Relationships Across Multiple Levels of a Hierarchical Data Structure [0055] To find all descendants of a target node in a hierarchical data structure, a simple query will be issued that identifies nodes having a TREE, SORT value with a leading substring that matches the TREE SORT of the target node.

[0056] For example, an efficient query to find all the descendants of Charlie (whose TREE SORT = 0102') would find all descendants having a TREE SORT with a leading substring equal to the TREE SORT value of Charlie. The following query will be issued: Select DATA from A TREE where TREE SORT like"0102%" [0057] This query produces the following output: Echo, Foxtrot, Golf, Hotel, and India.

Thus, using a TREE SORT construct to retrieve and sort data in a hierarchical data structure is advantageous over prior art solutions that would require performing a pointer-chain traversal to find all nodes having a ParentOID equal to the OID of Charlie or that of Charlie's child. Accordingly, a TREE SORT construct avoids the complexities of navigating the tree data structure.

[0058] To retrieve all ancestors of a target node in a hierarchical data structure, a simple query will be issued that identifies nodes having a TREE SORT value that match a leading substring of the target node.

[0059] To find out if a given node is descendant of a target node, a simple query will be issued to determine whether a leading substring of the TREE SORT of the given node matches the TREE SORT of the target node.

[0060] To find out if a given node is an ancestor of a target node, a simple query will be issued to determine whether the TREE SORT value of the given node matches the leading substring of the target node.

[0061] For example, find out if India a descendant of Charlie ?" using the generated TREE SORT construct, a database user needs to issue a query to find out if the TREE SORT of Charlie is the leading substring of the TREE SORT of India. An exemplary SQL query fragment is shown below: "where substring (India. TREE SORT, l, length (Charlie. TREE SORT)) = Charlie. TREE SORT" [0062] Database engine 260 executes this query as follows. Database engine 260 parses the TREE SORT value of India to identify a leading substring that starts with the first position and has the length of the Charlie's TREE SORT construct (four characters).

TREE SORT of India is 0102020101'and TREE SORT of Charlie is'0102'. The first four characters of TREE SORT of India are'0102'. Accordingly, Charlie is a direct ancestor of India. Thus, using a TREE SORT construct allows system 200 to efficiently retrieve and sort data in a hierarchical data structure thereby avoiding performing convoluted pointer- chain traversal queries.

Alternative Embodiments [0063] It should be noted that although Table 2 illustrates database representation of one hierarchical data structure, one of skill in the art would understand that multiple hierarchies can be stored in one database table. In such an implementation, a MASTEROID field is added to the table to identify nodes of a particular hierarchy within the table so that all nodes within a given hierarchy have the same ASTEROID value. Other implementations of the present invention store in a TREE SORT field only transformed Peer Sequence value of the ancestors of a particular node but omit the TREE SORT value of the root node to avoid redundancy.

[0064] To query nodes of a given tree structure identified by a unique ASTEROID from the database table that stores multiple hierarchies, database engine 260 issues the following query to select records indexed by, for example, MASTEROID=100 and ordered by TREE SORT : Select * from MANY TREES where ASTEROID = 100 order by TREE SORT [0065] To retrieve all descendants of a target node from a database table that stores multiple hierarchies, database engine 260 uses ASTEROID and the leading substring of TREE SORT of the target to obtain those results. For example, when the target node is Charlie, the following query is issued: Select * from MANY TREES where MASTER OID = 100 and TREE SORT like'0102%' [0066] In the above query,'0102%'is Charlie's TREE SORT value with the'%'the SQL string march operator tacked on. Charlie's descendants are nodes having TREE SORT values with a leading substring that matches Charlie's TREE SORT. In other words, their TREE SORT values start with the TREE SORT value of Charlie.

[0067] Thus, a TREE SORT construct is used to efficiently query data store 220 that holds database records for multiple hierarchical data structures.

Adding Nodes to the Hierarchical Data Structure [0068] According to an embodiment of the present invention, adding new nodes to a tree data structure involves creating a new OID, ParentOID, and Peer Sequence. To this end, it is desirable to set the interval for Peer-Sequence such that new sibling nodes can be added. However, if there is not enough room to add a new Peer Sequence value or the Interval=l, opening up a place for a new node involves renumbering Peer Sequence values.

The scope of this renumbering of Peer Sequence is limited to the siblings of the new node having the Peer Sequence value greater than that of the new node. The changes to the TREE SORT values involve changes to the TREE SORT for those siblings and their descendants.

XML Database Representation [0069] One application of the TREE SORT construct is for traversing XML documents. An XML document includes a plurality of elements that are organized in a hierarchical order. An element in the XML document may be associated with a value. A root element is the topmost element in the document that has no ancestor elements. An XML document also has leaf elements and internal elements. An internal element is an element that has one or more child elements. A leaf element has no children. All children of the same element are siblings.

[0070] An exemplary XML document is shown bellow.

&lt;Alpha URL="http : //www. nowhere. nohow. fake/example. xml"> <Bravo> <Delta>Hello There</Delta> &lt;/Bravo&gt; <Charlie> <Echo>Again</Echo> <Foxtrot> &lt;Golf&gt; <India>500.5</India> &lt;/Golf&gt; <Hotel>No Tell</Hotel> &lt;/Foxtrot&gt; </Charlie> &lt;Juliet&gt;&lt;/Juliet&gt; </Alpha> [0071] In the XML document shown above, Alpha, Bravo, Delta, etc. are elements.

Alpha is a root element in the hierarchy;"Bravo"and"Charlie"are children of Alpha. Thus, Bravo and Charlie are siblings. In the XML document, Delta has a value of"Hello There", and Echo has the value"Again." [0072] Referring again to Fig. 1, elements of the XML document shown above are illustrated in the hierarchical data structure shown in Fig. 1. Each element is identified by its OID, the ParentOID, Level, and the Peer-Sequence value.

[0073] The above XML document can be represented as records in a relational database. The representation of the XML document in the relational database is shown below in Table 3.

Table 3: Representation of XML Document in Relational Database OID Peer LEVEL ELEMENT ELEMENT Sequence NAME VALUE 100 1 1 Alpha 200 1 2 Bravo 300 2 2 Charlie 400 1 3 Delta Hello There 600 1 3 Echo Again 500 2 3 Foxtrot 700 1 4 Golf 800 2 4 Hotel No Tell 900 1 5 India 500. 5 1000 3 2 Juliet [0074] As shown in Table 3, each record has a plurality of fields. The DATA field has been expanded into ELEMENT NAME, ELEMENT VALUE, ATTRIBUTE NAME (not shown), ATTRIBUTE-SEQUENCE (not shown) and ATTRIBUTE_VALUE (not shown).

Other fields in the Table are the OID, the ParentOID, and Level.

[0075] According to an embodiment of the present invention, sorting construct generation engine 240 uses the Peer-Sequence value for each element in the XML document to generate TREE SORT constructs according to an algorithm described earlier. Table 4 below illustrates representation of the XML document in the database table with generated TREE SORT values.

Table 4. Representation of XML document in Relational Database with TREE SORT construct OID Peer LEVEL TREE SORT ELEMENT ELEMENT Sequence NAME VALUE 100 1 1 '01' Alpha 200 1 2'0101'Bravo 300 2 2'0102'Charlie 400 1 3 '010101'Delta Hello There 600 1 3 '010201' Echo Again 500 2 3'010202'Foxtrot 700 14'01020201'Golf 800 2 4'01020202'Hotel No Tell 900 1 5 '0102020101' India 500. 5 1000 3 2 '0103' Juliet [0076] Although in a preferred embodiment of the present invention, system 200 generates a TREE SORT construct of a string data type to benefit from string-type functions of the SQL to efficiently query hierarchical data structures represented in relational databases, a person skilled in the art would understand that a TREE SORT construct can be of any data type to benefit from the capabilities of SQL sort-type functions to efficiently query hierarchical data structures.

[0077] A person skilled in the art would understand that the present invention could be utilized with respect to any type of data. Notably, the present invention can be used in healthcare information systems. For example, the present invention can be utilized in the following aspects of the management of healthcare information systems: Evaluation and management coding. A TREE SORT construct is used to perform evaluation and management aggregation and summary of obtained findings for a patient into the complex counts and categorizations within a single query.

Chartable Item Templates. A TREE SORT construct can be used to efficiently portray and traverse hierarchical data structures and effectively use internal and external sub-trees; to portray expandable and collapsible lines in a flowsheet and to guide the interaction and charting from mini-forms for charting.

Aggregates. Using A TREE SORT construct yields an effective and easy traversal of aggregates in healthcare systems.

Clinical Notes/Documents. A TREE SORT construct is used for compact and efficient representation of composed phrases/sentences/paragraphs/sections since clinical documentation can be represented as hierarchical data structures.

Hierarchical Findings. A TREE SORT construct is used to roll-up and perform dependency determination. The TREE SORT construct allows for efficient use of hierarchical clinical context mini-trees to represent interconnected observations, and provides a bridge between post-coordination and the atomic medical event.

. Hierarchical selection lists.

A TREE SORT construct is used in general nomenclature subsets.

[0078] The present invention has been described in particular detail with respect to several possible embodiments. Those of skill in the art will appreciate that the invention may be practiced in other embodiments. First, the particular naming of the components, capitalization of terms, the attributes, data structures, or any other programming or structural aspect is not mandatory or significant, and the mechanisms that implement the invention or its features may have different names, formats, or protocols. Further, the system may be implemented via a combination of hardware and software, as described, or entirely in hardware elements. Also, the particular division of functionality between the various system components described herein is merely exemplary, and not mandatory; functions performed by a single system component may instead be performed by multiple components, and functions performed by multiple components may instead performed by a single component.

[0079] Some portions of above description present the features of the present invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. These operations, while described functionally or logically, are understood to be implemented by computer programs. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules or by functional names, without loss of generality.

[0080] Unless specifically stated otherwise as apparent from the above discussion, it is appreciated that throughout the description, discussions utilizing terms such as"processing" or"computing"or"calculating"or"determining"or"displaying"or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices.

[0081] Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by real time network operating systems.

[0082] The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored on a computer readable medium that can be accessed by the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic- optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability.

[0083] The algorithms and operations presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will be apparent to those of skill in the, along with equivalent variations. In addition, the present invention is not described with reference to any particular programming language. It is appreciated that a variety of programming languages may be used to implement the teachings of the present invention as described herein, and any references to specific languages are provided for disclosure of enablement and best mode of the present invention.

[0084] The present invention is well suited to a wide variety of computer network systems over numerous topologies. Within this field, the configuration and management of large networks comprise storage devices and computers that are communicatively coupled to dissimilar computers and storage devices over a network, such as the Internet.

Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.