5段階でSQL再帰的CTEを書く方法を学んでください

23352 ワード
postgres yugabytedb database sql テキストリンク
ノードの階層に従うグラフデータベースを必要としません.SQLは結合、自己結合、およびその前の結果に反復的に結合することもできます.このWITH RECURSIVE 節はしばしば「再帰的なCTE」と呼ばれます.これは、開発者が手続き言語に使用する抽象化のビットを必要とする場合があります.ここではどのように“手動で”2つの最初のレベルに参加することによって説明している、再帰せずに、さらに“再帰”に移動します.最初の2つのレベルから始まる簡単にロジックを検証するのに役立ちます.

( 0 )例: EMPテーブルの作成


最古のサンプルテーブルを作成します.
CREATE TABLE emp (empno, ename,    job,        mgr,   hiredate,     sal, comm, deptno, email, other_info) as values
(7369, 'SMITH',  'CLERK',     7902, '1980-12-17',  800, NULL,   20,'[email protected]', '{"skills":["accounting"]}'),
(7499, 'ALLEN',  'SALESMAN',  7698, '1981-02-20', 1600,  300,   30,'[email protected]', null),
(7521, 'WARD',   'SALESMAN',  7698, '1981-02-22', 1250,  500,   30,'[email protected]', null),
(7566, 'JONES',  'MANAGER',   7839, '1981-04-02', 2975, NULL,   20,'[email protected]', null),
(7654, 'MARTIN', 'SALESMAN',  7698, '1981-09-28', 1250, 1400,   30,'[email protected]', null),
(7698, 'BLAKE',  'MANAGER',   7839, '1981-05-01', 2850, NULL,   30,'[email protected]', null),
(7782, 'CLARK',  'MANAGER',   7839, '1981-06-09', 2450, NULL,   10,'[email protected]', '{"skills":["C","C++","SQL"]}'),
(7788, 'SCOTT',  'ANALYST',   7566, '1982-12-09', 3000, NULL,   20,'[email protected]', '{"cat":"tiger"}'),
(7839, 'KING',   'PRESIDENT', NULL, '1981-11-17', 5000, NULL,   10,'[email protected]', null),
(7844, 'TURNER', 'SALESMAN',  7698, '1981-09-08', 1500,    0,   30,'[email protected]', null),
(7876, 'ADAMS',  'CLERK',     7788, '1983-01-12', 1100, NULL,   20,'[email protected]', null),
(7900, 'JAMES',  'CLERK',     7698, '1981-12-03',  950, NULL,   30,'[email protected]', null),
(7902, 'FORD',   'ANALYST',   7566, '1981-12-03', 3000, NULL,   20,'[email protected]', '{"skills":["SQL","CQL"]}'),
(7934, 'MILLER', 'CLERK',     7782, '1982-01-23', 1300, NULL,   10,'[email protected]', null)
;
mgrからempnoへの自己参照は以下のように宣言できます:
ALTER TABLE emp ADD PRIMARY KEY (empno)
;
ALTER TABLE emp ADD FOREIGN KEY (mgr) REFERENCES emp (empno)
;
これは必要ではありませんが、一貫性テストではなく、ビジネスロジックに集中できるようにクエリの正当性を保証します.

( 1 )ルートを見つける(レベル0 )


最初のステップはグラフのルートを識別することです.あなたは従業員によって開始し、自分のマネージャーを表示したり、マンガで起動し、その従業員を表示しますか?私は後者をします.階層の根元は管理者のないものですwhere mgr is null )
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null
;
結果は単純です.
yugabyte-> ;

 empno | ename | mgr
-------+-------+-----
  7839 | KING  |
(1 row)

yugabyte=>

（2）このレベル0をwith句で定義する


CTE ( common table expression )に入れますlevel0 私はそれから選択します.
-- (2) define the root as as level 0 in a CTE
with recursive
level0 as (
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null
) 
-- (2) query this level
select * from level0
;
結果は同じです.一番上のマネージャーはキングです.
yugabyte-> ;

 empno | ename | mgr
-------+-------+-----
  7839 | KING  |
(1 row)

yugabyte=>
私はちょうど1つずつブロックを構築しています.そして、私は前のステップと何が加えられるかについて明確にするために、コメントを残しました.私は既にwith句で再帰的に追加しますが、現時点では、自己参照がないので、1回だけ繰り返します.

( 3 )次のレベルへの結合を定義する


私のレベル0が定義されているのでemp 次のレベルを取得するには、次のレベルを取得します.
-- (2) define the root as as level 0 in a CTE
with recursive
level0 as (
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null
) 
-- (3) join employees with level 0
select emp.empno,emp.ename,emp.mgr
,mgr.ename mgr_name
from emp
join level0 mgr on mgr.empno=emp.mgr
;
私はレベル0としてレベルをラベルしているmgr なぜなら、この新しいレベルの従業員のマネージャーになるからですemp . 次に、結合mgr.empno=emp.mgr つのレベルをリンクします.結合の結果ではmgr.ename ASmgr_name 同じ行のマネージャーの名前を見るために.
だからここでは従業員はキングを参照してください:
yugabyte-> ;

 empno | ename | mgr  | mgr_name
------------+-------+------+----------
  7698 | BLAKE | 7839 | KING
  7566 | JONES | 7839 | KING
  7782 | CLARK | 7839 | KING
