Hierarchical and recursive queries in SQL

Common table expression

This section needs expansion. You can help by adding to it. (November 2012)

A common table expression, or CTE, (in SQL) 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 (subquery), views, and inline user-defined functions.

Common table expressions are supported by Teradata (starting with version 14), DB2, Informix (starting with version 14.1), Firebird (starting with version 2.1),^[8]Microsoft SQL Server (starting with version 2005), Oracle (with recursion since 11g release 2), PostgreSQL (since 8.4), MariaDB (since 10.2), MySQL (since 8.0), SQLite (since 3.8.3), HyperSQL, Informix (since 14.10),^[9] Google BigQuery, Sybase (starting with version 9), Vertica, H2 (experimental),^[10] and many others. Oracle calls CTEs "subquery factoring".^[11]

The syntax for a CTE (which may or may not be recursive) is as follows:

WITH [RECURSIVE] with_query [, ...]
SELECT ...

where with_query‘s syntax is:

query_name [ (column_name [,...]) ] AS (SELECT ...)

Recursive CTEs can be used to traverse relations (as graphs or trees) although the syntax is much more involved because there are no automatic pseudo-columns created (like LEVEL below); if these are desired, they have to be created in the code. See MSDN documentation^[2] or IBM documentation^[12][13] for tutorial examples.

The RECURSIVE keyword is not usually needed after WITH in systems other than PostgreSQL.^[14]

In SQL:1999 a recursive (CTE) query may appear anywhere a query is allowed. It's possible, for example, to name the result using CREATE [RECURSIVE] VIEW.^[15] 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.^[16]

Some Databases, like PostgreSQL, support a shorter CREATE RECURSIVE VIEW format which is internally translated into WITH RECURSIVE coding.^[17]

An example of a recursive query computing the factorial of numbers from 0 to 9 is the following:

WITH RECURSIVE temp (n, fact) AS 
(SELECT 0, 1 -- Initial Subquery
  UNION ALL 
 SELECT n+1, (n+1)*fact FROM temp -- Recursive Subquery 
        WHERE n < 9)
SELECT * FROM temp;

CONNECT BY

An alternative syntax is the non-standard CONNECT BY construct; it was introduced by Oracle in the 1980s.^[18] 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 (and keyword), making the traversal work in the presence of cycles as well.^[19]

CONNECT BY is supported by Snowflake, EnterpriseDB,^[20]Oracle database,^[21]CUBRID,^[22]IBM Informix^[23] and DB2 although only if it is enabled as a compatibility mode.^[24] The syntax is as follows:

SELECT select_list
FROM table_expression
[ WHERE ... ]
[ START WITH start_expression ]
CONNECT BY [NOCYCLE] { PRIOR child_expr = parent_expr | parent_expr = PRIOR child_expr }
[ ORDER SIBLINGS BY column1 [ ASC | DESC ] [, column2 [ ASC | DESC ] ] ... ]
[ GROUP BY ... ]
[ HAVING ... ]
...

For example,

SELECT LEVEL, LPAD (' ', 2 * (LEVEL - 1)) || 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
(14 rows)

Pseudo-columns

• LEVEL
• CONNECT_BY_ISLEAF
• CONNECT_BY_ISCYCLE
• CONNECT_BY_ROOT

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(ename, '/') "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

See also

• Datalog also implements fixpoint queries
• Deductive databases
• Hierarchical model
• Reachability
• Transitive closure
• Tree structure

References

Further reading

• C. J. Date (2011). SQL and Relational Theory: How to Write Accurate SQL Code (2nd ed.). O'Reilly Media. pp. 159–163. ISBN 978-1-4493-1640-2.

Academic textbooks. Note that these cover only the SQL:1999 standard (and Datalog), but not the Oracle extension.

• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts (6th ed.). McGraw-Hill. pp. 187–192. ISBN 978-0-07-352332-3.
• Raghu Ramakrishnan; Johannes Gehrke (2003). Database management systems (3rd ed.). McGraw-Hill. ISBN 978-0-07-246563-1. Chapter 24.
• Hector Garcia-Molina; Jeffrey D. Ullman; Jennifer Widom (2009). Database systems: the complete book (2nd ed.). Pearson Prentice Hall. pp. 437–445. ISBN 978-0-13-187325-4.

External links

• https://stackoverflow.com/questions/1731889/cycle-detection-with-recursive-subquery-factoring
• http://explainextended.com/2009/11/18/sql-server-are-the-recursive-ctes-really-set-based/
• https://web.archive.org/web/20131114094211/http://gennick.com/with.html
• http://www.cs.duke.edu/courses/fall04/cps116/lectures/11-recursion.pdf
• http://www.blacktdn.com.br/2015/06/blacktdn-mssql-usando-consulta-cte.html