# US 7,412,444 B2 · Efficient indexing of hierarchical relational database records > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,412,444 B2 - Document ID: US7412444B2 - Status: Granted - Kind: B2 - Application number: 11/056,379 - Filed: 2005-02-10 - Published: 2005-09-08 - Granted: 2008-08-12 - Earliest claimed: 2004-02-11 - Assignees: IDX Systems Corporation - Inventors: Mark Gaponoff - Web page: https://patentgrep.com/patent/US7412444B2 ## CPC - G06F 16/2246: {Trees, e.g. B+trees} - Y10S 707/99935: Query augmenting and refining, e.g. inexact access - Y10S 707/99936: Pattern matching access - Y10S 707/99937: Sorting - Y10S 707/99938: Concurrency, e.g. lock management in shared database - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract According to various embodiments, systems, and methods, a sorting construct (TREE_SORT) is generated to efficiently traverse hierarchical data structures in relational databases. A TREE_SORT construct is generated by transforming a value that represents the sequential order of a given node relative to its siblings (Peer_Sequence) to a left-justified string of a given width. A TREE_SORT value for the parent of a given node is prepended to the left of the generated substring of the transformed Peer_Sequence value. As a result, a sorting construct of the parent node sorts before sorting constructs of child nodes. ## Claims ### Claim 1 A computer-implemented method for efficiently indexing a hierarchical data structure stored in a database, the method comprising: creating an instance of a database in which elements of a hierarchical data structure are in an ancestor-descendant relationship and an element is indexed by a peer sequence value that identifies sequential ordering of elements having a same parent; transforming the peer sequence value for a parent element into a sorting construct of a given width to generate the sorting tree construct of the parent element, wherein the sorting tree construct maintains the sequential ordering of the elements having the same parent; transforming the peer sequence value of a child element into a sorting construct of the given width, wherein the sorting construct of the child element maintains the sequential ordering of the child elements having the same parent; and prepending the sorting tree construct of the parent element to the left of the transformed peer sequence value of the child element to generate a sorting tree construct of the child element, wherein the peer sequence values and the sorting constructs are ordered according to the same collating sequence. ### Claim 2 (depends on 1) The method of claim 1, wherein peer sequence values are ordered according to the ASCII system. ### Claim 3 (depends on 1) The method of claim 1, wherein peer sequence values are ordered according to the Unicode system. ### Claim 4 (depends on 1) The method of claim 1, wherein the sorting construct is of a string data type. ### Claim 5 (depends on 1) The method of claim 1, further comprising adding characters to the sorting construct of a parent element, the added characters are sorted before text characters and digital characters. ### Claim 6 (depends on 1) The method of claim 1, wherein multiple hierarchical data structures are stored in the database. ### Claim 7 (depends on 1) The method of claim 1, wherein the hierarchical data structure describes an XML document. ### Claim 8 (depends on 1) The method of claim 1, wherein the length of the sorting construct is a function of a given width of the sorting construct and a maximum number of levels in the hierarchical data structure. ### Claim 9 (depends on 1) The method of claim 1, wherein peer sequence values are monotonically increasing among children of the same parent element. ### Claim 10 A system for efficiently indexing a hierarchical data structure in a database, the system comprises: the database contained on a computer readable storage medium for storing a hierarchical data structure, wherein elements in the hierarchical data structure are in a parent-child relationship, wherein each child element is indexed by a peer sequence value that identifies sequential ordering of child elements having a same parent element; a sorting construct generation module contained on the computer readable storage medium for performing the steps of: transforming a peer sequence value for a parent element into a sorting construct of a given width to generate a sorting tree construct of the parent element, wherein the sorting tree construct maintains the sequential ordering of elements having the same parent, transforming a peer sequence value of a child element into a sorting construct of the given width, wherein the sorting construct of the child element maintains the sequential ordering of the child elements having the same parent, and prepending the sorting tree construct of the parent element to the transformed peer sequence value of the child element to generate a sorting tree construct of the child element, wherein the peer sequence values and the sorting constructs are ordered according to the same collating sequence. ### Claim 11 (depends on 10) The system of claim 10, further comprising a database engine module for efficiently executing queries to the database using the generated sorting construct. ### Claim 12 (depends on 10) The system of claim 10, wherein the database comprises a plurality of tables, and wherein a table in the database for storing multiple hierarchical data structures. ### Claim 13 (depends on 10) The system of claim 10, wherein the sorting construct generation module is further for adding characters to the sorting construct of a parent element, the added characters are sorted before text characters and digital characters. ### Claim 14 (depends on 10) The system of claim 10, wherein the sorting construct has a length, and the length of the sorting construct is a function of the given width of the sorting construct and a maximum number of levels in the hierarchical data structure. ### Claim 15 A method for efficiently identifying a descendant of an element in a hierarchical data structure, the method comprising: creating an instance of a database in which elements of the hierarchical data structure are in an ancestor-descendant relationship and each element is indexed by a peer sequence value that identifies sequential ordering of elements having the same parent; generating a sorting construct for an element by transforming a peer sequence value for the element and prepending a leading substring, the leading substring is representative of a sorting construct of an ancestor of the element, wherein the peer sequence values and the sorting constructs are ordered according to the same collating sequence; and identifying elements in the data structure having a leading substring equal to the sorting construct of the element. ### Claim 16 A method for efficiently identifying an ancestor of an element in a hierarchical data structure, the method comprising: creating an instance of a database in which elements of the hierarchical data structure are in an ancestor-descendant relationship and each element is indexed by a peer sequence value that identifies sequential ordering of elements having the same parent; generating a sorting construct for an element by transforming a peer sequence value for the element and prepending a leading substring, the leading substring is representative of a sorting construct of an ancestor of the element, wherein the peer sequence values and the sorting constructs are ordered according to the same collating sequence; and identifying elements in the data structure with the sorting construct equal to the leading substring of the element. ### Claim 17 A computer program product comprising: a computer-readable medium having computer program code embodied therein for efficiently indexing a hierarchical data structure in a database, the computer program code adapted to: create an instance of a database in which elements of a hierarchical data structure are in an ancestor-descendant relationship and an element is indexed by a peer sequence value that identifies sequential ordering of elements having a same parent; transform a peer sequence value for a parent element into a sorting construct of a given width to generate a sorting construct of the parent element, wherein the sorting construct maintains the sequential ordering of the elements having the same parent; transform a peer sequence value of a child element into a sorting construct of the given width, wherein the sorting construct of the child element maintains the sequential ordering of the child elements having the same parent; and prepend the sorting construct of the parent element to the left of the transformed peer sequence value of the child element to generate a sorting tree construct of the child element, wherein the peer sequence values and the sorting constructs are ordered according to the same collating sequence.