(3 rows)

yugabyte=>

( 4 ) 2つのレベルを結合します


マネージャ名を示すのは1ステップでしたが、階層全体を表示するには、すべてのレベルから行を連結する必要があります.私は2つの最初のレベルから始まります.私はすべての組合が必要です.このため、with句で自分のjoinクエリを移動し、leveln . 名前が付けられたのにlevel1 何故ならlevel0 しかし、目標は、次のレベルの抽象化することです.私はすべての2つを結合するので、彼らは同じ列が必要です.leveln マネージャ名をmgr_name そこで、空の文字列としてクエリを行うときにこれを追加しますlevel0
-- (2) define the root as as level 0 in a CTE
with recursive
level0 as (
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null
),
-- (4) put the second level in the WITH clause
leveln as (
-- (3) join employees with level 0
select emp.empno,emp.ename,emp.mgr
,mgr.ename mgr_name
from emp
join level0 mgr on mgr.empno=emp.mgr
)
-- (4) concatenate the two levels
select *,'' mgr_name from level0
union all
select *             from leveln
;
これはよく見えるようになります.
yugabyte-> ;

 empno | ename | mgr  | mgr_name
------------+-------+------+----------
  7839 | KING  |      |
  7698 | BLAKE | 7839 | KING
  7566 | JONES | 7839 | KING
  7782 | CLARK | 7839 | KING
(4 rows)

yugabyte=>
これはあなたの結果を検証できる場所です.次のステップは自動的に再帰を加えることです.

( 5 ) 1つの再帰式でそれを取得する


私は2つの最初のレベルの結果を検証したので、それを再帰的に取得する時間です.加わる代わりにlevel0 私が加わるleveln これは以前の結果です.そして、私はこのすべてに組合を動かしますleveln CTE
-- (2) define the root as as level 0 in a CTE
with recursive
level0 as (
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null
),
-- (4) put the second level in the WITH clause
leveln as (
-- (5) put the UNION ALL in the recursive level
-- (4) concatenate the two levels
select *,'' mgr_name from level0
union all
-- (3) join employees with level 0
select emp.empno,emp.ename,emp.mgr
,mgr.ename mgr_name
from emp
-- (5) change level0 to leveln to join iteratively
join leveln mgr on mgr.empno=emp.mgr
)
-- (5) query this level n
select *             from leveln
;
最初の2つのレベルで結合を検証した場合、この最後の変換は自動的です.実行時には、最初の反復は最初のレベルを取得し、unionの2番目の部分はすべて前の結果との結合のために行を持たない.次の繰り返しで結合の結果が追加されます.そして、私たちが葉っぱにいるので、joinが行を返さないまで、前の結果が管理者のリストとみなされて、従業員はいません.
yugabyte-> ;

 empno | ename  | mgr  | mgr_name
------------+--------+------+----------
  7839 | KING   |      |
  7698 | BLAKE  | 7839 | KING
  7566 | JONES  | 7839 | KING
  7782 | CLARK  | 7839 | KING
  7788 | SCOTT  | 7566 | JONES
  7902 | FORD   | 7566 | JONES
  7844 | TURNER | 7698 | BLAKE
  7499 | ALLEN  | 7698 | BLAKE
  7521 | WARD   | 7698 | BLAKE
  7654 | MARTIN | 7698 | BLAKE
  7900 | JAMES  | 7698 | BLAKE
  7934 | MILLER | 7782 | CLARK
  7876 | ADAMS  | 7788 | SCOTT
  7369 | SMITH  | 7902 | FORD
(14 rows)

yugabyte=>
これは魔法がどこにあるのか.慎重にあなたの最初の2つのレベルをテストする場合は、すべての他のクエリは、その前の結果に参加することによって反復的な反復を変換することによって来る.私が最初のレベルを残したことに注意してくださいlevel0 CTEあなたはそれを置くことができますleveln しかし、私はそれがこれのように読みやすいと思います.
実行計画では、それを再帰的な組合として見る
                                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on leveln  (cost=20.23..22.86 rows=131 width=72) (actual time=0.023..0.281 rows=14 loops=1)
   CTE leveln
     ->  Recursive Union  (cost=0.00..20.23 rows=131 width=46) (actual time=0.021..0.269 rows=14 loops=1)
           ->  Seq Scan on emp  (cost=0.00..1.14 rows=1 width=46) (actual time=0.019..0.021 rows=1 loops=1)
                 Filter: (mgr IS NULL)
           ->  Hash Join  (cost=0.33..1.65 rows=13 width=46) (actual time=0.054..0.058 rows=3 loops=4)
                 Hash Cond: (emp_1.mgr = mgr.empno)
                 ->  Seq Scan on emp emp_1  (cost=0.00..1.14 rows=14 width=14) (actual time=0.002..0.003 rows=14 loops=4)
                 ->  Hash  (cost=0.20..0.20 rows=10 width=36) (actual time=0.044..0.044 rows=4 loops=4)
                       ->  WorkTable Scan on leveln mgr  (cost=0.00..0.20 rows=10 width=36) (actual time=0.001..0.001 rows=4 loops=4)
数loops 番目の部分が実行された方法を多くの時間を指示します.これはPostgreSQLとyugabytedbでも同じです.
2.レイアウトソリューション-水平レイアウト<1>
#BOJ 9663 N-Queen