Browse Prior Art Database

Subtree Move of Hierarchical Data In A Relational Database

IP.com Disclosure Number: IPCOM000015951D
Original Publication Date: 2002-May-02
Included in the Prior Art Database: 2003-Jun-21
Document File: 3 page(s) / 59K

Publishing Venue

IBM

Abstract

This disclosure contains a description of the relational database table layout used by the Lightweight Directory Access Protocol (LDAP) Directory Services Server program to store directory hierarchy information, and the Structured Query Language (SQL) Data Manipulation Language (DML) statements used by the server program to perform movements of directory subtrees within this table. The data model described herein is general-purpose in nature, and may be used to represent any hierarchical data structure in relational form. As such, the SQL DML statements described here may be adopted for relocation of a subtree within any similar hierarchical representation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 71% of the total text.

Page 1 of 3

Subtree Move of Hierarchical Data In A Relational Database

  This disclosure contains a description of the relational database table layout used by the Lightweight Directory Access Protocol (LDAP) Directory Services Server program to store directory hierarchy information, and the Structured Query Language (SQL) Data Manipulation Language (DML) statements used by the server program to perform movements of directory subtrees within this table. The data model described herein is general-purpose in nature, and may be used to represent any hierarchical data structure in relational form. As such, the SQL DML statements described here may be adopted for relocation of a subtree within any similar hierarchical representation.

Hierarchical ("tree") structures are easily represented in what is referred to as "speed" tables which denormalize the hierarchy data to improve the performance of queries. The LDAP Directory Services Server program uses a "speed" table called DESC whose format is simply two columns: AEID, used to represent an ascendant node in a parent-child relationship, and DEID, used to represent the descendant node in the parent-child relationship. Instead of maintaining a single row for the relationship with a child and its immediate superior (as would be done in a fully-normalized representation), there is a row for the relationship between a child and EACH of its superior nodes, as well as a row to represent the child itself.

Example:

Hierarchy DESC table DESC table (continued)

AEID DEID AEID DEID

1 1 1 4 5

/ \ 1 2 5 5

2 4 2 2 1 6

/ / \ 1 3 4 6

3 5 7 2 3 5 6

/ 3 3 6 6

6 1 4 1 7

4 4 4 7

1 5 7 7

A common operation performed on a hierarchical structure is the movement of some subtree of the structure beneath a new superior node.

Continuing the example, one may wish to move the subtree containing nodes 5 and 6 beneath the new superior node 2. There are a variety of ways for accomplishing such a move; in the interest of minimizing I/O between the database manager and the application to improve performance, the LDAP server adopts the following approach: (A) remove from the "speed" table those rows used to represent ancestors of the moved subtree in its old location in the hierarchy, a...