MySQL: Baumhierarchische Abfrage

20

UNTERBAUM IN EINEM BAUM in MySQL

In meinem MYSQL habe Database COMPANYich eine Table: Employeerekursive Assoziation, ein Mitarbeiter kann Chef eines anderen Mitarbeiters sein. A self relationship of kind (SuperVisor (1)- SuperVisee (∞) ).

Abfrage zum Erstellen einer Tabelle:

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;

Ich habe eine Reihe von Tupeln eingefügt (Abfrage):

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

Die eingefügten Zeilen haben folgende Baum-Hierarchie-Beziehung :

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

Ich habe eine Anfrage geschrieben, um eine Beziehung zu finden:

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;

Und die Ausgabe ist:

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

[ FRAGE ]
Anstelle des vollständigen hierarchischen Baums benötige ich ein SUB-TREEvon einem Punkt (selektiv) zB:
Wenn das Eingabeargument Bdann ausgegeben wird, sollte es wie folgt aussehen ...

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

Bitte helfen Sie mir dabei. Wenn dies nicht der Fall ist, kann eine gespeicherte Prozedur hilfreich sein.
Ich habe es versucht, aber alle Anstrengungen waren nutzlos!

Grijesh Chauhan
quelle
1
Probe Test Geige
mellamokb
Ich habe lediglich ein Test-Framework zur Verfügung gestellt, mit dem die Community diese Frage leichter untersuchen kann.
Mellamokb
@bluefeet Ja, sobald ich eine Antwort bekomme, werde ich eine dieser beiden entfernen.
Grijesh Chauhan
1
@GrijeshChauhan lass mich dich Folgendes fragen: Was ist besser, um deine eigenen sichtbaren Wellen zu erzeugen? Kieselsteine ​​ins Meer werfen oder Steine ​​in einen kleinen Teich werfen? Wenn Sie direkt zu den Experten gehen, erhalten Sie mit ziemlicher Sicherheit die beste Antwort. Diese Art von Frage ist so wichtig (fortgeschrittene Datenbankthemen), dass wir ihr eine eigene Site im Netzwerk zugewiesen haben. Aber ich werde Sie nicht davon abhalten, danach zu fragen, wo Sie möchten, das ist Ihr Vorrecht. Mein Vorrecht ist es, abzustimmen, um es auf eine andere Site zu verschieben, wenn ich denke, dass es dort hingehört. : D In diesem Fall verwenden wir beide das Netzwerk, wie wir es für richtig halten: D
jcolebrand
1
@jcolebrand: Eigentlich war es nur meine Schuld. Ich poste Fragen auf mehreren Seiten, um eine bessere, schnellere und vielfältigere Antwort zu erhalten. It my experience Ich habe immer bessere Antworten von Experten bekommen . Und ich denke, es war eine bessere Entscheidung, Fragen an Datenbankadministratoren zu übertragen. In allen Fällen bin ich Stackoverflow und den hier aktiven Leuten sehr dankbar. Ich habe wirklich eine Lösung für viele Probleme gefunden, die sehr schwierig waren, mich selbst oder ein anderes Web zu finden.
Grijesh Chauhan

Antworten:

5

Mit Stored Procedures habe ich bereits etwas Ähnliches angesprochen: Finde die höchste Ebene eines hierarchischen Feldes: mit vs ohne CTEs ( 24.10.2011 )

Wenn Sie in meinem Beitrag nachsehen, können Sie die Funktionen GetAncestry und GetFamilyTree als Modell verwenden, um den Baum von einem bestimmten Punkt aus zu durchlaufen.

UPDATE 11.12.2012 12:11 EDT

Ich habe meinen Code von meinem Post zurückgeschaut . Ich habe die Stored Function für Sie geschrieben:

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

Es funktioniert tatsächlich. Hier ist ein Beispiel:

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>

Es gibt nur einen Haken. Ich habe eine zusätzliche Zeile für den Eigentümer hinzugefügt

  • Der Besitzer hat SSN 0
  • Der Besitzer ist sein eigener Chef mit MSSN 0

Hier sind die Daten

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
quelle
verstand die Idee!
Grijesh Chauhan
Wie kann ich mich anpassen, um alle Nachkommen Adieser Art zu bekommenA 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
funktioniert es auch mit multinodes? da es in meiner Datenbank hängt, wo mehrere Knoten eines übergeordneten
Elements
3

Was Sie verwenden, heißt Adjacency List Model . Es gibt viele Einschränkungen. Sie werden Probleme haben, wenn Sie einen Knoten an einer bestimmten Stelle löschen / einfügen möchten. Es ist besser, wenn Sie das verschachtelte Set-Modell verwenden .

Es gibt eine detaillierte Erklärung . Leider existiert der Artikel auf mysql.com nicht mehr.

Shiplu Mokaddim
quelle
5
" Es hat viele Einschränkungen " - aber nur bei der Verwendung von MySQL. Nahezu alle DBMS unterstützen rekursive Abfragen (MySQL ist eine der wenigen, die dies nicht tun), wodurch das Modell sehr einfach zu handhaben ist.
a_horse_with_no_name
@a_horse_with_no_name Nie etwas anderes als MySQL verwendet. Also habe ich es nie gewusst. Danke für die Information.
Shiplu Mokaddim