6.7. Hierarchical Queries

6.7.1. What are Hierarchical Queries?

Some systems make extensive use of hierarchical data like an organizational chart or a family tree. These types of information are best represented in a tree like structure. However, such data can easily be made to fit into a relational table by using a self-referential relationship making use of hierarchical queries. With the hierarchical queries support in EnterpriseDB complex hierarchical operations can be constructed on tree-structured data.

For each hierarchical query we need to specify a starting condition with the START WITH clause, which will trickle down to all dependant rows using one or more conditions specified by the CONNECT BY clause.

6.7.2. Usage

The START WITH...CONNECT BY clause can be used to select data that has a hierarchical relationship. Such data is usually in the form of some parent child relationship e.g. manager to employee relationship.

START WITH  condition_1
CONNECT BY PRIOR condition_2

Parameters

condition_1: The condition clause in the START WITH is used to specify the relationship between parent rows and child rows of the hierarchy.
condition_2: The condition in the CONNECT BY PRIOR clause is used to identify the row(s) to be used as the root(s) of a hierarchical query.

To find the children of a parent row, the clause evaluates the PRIOR expression of the CONNECT BY condition for the parent row and the other expression for each row in the table. Rows for which the condition is true are the children of the parent. The CONNECT BY condition can contain other conditions to further filter the rows selected by the query. The CONNECT BY condition cannot contain a subquery.

CONNECT BY PRIOR Clause

It specifies a condition that identifies the relationship between parent rows and child rows of the hierarchy.

START WITH Clause

It specifies a condition that identifies the row(s) to be used as the root(s) of a hierarchical query.

PRIOR Clause

In a hierarchical query, one expression in condition must be qualified with the PRIOR operator to refer to the parent row. For example,

 ... PRIOR expr = expr

or

... expr = PRIOR expr

PRIOR is a unary operator and has the same precedence as the unary + and - arithmetic operators. It evaluates the immediately following expression for the parent row of the current row in a hierarchical query.

PRIOR is most commonly used when comparing column values with the equality operator. (The PRIOR keyword can be on either side of the operator.) PRIOR causes EnterpriseDB to use the value of the parent row in the column. Operators other than the equal sign (=) are theoretically possible in CONNECT BY clauses. However, the conditions created by these other operators can result in an infinite loop through the possible combinations. In this case, EnterpriseDB detects the loop at run time and returns an error.

Processing of Hierarchical Queries

The processing of hierarchical queries is as follows:

A join, if present, is evaluated first, whether the join is specified in the FROM clause or with WHERE clause predicates.
The CONNECT BY condition is evaluated.
Any remaining WHERE clause predicates are evaluated.
EnterpriseDB then uses the information from these evaluations to form the hierarchy using the following steps:
1. It selects the root row(s) of the hierarchy-those rows that satisfy the START WITH condition.
2. It selects the child rows of each root row. Each child row must satisfy the condition of the CONNECT BY clause with respect to one of the root rows.
3. It selects successive generations of child rows. EnterpriseDB first selects the children of the rows returned in step 2, and then the children of those children, and so on. It always selects children by evaluating the CONNECT BY condition with respect to a current parent row.
4. It selects successive generations of child rows. EnterpriseDB first selects the children of the rows returned in step 2, and then the children of those children, and so on. It always selects children by evaluating the CONNECT BY condition with respect to a current parent row.
5. If the query contains a WHERE clause without a join, then EnterpriseDB eliminates all rows from the hierarchy that do not satisfy the condition of the WHERE clause.
6. It evaluates this condition for each row individually, rather than removing all the children of a row that does not satisfy the condition.
7. It returns the rows in the order shown in the following figure. In the diagram, children appear below their parents.

To find the children of a parent row, EnterpriseDB evaluates the PRIOR expression of the CONNECT BY condition for the parent row and the other expression for each row in the table. Rows for which the condition is true are the children of the parent. The CONNECT BY condition can contain other conditions to further filter the rows selected by the query. The CONNECT BY condition cannot contain a subquery. If the CONNECT BY condition results in a loop in the hierarchy, then it returns an error. A loop occurs if one row is both the parent (or grandparent or direct ancestor) and a child (or a grandchild or a direct descendent) of another row.

Level Pseudo Column

For each row returned by a hierarchical query, the LEVEL pseudo column returns 1 for a root row, 2 for a child of a root, and so on.

START WITH... CONNECT BY Clause

The START WITH... CONNECT BY clause can be used to select data that has a hierarchical relationship, i.e. usually some kind of parent Child relationship, e.g. manager->employee.

START WITH is used to specify the root of the hierarchy, typically the element which has no parent, although other elements can be chosen as the root as well to generate partial hierarchies.

CONNECT BY is used to specify the recurse-condition. In order to define hierarchies, the recurse-condition can make use of the keyword prior:

CONNECT BY PRIOR foo = bar;

This construct establishes recursion. All records that are part of the next lower hierarchical level are found by having bar = foo. foo is a value found in the current hierarchical level.

There is a pseudo-column LEVEL available which can be used to determine the hierarchical level of any row. LEVEL can not be used in any expression/function.

6.7.3. Examples

Example (Using EnterpriseDB Sample Database)

The following example illustrates the use of the START WITH.....CONNECT BY clause:

   
SELECT           LEVEL, ename, empno, mgr
FROM             emp
START WITH       mgr IS NULL
CONNECT BY PRIOR empno = mgr;

