ツリー内の最新ノードの別個のルートノードを見つける方法（クロージャテーブルを保持）？

Question

私は、MySQLのクロージャテーブルとしてメッセージツリーを格納しようとしています。 Bill KarwinのプレゼンテーションModels for hierarchical dataからこの方法についてほとんど学びました。問題は：私は、3つのルートノード（=祖先がないノード）を見つけたいと思っています。ツリーには最近のノードがあります。注意！たとえルートノードのサブツリーに10個の最新ノードがある場合でも、1回だけカウントされます。

すべてのノードには修正時間がありますが、簡単にするために、ノードIDは最後の変更の時刻も表しています（ただしquerysで時間を表すIDは使用できません）。最初は1位、最後は17位です。私は3列（祖先、子孫、深さ）を持っているので、木はそのように提示された閉鎖テーブルで

1 
2 
    8 
    15 
    16 
    17 
7 
3 
4 
    5 
6 
9 
12 
10 
14 
11 
13 

：

| ancestor | descendant | depth | 
+----------+------------+-------+ 
|  1 |   1 |  0 | 
|  1 |   2 |  1 | 
|  1 |   7 |  1 | 
|  1 |   8 |  2 | 
|  1 |   15 |  3 | 
|  1 |   16 |  3 | 
|  1 |   17 |  2 | 
|  2 |   2 |  0 | 
|  2 |   8 |  1 | 
|  2 |   15 |  2 | 
|  2 |   16 |  2 | 
|  2 |   17 |  1 | 
|  3 |   3 |  0 | 
|  3 |   4 |  1 | 
|  3 |   5 |  2 | 
|  3 |   6 |  1 | 
|  4 |   4 |  0 | 
|  4 |   5 |  1 | 
|  5 |   5 |  0 | 
|  6 |   6 |  0 | 
|  7 |   7 |  0 | 
|  8 |   8 |  0 | 
|  8 |   15 |  1 | 
|  8 |   16 |  1 | 
|  9 |   9 |  0 | 
|  9 |   12 |  1 | 
|  10 |   10 |  0 | 
|  10 |   14 |  1 | 
|  11 |   11 |  0 | 
|  11 |   13 |  1 | 
|  12 |   12 |  0 | 
|  13 |   13 |  0 | 
|  14 |   14 |  0 | 
|  15 |   15 |  0 | 
|  16 |   16 |  0 | 
|  17 |   17 |  0 | 

私はそのような最新のサブツリーを得ることができます：

SELECT c.ancestor, MAX(time) AS t 
FROM closure c 
    JOIN nodes n ON (c.descendant = n.node AND c.ancestor <> n.node) 
GROUP BY c.ancestor ORDER BY t desc; 

どうすれば分かりますか？ルート最新の投稿（この場合は1、10、11）のノードはありますか？ 1つのクエリでこれは可能（合理的）ですか？

---

編集：私は、私はデータベースにそれをシミュレートしようとした、と私は、最新の投稿を持つ最後の3つのルートノードを見つけるために、このクエリを生成sample tables to pastebin

Answer 1

私は解決策のようなものを得ました。 "Kind of"は、node-table：rootで追加の列を使用しなければならなかったためです。ノードがルートノードであるかどうかを示します。この追加のビットを使用して、私はそのようなクエリを構成することができます：

SELECT c.ancestor, MAX(n.time) AS t FROM closure c 
    JOIN nodes n ON (c.descendant = n.node AND c.ancestor <> n.node) 
    JOIN nodes n2 ON (c.ancestor = n2.node AND n2.root = 1) 
    GROUP BY c.ancestor ORDER BY t desc LIMIT 3; 

私にはよく見えます。それはあまりにもスケールする。私は100000ノードのツリーを生成し、結果を得るのに約1秒かかりました（ツリーの最大深さは18でした）。

コンテンツの生成にperlスクリプト（およびテーブルスキーマ）を添付しているため、このクエリがパフォーマンスが向上するよう調整する人もいます。

