100% Java Object-Relational Database Systems 
FirstSQL Home
Home Company Overview Products Technical Papers Download Contacts/Links Partners
:. Technical Articles and Issue Papers

FirstSQL/J v2.5 Extensions to Support Recursive Queries (CONNECT BY)

Business intelligence systems need to perform complex queries efficiently, and some of these queries must access hierarchical data. For example, an employee table may hold an organization's hierarchy information by listing each employee's name and manager. How can we generate an organization chart based on the hierarchical data? FirstSQL/J can readily perform the necessary hierarchical query with the CONNECT BY clause. The CONNECT BY clause specifies the relationship between parent rows and child rows in the hierarchy and the starting point of the hierarchy. The CONNECT BY construct supports recursive queries. A recursive query traverses a tree structure to produce a flat result set. A single table or a join of tables can represent a tree in the database.

An example of a single table that uses a tree structure is the employees table, containing both regular employees and their managers. Each row in the table represents an employee or manager. A managed employee references their direct manager with a foreign key.

The CREATE TABLE for employees:

    CREATE TABLE employees
    (emp_no INT PRIMARY KEY,
    name VARCHAR(32) NOT NULL,
    hire_date DATE,
    salary DECIMAL(7,2),
    mgr_no INT REFERENCES employees
    )

A simple employee tree:

is represented by the following rows in employees:

    emp_no name hire_date salary mgr_no
    1001 Mary 1999-01-01 40000.00 NULL
    1002 John 1999-03-17 30000.00 1001
    1003 Gail 1999-04-01 30000.00 1001
    1004 Bill 1999-04-21 30000.00 1001
    1005 Jane 1999-06-01 20000.00 1002
    1006 Fred 1999-06-01 20000.00 1002
    1007 Ruth 1999-06-24 20000.00 1002
    1008 Burt 1999-06-30 20000.00 1003
    1009 Lucy 1999-07-13 20000.00 1003
    1010 Alan 1999-07-28 20000.00 1003
    1011 Beth 1999-08-03 20000.00 1003
    1012 Dora 1999-08-15 20000.00 1004
    1013 Mark 1999-09-05 20000.00 1004
    1014 Lynn 1999-09-19 20000.00 1004
A recursive query using the CONNECT BY construct creates a result by traversing the tree. It has the following general format:
    SELECT select-list
    FROM from-list
    [WHERE predicate]
    START WITH predicate
    CONNECT BY predicate

The START WITH predicate selects the row or rows that are the root of one or more independent trees. The CONNECT BY predicate links successive levels of the tree. It connects the root to the second level, the second level to the third, and so on. In the CONNECT BY predicate, the PRIOR keyword marks references to the previous level.

The following query traverses the employee tree shown above:

    SELECT LEVEL, name
    FROM employees
    START WITH name = 'Mary'
    CONNECT BY PRIOR emp_no = mgr_no

Note: The LEVEL keyword is a system value used in CONNECT BY queries. It contains the level number of the current row in the tree.

The query result is:

    level name
    1 Mary
    2 John
    3 Jane
    3 Fred
    3 Ruth
    2 Gail
    3 Burt
    3 Lucy
    3 Alan
    3 Beth
    2 Bill
    3 Dora
    3 Mark
    3 Lynn
The processing steps for the first three result rows are:
  • Select the root row (Mary) with the START WITH predicate.
  • Select the second level row (John) with the CONNECT BY predicate by matching the emp_no for the root level (1001 for Mary) against the mgr_no for the candidate rows.
  • Select the third level row (Jane) by matching the emp_no for the prior level (1002 for John) against the mgr_no for the candidate rows.
When a row is selected for a given level, the descendants for that row (if any) are selected before the next row at the same level is processed. In the sample query above, the second level descendants of the root level (Mary) are John, Gail, Bill. John is selected first followed by all third level descendants of John before processing Gail.

The from-list for a CONNECT BY may contain outer joins and nested queries (table subqueries). The only restriction on table subqueries is that they may not contain a nested CONNECT BY query. Predicate subqueries and scalar subqueries, on the other hand, may be or contain a CONNECT BY query.

The tree cannot contain any loops (cycles). Tree loops occur because of loops in the data or because the query is incorrectly formulated. If it detects a loop in the tree traversal, the query terminates and throws a SQL Exception.

Extended Capabilities

FirstSQL/J provides extended capabilities within a CONNECT BY query. This includes the PRIOR and LEVEL keywords introduced above, plus the connectByPath() function.

PRIOR Keyword

