隣接リストモデルから入れ子集合モデルへの変換クエリ

#まえがき
木構造に興味持ったので、あそんでみようと思いました。

#参考文献

いろいろ書いてあんなーって感じです。

[プログラマのためのSQLグラフ原論 リレーショナルデータベースで木と階層構造を扱うために](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AESQL%E3%82%B0%E3%83%A9%E3%83%95%E5%8E%9F%E8%AB%96-%E3%83%AA%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9%E3%81%A7%E6%9C%A8%E3%81%A8%E9%9A%8E%E5%B1%A4%E6%A7%8B%E9%80%A0%E3%82%92%E6%89%B1%E3%81%86%E3%81%9F%E3%82%81%E3%81%AB-%E3%82%B8%E3%83%A7%E3%83%BC%E3%83%BB%E3%82%BB%E3%83%AB%E3%82%B3/dp/4798144576)

#ランダムで作るやつ
>適当に。開始ノード３つぐらい狙って。

```sql
DROP TABLE test____$_____ PURGE;
CREATE TABLE test____$_____ AS WITH src AS ( SELECT LEVEL AS rn FROM dual CONNECT BY LEVEL <= 26 ) SELECT CHR(64 + decode(MOD(s1.rn, 26), 0, 26, MOD(s1.rn, 26) ) ) AS node ,MIN(CASE WHEN s2.rn <= 23 THEN CHR(64 + decode(MOD(s2.rn, 26), 0, 26, MOD(s2.rn, 26) ) ) ELSE NULL END) KEEP (DENSE_RANK FIRST ORDER BY dbms_random.VALUE) AS oya_node FROM src s1 , src s2 GROUP BY CHR(64 + decode(MOD(s1.rn, 26), 0, 26, MOD(s1.rn, 26) ) ) ; 
```

#ランダムデータでバグでないかモノできてから確認する用データ

```sql
WITH sub AS (
	SELECT
		DENSE_RANK() OVER(
			ORDER BY
				CONNECT_BY_ROOT node
		) AS grp
		, level AS lv
		, ROW_NUMBER() OVER(
			PARTITION BY CONNECT_BY_ROOT node, level
			ORDER BY
				ROWNUM
		) AS rn
		, node
		, oya_node
		, CONNECT_BY_ISLEAF AS isleaf
		, CONNECT_BY_ROOT node AS root_val
		, sys_connect_by_path(node, ',') AS ph
	FROM
		test____$_____
	START WITH
		oya_node IS NULL
	CONNECT BY
		PRIOR node = oya_node
) SELECT
	s1.*
	, CASE
			WHEN NOT EXISTS (
				SELECT
					1
				FROM
					sub s2
				WHERE
					s1.root_val = s2.root_val
					AND s1.lv > s2.lv
			) THEN 1
			ELSE 0
		END
	AS root_flg
  FROM
	sub s1
ORDER BY
	s1.grp
	, s1.lv
	, s1.rn;
```

#モノをつくるためのデータ
```sql
DROP TABLE test____$_____ PURGE;
CREATE TABLE test____$_____ ( node VARCHAR2(4 BYTE), oya_node VARCHAR2(4 BYTE) ) ;
SET DEFINE OFF;
INSERT INTO test____$_____ (node,oya_node) VALUES ('A','S');
INSERT INTO test____$_____ (node,oya_node) VALUES ('B','H');
INSERT INTO test____$_____ (node,oya_node) VALUES ('C',NULL);
INSERT INTO test____$_____ (node,oya_node) VALUES ('D','O');
INSERT INTO test____$_____ (node,oya_node) VALUES ('E','M');
INSERT INTO test____$_____ (node,oya_node) VALUES ('F','U');
INSERT INTO test____$_____ (node,oya_node) VALUES ('G','T');
INSERT INTO test____$_____ (node,oya_node) VALUES ('H',NULL);
INSERT INTO test____$_____ (node,oya_node) VALUES ('I','M');
INSERT INTO test____$_____ (node,oya_node) VALUES ('J','B');
INSERT INTO test____$_____ (node,oya_node) VALUES ('K','I');
INSERT INTO test____$_____ (node,oya_node) VALUES ('L','I');
INSERT INTO test____$_____ (node,oya_node) VALUES ('M','C');
INSERT INTO test____$_____ (node,oya_node) VALUES ('N','K');
INSERT INTO test____$_____ (node,oya_node) VALUES ('O','N');
INSERT INTO test____$_____ (node,oya_node) VALUES ('P','W');
INSERT INTO test____$_____ (node,oya_node) VALUES ('Q','B');
INSERT INTO test____$_____ (node,oya_node) VALUES ('R',NULL);
INSERT INTO test____$_____ (node,oya_node) VALUES ('S','I');
INSERT INTO test____$_____ (node,oya_node) VALUES ('T',NULL);
INSERT INTO test____$_____ (node,oya_node) VALUES ('U','B');
INSERT INTO test____$_____ (node,oya_node) VALUES ('V','I');
INSERT INTO test____$_____ (node,oya_node) VALUES ('W','E');
INSERT INTO test____$_____ (node,oya_node) VALUES ('X','O');
INSERT INTO test____$_____ (node,oya_node) VALUES ('Y','J');
INSERT INTO test____$_____ (node,oya_node) VALUES ('Z','U');
COMMIT;
```