#!/usr/bin/perl -- 

use strict; 
use warnings; 
use Data::Random qw(:all); 
my ($maxnode, $node) =(); 

my $dbh = !DATABASE INIT! 

foreach (1 .. $ARGV[0]) { 
    $node = ($_ == 1) ? 0 : int(rand(4)); 

    if (!$node) { 
     $maxnode = &RootNode(1); 
    } 
    else { 
     $maxnode = &Node($maxnode); 
    } 
} 


## 
## 
sub Node { 
my $parent = int(rand($_[0])) + 1; 

my $id = &RootNode(0, $parent); 

my $insert = qq|INSERT INTO test.closure (ancestor, descendant, depth) 
     SELECT ancestor, $id, depth + 1 
     FROM test.closure WHERE descendant = ?|; 
$dbh->do($insert, undef, $parent); 
return $id; 

} 
## 


## 
## 
sub RootNode { 
my $min_datetime = $_[0] 
     ? '2008-9-21 4:0:0' 
     : $dbh->selectrow_array("SELECT time 
       FROM test.nodes WHERE node = ?", undef, $_[1]); 
my $label = join("", rand_chars(set => 'alpha', min => 5, max => 20)); 
my $time = rand_datetime(min => $min_datetime, max => 'now'); 

my $insert = qq|INSERT INTO test.nodes (label, time, root) VALUES (?, ?, ?)|; 
$dbh->do($insert, undef, $label, $time, $_[0]); 
my ($id) = $dbh->selectrow_array("SELECT LAST_INSERT_ID()"); 

$insert = qq|INSERT INTO test.closure (ancestor, descendant, depth) 
     VALUES (?, ?, 0)|; 
$dbh->do($insert, undef, $id, $id); 

return $id; 
} 
## 

__DATA__ 
USE test 

DROP TABLE IF EXISTS `closure`; 
DROP TABLE IF EXISTS `nodes`; 

CREATE TABLE `nodes` (
`node` int(11) NOT NULL auto_increment, 
`label` varchar(20) NOT NULL, 
`time` datetime default NULL, 
`root` tinyint(1) unsigned default NULL, 
PRIMARY KEY (`node`) 
) ENGINE=InnoDB; 

CREATE TABLE `closure` (
`ancestor` int(11) NOT NULL, 
`descendant` int(11) NOT NULL, 
`depth` tinyint(3) unsigned default NULL, 
PRIMARY KEY (`ancestor`,`descendant`), 
KEY `descendant` (`descendant`), 
CONSTRAINT `closure_ibfk_1` FOREIGN KEY (`ancestor`) REFERENCES `nodes` (`node`), 
CONSTRAINT `closure_ibfk_2` FOREIGN KEY (`descendant`) REFERENCES `nodes` (`node`) 
) ENGINE=InnoDB; 

Answer 2

を置きます。私は本当にあなたのすべての要求を望ましくないとは確信していませんが、もし私がしなければ、私に教えてください、できるだけ早く私はあなたを助けようとします。

私のクエリは、次のいずれかです。

---

SELECT TOP 3 QRY_GROUP_ALL_OF_THEM.MínDeancestor, Max(QRY_GROUP_ALL_OF_THEM.descendant) AS MáxDedescendant 
FROM ( SELECT Min(closure.ancestor) AS MínDeancestor, [QRY_LAST_INSERTIONS].[descendant] 
    FROM closure, (SELECT DISTINCT closure.descendant 
     FROM closure 
     GROUP BY closure.descendant, closure.depth, closure.ancestor, closure.descendant 
     HAVING (((closure.descendant>12 And closure.descendant<>[closure].[ancestor]) AND (closure.depth<>0)) 
      OR ((closure.descendant<>[closure].[ancestor]) AND (closure.depth<>0))) 
     ) AS QRY_LAST_INSERTIONS 
    GROUP BY closure.descendant, [QRY_LAST_INSERTIONS].[descendant] 
    HAVING (((closure.descendant)=[QRY_LAST_INSERTIONS].[descendant])) 
) AS QRY_GROUP_ALL_OF_THEM 
GROUP BY QRY_GROUP_ALL_OF_THEM.MínDeancestor 
ORDER BY Max(QRY_GROUP_ALL_OF_THEM.descendant) DESC; 

---

あなたが見ることができるように、3件の問い合わせは同1です。 それはあなたには、ちょうど私に教えてください、私はそれが明日どのように動作するか説明します。ここで

敬具、 ジョーディ・マス

Answer 3

あなたは、それをチェックし、それはあなたと一緒に動作するかどうかを教えて、別名で引用符なしで同じコードをしてください持っています。私は自分のラップトップにMySQL Serverを持っていないので、Microsoft SQL Serverの下で試してみましたが、うまくいかない場合は教えてください。

クエリ：

SELECT TOP 3 QRY_GROUP_ALL_OF_THEM.MinAncestor, Max(QRY_GROUP_ALL_OF_THEM.descendant) AS MaxDescendant 
FROM ( 
SELECT Min(closure.ancestor) AS MinAncestor, [QRY_LAST_INSERTIONS].[descendant]  
FROM closure, (
    SELECT DISTINCT closure.descendant   
    FROM closure   
    GROUP BY closure.descendant, closure.depth, closure.ancestor, closure.descendant   
    HAVING (((closure.descendant>12 And closure.descendant<>[closure].[ancestor]) 
     AND (closure.depth<>0))    
     OR ((closure.descendant<>[closure].[ancestor]) AND (closure.depth<>0)))   
) AS QRY_LAST_INSERTIONS  
GROUP BY closure.descendant, [QRY_LAST_INSERTIONS].[descendant]  
HAVING (((closure.descendant)=[QRY_LAST_INSERTIONS].[descendant]))) AS QRY_GROUP_ALL_OF_THEM 
GROUP BY QRY_GROUP_ALL_OF_THEM.MinAncestor 
ORDER BY Max(QRY_GROUP_ALL_OF_THEM.descendant) DESC; 

この照会の結果、あなたのデータとは、次のいずれか：

MinAncestor：1、10、11

MaxDescendant：17、14、13

私はそれがあなたを助けてくれることを願っています。TOP声明についてコメントした後

---

（これは、MySQL上では動作しません）、最後のクエリはこの1つでなければなりませんでした：

SELECT 
    QRY_GROUP_ALL_OF_THEM.MinAncestor, 
    Max(QRY_GROUP_ALL_OF_THEM.descendant) AS MaxDescendant LIMIT 0,3 
FROM 
    ( 
     SELECT 
      Min(closure.ancestor) AS MinAncestor, 
      [QRY_LAST_INSERTIONS].[descendant]  
     FROM closure, 
      (
       SELECT DISTINCT closure.descendant 
       FROM closure 
       GROUP BY closure.descendant, 
          closure.depth, 
          closure.ancestor, 
          closure.descendant 
       HAVING (((closure.descendant > 12 
          AND closure.descendant <> [closure].[ancestor]) 
          AND (closure.depth <> 0)) 
          OR ((closure.descendant <> [closure].[ancestor]) 
           AND (closure.depth <> 0)))   
      ) AS QRY_LAST_INSERTIONS  
     GROUP BY 
      closure.descendant, 
      [QRY_LAST_INSERTIONS].[descendant]  
     HAVING (((closure.descendant)=[QRY_LAST_INSERTIONS].[descendant])) 
    ) AS QRY_GROUP_ALL_OF_THEM 
GROUP BY QRY_GROUP_ALL_OF_THEM.MinAncestor 
ORDER BY Max(QRY_GROUP_ALL_OF_THEM.descendant) DESC; 

Answer 4

トップレベル要素を1つ作成することができます。これは参照用であり、すべての子孫がルートノードになります。

• トップ
  
  • ルート
    • SUB1
    • SUB2
    • SUB3
  • root2
  • ROOT3
  • root4

Answer 5

このスレッドはかなり古いですが、私は、あなたもするので、時間を必要としない標準の祖先&子孫のほかに、追加の列を必要としない解決策を考え出す前に、それを偶然見つけOP自身は問題を述べています：あなたは他の誰の子孫でもある祖先を望みます。以下は最終的なクエリです。その下にあるのは、自分で試してみるためのテストデータです。

--create table test.hier (
-- node_name varchar(10), 
-- node_id int identity (1,1) primary key 
--)  

--insert into test.hier (node_name) 
--values ('ROOT1') 
--insert into test.hier (node_name) 
--values ('ROOT2') 
--insert into test.hier (node_name) 
--values ('ROOT3') 
--insert into test.hier (node_name) 
--values ('ChildOf1') 
--insert into test.hier (node_name) 
--values ('ChildOf1') 
--insert into test.hier (node_name) 
--values ('ChildOf1') 
--insert into test.hier (node_name) 
--values ('ChildOf1') 
--insert into test.hier (node_name) 
--values ('ChildOf1') 
--insert into test.hier (node_name) 
--values ('ChildOf2') 
--insert into test.hier (node_name) 
--values ('ChildOf2') 
--insert into test.hier (node_name) 
--values ('ChildOf3') 
--insert into test.hier (node_name) 
--values ('ChildOf3') 
--insert into test.hier (node_name) 
--values ('ChildOf3') 
--insert into test.hier (node_name) 
--values ('ChildOf3') 
--insert into test.hier (node_name) 
--values ('LeafOf3') 
--insert into test.hier (node_name) 
--values ('LeafOf3') 
--insert into test.hier (node_name) 
--values ('LeafOf3') 
--insert into test.hier (node_name) 
--values ('LeafOf3') 
--insert into test.hier (node_name) 
--values ('LeafOf1') 
--insert into test.hier (node_name) 
--values ('LeafOf2') 

--create table test.closure_tree (
-- ancestor int, 
-- descendant int, 
-- PRIMARY KEY (ancestor, descendant), 
-- constraint fk_test_a FOREIGN KEY (ancestor) references test.hier (node_id), 
-- constraint fk_test_d FOREIGN KEY (descendant) references test.hier (node_id) 
--) 

-- SELF REFERENCES 
--insert into test.closure_tree (ancestor, descendant) 
--select node_id as a, node_id as d 
--from test.hier 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ROOT1' 
--  and b.node_name = 'ChildOf1' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ROOT2' 
--  and b.node_name = 'ChildOf2' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ROOT3' 
--  and b.node_name = 'ChildOf3' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ChildOf3' 
--  and b.node_name = 'LeafOf3' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ROOT3' 
--  and b.node_name = 'LeafOf3' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ROOT1' 
--  and b.node_name = 'LeafOf1' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ChildOf1' 
--  and b.node_name = 'LeafOf1' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'ChildOf2' 
--  and b.node_name = 'LeafOf2' 

--insert into test.closure_tree (ancestor, descendant) 
--select a.node_id, b.node_id 
--from test.hier a join test.hier b 
--  on a.node_name = 'Root2' 
--  and b.node_name = 'LeafOf2' 


---- Test read of hierarchy with weird ordering for human readability 
--select a.node_name, b.node_name as descendant_node_name 
--from test.hier a join test.closure_tree c 
-- on a.node_id = c.ancestor 
-- join test.hier b 
-- on c.descendant = b.node_id 
--order by right(a.node_name, 1), left(a.node_name, 1) desc 

Answer 6

select x.ancestor 
from nodes n 
join closure c on (c.descendant = n.node) 
join (
-- all root node 
    select ancestor 
    from closure 
    group by descendant 
    having count(*) = 1 
) x ON x.ancestor = c.ancestor 
where c.depth = 1 
order by n.time desc 
limit 3