2011-02-10 4 views
2

の最も深い両親(ないリーフノード)を見つけるのですか:私はCとE(の2つの最も深いノードを見つける必要がありSQL - ネストされたセットモデル - 私はこのような木を考えると、各ブランチ

 
A----B---------C----D 
    |   | 
    E----F G 
    | 
    H 

それぞれ固有のブランチ、ACとAE)

私たちのデータベースは、左と右の値が同期しなくなった場合にツリー構造を維持するために、ネストされたセットモデルと隣接リストをバックアップとして使用します。

私はすべてのリーフノードを除外することができます(RGT = LFT + 1) とルートノード(LFT = 1)あなたは、これが非常に簡略化例です想像できるように私はCをBE WITH残し 、私たちの木の一部を100ノード以上あります。私のデータでこのノイズを取り除くにはどうすればいいですか?

上記の例のデータがデータベースに保存されている場合のデータです。

 
node | parent | lft | rgt | 
------+--------+-----+-----+ 
    A | NULL | 1| 16| 
    B | A | 2| 15| 
    E | B | 3| 8| 
    F | E | 4| 5| 
    H | E | 6| 7| 
    C | B | 9| 14| 
    D | C | 10| 11| 
    G | C | 12| 13| 

ありがとうございました!

答えて

0

あなたは正しいです。最初のステップは、そのプロパティの右端がleft + 1に等しいように葉ノードを識別することです。次に、葉ノードの親ノードをすべて見つけることです。これらの葉ノードは、葉のそれよりも大きい。そして最後のステップは、最も大きい左値を有する(すなわち、リーフノードに最も近い)親を除くすべての親を除外することである。

T-SQLの例では、lはリーフノード、p1は私たちが探している直接の親、p2はすべての直接的でない親を取り除くために使用されます。

まずその中にあなたの例のデータを使用してテストテーブル設定:

if object_id('tempdb..#nsm') is not null 
    drop table #nsm; 

select v.node, v.parent, v.lft, v.rgt 
into #nsm 
from (
    values 
     ('A' ,  NULL,  1, 16), 
     ('B' , 'A' , 2, 15), 
     ('E' , 'B' , 3, 8), 
     ('F' , 'E' , 4, 5), 
     ('H' , 'E' , 6, 7), 
     ('C' , 'B' , 9, 14), 
     ('D' , 'C' , 10, 11), 
     ('G' , 'C' , 12, 13) 
    ) v (node, parent, lft, rgt) 

をそして、ここであなたが要求し、両方のノードCとE取得するクエリです:

select p1.node, p1.parent, p1.lft, p1.rgt 
from #nsm p1 
where exists (
      select * 
      from #nsm l 
      where l.rgt = l.lft + 1 
       and p1.lft < l.lft 
       and p1.rgt > l.rgt 
       and not exists (
         select * 
         from #nsm p2 
         where p2.lft < l.lft 
          and p2.rgt > l.rgt 
          and p2.lft > p1.lft 
        ) 
     ) 
は、
関連する問題