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 (CTEs). Unlike Oracle's earlier connect-by clause, recursive CTEs were designed with fixpoint semantics from the beginning.^[1] Recursive CTEs from the standard were relatively close to the existing implementation in IBM DB2 version 2.^[1] Recursive CTEs are also supported by Microsoft SQL Server (since SQL Server 2008 R2),^[2] Firebird 2.1,^[3] PostgreSQL 8.4+,^[4] SQLite 3.8.3+,^[5] IBM Informix version 11.50+, CUBRID, MariaDB 10.2+ and MySQL 8.0.1+.^[6] Tableau has documentation 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.^[7]

Common table expression

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), IBM 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  WHERE n < 9  -- Recursive Subquery
)
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 IBM 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)

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";

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