Output

The output of the above query is as follows:

  
 level | ename  | empno | mgr
-------+--------+-------+------
     1 | KING   |  7839 |
     2 | JONES  |  7566 | 7839
     3 | SCOTT  |  7788 | 7566
     4 | ADAMS  |  7876 | 7788
     3 | FORD   |  7902 | 7566
     4 | SMITH  |  7369 | 7902
     2 | BLAKE  |  7698 | 7839
     3 | ALLEN  |  7499 | 7698
     3 | WARD   |  7521 | 7698
     3 | MARTIN |  7654 | 7698
     3 | TURNER |  7844 | 7698
     3 | JAMES  |  7900 | 7698
     2 | CLARK  |  7782 | 7839
     3 | MILLER |  7934 | 7782
     1 | user   |     1 |
(15 rows)

To use LEVEL in expressions/functions there exists a work-around. The query can be used as a subquery, then the outer query can use LEVEL as a regular column in expressions/functions.

Simple Example

Another example that uses the START WITH.....CONNECT BY clause is as follows:

CREATE TABLE Geometry
(
    name   VARCHAR,
    typeof VARCHAR
);

INSERT INTO Geometry VALUES( 'Shape', NULL );
INSERT INTO Geometry VALUES( 'Circle', 'Shape' );
INSERT INTO Geometry VALUES( 'Polygon', 'Shape' );
INSERT INTO Geometry VALUES( 'Triangle', 'Polygon' );
INSERT INTO Geometry VALUES( 'Quadrilateral', 'Polygon' );
INSERT INTO Geometry VALUES( 'Rectangle', 'Quadrilateral' );
INSERT INTO Geometry VALUES( 'Square', 'Rectangle' );
INSERT INTO Geometry VALUES( 'Parallelogram', 'Quadrilateral' );
INSERT INTO Geometry VALUES( 'Rhombus', 'Parallelogram' );
INSERT INTO Geometry VALUES( 'Hexagon', 'Polygon' );

SELECT   LEVEL, LPAD(' ',3*(LEVEL - 1)) || name AS "Shape", TYPEOF AS "is a type of"
FROM     (
             SELECT           LEVEL, name, TYPEOF
             FROM             Geometry
             START WITH       TYPEOF  IS  NULL
             CONNECT BY PRIOR name =  TYPEOF
         )   AS subquery;	

DROP TABLE Geometry;

Output

The output of the above query is as follows:

 level |         Shape          | is a type of
-------+------------------------+---------------
     1 | Shape                  |
     2 |    Circle              | Shape
     2 |    Polygon             | Shape
     3 |       Triangle         | Polygon
     3 |       Quadrilateral    | Polygon
     4 |          Rectangle     | Quadrilateral
     5 |             Square     | Rectangle
     4 |          Parallelogram | Quadrilateral
     5 |             Rhombus    | Parallelogram
     3 |       Hexagon          | Polygon
(10 rows)

Example (Using EnterpriseDB Sample Database)

SELECT   LEVEL, LPAD(' ',3*(LEVEL - 1)) || ename AS "Employee", empno, mgr
FROM     (
             SELECT           LEVEL, ename, empno, mgr
             FROM             emp
             START WITH       mgr IS NULL
             CONNECT BY PRIOR empno = mgr
         )   AS subquery;

Output

The output of the above query is as follows:

 level |    Employee    | empno | mgr
-------+----------------+-------+------
     1 | KING           |  7839 |
     2 |    JONES       |  7566 | 7839
     3 |       SCOTT    |  7788 | 7566
     4 |          ADAMS |  7876 | 7788
     3 |       FORD     |  7902 | 7566
     4 |          SMITH |  7369 | 7902
     2 |    BLAKE       |  7698 | 7839
     3 |       ALLEN    |  7499 | 7698
     3 |       WARD     |  7521 | 7698
     3 |       MARTIN   |  7654 | 7698
     3 |       TURNER   |  7844 | 7698
     3 |       JAMES    |  7900 | 7698
     2 |    CLARK       |  7782 | 7839
     3 |       MILLER   |  7934 | 7782
     1 | user           |     1 |
(15 rows)

Example

SELECT LEVEL, ename, empno, mgr
FROM  emp
START WITH empno = 7788
CONNECT BY PRIOR empno = mgr;

Output

The output of the above query is as follows:

 level | ename | empno | mgr
-------+-------+-------+------
     1 | SCOTT |  7788 | 7566
     2 | ADAMS |  7876 | 7788
(2 rows)

Example

SELECT LEVEL, ename, mgr
FROM emp
START WITH empno= 7839
CONNECT BY PRIOR empno=mgr;

Output

The output of the above query is as follows:

 level | ename  | mgr
-------+--------+------
     1 | KING   |
     2 | JONES  | 7839
     3 | SCOTT  | 7566
     4 | ADAMS  | 7788
     3 | FORD   | 7566
     4 | SMITH  | 7902
     2 | BLAKE  | 7839
     3 | ALLEN  | 7698
     3 | WARD   | 7698
     3 | MARTIN | 7698
     3 | TURNER | 7698
     3 | JAMES  | 7698
     2 | CLARK  | 7839
     3 | MILLER | 7782
(14 rows)