Database Journal
MS SQL Oracle DB2 Access MySQL PostgreSQL Sybase PHP SQL Etc SQL Scripts & Samples Links Database Forum

» Database Journal Home
» Database Articles
» Database Tutorials
MS SQL
Oracle
DB2
MS Access
MySQL
» RESOURCES
Database Tools
SQL Scripts & Samples
Links
» Database Forum
» Sitemap
Free Newsletters:
DatabaseDaily  
News Via RSS Feed


follow us on Twitter
Database Journal |DBA Support |SQLCourse |SQLCourse2
 

Featured Database Articles

Oracle

Posted Mar 22, 2006

Trees and Hierarchies in Oracle

By Steve Callan

You may think you know everything there is to know about the Scott schema, but part of its overall usefulness lies in how versatile it is with respect to its ability to illustrate many of Oracle's and SQL's features. The illustrative point examined in this article concerns trees and hierarchies. An excellent book by Joe Celko (Joe Celko's Trees and Hierarchies in SQL for Smarties) shows several means of arranging hierarchical data. This article combines the familiar emp table and some of the examples shown in Celko's book.

The standard nested hierarchy

A quick search on the Internet yields numerous sites showing you how to get a nested hierarchy of the emp table. Another typical example of this hierarchy is that of parent-child foreign key relationships. Shown below is an example of the typical hierarchy based on the emp table, but with an extra feature (the mgr_key). This example is available at the askTom Web site (you'll have to add the mgr_lookup function, and the code for that is at the site).

select /*+ first_rows */
rpad( '*', (level-1)*2, '*' ) || 
   ename ename, empno, mgr_key
from emp
start with mgr_lookup(mgr_key) = -1
connect by prior empno = mgr_lookup(mgr_key);
ENAME                EMPNO MGR_KEY
--------------- ---------- --------
KING                  7839 mgr_
**JONES               7566 mgr_7839
****SCOTT             7788 mgr_7566
******ADAMS           7876 mgr_7788
****FORD              7902 mgr_7566
******SMITH           7369 mgr_7902
**BLAKE               7698 mgr_7839
****ALLEN             7499 mgr_7698
****WARD              7521 mgr_7698
****MARTIN            7654 mgr_7698
****TURNER            7844 mgr_7698
****JAMES             7900 mgr_7698
**CLARK               7782 mgr_7839
****MILLER            7934 mgr_7782

Let's put this into an organization chart (or wire diagram).

This chart is courtesy of Visio's Organization Chart Wizard. The wizard connects to a data source (a database in this case), queries the table you select, and determines the hierarchical relationship of the table's elements. Aside from presenting an easier means of interpreting the hierarchical relationships within the emp table, the chart leads us into the first example of how to record the relationships by using a nested set model.

The "emp" family

The algorithm for creating a nested set model is pretty simple. Start at the top, enter the next number in the lower left corner of the element's box, then move down a level if there is one, or across the element, and enter the next number. If there are no lower elements, traverse across that element and enter the next number, then traverse across to the next sibling, and repeat the numbering. Continue until you return to the top element of the current branch. Traverse across to the next branch and repeat. Return to the top-level element when there are no more lower level branches to traverse to and enter the final/last number of the sequence.

Putting an algorithm into words may make it seem confusing, but when applying the steps, the implementation is usually much easier, and even more so when you have an example to go by. We start with King and enter a 1 in the lower left corner. Move down to Clark and enter a 2. Since Clark has a lower level/child element, move down to Miller and enter a 3. Move across Miller and enter a 4, returning to Clark with a 5. Traverse across to Blake and enter a 6, and so on from there.

Now that we have an ordered pair identification scheme (e.g., Martin is [9,10]), we can create a new emp table as shown below.

CREATE TABLE EMP_ORG
(EMPNO NUMBER NOT NULL,
LEFT NUMBER NOT NULL,
RIGHT NUMBER NOT NULL);
INSERT INTO EMP_ORG VALUES (7839,1,28);
INSERT INTO EMP_ORG VALUES (7782,2,5);
INSERT INTO EMP_ORG VALUES (7934,3,4);
INSERT INTO EMP_ORG VALUES (7698,6,17);
INSERT INTO EMP_ORG VALUES (7844,7,8);
INSERT INTO EMP_ORG VALUES (7654,9,10);
INSERT INTO EMP_ORG VALUES (7521,11,12);
INSERT INTO EMP_ORG VALUES (7900,13,14);
INSERT INTO EMP_ORG VALUES (7499,15,16);
INSERT INTO EMP_ORG VALUES (7566,18,27);
INSERT INTO EMP_ORG VALUES (7788,19,22);
INSERT INTO EMP_ORG VALUES (7876,20,21);
INSERT INTO EMP_ORG VALUES (7902,23,26);
INSERT INTO EMP_ORG VALUES (7369,24,25);
SQL> select * from emp_org;
     EMPNO       LEFT      RIGHT
---------- ---------- ----------
      7839          1         28
      7782          2          5
      7934          3          4
      7698          6         17
      7844          7          8
      7654          9         10
      7521         11         12
      7900         13         14
      7499         15         16
      7566         18         27
      7788         19         22
      7876         20         21
      7902         23         26
      7369         24         25
14 rows selected.

Following along with an example in the book, the next step is to create a view.

CREATE OR REPLACE VIEW EMP_ORG_VIEW 
(EMPNO, LEVEL_0, LEVEL_1, LEVEL_2)
AS
SELECT A.EMPNO,
  CASE WHEN COUNT(C.EMPNO) = 2
       THEN B.EMPNO
       ELSE NULL END AS LEVEL_0,
  CASE WHEN COUNT(C.EMPNO) = 3
       THEN B.EMPNO
       ELSE NULL END AS LEVEL_1,
  CASE WHEN COUNT(C.EMPNO) = 4
       THEN B.EMPNO
       ELSE NULL END AS LEVEL_2
FROM EMP_ORG A,
     EMP_ORG B,
     EMP_ORG C
WHERE
   A.LEFT BETWEEN B.LEFT AND B.RIGHT
AND
   C.LEFT BETWEEN B.LEFT AND B.RIGHT
AND
   A.LEFT BETWEEN C.LEFT AND C.RIGHT
GROUP BY A.EMPNO, B.EMPNO;       

The final step is to write the query which shows the hierarchical structure of the organization.

SELECT EMPNO,
       MAX(LEVEL_0) "LVL 0",
       MAX(LEVEL_1) "LVL 1",
       MAX(LEVEL_2) "LVL 2"
FROM EMP_ORG_VIEW
GROUP BY EMPNO;
     EMPNO LVL 0 LVL 1 LVL 2
     ----- ----- ----- -----
      7844  7698  7839
      7839
      7782  7839
      7698  7839
      7521  7698  7839
      7902  7566  7839
      7788  7566  7839
      7654  7698  7839
      7934  7782  7839
      7566  7839
      7499  7698  7839
      7876  7788  7566  7839
      7900  7698  7839
      7369  7902  7566  7839
14 rows selected.

As an alternative, you can replace empno with ename (make changes as appropriate for the data type and references), and generate a name display.

ENAME        LVL 0   LVL 1   LVL 2
------------ ------- ------- -------
ALLEN        BLAKE   KING
JONES        KING
FORD         JONES   KING
MILLER       CLARK   KING
CLARK        KING
SMITH        FORD    JONES   KING
WARD         BLAKE   KING
TURNER       BLAKE   KING
MARTIN       BLAKE   KING
ADAMS        SCOTT   JONES   KING
SCOTT        JONES   KING
BLAKE        KING
JAMES        BLAKE   KING
KING

Either way (by empno or ename), the results reflect the same organizational structure, but the ordered representation is somewhat hard to follow. Unfortunately, that is not the worst problem with a nested set. The number one weakness of this model is its inflexibility. What happens if a leaf node/element (Smith) leaves the organization? The structure survives, but what if you need to add a new element? For example, how do you add a new level under Ward?

The "connect by prior" version is indifferent to changes like that. Simply add the new employee, assign a manager (Ward), and the query output reflects the change. In the nested set model, every position after the insertion requires modification. Another real world example of a structure-breaking change is that of adding a new branch/department. Not only is there the reordering issue, but we have now introduced another problem – updating the structure of the view (adding a new level). Clearly, this type of model, although useful for academic purposes, is a maintenance nightmare. In fact, rigid models such as this are analogous to the rigid structure of hierarchical databases before the days of the relational model.

Build in some flexibility

As another example, who says the numbers you use in the ordered pair have to be consecutive? What matters is the relative ordering of the numbers (increasing in value as you walk the chart, but not necessarily increasing by one). Let's take the ename version and induce a range (multiply each position value by 10).

CREATE TABLE ENAME_BY10_ORG
(ENAME VARCHAR2(12) NOT NULL,
LEFT NUMBER NOT NULL,
RIGHT NUMBER NOT NULL);
INSERT INTO ENAME_BY10_ORG VALUES ('KING',10,280);
INSERT INTO ENAME_BY10_ORG VALUES ('CLARK',20,50);
INSERT INTO ENAME_BY10_ORG VALUES ('MILLER',30,40);
INSERT INTO ENAME_BY10_ORG VALUES ('BLAKE',60,170);
INSERT INTO ENAME_BY10_ORG VALUES ('TURNER',70,80);
INSERT INTO ENAME_BY10_ORG VALUES ('MARTIN',90,100);
INSERT INTO ENAME_BY10_ORG VALUES ('WARD',110,120);
INSERT INTO ENAME_BY10_ORG VALUES ('JAMES',130,140);
INSERT INTO ENAME_BY10_ORG VALUES ('ALLEN',150,160);
INSERT INTO ENAME_BY10_ORG VALUES ('JONES',180,270);
INSERT INTO ENAME_BY10_ORG VALUES ('SCOTT',190,220);
INSERT INTO ENAME_BY10_ORG VALUES ('ADAMS',200,210);
INSERT INTO ENAME_BY10_ORG VALUES ('FORD',230,260);
INSERT INTO ENAME_BY10_ORG VALUES ('SMITH',240,250);

Let's add someone between Martin and Ward.

INSERT INTO ENAME_BY10_ORG VALUES ('COLE',101,102);

You can see that Cole picks up the same hierarchy as her siblings.

So far, so good. Now let's add someone between Martin and Cole. Oops, we didn't plan far enough ahead in the insertion/addition scheme because there isn't any room (numerically speaking, using whole numbers) between 100 (the end of Martin) and 101 (the beginning of Cole). Without having to resort to real numbers (which includes values such as 100.2, 100.74, etc.), one way to preserve the use of whole numbers is to make the range wide enough, and then pack in additions close to the boundary, but not too close so as to leave room for future additions.

With this modification to the nested set model, adding new nodes within existing levels is quite easy due to the increased range of numbers, but we are still faced with the maintenance issue regarding the addition of new levels. You can always create the view with more levels than currently being used, so that helps to minimize the maintenance problem.

Coming back to Oracle

What do connect by prior, start with, and level mean in this query?

select rpad( '*', (level-1)*2, '*' ) || table_name table_name
from temp_constraints
start with fkey_constraint is null
connect by prior pkey_constraint = r_constraint_name;

The SQL Reference guide defines these items as such:

  • START WITH specifies the root row(s) of the hierarchy.
  • CONNECT BY specifies the relationship between parent rows and child rows of the hierarchy. In a hierarchical query, one expression in condition must be qualified with the PRIOR operator to refer to the parent row.
  • LEVEL (pseudocolumn) returns 1 for a root row, 2 for a child of a root, and so on for each row returned by a hierarchical query

"Connect by" is not a SQL-92 ANSI standard, and other versions of SQL use different constructs to perform the same function. You can begin to appreciate the power and usefulness of this feature, especially when faced with having to query hierarchical relationships using nested sets or other set models.

In Closing

One of the hidden tools or algorithms behind hierarchical queries is recursion. The best way to learn to recursion is to first learn recursion. That's an old joke, but recursion helps drive complex queries, and queries involving hierarchies and trees are certainly among the most complex. Fortunately for us mere mortals, masters of the trade such as Joe Celko and Tom Kyte have reduced the seemingly complex into more understandable chunks of information. Understanding and have some adeptness at using SQL is one of the key requirements for becoming a better DBA.

» See All Articles by Columnist Steve Callan



Oracle Archives

Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 




Latest Forum Threads
Oracle Forum
Topic By Replies Updated
Oracle Data Mining: Classification jan.hasller 0 July 5th, 07:19 AM
Find duplicates - Unique IDs Lava 5 July 2nd, 08:30 AM
no matching unique or primary key rcanter 1 April 25th, 12:32 PM
Update values of one table based on condition of values in other table using Trigger Gladiator 3 February 29th, 06:01 PM


















Thanks for your registration, follow us on our social networks to keep up-to-date