Как найти различные корневые узлы новейших узлов в деревьях (удерживайте в таблице замыканий)? - PullRequest
Новая
       3

Как найти различные корневые узлы новейших узлов в деревьях (удерживайте в таблице замыканий)?

3 голосов
/ 10 февраля 2011

Я пытаюсь сохранить дерево сообщений в качестве таблицы закрытия на MySQL. В основном об этом методе узнали из презентации Билла Карвина Модели для иерархических данных . Проблема в том, что я хочу найти 3 разных корневых узла (= узлы без предков), которые имеют самые последние узлы в своих деревьях. NB! Даже если у некоторого корневого узла есть 10 самых новых узлов в поддереве, он будет учитываться только один раз.

У всех узлов есть время модификации, для простоты предположим, что идентификаторы узлов представляют также время их последней модификации (но мы не можем использовать идентификаторы в запросах как время), первый - 1-й, а последний - 17-й. 

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

В таблице закрытия у меня есть 3 столбца (предок, потомок, глубина), поэтому дерево представлено так: 

| 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;

Но как мне получить 3 корневых узлов с самыми новыми сообщениями (в данном случае 1, 10 и 11)? Возможно ли это (и рационально) с одним запросом?

Редактировать: я положил образцы таблиц в pastebin

Ответы [ 6 ]

2 голосов
/ 12 ноября 2011

Вы можете создать один элемент верхнего уровня, который предназначен только для справки, и все его потомки будут корневыми узлами.

  • top
    • root
      • sub1
      • sub2
      • sub3
    • root2
    • root3
    • root4
2 голосов
/ 11 февраля 2011

У меня есть какое-то решение."Вид", потому что мне пришлось использовать дополнительный столбец в таблице узлов: корень.Он говорит, является ли узел корневым или нет.Используя этот дополнительный бит, я могу составить такой запрос: 

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;
1 голос
/ 03 февраля 2012

Этот поток довольно старый, но я наткнулся на него, прежде чем нашел решение, которое не требует дополнительных столбцов, кроме стандартного предка и потомка, вам даже не нужно время, потому что сам ОП заявляет о проблеме: вы хочу предков, которые не являются потомками других. Ниже приведен окончательный запрос, а под ним - тестовые данные, которые можно попробовать самостоятельно. 

select a.node_name, a.node_id
from test.hier a left outer join 
             (select coo.descendant /* coo = CHILD OF OTHER */
              from test.closure_tree coo right outer join test.closure_tree ro
                    on coo.ancestor <> ro.descendant /* ignore its self reference */
                    and coo.descendant = ro.descendant /* belongs to another node besides itself */)lo 
on a.node_id = lo.descendant
where lo.descendant is null /* wasn't found to be a child of another node besides itself */
group by a.node_name, a.node_id

Тестовые сценарии данных для загрузки этой тестовой иерархии: 

--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
1 голос
/ 11 февраля 2011

Здесь у вас тот же код без кавычек в псевдониме, проверьте его и скажите, пожалуйста, работает ли он с вами.Я пробовал под Microsoft SQL Server, потому что у меня на ноутбуке нет MySQL 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), последний запрос должен был быть таким: 

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;
1 голос
/ 10 февраля 2011

Я попытался смоделировать его в базе данных и сгенерировал этот запрос, чтобы найти последние 3 корневых узла с самыми новыми записями.Я не совсем уверен, что я понял все ваши запросы, но если я этого не сделаю, скажите мне, и как можно скорее я постараюсь вам помочь.: 

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;

Как видите, в одном запросе три запроса.Если это работает для вас, просто скажите мне, и я объясню, как это работает завтра.

0 голосов
/ 13 августа 2014 
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
...