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 (CTEs). Unlike the Oracle extension described below, the recursive CTEs were designed with fixpoint semantics from the beginning.[1] The 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] Oracle 11g Release 2, IBM Informix version 11.50+, CUBRID and MySQL 8.0.1+,[6]. Tableau and TIBCO Spotfire do not support CTEs.

An alternative syntax is the non-standard CONNECT BY construct; it was introduced by Oracle in the 1980s.[7] 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.[8]

Without Common-table-expressions or a connected-by clause it is possible to achieve hierarchical queries with user-defined recursive functions.[9]

CONNECT BY

CONNECT BY is supported by EnterpriseDB,[10]Oracle database,[11]CUBRID,[12]IBM Informix[13] and DB2 although only if it is enabled as a compatibility mode.[14] 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

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, DB2, Firebird,[15]Microsoft SQL Server, Oracle (with recursion since 11g release 2), PostgreSQL (since 8.4), MariaDB (since 10.2), SQLite (since 3.8.3), HyperSQL and H2 (experimental).[16] Oracle calls CTEs "subquery factoring".[17] Though MySQL does not support common table expressions there exists a demonstration of WITH RECURSIVE emulation[18] using stored procedures, upcoming version 8.0 plans support.[19]

The syntax for a Recursive CTE is as follows:

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

where with_query's syntax is:

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

Recursive CTEs (or "recursive subquery factoring"[20] in Oracle jargon) 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 above); if these are desired, they have to be created in the code. See MSDN documentation[2] or IBM documentation[21][22] for tutorial examples.

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

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.[24] 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.[25]

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;

See also

References

  1. ^ a b Jim Melton; Alan R. Simon (2002). SQL:1999: Understanding Relational Language Components. Morgan Kaufmann. ISBN 978-1-55860-456-8. 
  2. ^ a b Microsoft. "Recursive Queries Using Common Table Expressions". Retrieved . 
  3. ^ Helen Borrie (2008-07-15). "Firebird 2.1 Release Notes". Retrieved . 
  4. ^ "WITH Queries".  PostgreSQL
  5. ^ "WITH Clause".  SQLite
  6. ^ "MySQL 8.0 Labs: [Recursive] Common Table Expressions in MySQL (CTEs)".  mysqlserverteam.com
  7. ^ Benedikt, M.; Senellart, P. (2011). "Databases". In Blum, Edward K.; Aho, Alfred V. Computer Science. The Hardware, Software and Heart of It. p. 189. doi:10.1007/978-1-4614-1168-0_10. ISBN 978-1-4614-1167-3. 
  8. ^ Sanjay Mishra; Alan Beaulieu (2004). Mastering Oracle SQL. O'Reilly Media, Inc. p. 227. ISBN 978-0-596-00632-7. 
  9. ^ Paragon corporation: Using PostgreSQL User-Defined Functions to solve the Tree Problem, February 15, 2004, accessed September 19, 2015
  10. ^ Hierarchical Queries, EnterpriseDB
  11. ^ Hierarchical Queries, Oracle
  12. ^ "CUBRID Hierarchical Query". Retrieved 2013. 
  13. ^ Hierarchical Clause, IBM Informix
  14. ^ Jonathan Gennick (2010). SQL Pocket Guide (3rd ed.). O'Reilly Media, Inc. p. 8. ISBN 978-1-4493-9409-7. 
  15. ^ Comparison of relational database management systems#Database capabilities
  16. ^ http://www.h2database.com/html/advanced.html#recursive_queries
  17. ^ Karen Morton; Robyn Sands; Jared Still; Riyaj Shamsudeen; Kerry Osborne (2010). Pro Oracle SQL. Apress. p. 283. ISBN 978-1-4302-3228-5. 
  18. ^ https://planet.mysql.com/entry/?id=599259
  19. ^ https://dev.mysql.com/doc/refman/8.0/en/with.html
  20. ^ Karen Morton; Robyn Sands; Jared Still; Riyaj Shamsudeen; Kerry Osborne (2010). Pro Oracle SQL. Apress. p. 304. ISBN 978-1-4302-3228-5. 
  21. ^ http://publib.boulder.ibm.com/infocenter/dzichelp/v2r2/topic/com.ibm.db2z9.doc.apsg/src/tpc/db2z_xmprecursivecte.htm
  22. ^ http://publib.boulder.ibm.com/infocenter/iseries/v5r4/index.jsp?topic=%2Fsqlp%2Frbafyrecursivequeries.htm
  23. ^ Regina Obe; Leo Hsu (2012). PostgreSQL: Up and Running. O'Reilly Media. p. 94. ISBN 978-1-4493-2633-3. 
  24. ^ Jim Melton; Alan R. Simon (2002). SQL:1999: Understanding Relational Language Components. Morgan Kaufmann. p. 352. ISBN 978-1-55860-456-8. 
  25. ^ Don Chamberlin (1998). A Complete Guide to DB2 Universal Database. Morgan Kaufmann. pp. 253-254. ISBN 978-1-55860-482-7. 

Further reading

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


  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Hierarchical_and_recursive_queries_in_SQL
 



 

Connect with defaultLogic
What We've Done
Led Digital Marketing Efforts of Top 500 e-Retailers.
Worked with Top Brands at Leading Agencies.
Successfully Managed Over $50 million in Digital Ad Spend.
Developed Strategies and Processes that Enabled Brands to Grow During an Economic Downturn.
Taught Advanced Internet Marketing Strategies at the graduate level.


Manage research, learning and skills at defaultLogic. Create an account using LinkedIn or facebook to manage and organize your Digital Marketing and Technology knowledge. defaultLogic works like a shopping cart for information -- helping you to save, discuss and share.


  Contact Us