Hierarchical and recursive queries in SQL

A '''hierarchical query''' is a type of SQL query that handles hierarchical model data. These are useful for working with databases of graph-structured data, such as river networks, file system trees, or threaded comments. 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.<ref name="JimMelton1">{{cite book|author1=Jim Melton|author2=Alan R. Simon|title=SQL:1999: Understanding Relational Language Components|url=https://books.google.com/books?id=wyhXvU0Eyg0C&pg=PA352|year=2002|publisher=Morgan Kaufmann|isbn=978-1-55860-456-8}}</ref> Recursive CTEs from the standard were relatively close to the existing implementation in IBM DB2 version 2.<ref name="JimMelton1"/> Recursive CTEs are also supported by Microsoft SQL Server (since SQL Server 2008 R2),<ref name="msdnRCTEs">{{cite web |url=http://msdn.microsoft.com/en-us/library/ms186243.aspx |title=Recursive Queries Using Common Table Expressions |author=Microsoft |access-date=2009-12-23}}</ref> Firebird 2.1,<ref>{{cite web |url=http://firebirdsql.org/rlsnotesh/rlsnotes210.html#rnfb210-cte |title=Firebird 2.1 Release Notes |author=Helen Borrie |date=2008-07-15 |access-date=2015-11-24}}</ref> PostgreSQL 8.4+,<ref>{{cite web |url=http://www.postgresql.org/docs/current/interactive/queries-with.html |title=WITH Queries|date=10 February 2022}} PostgreSQL</ref> SQLite 3.8.3+,<ref>{{cite web |url=http://www.sqlite.org/lang_with.html |title=WITH Clause}} SQLite</ref> IBM Informix version 11.50+, CUBRID, MariaDB 10.2+ and MySQL 8.0.1+.<ref>{{cite web |url=https://mysqlserverteam.com/mysql-8-0-labs-recursive-common-table-expressions-in-mysql-ctes/ |title=MySQL 8.0 Labs: [Recursive] Common Table Expressions in MySQL (CTEs) |access-date=2017-12-20 |archive-date=2019-08-16 |archive-url=https://web.archive.org/web/20190816150345/https://mysqlserverteam.com/mysql-8-0-labs-recursive-common-table-expressions-in-mysql-ctes/ |url-status=dead }} mysqlserverteam.com</ref> [https://kb.tableau.com/articles/howto/using-common-table-expressions 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.<ref>[http://www.paragoncorporation.com/ArticleDetail.aspx?ArticleID=24 Paragon corporation: Using PostgreSQL User-Defined Functions to solve the Tree Problem], February 15, 2004, accessed September 19, 2015</ref>

== Common table expression == {{expand section|date=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 <code>SELECT</code>, <code>INSERT</code>, <code>UPDATE</code>, or <code>DELETE</code> 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),<ref>{{Cite web| title=Firebird 2.5 Language Reference Update | url=https://firebirdsql.org/file/documentation/reference_manuals/reference_material/Firebird-2.5-LangRef-Update.pdf | archive-url=https://web.archive.org/web/20111114164747/http://www.firebirdsql.org/file/documentation/reference_manuals/reference_material/Firebird-2.5-LangRef-Update.pdf | archive-date=2011-11-14}}</ref> Microsoft SQL Server (starting with version 2005), Oracle (with recursion since 11g release 2), PostgreSQL (since 8.4), MariaDB (since 10.2<ref>{{Cite web |title=MariaDB 10.2.0 Changelog |url=https://mariadb.com/kb/en/mariadb-1020-changelog/ |access-date=2024-12-22 |website=MariaDB KnowledgeBase}}</ref>), MySQL (since 8.0), SQLite (since 3.8.3), HyperSQL, Informix (since 14.10),<ref>possible before 14.10 with temp tables https://stackoverflow.com/questions/42579298/why-does-a-with-clause-give-a-syntax-error-on-informix</ref> Google BigQuery, Sybase (starting with version 9), Vertica, H2 (experimental),<ref>{{Cite web|url=http://www.h2database.com/html/advanced.html#recursive_queries|title = Advanced}}</ref> and many others. Oracle calls CTEs "subquery factoring".<ref name="MortonSands2010">{{cite book|author1=Karen Morton|author2=Robyn Sands|author3=Jared Still|author4=Riyaj Shamsudeen |author5=Kerry Osborne|title=Pro Oracle SQL|url=https://books.google.com/books?id=nrwu-f4JwjcC&pg=PA283|year=2010|publisher=Apress|isbn=978-1-4302-3228-5|page=283}}</ref>

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

<syntaxhighlight lang="sql"> WITH [RECURSIVE] with_query [, ...] SELECT ... </syntaxhighlight>

where <code>with_query</code>'s syntax is:

<syntaxhighlight lang="sql"> query_name [ (column_name [,...]) ] AS (SELECT ...) </syntaxhighlight>

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 <code>LEVEL</code> below); if these are desired, they have to be created in the code. See MSDN documentation<ref name="msdnRCTEs"/> or IBM documentation<ref>{{Cite web|url=http://publib.boulder.ibm.com/infocenter/dzichelp/v2r2/topic/com.ibm.db2z9.doc.apsg/src/tpc/db2z_xmprecursivecte.htm|title = IBM Docs}}</ref><ref>{{Cite web|url=http://publib.boulder.ibm.com/infocenter/iseries/v5r4/index.jsp?topic=%2Fsqlp%2Frbafyrecursivequeries.htm|title=IBM Docs}}</ref> for tutorial examples.

The <code>RECURSIVE</code> keyword is not usually needed after WITH in systems other than PostgreSQL.<ref name="ObeHsu2012">{{cite book|author1=Regina Obe|author2=Leo Hsu|title=PostgreSQL: Up and Running|url=https://books.google.com/books?id=Q8jkIZkMTPcC&pg=PA94|year=2012|publisher=O'Reilly Media|isbn=978-1-4493-2633-3|page=94}}</ref>

In SQL:1999 a recursive (CTE) query may appear anywhere a query is allowed. It's possible, for example, to name the result using <code>CREATE</code> [<code>RECURSIVE</code>] <code>VIEW</code>.<ref>{{cite book|author1=Jim Melton|author2=Alan R. Simon|title=SQL:1999: Understanding Relational Language Components|url=https://books.google.com/books?id=wyhXvU0Eyg0C&pg=PA352|year=2002|publisher=Morgan Kaufmann|isbn=978-1-55860-456-8|page=352}}</ref> Using a CTE inside an <code>INSERT INTO</code>, 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.<ref name="ChamberlinChamberlin1998">{{cite book|author1=Don Chamberlin|title=A Complete Guide to DB2 Universal Database|url=https://books.google.com/books?id=hb4zskzHrWYC&pg=PA253|year=1998|publisher=Morgan Kaufmann|isbn=978-1-55860-482-7|pages=253–254}}</ref>

Some Databases, like PostgreSQL, support a shorter CREATE RECURSIVE VIEW format which is internally translated into WITH RECURSIVE coding.<ref>{{Cite web|url=https://www.postgresql.org/docs/10/static/sql-createview.html|title = Create View|date = 10 February 2022}}</ref>

An example of a recursive query computing the factorial of numbers from 0 to 9 is the following: <syntaxhighlight lang="sql"> 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; </syntaxhighlight>

== CONNECT BY == An alternative syntax is the non-standard <code>CONNECT BY</code> construct; introduced by Oracle in the 1980s.<ref>{{Cite book | last1 = Benedikt | first1 = M. | last2 = Senellart | first2 = P. | doi = 10.1007/978-1-4614-1168-0_10 | chapter = Databases | title = Computer Science. The Hardware, Software and Heart of It | page = 189 | year = 2011 | isbn = 978-1-4614-1167-3 | editor1-last = Blum | editor1-first = Edward K. | editor2-last = Aho | editor2-first = Alfred V. }}</ref> 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.<ref name="MishraBeaulieu2004">{{cite book|author1=Sanjay Mishra|author2=Alan Beaulieu|title=Mastering Oracle SQL|url=https://books.google.com/books?id=r5vbGgz7TFsC&pg=PT227|year=2004|publisher=O'Reilly Media, Inc.|isbn=978-0-596-00632-7|page=227}}</ref>

<code>CONNECT BY</code> is supported by Snowflake, EnterpriseDB,<ref>[http://www.enterprisedb.com/documentation/hierarchical-queries.html Hierarchical Queries] {{Webarchive|url=https://web.archive.org/web/20080621031850/http://www.enterprisedb.com/documentation/hierarchical-queries.html |date=2008-06-21 }}, EnterpriseDB</ref> Oracle database,<ref>[http://download.oracle.com/docs/cd/B19306_01/server.102/b14200/queries003.htm Hierarchical Queries], Oracle</ref> CUBRID,<ref>{{cite web|title=CUBRID Hierarchical Query|url=http://www.cubrid.org/manual/841/en/Hierarchical%20Query|access-date=11 February 2013|archive-date=14 February 2013|archive-url=https://web.archive.org/web/20130214060900/http://www.cubrid.org/manual/841/en/Hierarchical%20Query|url-status=dead}}</ref> IBM Informix<ref>[https://www-01.ibm.com/support/knowledgecenter/SSGU8G_12.1.0/com.ibm.sqls.doc/ids_sqs_2033.htm Hierarchical Clause], IBM Informix</ref> and IBM Db2 although only if it is enabled as a compatibility mode.<ref name="Gennick2010">{{cite book|author=Jonathan Gennick|title=SQL Pocket Guide|url=https://books.google.com/books?id=rEAFRzMe_SMC&pg=PA8|year=2010|publisher=O'Reilly Media, Inc.|isbn=978-1-4493-9409-7|page=8|edition=3rd}}</ref> The syntax is as follows:

<syntaxhighlight lang="sql"> 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 ... ] ... </syntaxhighlight>

; For example,

<syntaxhighlight lang="sql"> SELECT LEVEL, LPAD (' ', 2 * (LEVEL - 1)) || ename "employee", empno, mgr "manager" FROM emp START WITH mgr IS NULL CONNECT BY PRIOR empno = mgr; </syntaxhighlight>

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 === * {{mono|LEVEL}} * {{mono|CONNECT_BY_ISLEAF}} * {{mono|CONNECT_BY_ISCYCLE}} * {{mono|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:

<syntaxhighlight lang="sql"> 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"; </syntaxhighlight>

=== Functions === * <code>SYS_CONNECT_BY_PATH</code>

== See also == * Datalog also implements fixpoint queries * Regular path queries are a specific kind of recursive query in graph databases * Deductive databases * Hierarchical model * Recursive join * Reachability * Transitive closure * Tree structure

== References == {{Reflist}}

== Further reading == * {{cite book|author=C. J. Date|author-link=C. J. Date|title=SQL and Relational Theory: How to Write Accurate SQL Code|year=2011|publisher=O'Reilly Media|isbn=978-1-4493-1640-2|edition=2nd|pages=159–163}} '''Academic textbooks'''. Note that these cover only the SQL:1999 standard (and Datalog), but not the Oracle extension. * {{cite book|author1=Abraham Silberschatz|author2=Henry Korth|author3=S. Sudarshan|title=Database System Concepts|year=2010|edition=6th|publisher=McGraw-Hill|isbn=978-0-07-352332-3|pages=187–192}} * {{cite book|author1=Raghu Ramakrishnan|author2=Johannes Gehrke|title=Database management systems|year=2003|publisher=McGraw-Hill|isbn=978-0-07-246563-1|edition=3rd}} Chapter 24. * {{cite book|author1=Hector Garcia-Molina|author2=Jeffrey D. Ullman|author3=Jennifer Widom|title=Database systems: the complete book|year=2009|publisher=Pearson Prentice Hall|isbn=978-0-13-187325-4|edition=2nd|pages=437–445}}

== External links == * {{Cite web | title=sql - Cycle detection with recursive subquery factoring - Stack Overflow | url=https://stackoverflow.com/questions/1731889/cycle-detection-with-recursive-subquery-factoring | access-date=2026-02-04 | website=stackoverflow.com}} * {{Cite web | title=SQL Server: are the recursive CTE's really set-based? at EXPLAIN EXTENDED | url=http://explainextended.com/2009/11/18/sql-server-are-the-recursive-ctes-really-set-based/ | access-date=2026-02-04 | website=explainextended.com}} * {{Cite web | title=Understanding the WITH Clause {{!}} Jonathan Gennick | url=http://gennick.com/with.html | archive-url=https://web.archive.org/web/20131114094211/http://gennick.com/with.html | archive-date=2013-11-14 | access-date=2026-02-04}} * {{Cite web| title=SQL: Recursion | url=http://www.cs.duke.edu/courses/fall04/cps116/lectures/11-recursion.pdf | archive-url=https://web.archive.org/web/20050117015207/http://www.cs.duke.edu:80/courses/fall04/cps116/lectures/11-recursion.pdf | archive-date=2005-01-17}} * {{Cite web | title=BlackTDN :: MSSQL Usando Consulta CTE Recursiva para montagem de Tree | url=http://www.blacktdn.com.br/2015/06/blacktdn-mssql-usando-consulta-cte.html | access-date=2026-02-04 | website=www.blacktdn.com.br}}

{{DEFAULTSORT:Hierarchical Query}} Category:Database management systems Category:SQL Category:Articles with example SQL code Category:Recursion