Hierarchical and recursive queries in SQL


A hierarchical query is a type of SQL query that handles hierarchical model data. They are special cases of more general recursive fixpoint queries, which compute transitive closures.
In standard SQL:1999 hierarchical queries are implemented by way of recursive common table expressions. Unlike Oracle's earlier [|connect-by clause], recursive CTEs were designed with fixpoint semantics from the beginning. Recursive CTEs from the standard were relatively close to the existing implementation in IBM DB2 version 2. Recursive CTEs are also supported by Microsoft SQL Server, Firebird 2.1, PostgreSQL 8.4+, SQLite 3.8.3+, IBM Informix version 11.50+, CUBRID, MariaDB 10.2+ and MySQL 8.0.1+. describing how CTEs can be used. TIBCO Spotfire does not support CTEs, while Oracle 11g Release 2's implementation lacks fixpoint semantics.
Without common table expressions or connected-by clauses it is possible to achieve hierarchical queries with user-defined recursive functions.

Common table expression

A common table expression, or CTE, is a temporary named result set, derived from a simple query and defined within the execution scope of a SELECT, INSERT, UPDATE, or DELETE statement.
CTEs can be thought of as alternatives to derived tables, views, and inline user-defined functions.
Common table expressions are supported by Teradata, IBM Db2, Informix, Firebird, Microsoft SQL Server, Oracle, PostgreSQL, MariaDB, MySQL, SQLite, HyperSQL, Informix, Google BigQuery, Sybase, Vertica, H2, and many others. Oracle calls CTEs "subquery factoring".
The syntax for a CTE is as follows:

WITH with_query
SELECT...

where with_query's syntax is:

query_name AS

Recursive CTEs can be used to traverse relations although the syntax is much more involved because there are no automatic pseudo-columns created ; if these are desired, they have to be created in the code. See MSDN documentation or IBM documentation for tutorial examples.
The RECURSIVE keyword is not usually needed after WITH in systems other than PostgreSQL.
In SQL:1999 a recursive query may appear anywhere a query is allowed. It's possible, for example, to name the result using CREATE VIEW. Using a CTE inside an INSERT INTO, one can populate a table with data generated from a recursive query; random data generation is possible using this technique without using any procedural statements.
Some Databases, like PostgreSQL, support a shorter CREATE RECURSIVE VIEW format which is internally translated into WITH RECURSIVE coding.
An example of a recursive query computing the factorial of numbers from 0 to 9 is the following:

WITH recursive temp AS *fact FROM temp WHERE n < 9 -- Recursive Subquery
SELECT * FROM temp;

CONNECT BY

An alternative syntax is the non-standard CONNECT BY construct; introduced by Oracle in the 1980s. Prior to Oracle 10g, the construct was only useful for traversing acyclic graphs because it returned an error on detecting any cycles; in version 10g Oracle introduced the NOCYCLE feature, making the traversal work in the presence of cycles as well.
CONNECT BY is supported by Snowflake, EnterpriseDB, Oracle database, CUBRID, IBM Informix and IBM Db2 although only if it is enabled as a compatibility mode. The syntax is as follows:

SELECT select_list
FROM table_expression
CONNECT BY
]... ]
...

; For example,

SELECT LEVEL, LPAD || ename "employee", empno, mgr "manager"
FROM emp START WITH mgr IS NULL
CONNECT BY PRIOR empno = mgr;

The output from the above query would look like:
level | employee | empno | manager
-------+-------------+-------+---------
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

Pseudo-columns

  • Unary operators

The following example returns the last name of each employee in department 10, each manager above that employee in the hierarchy, the number of levels between manager and employee, and the path between the two:

SELECT
ename "Employee",
CONNECT_BY_ROOT ename "Manager",
LEVEL-1 "Pathlen",
SYS_CONNECT_BY_PATH "Path"
FROM emp
WHERE LEVEL > 1 AND deptno = 10
CONNECT BY PRIOR empno = mgr
ORDER BY "Employee", "Manager", "Pathlen", "Path";

Functions

  • SYS_CONNECT_BY_PATH