Efficient indexing of hierarchical relational database records

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.

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.

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.

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.