Comment trouver des racines-nœuds distincts des nœuds les plus récents dans les arbres (tenir dans la table de fermeture)?

Question

Je tente de stocker l'arborescence des messages comme table de fermeture sur MySQL. Principalement appris sur cette méthode de la présentation de Bill Karwin Models for hierarchical data. Le problème est: je veux trouver 3 nœuds racines distincts (= nœuds sans ancêtres), qui ont les nœuds les plus récents dans leurs arbres. NB! Même si un nœud racine a 10 nouveaux nœuds dans son sous-arbre, il ne compterait qu'une seule fois. Tous les nœuds ont leur temps de modification, pour la simplicité disons que les identifiants de nœuds représentent aussi l'heure de leur dernière modification (mais nous ne pouvons pas utiliser les identifiants dans les requêtes comme temps), le premier est le 1er et le dernier est le 17ème.

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

Dans le tableau de fermeture i have 3 colonnes (ancêtre, descendant, profondeur), de sorte que l'arbre est présenté comme ça:

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

je pourrais obtenir les plus récents sous-arbres comme ça:

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; 

Mais comment pourrais-je obtenir distinct 3 racine nœuds ayant des messages les plus récents (1, 10 et 11 dans ce cas)? Est-ce possible (et rationnel) avec une requête?

---

Edit: i mettre sample tables to pastebin

Answer 1

je suis arrivé genre de solution. "Kind of", parce que j'ai dû utiliser une colonne supplémentaire dans nodes-table: root. Il indique si le noeud est un noeud racine ou non. En utilisant ce bit supplémentaire je peux composer une telle requête:

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; 

Semble à moi, il fonctionne assez bien. Il échelles aussi. J'ai généré l'arbre avec 100 000 nœuds et il a fallu environ 1 seconde pour obtenir des résultats (la profondeur maximale de l'arbre était de 18).

Je joins le script perl (et le schéma de la table) pour la génération de contenu, donc peut-être que certains pourraient améliorer cette requête.

#!/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

J'ai essayé de simuler dans une base de données, et je généré cette requête pour trouver les derniers 3 nœuds racine ayant les plus récents messages. Je ne suis pas vraiment sûr d'avoir répondu à toutes vos demandes, mais si ce n'est pas le cas, dites-le moi et, le plus tôt possible, j'essaierai de vous aider.

Ma requête est la suivante:

---

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; 

---

Comme vous pouvez le voir, il y a trois requêtes dans le même. Si cela fonctionne pour vous, dites-moi, et je vais vous expliquer comment cela fonctionne demain.

Cordialement, Jordi Mas

Answer 3

Ici vous avez le même code sans les guillemets dans l'alias, vérifiez et me dire si cela fonctionne avec vous, s'il vous plaît. J'ai essayé sous Microsoft SQL Server, parce que je n'ai pas de serveur MySQL sur mon ordinateur portable, mais si cela ne fonctionne pas, dites-le moi et je vais l'installer et l'essayer.

Query:

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; 

Le résultat de cette recherche, avec vos données est la suivante:

MinAncestor: 1, 10, 11

MaxDescendant: 17, 14, 13

J'espère que cela va vous aider.

---

Après vos commentaires sur déclaration TOP (il ne fonctionne pas sur MySQL), la requête finale devait être celle-ci:

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

Vous pouvez créer un élément de niveau supérieur, ce qui est seulement pour référence et tous ses descendants seront les nœuds racines.

• haut
  
  • racine
    • SUB1
    • SUB2
    • SUB3
  • root2
  • root3
  • root4

Answer 5

Ce fil est assez vieux mais je suis tombé sur elle avant de venir avec une solution qui ne nécessite pas des colonnes supplémentaires en plus de l'ancêtre descendant norme &, vous ne même pas besoin de temps, parce que l'OP lui-même énonce le problème: vous voulez des ancêtres qui ne sont des descendants d'aucun autre. Vous trouverez ci-dessous la dernière requête, et ci-dessous les données de test pour l'essayer vous-même.

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 

scripts de données de test pour charger cette hiérarchie de test:

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