sql - SQLでのツリーの深さ

Question

と呼ばれるテーブルtree_nodeがあり、主キーがと呼ばれid、null許容列がと呼ばれparent_id、テーブルにツリー構造（またはフォレスト）が埋め込まれているとすると、ツリー/フォレスト内のノードの深さを効率的に計算するにはどうすればよいですか？ SQLで？

Answer 1

再帰機能が必要になります。再帰クエリを使用すると、これは次のようになります。

WITH RECURSIVE node_ancestors(node_id, parent_id) AS (
        SELECT id, id FROM tree_node WHERE id IN (1, 2, 3)
    UNION ALL
        SELECT na.node_id, tree_node.parent_id
            FROM node_ancestors AS na, tree_node
            WHERE tree_node.id = na.parent_id AND tree_node.parent_id IS NOT NULL
)
SELECT node_id, COUNT(parent_id) AS depth FROM node_ancestors GROUP BY node_id;

他のオプションは、ストアドプロシージャで再帰を実行し、アプリケーションで再帰を実行し、再帰の量を制限し、多くの結合を使用することです。（最後のオプションは、重要な深さに対しては実際には効率的ではありません）

Answer 2

深さが無制限の場合、問題は再帰的であり、実際には簡単で効率的な解決策はありません。（簡単なxor効率的な解決策があるかもしれません。）スキーマを制御でき、この種のデータに定期的にアクセスする必要がある場合は、各要素の左右の包含境界を使用して、テーブルをネストされたセットとしてリファクタリングできます。これにより、基本条件を使用した単一のクエリでノードの深さを計算できます。

select count(*) from tree_node
    where left < myLeft
    and right > myRight

Answer 3

ツリーを処理する一般的な方法は、KEYとPARENTの通常の列に加えて、PATHタイプの列もあります。これには、ルートからのパスを構成するノードのキーを含む文字列値が含まれます。キー自体の一部にすることを許可されていない文字で区切られた、ノード自体まで。

例を挙げましょう：

KEY        PARENT         PATH
1          -              *1*
  2        1              *1*2*
  3        1              *1*3*
    4      3              *1*3*4*
  5        1              *1*5*
    6      5              *1*5*6*

これは主に、部門階層など、あまり変更されないツリーで使用されます。

このような文字列は、複数のルール（マルチキー、複数値フィールドなど）を無効にするように見えるため、正規化理論に正確に準拠していないことはわかっていますが、現在のシナリオを含め、多くのシナリオで非常に役立ちます。を求めて。

あなたの場合、問題のノードのTREE値を取得するだけでよく、最も簡単なものに応じて、区切り文字の数を数えるか、置換関数を使用してそれらを削除し、長さの差を計算します。

上記のノードのリストとその深さを示すSQLは次のとおりです。

select KEY, PARENT, LEN(PATH)-LEN(REPLACE(PATH, '*', ''))-1 as DEPTH
from NODES

このアプローチは、再帰SQL用のデータベースエンジンによる特別な構文やサポートを必要とせず、インデックス作成にも非常に適していることに注意してください。

Answer 4

あまり賢い解決策ではありませんが、追加の列や再帰機能がなくても機能します。

次のように左結合を実行できます。

select  p10.ParentId as parent10_id,
        p9.ParentId as parent9_id,
        p8.ParentId as parent8_id,
        p7.ParentId as parent7_id,
        p6.ParentId as parent6_id,          
        p5.ParentId as parent5_id,
        p4.ParentId as parent4_id,
        p3.ParentId as parent3_id,
        p2.ParentId as parent2_id,
        p1.ParentId as ParentId,
        p1.id as id
from        tree_node p1
left join   tree_node p2 on p2.id = p1.ParentId 
left join   tree_node p3 on p3.id = p2.ParentId 
left join   tree_node p4 on p4.id = p3.ParentId  
left join   tree_node p5 on p5.id = p4.ParentId  
left join   tree_node p6 on p6.id = p5.ParentId
left join   tree_node p7 on p7.id = p6.ParentId
left join   tree_node p8 on p8.id = p7.ParentId
left join   tree_node p9 on p9.id = p8.ParentId
left join   tree_node p10 on p10.id = p9.ParentId
order       by 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;

そして、最後の列でnull以外の値を確認します。列番号8がnull値のみを持つ最初の列である場合、深さは7です。

これは確かに洗練されたソリューションではありませんが、すべてのデータベースで機能するはずです。