Hierarchical (recursive) queries

To understand recursion, you first need to understand recursion. Perhaps that is why recursive queries are used so rarely. Surely you imagine what a SQL query is, I will tell you how recursive queries differ from ordinary ones. Subject turned voluminous, get ready for a long reading. Basically it will be about Oracle, but other DBMS are mentioned.


')

The essence of the problem

Most modern DBMSs (Database Management System) are relational, i.e. present data in the form of a two-dimensional table, in which there are rows (records) and columns (fields of records). But in practice, we often encounter a different data organization, namely hierarchical.

Take a look at the list of files on your computer: they are all organized in a tree. Similarly, you can submit books in the library: Library-> Hall-> Wardrobe-> Shelf-> Book. The same and articles on the site: Site-> Section-> Subsection-> Article. Examples can be given for a long time. However, it is still possible to divide everything into separate tables: a table for storing the list of libraries, another table for the list of halls, a third for cabinets, etc. But if the nesting depth is not known in advance, or this nesting can change, then you can’t get rid of the hierarchy.

The problem is that data that has a hierarchical structure is very poorly represented in the relational model. The SQL-92 standard does not have the means to process them.

But such tools appeared in the standard SQL-1999. True, by that time Oracle already had its own CONNECT BY operator. Despite this, in SQL-1999 the syntax of recursive queries is completely different from the syntax CONNECT BY in Oracle and uses the keyword WITH. The implementation of recursive queries in other DBMSs was somewhat delayed, as it appeared in MS SQL Server only in version 2005.

Just as in the syntax, there are differences in terminology. In Oracle, queries that are commonly discussed are called “hierarchical,” while for others, “recursive”. The essence of this does not change, I will use both.

From words to deeds!

For the demonstration we will use the directory structure, we will need a test table consisting of 3 fields:
id - id
pid is the parent ID (refers to the id of another entry in the same table),
title - the name of the directory (instead, it can be anything, even a few fields or links to other tables).

create table test_table (
  id int,
  pid int,
  title varchar(256)
);

mySQL, . , Oracle : int — number, varchar — varchar2.

. , . , , , , .

insert into test_table values (1, null, '');

, . , . -, SELECT * FROM test_table :

  ID        PID TITLE
---- ---------- --------------------
   1            
   2          1 
   3          2  "  "
   4          1 
   5          1 
   6          3  
   7          3  1
   8          3  2
   9          8  1
  10          5 

. .

mySQL

mySQL – , php ( , , , “mySQL tree” ..).

, , , . , .

- php. mySQL. , , ( ). , AJAX. pid , . , , .

SQL-1999

SQL-92, , . :-), (LOB), SIMILAR DISTINCT, , , . , .

, WITH. . :

WITH [recursive] __ [ ( ) ]
AS () 
 

MS SQL RECURSIVE, . . DB2, Sybase iAnywhere, MS SQL, 2005, , SQL 1999.

:

WITH RECURSIVE
 Rec (id, pid, title)
 AS (
   SELECT id, pid, title FROM test_table
   UNION ALL
   SELECT Rec.id, Rec.pid, Rec.title
    FROM Rec, test_table
    WHERE Rec.id = test_table.pid
   )
 SELECT * FROM Rec
 WHERE pid is null;

Rec, , test_table. Rec , : WHERE Rec.id = test_table.pid. , , pid , .. .

, MS SQL Server 2005 , . . , .

MS SQL 2008 hierarchyid. XaocCPS .

Oracle

- Oracle! . Oracle 8- , . . . , , .

: . ?



, – CONNECT BY, “” .

START WITH , .. ( ) . , : pid is null, id = 1, substr(title, 1, 1) = ‘’.

CONNECT BY . , . - while . , 10 : rownum<=10 – 10 . ? , – 1- . , rownum , , 1 . . .

? , PRIOR. , + -. “ ” – , . pid = PRIOR id ( PRIOR id = pid, , …).