#任意のノードから自身を除く子ノードの個数を求める関数

参考にさせてもらいました。ありがとうございます。

[木構造の親または子を再帰的に取得する](https://qiita.com/neko_the_shadow/items/d401e0c23892b0d53c2a)

```sql
DROP FUNCTION cld_cnt_ecl_slf;
/

CREATE OR REPLACE FUNCTION cld_cnt_ecl_slf(p_node VARCHAR2)
RETURN NUMBER
AS child_cnt NUMBER;
BEGIN
	WITH rec(
			dph
			,node
			,oya_node
			)AS(
			SELECT
				0 AS dph
				,node
				,oya_node
			FROM
				test____$_____
			WHERE
				node = p_node
			UNION ALL
			SELECT
				1 + s1.dph AS dph
				,s2.node AS node
				,s2.oya_node AS oya_node
			FROM
				rec s1
				,test____$_____ s2
			WHERE
				s1.node = s2.oya_node
			)
	SELECT SUM(case when node <> p_node then 1 else 0 end) INTO child_cnt FROM rec;
	RETURN child_cnt;
END;
/

SELECT cld_cnt_ecl_slf(node) FROM test____$_____ WHERE node =:node;

```

#与えられたコレクションから最大値を返却する関数

```sql
drop function mx_ele;
/

create or replace type item_liz is table of varchar2(4000);
/

create or replace function mx_ele(p_liz item_liz)
return number
as mx number;
begin
    select max(to_number(column_value)) into mx from table(p_liz);
    return mx;
end;
/

with sub as (select level as lv from dual connect by level <= 10)
select LISTAGG('''' || lv || '''',',')within group (order by rownum) as liz from sub;

select mx_ele(item_liz('1','2','3','4','5','6','7','8','9','10')) as mx from dual;
```


#深さ優先探索順で座標求める

```sql
CREATE OR REPLACE TYPE item_liz IS
    TABLE OF VARCHAR2(4000);
/

WITH sub AS (
    SELECT
        s1.grp
        , s1.grpseq
        , s1.revgrpseq
        , s1.ptn
        , ROW_NUMBER() OVER(
            PARTITION BY s1.grp, s1.ptn
            ORDER BY
                grpseq
        ) AS ptnseq
        , s1.root_flg
        , s1.isleaf
        , s1.cld_cnt
        , s1.root_val
        , s1.node
        , s1.ph
        , s1.mx_grp_cnt
        , s1.ptnrn
        , s1.lv
        , s1.rn
        , s1.oya_node
    FROM
        (
            SELECT
                s1.*
                , SUM(s1.ptnrn) OVER(
                    PARTITION BY s1.grp
                    ORDER BY
                        s1.grpseq
                ) AS ptn
            FROM
                (
                    SELECT
                        s1.*
                        , ROW_NUMBER() OVER(
                            PARTITION BY s1.grp
                            ORDER BY
                                s1.ph
                        ) AS grpseq
                        , ROW_NUMBER() OVER(
                            PARTITION BY s1.grp
                            ORDER BY
                                s1.ph DESC
                        ) AS revgrpseq
                        , CASE
                                WHEN root_flg = 1 THEN 1
                                WHEN LAG(s1.cld_cnt, 1, s1.cld_cnt) OVER(
                                    PARTITION BY s1.grp
                                    ORDER BY
                                        s1.ph
                                ) = 0 THEN 1
                                ELSE 0
                            END
                        AS ptnrn
                    FROM
                        (
                            SELECT
                                DENSE_RANK() OVER(
                                    ORDER BY
                                        CONNECT_BY_ROOT node
                                ) AS grp
                                , level AS lv
                                , ROW_NUMBER() OVER(
                                    PARTITION BY CONNECT_BY_ROOT node, level
                                    ORDER BY
                                        sys_connect_by_path(node, ',')
                                ) AS rn
                                , CASE
                                        WHEN level = 1 THEN 1
                                        ELSE 0
                                    END
                                AS root_flg
                                , node
                                , oya_node
                                , COUNT(*) OVER(
                                    PARTITION BY CONNECT_BY_ROOT node
                                ) AS mx_grp_cnt
                                , CONNECT_BY_ISLEAF AS isleaf
                                , CONNECT_BY_ROOT node AS root_val
                                , sys_connect_by_path(node, ',') AS ph
                                , cld_cnt_ecl_slf(node) AS cld_cnt
                            FROM
                                test____$_____
                            START WITH
                                oya_node IS NULL
                            CONNECT BY
                                PRIOR node = oya_node
                        ) s1
                ) s1
        ) s1
    ORDER BY
        s1.grp
        , s1.ph
), pre_flw AS (
    SELECT
        s1.*
        , CASE
                WHEN nvl(FIRST_VALUE(
                    CASE
                        WHEN s1.isleaf > 0 THEN s1.grpseq
                    END
                IGNORE NULLS) OVER(
                    PARTITION BY s1.grp
                    ORDER BY
                        s1.grpseq
                ), s1.grpseq) < s1.grpseq THEN s1.grpseq + s1.ptn - 1
                ELSE s1.grpseq
            END
        AS lft_tmp
    FROM
        sub s1
), init_flw AS (
    SELECT
        s1.grp
        , s1.grpseq
        , s1.revgrpseq
        , s1.ptn
        , s1.ptnseq
        , s1.root_flg
        , s1.isleaf
        , s1.cld_cnt
        , s1.root_val
        , s1.node
        , s1.ph
        , s1.mx_grp_cnt
        , s1.ptnrn
        , s1.lv
        , s1.rn
        , s1.oya_node
        , s1.lft_tmp
        , CASE
                WHEN s1.root_flg = 1 THEN mx_grp_cnt * 2
                WHEN s1.isleaf > 0   THEN s1.lft_tmp + 1
                ELSE 0
            END
        AS rgt_tmp
    FROM
        pre_flw s1
), rec (
    grp
    , grpseq
    , revgrpseq
    , ptn
    , ptnseq
    , root_flg
    , isleaf
    , cld_cnt
    , root_val
    , node
    , ph
    , mx_grp_cnt
    , ptnrn
    , lv
    , rn
    , oya_node
    , lft_tmp
    , rgt_tmp
    , pre_rgt_tmp
    , mx_rgt_tmp
    , liz
) AS (
    SELECT
        grp
        , grpseq
        , revgrpseq
        , ptn
        , ptnseq
        , root_flg
        , isleaf
        , cld_cnt
        , root_val
        , node
        , ph
        , mx_grp_cnt
        , ptnrn
        , lv
        , rn
        , oya_node
        , lft_tmp
        , rgt_tmp
        , rgt_tmp AS pre_rgt_tmp
        , rgt_tmp AS mx_rgt_tmp
        , item_liz(rgt_tmp) AS liz
    FROM
        init_flw
    WHERE
        revgrpseq = 1
    UNION ALL
    SELECT
        s2.grp
        , s2.grpseq
        , s2.revgrpseq
        , s2.ptn
        , s2.ptnseq
        , s2.root_flg
        , s2.isleaf
        , s2.cld_cnt
        , s2.root_val
        , s2.node
        , s2.ph
        , s2.mx_grp_cnt
        , s2.ptnrn
        , s2.lv
        , s2.rn
        , s2.oya_node
        , s2.lft_tmp
        , CASE
                WHEN s2.rgt_tmp = 0 THEN mx_ele(s1.liz) + 1
                ELSE s2.rgt_tmp
            END
        AS rgt_tmp
        , s2.rgt_tmp AS pre_rgt_tmp
        , mx_ele(liz) AS mx_rgt_tmp
        , s1.liz MULTISET UNION ALL item_liz(
            CASE
                WHEN s2.rgt_tmp = 0 THEN mx_ele(s1.liz) + 1
                ELSE s2.rgt_tmp
            END
        ) AS liz
    FROM
        rec s1
        , init_flw s2
    WHERE
        s1.grp = s2.grp
        AND s1.revgrpseq + 1 = s2.revgrpseq
) SELECT
    grp
    , node
    , ph
    , lft_tmp as lft
    , rgt_tmp as rgt
  FROM
    rec
ORDER BY
    grp
    , grpseq;
```

>いけてそー。。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/286037/316f9829-62c6-7488-3982-483783f86c50.png)