The PRIOR keyword is valid only in the CONNECT BY predicate. It modifies a column name to reference the previous level of the tree. For example,
    PRIOR emp_no
This references the emp_no column in the result row from the previous level. The expression:
    PRIOR emp_no = mgr_no
matches the emp_no column from the previous level with the mgr_no column from the current level. The expression connects an employee from the current level with its immediate manager on the previous level of the tree.

The CONNECT BY predicate can have multiple references to columns on the previous level, each using the PRIOR modifier.

LEVEL Keyword

The LEVEL keyword is valid in the CONNECT BY predicate and in the select-list of the CONNECT BY query. It is a reference to a built-in system value containing the current level being processed. LEVEL is an integer value. The root level has a LEVEL value of 1, the next level is numbered 2, and so on.

Full query example:

    SELECT LEVEL, name
    FROM employees
    START WITH mgr_no IS NULL
    CONNECT BY PRIOR emp_no = mgr_no
    AND LEVEL <= 2

    level name
    1 Mary
    2 John
    2 Gail
    2 Bill
This query includes the LEVEL number in the select list. It also uses the LEVEL number in the CONNECT BY predicate to limit the tree traversal to 2 levels.

connectByPath() Function

The connectByPath() function constructs a string path from the root to the current level that includes all intervening levels. It is only valid in the select-list of a CONNECT BY query. The connectByPath() function has the following general format:

    SET.connectByPath(column-name, separator)

connectByPath() is a method in the built-in system class -- SET. Its arguments are:
  • column-name -- the name of a character column in the CONNECT BY query. The connectByPath() function collects the value of this column from each successive level in constructing the path string.
  • separator -- string value used to separate each level value in the path string.
This is best illustrated by modifying the initial example query to use the function:

    SELECT LEVEL, name, SET.connectByPath(name, '/') path
    FROM employees
    START WITH name = 'Mary'
    CONNECT BY PRIOR emp_no = mgr_no

    level name path
    1 Mary /Mary
    2 John /Mary/John
    3 Jane /Mary/John/Jane
    3 Fred /Mary/John/Fred
    3 Ruth /Mary/John/Ruth
    2 Gail /Mary/Gail
    3 Burt /Mary/Gail/Burt
    3 Lucy /Mary/Gail/Lucy
    3 Alan /Mary/Gail/Alan
    3 Beth /Mary/Gail/Beth
    2 Bill /Mary/Bill
    3 Dora /Mary/Bill/Dora
    3 Mark /Mary/Bill/Mark
    3 Lynn /Mary/Bill/Lynn
The connectByPath() function will accept any string expression for both arguments. It also has a single argument form:

    SET.connectByPath(string-expression)

The 2 argument example above:

    SET.connectByPath(name, '/')

is equivalent to:

    SET.connectByPath('/' || name)

using the single argument form. For example:

    SELECT LEVEL, name, SET.connectByPath('/' || name) path
    FROM employees
    START WITH name = 'Mary'
    CONNECT BY PRIOR emp_no = mgr_no

    level name path
    1 Mary /Mary
    2 John /Mary/John
    3 Jane /Mary/John/Jane
    3 Fred /Mary/John/Fred
    3 Ruth /Mary/John/Ruth
    2 Gail /Mary/Gail
    3 Burt /Mary/Gail/Burt
    3 Lucy /Mary/Gail/Lucy
    3 Alan /Mary/Gail/Alan
    3 Beth /Mary/Gail/Beth
    2 Bill /Mary/Bill
    3 Dora /Mary/Bill/Dora
    3 Mark /Mary/Bill/Mark
    3 Lynn /Mary/Bill/Lynn
Note: SQL scripts for creating and populating the employees table and the example queries above are included with the distribution.

Copyright © 2003 FFE Software, Inc. All Rights Reserved WorldWide

:. Products
FirstSQL/J Database Products
FirstSQL/J Enterprise Server v3.20



Administrative and Development Tools
Enterprise Server Tools

iodbc - a complete console utility for database access using ODBC.


:. Technical Papers
Technical Articles (all)
SQL Tutorial
Java Objects in the Database Tutorial
Frequently Asked Questions
Extended Referential Integrity
Highly Available Databases
Issue Papers (all)
Should Nulls be considered harmful?
Do DBMSs Process Subqueries Correctly?
Open Database Access and ODBC
Relational Databases, Do Users Benefit?
In Defense of Nulls
:. Company Info
FirstSQL Software

El Cerrito, CA 94530






E-mail: info@firstsql.com


Copyright © 2001-15 FirstSQL Software All Rights Reserved WorldWide