? , START WITH, . PRIOR. , , (pid) , id . . , , .

, Oracle. , . , , - . id pid. , Oracle LEVEL. , . , 1- 1, 2, — 3 ..

SELECT level, id, pid, title
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid;

LEVEL         ID        PID TITLE
------ ---------- ---------- -------------------
     1          1            
     2          2          1 
     3          3          2  "  "
     4          6          3  
     4          7          3  1
     4          8          3  2
     5          9          8  1
     2          4          1 
     2          5          1 
     3         10          5 

. . , -, . , : ORDER BY title.

SELECT level, id, pid, title
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid
ORDER BY title;

LEVEL         ID        PID TITLE
------ ---------- ---------- -------------------
     2          2          1 
     4          6          3  
     2          5          1 
     3         10          5 
     2          4          1 
     3          3          2  "  "
     4          7          3  1
     4          8          3  2
     1          1            
     5          9          8  1

, ! . ? ( level), ORDER BY. , , SIBLINGS. ORDER SIBLINGS BY title – .

, , . “” , :

SELECT lpad(' ', 3*level)||title as Tree
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid
ORDER SIBLINGS BY title;

TREE
-----------------------------
   
      
          "  "
             
             1
             2
                1
      
         
      

, , .

, , : /home/maovrn/documents/ ..? . : Oracle . SYS_CONNECT_BY_PATH(). : -. , : SYS_CONNECT_BY_PATH(title, ‘/’).

, . , , WHERE. . , FROM. “ 1”, id=9:

SELECT SYS_CONNECT_BY_PATH(title, '/') as Path
FROM test_table
WHERE id=9
START WITH pid is null
CONNECT BY PRIOR id = pid;

PATH
----------------------------------------------------
/// "  "/ 2/ 1

CONNECT_BY_ISLEAF. , LEVEL. 0 1. – 0. , “”, CONNECT_BY_ISLEAF 1.

? , . PRIOR, . CONNECT_BY_ROOT, ( !) , .. .

SELECT id, pid, title, level,
 CONNECT_BY_ISLEAF as IsLeaf,
 PRIOR title as Parent,
 CONNECT_BY_ROOT title as Root
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid
ORDER SIBLINGS BY title;

ID PID TITLE                LEVEL LEAF PARENT               ROOT
-- --- -------------------- ----- ---- -------------------- ------
1                     1     0    
2  1                 2     0                   
3  2    "  "  3     0                  
6  3             4     1     "  "  
7  3    1               4     1     "  "  
8  3    2               4     0     "  "  
9  8    1             5     1     2               
5  1                   2     0                   
10 5              3     1                    
4  1                  2     1                   

, , Oracle . , , – , . “” NOCYCLE CONNECT BY – . . “” , CONNECT_BY_ISCYCLE – 0, , , 1.

, . ; , ( commit – ):

update test_table set pid=10 where id=5;

- , , , , . , , .. . START WITH, – . . :

SELECT CONNECT_BY_ISCYCLE as cycl, id, pid, title
FROM test_table
START WITH id=5
CONNECT BY NOCYCLE PRIOR id = pid;

CYCL         ID        PID TITLE
---- ---------- ---------- ----------
   0          5         10 
   1         10          5 

, .

, . , id 1, . . , .

. :

DELETE FROM test_table WHERE id IN (3, 5);

? -, 1 , . id , , :

SELECT max(id) FROM test_table

1 max . ! – .

SELECT rownum as rn FROM dual
 CONNECT BY level <= (SELECT max(id) FROM test_table);

“SELECT … FROM dual” , , . Dual – , . ‘X’. , .

, , , pivot. , . dual Oracle .

, , , :

SELECT sq.rn
FROM (SELECT rownum as rn FROM dual
 CONNECT BY level <= (SELECT max(id) FROM test_table)) sq
WHERE sq.rn not in (SELECT id FROM test_table)
ORDER BY rn;

  RN
----
   3
   5

. , . ROLLBACK. COMMIT!