[SQLServer]階層構造のデータを再帰クエリでフラットにするSQL


再帰クエリを使い、親子関係で結ばれた階層構造のデータをフラットにするSQLの例です
本ページは対象をSQLServerとして記述しています



階層化されたデータ

データを親子関係で結んだデータを階層化されたデータといいます。
例えばディレクトリ(c:\windows等)は良い例です。
「Cドライブ」の下に「Windows」フォルダや「Program Files」フォルダがあり、また、「Windows」フォルダの下には「System32」フォルダがあります。
このようなデータ構造のことを言います。

C:\
 +-- Windows
      +-- System32
           +-- Drivers
                 +-- etc
      +-- Microsoft.NET
      +--  : : :
 +-- Program Files
      +--  : : :
      +--  : : :

階層構造のテーブル定義

これから説明するSQLで利用するテーブルの定義です
これは、前述のディレクトリの構造を持つテーブルとなります

テーブル名:FOLDER

列名 属性 説明
ID BigInt ユニークな値(プライマリキー)
PATH nvarchar(MAX) “Windows”,”Program Files”等、フォルダ名
PARENT_ID BigInt 親フォルダのID値

いわゆる「隣接リストモデル」のテーブル構造です。
上記テーブルに投入したデータは以下です。

ID PATH PARENT_ID
1 C: NULL
2 Windows 1
3 System 2
4 System32 2
5 drivers 4
6 etc 5
7 Microsoft.NET 2
8 Program Files 1
9 Common Files 8
10 Internet Explorer 8

例えば、ID=4のデータは、親(PARENT_ID)が「2」です。更に、ID=2のPARNT_IDは「1」です。ID=1のPARENT_IDはNULLですので、ここが最上位となります。
結果、ID=4のPATHは「System32」ですが、フルパスだとID=4→2→1と辿って「C:\Windows\System32」となります。

SQLでフルパスを求める

データの構造が分かれば、データを辿ることによってフルパスは求められます。
これをSQL一発で取得するにはどうすればよいでしょうか。
ここで登場するのが再帰クエリです。
データを再帰的に辿ることにより、フルパスを求められます。
実際のSQLは以下となります。

WITH rec(DEPTH, ID, BASE_PATH, PATH, PARENT_ID, FULLPATH) as (
SELECT
 1 AS DEPTH
,ID
,PATH AS BASE_PATH
,PATH
,PARENT_ID
,PATH AS FULLPATH
FROM FOLDER
WHERE PARENT_ID is NULL
UNION ALL
SELECT
 a.DEPTH + 1
,b.ID
,a.BASE_PATH
,b.PATH
,b.PARENT_ID
,a.FULLPATH + '\' + b.PATH
FROM 
 rec a
,FOLDER b
WHERE a.ID = b.PARENT_ID)
SELECT * FROM rec

このSQLを実行した結果は以下となります

DEPTH ID  BASE_PATH  PATH               PARENT_ID  FULL_PATH
1      1    C:       C:                 NULL       C:
2      2    C:       Windows            1          C:\Windows
2      8    C:       Program Files      1          C:\Program Files
3      9    C:       Common Files       8          C:\Program Files\Common Files
3     10    C:       Internet Explorer  8          C:\Program Files\Internet Explorer
3      3    C:       System             2          C:\Windows\System
3      4    C:       System32           2          C:\Windows\System32
3      7    C:       Microsoft.NET      2          C:\Windows\Microsoft.NET
4      5    C:       drivers            4          C:\Windows\System32\drivers
5      6    C:       etc                5          C:\Windows\System32\drivers\etc

ID=4のFULL_PATH列は頭で考えたのと同じ「C:\WIndows\System32」となっています。
ちなみに「DEPTH」列は、階層の深さを表しています

応用

これを使えば、例えば出発地点から目的地までのルート検索や最短ルートを求めたりすることができると思います
まぁ、その為にはテーブル構造がしっかりしていないとダメなんですが・・・