MySQL: Consulta Hierárquica em Árvore

20

SUB-ÁRVORE DENTRO DE UMA ÁRVORE no MySQL

No meu MYSQL Database COMPANY, eu tenho uma Table: Employeeassociação recursiva, um funcionário pode ser chefe de outro funcionário. A self relationship of kind (SuperVisor (1)- SuperVisee (∞) ).

Consulta para criar tabela:

CREATE TABLE IF NOT EXISTS `Employee` (
  `SSN` varchar(64) NOT NULL,
  `Name` varchar(64) DEFAULT NULL,
  `Designation` varchar(128) NOT NULL,
  `MSSN` varchar(64) NOT NULL, 
  PRIMARY KEY (`SSN`),
  CONSTRAINT `FK_Manager_Employee`  
              FOREIGN KEY (`MSSN`) REFERENCES Employee(SSN)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Eu inseri um conjunto de tuplas (consulta):

INSERT INTO Employee VALUES 
 ("1", "A", "OWNER",  "1"),  

 ("2", "B", "BOSS",   "1"), # Employees under OWNER 
 ("3", "F", "BOSS",   "1"),

 ("4", "C", "BOSS",   "2"), # Employees under B
 ("5", "H", "BOSS",   "2"), 
 ("6", "L", "WORKER", "2"), 
 ("7", "I", "BOSS",   "2"), 
 # Remaining Leaf nodes   
 ("8", "K", "WORKER", "3"), # Employee under F     

 ("9", "J", "WORKER", "7"), # Employee under I     

 ("10","G", "WORKER", "5"), # Employee under H

 ("11","D", "WORKER", "4"), # Employee under C
 ("12","E", "WORKER", "4")  

As linhas inseridas têm o seguinte relacionamento hierárquico em árvore :

         A     <---ROOT-OWNER
        /|\             
       / A \        
      B     F 
    //| \    \          
   // |  \    K     
  / | |   \                     
 I  L H    C        
/     |   / \ 
J     G  D   E

Eu escrevi uma consulta para encontrar relacionamento:

SELECT  SUPERVISOR.name AS SuperVisor, 
        GROUP_CONCAT(SUPERVISEE.name  ORDER BY SUPERVISEE.name ) AS SuperVisee, 
        COUNT(*)  
FROM Employee AS SUPERVISOR 
  INNER JOIN Employee SUPERVISEE ON  SUPERVISOR.SSN = SUPERVISEE.MSSN 
GROUP BY SuperVisor;

E a saída é:

+------------+------------+----------+
| SuperVisor | SuperVisee | COUNT(*) |
+------------+------------+----------+
| A          | A,B,F      |        3 |
| B          | C,H,I,L    |        4 |
| C          | D,E        |        2 |
| F          | K          |        1 |
| H          | G          |        1 |
| I          | J          |        1 |
+------------+------------+----------+
6 rows in set (0.00 sec)

[ PERGUNTA ]
Em vez da árvore hierárquica completa, preciso SUB-TREEde um ponto (seletivo), por exemplo:
se o argumento de entrada for, Bentão a saída deve ser a seguinte ...

+------------+------------+----------+
| SuperVisor | SuperVisee | COUNT(*) |
+------------+------------+----------+
| B          | C,H,I,L    |        4 |
| C          | D,E        |        2 |
| H          | G          |        1 |
| I          | J          |        1 |
+------------+------------+----------+   

Por favor me ajude nisso. Caso contrário, um procedimento armazenado pode ser útil.
Eu tentei, mas todos os esforços foram inúteis!

Grijesh Chauhan
fonte
Simplesmente forneci uma estrutura de teste para a comunidade usar na exploração dessa questão com mais facilidade.
Mkamokb
@bluefeet Sim, quando eu receber resposta, removerei um desses dois.
Grijesh Chauhan 6/12/12
11
@GrijeshChauhan, deixe-me perguntar: o que é melhor para criar suas próprias ondas visíveis? Jogar pedras no oceano ou atirar pedras em um pequeno lago? Ir direto aos especialistas quase certamente lhe dará a melhor resposta, e esse tipo de pergunta é tão importante (tópicos avançados do banco de dados) que criamos seu próprio site na rede. Mas não vou impedi-lo de perguntar onde você gosta, essa é sua prerrogativa. Minha prerrogativa é votar para movê-lo para outro site, se eu acho que é onde ele pertence. : D Nós tanto para uso da rede que acharmos conveniente, neste caso: D
jcolebrand
11
@ jcolebrand: Na verdade, foi apenas minha culpa. Costumo postar perguntas de vários lados para obter uma resposta melhor, rápida e com muitas respostas. It my experience Sempre obtive uma resposta melhor de especialistas . E acho que foi melhor decisão passar a pergunta para os administradores de banco de dados. Em todos os casos, sou muito grato ao stackoverflow e às pessoas que estão ativas aqui. Eu realmente tenho solução para muitos problemas que eram muito difíceis de encontrar ou para qualquer outra web.
Grijesh Chauhan 6/12/12

Respostas:

5

Eu já resolvi algo dessa natureza usando Procedimentos armazenados: encontre o nível mais alto de um campo hierárquico: com vs sem CTEs (24 de outubro de 2011)

Se você olhar no meu post, poderá usar as funções GetAncestry e GetFamilyTree como modelo para percorrer a árvore a partir de qualquer ponto.

UPDATE 2012-12-11 12:11 EDT

Olhei para o meu código da minha postagem . Eu escrevi a Função Armazenada para você:

DELIMITER $$

DROP FUNCTION IF EXISTS `cte_test`.`GetFamilyTree` $$
CREATE FUNCTION `cte_test`.`GetFamilyTree`(GivenName varchar(64))
RETURNS varchar(1024) CHARSET latin1
DETERMINISTIC
BEGIN

    DECLARE rv,q,queue,queue_children,queue_names VARCHAR(1024);
    DECLARE queue_length,pos INT;
    DECLARE GivenSSN,front_ssn VARCHAR(64);

    SET rv = '';

    SELECT SSN INTO GivenSSN
    FROM Employee
    WHERE name = GivenName
    AND Designation <> 'OWNER';
    IF ISNULL(GivenSSN) THEN
        RETURN ev;
    END IF;

    SET queue = GivenSSN;
    SET queue_length = 1;

    WHILE queue_length > 0 DO
        IF queue_length = 1 THEN
            SET front_ssn = queue;
            SET queue = '';
        ELSE
            SET pos = LOCATE(',',queue);
            SET front_ssn = LEFT(queue,pos - 1);
            SET q = SUBSTR(queue,pos + 1);
            SET queue = q;
        END IF;
        SET queue_length = queue_length - 1;
        SELECT IFNULL(qc,'') INTO queue_children
        FROM
        (
            SELECT GROUP_CONCAT(SSN) qc FROM Employee
            WHERE MSSN = front_ssn AND Designation <> 'OWNER'
        ) A;
        SELECT IFNULL(qc,'') INTO queue_names
        FROM
        (
            SELECT GROUP_CONCAT(name) qc FROM Employee
            WHERE MSSN = front_ssn AND Designation <> 'OWNER'
        ) A;
        IF LENGTH(queue_children) = 0 THEN
            IF LENGTH(queue) = 0 THEN
                SET queue_length = 0;
            END IF;
        ELSE
            IF LENGTH(rv) = 0 THEN
                SET rv = queue_names;
            ELSE
                SET rv = CONCAT(rv,',',queue_names);
            END IF;
            IF LENGTH(queue) = 0 THEN
                SET queue = queue_children;
            ELSE
                SET queue = CONCAT(queue,',',queue_children);
            END IF;
            SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
        END IF;
    END WHILE;

    RETURN rv;

END $$

Isso realmente funciona. Aqui está uma amostra:

mysql> SELECT name,GetFamilyTree(name) FamilyTree
    -> FROM Employee WHERE Designation <> 'OWNER';
+------+-----------------------+
| name | FamilyTree            |
+------+-----------------------+
| A    | B,F,C,H,L,I,K,D,E,G,J |
| G    |                       |
| D    |                       |
| E    |                       |
| B    | C,H,L,I,D,E,G,J       |
| F    | K                     |
| C    | D,E                   |
| H    | G                     |
| L    |                       |
| I    | J                     |
| K    |                       |
| J    |                       |
+------+-----------------------+
12 rows in set (0.36 sec)

mysql>

Há apenas uma captura. Adicionei uma linha extra para o proprietário

  • O proprietário possui SSN 0
  • O proprietário é seu próprio chefe no MSSN 0

Aqui estão os dados

mysql> select * from Employee;
+-----+------+-------------+------+
| SSN | Name | Designation | MSSN |
+-----+------+-------------+------+
| 0   | A    | OWNER       | 0    |
| 1   | A    | BOSS        | 0    |
| 10  | G    | WORKER      | 5    |
| 11  | D    | WORKER      | 4    |
| 12  | E    | WORKER      | 4    |
| 2   | B    | BOSS        | 1    |
| 3   | F    | BOSS        | 1    |
| 4   | C    | BOSS        | 2    |
| 5   | H    | BOSS        | 2    |
| 6   | L    | WORKER      | 2    |
| 7   | I    | BOSS        | 2    |
| 8   | K    | WORKER      | 3    |
| 9   | J    | WORKER      | 7    |
+-----+------+-------------+------+
13 rows in set (0.00 sec)

mysql>
RolandoMySQLDBA
fonte
entendeu a idéia!
Grijesh Chauhan
Como posso adaptar para obter todos os descendentes de Acomo esta A A/B A/B/C A/B/C/D A/B/C/E A/B/H A/B/H/G A/B/I A/B/I/J A/B/L A/F A/F/K
Smith
também lida com multinodes? como ele está pendurado no meu banco de dados onde vários nós de um pai encontrou
عثمان غني
3

O que você está usando é chamado Modelo de Lista de Adjacência . Tem muitas limitações. Você será um problema quando desejar excluir / inserir um nó em um local específico. É melhor você usar o modelo de conjunto aninhado .

Há uma explicação detalhada . Infelizmente, o artigo no mysql.com não existe mais.

Shiplu Mokaddim
fonte
5
" tem muitas limitações " - mas somente ao usar o MySQL. Quase todos os DBMS suportam consultas recursivas (o MySQL é um dos poucos que não suportam) e isso torna o modelo realmente fácil de lidar.
a_horse_with_no_name
@a_horse_with_no_name Nunca usou nada além de MySQL. Então eu nunca soube disso. Obrigado pela informação.
Shiplu Mokaddim