#幅優先探索順で座標求める

>order by句に**s1.ph**と記載されているところを**s1.lv,s1.node**に書き換える。

```sql
CREATE OR REPLACE TYPE item_liz IS
    TABLE OF VARCHAR2(4000);
/

WITH sub AS (
    SELECT
        s1.grp
        , s1.grpseq
        , s1.revgrpseq
        , s1.ptn
        , ROW_NUMBER() OVER(
            PARTITION BY s1.grp, s1.ptn
            ORDER BY
                grpseq
        ) AS ptnseq
        , s1.root_flg
        , s1.isleaf
        , s1.cld_cnt
        , s1.root_val
        , s1.node
        , s1.ph
        , s1.mx_grp_cnt
        , s1.ptnrn
        , s1.lv
        , s1.rn
        , s1.oya_node
    FROM
        (
            SELECT
                s1.*
                , SUM(s1.ptnrn) OVER(
                    PARTITION BY s1.grp
                    ORDER BY
                        s1.grpseq
                ) AS ptn
            FROM
                (
                    SELECT
                        s1.*
                        , ROW_NUMBER() OVER(
                            PARTITION BY s1.grp
                            ORDER BY
--                                s1.ph
								s1.lv
								,s1.node
                        ) AS grpseq
                        , ROW_NUMBER() OVER(
                            PARTITION BY s1.grp
                            ORDER BY
--                                s1.ph DESC
								s1.lv DESC
								,s1.node DESC
                        ) AS revgrpseq
                        , CASE
                                WHEN root_flg = 1 THEN 1
                                WHEN LAG(s1.cld_cnt, 1, s1.cld_cnt) OVER(
                                    PARTITION BY s1.grp
                                    ORDER BY
--                                        s1.ph
										s1.lv
										,s1.node
                                ) = 0 THEN 1
                                ELSE 0
                            END
                        AS ptnrn
                    FROM
                        (
                            SELECT
                                DENSE_RANK() OVER(
                                    ORDER BY
                                        CONNECT_BY_ROOT node
                                ) AS grp
                                , level AS lv
                                , ROW_NUMBER() OVER(
                                    PARTITION BY CONNECT_BY_ROOT node, level
                                    ORDER BY
                                        sys_connect_by_path(node, ',')
                                ) AS rn
                                , CASE
                                        WHEN level = 1 THEN 1
                                        ELSE 0
                                    END
                                AS root_flg
                                , node
                                , oya_node
                                , COUNT(*) OVER(
                                    PARTITION BY CONNECT_BY_ROOT node
                                ) AS mx_grp_cnt
                                , CONNECT_BY_ISLEAF AS isleaf
                                , CONNECT_BY_ROOT node AS root_val
                                , sys_connect_by_path(node, ',') AS ph
                                , cld_cnt_ecl_slf(node) AS cld_cnt
                            FROM
                                test____$_____
                            START WITH
                                oya_node IS NULL
                            CONNECT BY
                                PRIOR node = oya_node
                        ) s1
                ) s1
        ) s1
    ORDER BY
        s1.grp
        , s1.ph
), pre_flw AS (
    SELECT
        s1.*
        , CASE
                WHEN nvl(FIRST_VALUE(
                    CASE
                        WHEN s1.isleaf > 0 THEN s1.grpseq
                    END
                IGNORE NULLS) OVER(
                    PARTITION BY s1.grp
                    ORDER BY
                        s1.grpseq
                ), s1.grpseq) < s1.grpseq THEN s1.grpseq + s1.ptn - 1
                ELSE s1.grpseq
            END
        AS lft_tmp
    FROM
        sub s1
), init_flw AS (
    SELECT
        s1.grp
        , s1.grpseq
        , s1.revgrpseq
        , s1.ptn
        , s1.ptnseq
        , s1.root_flg
        , s1.isleaf
        , s1.cld_cnt
        , s1.root_val
        , s1.node
        , s1.ph
        , s1.mx_grp_cnt
        , s1.ptnrn
        , s1.lv
        , s1.rn
        , s1.oya_node
        , s1.lft_tmp
        , CASE
                WHEN s1.root_flg = 1 THEN mx_grp_cnt * 2
                WHEN s1.isleaf > 0   THEN s1.lft_tmp + 1
                ELSE 0
            END
        AS rgt_tmp
    FROM
        pre_flw s1
), rec (
    grp
    , grpseq
    , revgrpseq
    , ptn
    , ptnseq
    , root_flg
    , isleaf
    , cld_cnt
    , root_val
    , node
    , ph
    , mx_grp_cnt
    , ptnrn
    , lv
    , rn
    , oya_node
    , lft_tmp
    , rgt_tmp
    , pre_rgt_tmp
    , mx_rgt_tmp
    , liz
) AS (
    SELECT
        grp
        , grpseq
        , revgrpseq
        , ptn
        , ptnseq
        , root_flg
        , isleaf
        , cld_cnt
        , root_val
        , node
        , ph
        , mx_grp_cnt
        , ptnrn
        , lv
        , rn
        , oya_node
        , lft_tmp
        , rgt_tmp
        , rgt_tmp AS pre_rgt_tmp
        , rgt_tmp AS mx_rgt_tmp
        , item_liz(rgt_tmp) AS liz
    FROM
        init_flw
    WHERE
        revgrpseq = 1
    UNION ALL
    SELECT
        s2.grp
        , s2.grpseq
        , s2.revgrpseq
        , s2.ptn
        , s2.ptnseq
        , s2.root_flg
        , s2.isleaf
        , s2.cld_cnt
        , s2.root_val
        , s2.node
        , s2.ph
        , s2.mx_grp_cnt
        , s2.ptnrn
        , s2.lv
        , s2.rn
        , s2.oya_node
        , s2.lft_tmp
        , CASE
                WHEN s2.rgt_tmp = 0 THEN mx_ele(s1.liz) + 1
                ELSE s2.rgt_tmp
            END
        AS rgt_tmp
        , s2.rgt_tmp AS pre_rgt_tmp
        , mx_ele(liz) AS mx_rgt_tmp
        , s1.liz MULTISET UNION ALL item_liz(
            CASE
                WHEN s2.rgt_tmp = 0 THEN mx_ele(s1.liz) + 1
                ELSE s2.rgt_tmp
            END
        ) AS liz
    FROM
        rec s1
        , init_flw s2
    WHERE
        s1.grp = s2.grp
        AND s1.revgrpseq + 1 = s2.revgrpseq
) SELECT
    grp
    , node
	, lv
	, ph
    , lft_tmp as lft
    , rgt_tmp as rgt
  FROM
    rec
ORDER BY
    grp
    , grpseq;

```

>いけてそー。。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/286037/d61ea445-53d2-119f-572e-f1e89c7cbec4.png)


#あとがき
入れ子集合がさくっと作れるようになったので、またいろいろあそべそー。いろいろ試して生きたい。雰囲気でいったので、バグってるかもです。間違っていたらコメントください。また他にもいいやり方があればコメントいただけるとうれしいです。

検算のやり方考えないとなー。

以上、ありがとうございました。