Finden Sie die höchste Ebene eines hierarchischen Feldes: mit vs ohne CTEs
hinweis: Diese Frage wurde aktualisiert, um zu berücksichtigen, dass wir derzeit MySQL verwenden. Nachdem dies geschehen ist, würde ich gerne sehen, wie viel einfacher es wäre, wenn wir zu einer CTE-unterstützenden Datenbank wechseln würden.
Ich habe eine selbstreferenzierende Tabelle mit einem Primärschlüssel id und einem Fremdschlüssel parent_id.
+------------+--------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+------------+--------------+------+-----+---------+----------------+
| id | int(11) | NO | PRI | NULL | auto_increment |
| parent_id | int(11) | YES | | NULL | |
| name | varchar(255) | YES | | NULL | |
| notes | text | YES | | NULL | |
+------------+--------------+------+-----+---------+----------------+
Wie kann ich bei einem name das übergeordnete übergeordnete Element abfragen?
Wie kann ich bei einem name alle id abfragen, die einem Datensatz von name = 'foo' Zugeordnet sind?
context: Ich bin kein dba, plane aber, einen dba zu bitten, diese Art von hierarchischer Struktur zu implementieren, und möchte einige Abfragen testen. Die Motivation dafür wird von Kattge et al 2011 beschrieben.
Hier ist ein Beispiel für die Beziehungen zwischen IDs in der Tabelle:
-- -----------------------------------------------------
-- Create a new database called 'testdb'
-- -----------------------------------------------------
SET @[email protected]@UNIQUE_CHECKS, UNIQUE_CHECKS=0;
SET @[email protected]@FOREIGN_KEY_CHECKS, FOREIGN_KEY_CHECKS=0;
SET @[email protected]@SQL_MODE, SQL_MODE='TRADITIONAL';
CREATE SCHEMA IF NOT EXISTS `testdb` DEFAULT CHARACTER SET latin1 COLLATE latin1_swedish_ci ;
USE `testdb` ;
-- -----------------------------------------------------
-- Table `testdb`.`observations`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `testdb`.`observations` (
`id` INT NOT NULL ,
`parent_id` INT NULL ,
`name` VARCHAR(45) NULL ,
PRIMARY KEY (`id`) )
ENGINE = InnoDB;
SET [email protected]_SQL_MODE;
SET [email protected]_FOREIGN_KEY_CHECKS;
SET [email protected]_UNIQUE_CHECKS;
-- -----------------------------------------------------
-- Add Example Data Set
-- -----------------------------------------------------
INSERT INTO observations VALUES (1,3), (2,5), (3,NULL), (4,10),
(5,NULL), (6,1), (7,5), (8,10), (9,10), (10,3);
Sie müssen dies definitiv über MySQL Stored Procedure Language schreiben
Hier ist eine gespeicherte Funktion namens GetParentIDByID, um eine ParentID abzurufen, der eine ID zum Suchen gegeben wurde
DELIMITER $$
DROP FUNCTION IF EXISTS `junk`.`GetParentIDByID` $$
CREATE FUNCTION `junk`.`GetParentIDByID` (GivenID INT) RETURNS INT
DETERMINISTIC
BEGIN
DECLARE rv INT;
SELECT IFNULL(parent_id,-1) INTO rv FROM
(SELECT parent_id FROM pctable WHERE id = GivenID) A;
RETURN rv;
END $$
DELIMITER ;
Hier ist eine gespeicherte Funktion namens GetAncestry zum Abrufen einer Liste von Eltern-IDs ab der ersten Generation in der gesamten Hierarchie, für die zunächst eine ID angegeben wurde:
DELIMITER $$
DROP FUNCTION IF EXISTS `junk`.`GetAncestry` $$
CREATE FUNCTION `junk`.`GetAncestry` (GivenID INT) RETURNS VARCHAR(1024)
DETERMINISTIC
BEGIN
DECLARE rv VARCHAR(1024);
DECLARE cm CHAR(1);
DECLARE ch INT;
SET rv = '';
SET cm = '';
SET ch = GivenID;
WHILE ch > 0 DO
SELECT IFNULL(parent_id,-1) INTO ch FROM
(SELECT parent_id FROM pctable WHERE id = ch) A;
IF ch > 0 THEN
SET rv = CONCAT(rv,cm,ch);
SET cm = ',';
END IF;
END WHILE;
RETURN rv;
END $$
DELIMITER ;
Hier ist etwas, um Beispieldaten zu generieren:
USE junk
DROP TABLE IF EXISTS pctable;
CREATE TABLE pctable
(
id INT NOT NULL AUTO_INCREMENT,
parent_id INT,
PRIMARY KEY (id)
) ENGINE=MyISAM;
INSERT INTO pctable (parent_id) VALUES (0);
INSERT INTO pctable (parent_id) SELECT parent_id+1 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+2 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+3 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+4 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+5 FROM pctable;
SELECT * FROM pctable;
Folgendes wird generiert:
mysql> USE junk
Database changed
mysql> DROP TABLE IF EXISTS pctable;
Query OK, 0 rows affected (0.00 sec)
mysql> CREATE TABLE pctable
-> (
-> id INT NOT NULL AUTO_INCREMENT,
-> parent_id INT,
-> PRIMARY KEY (id)
-> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.05 sec)
mysql> INSERT INTO pctable (parent_id) VALUES (0);
Query OK, 1 row affected (0.00 sec)
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+1 FROM pctable;
Query OK, 1 row affected (0.00 sec)
Records: 1 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+2 FROM pctable;
Query OK, 2 rows affected (0.00 sec)
Records: 2 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+3 FROM pctable;
Query OK, 4 rows affected (0.00 sec)
Records: 4 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+4 FROM pctable;
Query OK, 8 rows affected (0.01 sec)
Records: 8 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+5 FROM pctable;
Query OK, 16 rows affected (0.00 sec)
Records: 16 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM pctable;
+----+-----------+
| id | parent_id |
+----+-----------+
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 3 |
| 6 | 4 |
| 7 | 5 |
| 8 | 6 |
| 9 | 4 |
| 10 | 5 |
| 11 | 6 |
| 12 | 7 |
| 13 | 7 |
| 14 | 8 |
| 15 | 9 |
| 16 | 10 |
| 17 | 5 |
| 18 | 6 |
| 19 | 7 |
| 20 | 8 |
| 21 | 8 |
| 22 | 9 |
| 23 | 10 |
| 24 | 11 |
| 25 | 9 |
| 26 | 10 |
| 27 | 11 |
| 28 | 12 |
| 29 | 12 |
| 30 | 13 |
| 31 | 14 |
| 32 | 15 |
+----+-----------+
32 rows in set (0.00 sec)
Folgendes generieren die Funktionen für jeden Wert:
mysql> SELECT id,GetParentIDByID(id),GetAncestry(id) FROM pctable;
+----+---------------------+-----------------+
| id | GetParentIDByID(id) | GetAncestry(id) |
+----+---------------------+-----------------+
| 1 | 0 | |
| 2 | 1 | 1 |
| 3 | 2 | 2,1 |
| 4 | 3 | 3,2,1 |
| 5 | 3 | 3,2,1 |
| 6 | 4 | 4,3,2,1 |
| 7 | 5 | 5,3,2,1 |
| 8 | 6 | 6,4,3,2,1 |
| 9 | 4 | 4,3,2,1 |
| 10 | 5 | 5,3,2,1 |
| 11 | 6 | 6,4,3,2,1 |
| 12 | 7 | 7,5,3,2,1 |
| 13 | 7 | 7,5,3,2,1 |
| 14 | 8 | 8,6,4,3,2,1 |
| 15 | 9 | 9,4,3,2,1 |
| 16 | 10 | 10,5,3,2,1 |
| 17 | 5 | 5,3,2,1 |
| 18 | 6 | 6,4,3,2,1 |
| 19 | 7 | 7,5,3,2,1 |
| 20 | 8 | 8,6,4,3,2,1 |
| 21 | 8 | 8,6,4,3,2,1 |
| 22 | 9 | 9,4,3,2,1 |
| 23 | 10 | 10,5,3,2,1 |
| 24 | 11 | 11,6,4,3,2,1 |
| 25 | 9 | 9,4,3,2,1 |
| 26 | 10 | 10,5,3,2,1 |
| 27 | 11 | 11,6,4,3,2,1 |
| 28 | 12 | 12,7,5,3,2,1 |
| 29 | 12 | 12,7,5,3,2,1 |
| 30 | 13 | 13,7,5,3,2,1 |
| 31 | 14 | 14,8,6,4,3,2,1 |
| 32 | 15 | 15,9,4,3,2,1 |
+----+---------------------+-----------------+
32 rows in set (0.02 sec)
MORAL DER GESCHICHTE: Das Abrufen rekursiver Daten muss in MySQL erfolgen
PDATE 2011-10-24 17:17 EDT
Hier ist die Umkehrung von GetAncestry. Ich nenne es GetFamilyTree.
Hier ist der Algorithmus:
- Geben Sie die angegebene ID in die Warteschlange ein
- Schleife
- In front_id einreihen
- Rufen Sie alle IDs in queue_children ab, deren parent_id = front_id
- Hänge queue_children an retval_list (rv) an
- Queue_children in die Warteschlange stellen
- Wiederholen Sie diesen Vorgang, bis queue und queue_children gleichzeitig leer sind
Ich glaube, aus meinen Datenstruktur- und Algorithmusklassen im College wird dies so etwas wie Vorbestellungs-/Präfixbaumdurchquerung genannt.
Hier ist der Code:
DELIMITER $$
DROP FUNCTION IF EXISTS `junk`.`GetFamilyTree` $$
CREATE FUNCTION `junk`.`GetFamilyTree` (GivenID INT) RETURNS varchar(1024) CHARSET latin1
DETERMINISTIC
BEGIN
DECLARE rv,q,queue,queue_children VARCHAR(1024);
DECLARE queue_length,front_id,pos INT;
SET rv = '';
SET queue = GivenID;
SET queue_length = 1;
WHILE queue_length > 0 DO
SET front_id = FORMAT(queue,0);
IF queue_length = 1 THEN
SET queue = '';
ELSE
SET pos = LOCATE(',',queue) + 1;
SET q = SUBSTR(queue,pos);
SET queue = q;
END IF;
SET queue_length = queue_length - 1;
SELECT IFNULL(qc,'') INTO queue_children
FROM (SELECT GROUP_CONCAT(id) qc
FROM pctable WHERE parent_id = front_id) 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_children;
ELSE
SET rv = CONCAT(rv,',',queue_children);
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 $$
Hier ist, was jede Zeile produziert
mysql> SELECT id,parent_id,GetParentIDByID(id),GetAncestry(id),GetFamilyTree(id) FROM pctable;
+----+-----------+---------------------+-----------------+--------------------------------------------------------------------------------------+
| id | parent_id | GetParentIDByID(id) | GetAncestry(id) | GetFamilyTree(id) |
+----+-----------+---------------------+-----------------+--------------------------------------------------------------------------------------+
| 1 | 0 | 0 | | 2,3,4,5,6,9,7,10,17,8,11,18,15,22,25,12,13,19,16,23,26,14,20,21,24,27,32,28,29,30,31 |
| 2 | 1 | 1 | 1 | 3,4,5,6,9,7,10,17,8,11,18,15,22,25,12,13,19,16,23,26,14,20,21,24,27,32,28,29,30,31 |
| 3 | 2 | 2 | 2,1 | 4,5,6,9,7,10,17,8,11,18,15,22,25,12,13,19,16,23,26,14,20,21,24,27,32,28,29,30,31 |
| 4 | 3 | 3 | 3,2,1 | 6,9,8,11,18,15,22,25,14,20,21,24,27,32,31 |
| 5 | 3 | 3 | 3,2,1 | 7,10,17,12,13,19,16,23,26,28,29,30 |
| 6 | 4 | 4 | 4,3,2,1 | 8,11,18,14,20,21,24,27,31 |
| 7 | 5 | 5 | 5,3,2,1 | 12,13,19,28,29,30 |
| 8 | 6 | 6 | 6,4,3,2,1 | 14,20,21,31 |
| 9 | 4 | 4 | 4,3,2,1 | 15,22,25,32 |
| 10 | 5 | 5 | 5,3,2,1 | 16,23,26 |
| 11 | 6 | 6 | 6,4,3,2,1 | 24,27 |
| 12 | 7 | 7 | 7,5,3,2,1 | 28,29 |
| 13 | 7 | 7 | 7,5,3,2,1 | 30 |
| 14 | 8 | 8 | 8,6,4,3,2,1 | 31 |
| 15 | 9 | 9 | 9,4,3,2,1 | 32 |
| 16 | 10 | 10 | 10,5,3,2,1 | |
| 17 | 5 | 5 | 5,3,2,1 | |
| 18 | 6 | 6 | 6,4,3,2,1 | |
| 19 | 7 | 7 | 7,5,3,2,1 | |
| 20 | 8 | 8 | 8,6,4,3,2,1 | |
| 21 | 8 | 8 | 8,6,4,3,2,1 | |
| 22 | 9 | 9 | 9,4,3,2,1 | |
| 23 | 10 | 10 | 10,5,3,2,1 | |
| 24 | 11 | 11 | 11,6,4,3,2,1 | |
| 25 | 9 | 9 | 9,4,3,2,1 | |
| 26 | 10 | 10 | 10,5,3,2,1 | |
| 27 | 11 | 11 | 11,6,4,3,2,1 | |
| 28 | 12 | 12 | 12,7,5,3,2,1 | |
| 29 | 12 | 12 | 12,7,5,3,2,1 | |
| 30 | 13 | 13 | 13,7,5,3,2,1 | |
| 31 | 14 | 14 | 14,8,6,4,3,2,1 | |
| 32 | 15 | 15 | 15,9,4,3,2,1 | |
+----+-----------+---------------------+-----------------+--------------------------------------------------------------------------------------+
32 rows in set (0.04 sec)
Dieser Algorithmus funktioniert sauber, sofern keine zyklischen Pfade vorhanden sind. Wenn zyklische Pfade vorhanden sind, müssen Sie der Tabelle eine Spalte "besucht" hinzufügen.
Sobald Sie die besuchte Spalte hinzugefügt haben, blockiert der Algorithmus zyklische Beziehungen:
- Geben Sie die angegebene ID in die Warteschlange ein
- Markieren Sie alle besuchten mit 0
- Schleife
- In front_id einreihen
- Rufen Sie alle IDs in queue_children ab, deren parent_id = front_id und visit = 0 ist
- Markieren Sie alle gerade abgerufenen queue_children mit visit = 1
- Hänge queue_children an retval_list (rv) an
- Queue_children in die Warteschlange stellen
- Wiederholen Sie diesen Vorgang, bis queue und queue_children gleichzeitig leer sind
PDATE 2011-10-24 17:37 EDT
Ich habe eine neue Tabelle mit dem Namen Beobachtungen erstellt und Ihre Beispieldaten ausgefüllt. Ich habe die gespeicherten Prozeduren geändert, um Beobachtungen anstelle von pctable zu verwenden. Hier ist Ihre Ausgabe:
mysql> CREATE TABLE observations LIKE pctable;
Query OK, 0 rows affected (0.04 sec)
mysql> INSERT INTO observations VALUES (1,3), (2,5), (3,0), (4,10),(5,0),(6,1),(7,5),(8,10),(9,10),(10,3);
Query OK, 10 rows affected (0.00 sec)
Records: 10 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM observations;
+----+-----------+
| id | parent_id |
+----+-----------+
| 1 | 3 |
| 2 | 5 |
| 3 | 0 |
| 4 | 10 |
| 5 | 0 |
| 6 | 1 |
| 7 | 5 |
| 8 | 10 |
| 9 | 10 |
| 10 | 3 |
+----+-----------+
10 rows in set (0.00 sec)
mysql> SELECT id,parent_id,GetParentIDByID(id),GetAncestry(id),GetFamilyTree(id) FROM observations;
+----+-----------+---------------------+-----------------+-------------------+
| id | parent_id | GetParentIDByID(id) | GetAncestry(id) | GetFamilyTree(id) |
+----+-----------+---------------------+-----------------+-------------------+
| 1 | 3 | 3 | | 6 |
| 2 | 5 | 5 | 5 | |
| 3 | 0 | 0 | | 1,10,6,4,8,9 |
| 4 | 10 | 10 | 10,3 | |
| 5 | 0 | 0 | | 2,7 |
| 6 | 1 | 1 | 1 | |
| 7 | 5 | 5 | 5 | |
| 8 | 10 | 10 | 10,3 | |
| 9 | 10 | 10 | 10,3 | |
| 10 | 3 | 3 | 3 | 4,8,9 |
+----+-----------+---------------------+-----------------+-------------------+
10 rows in set (0.01 sec)
PDATE 2011-10-24 18:22 EDT
Ich habe den Code für GetAncestry geändert. Dort war WHILE ch > 1 es sollte sein WHILE ch > 0
mysql> SELECT id,parent_id,GetParentIDByID(id),GetAncestry(id),GetFamilyTree(id) FROM observations;
+----+-----------+---------------------+-----------------+-------------------+
| id | parent_id | GetParentIDByID(id) | GetAncestry(id) | GetFamilyTree(id) |
+----+-----------+---------------------+-----------------+-------------------+
| 1 | 3 | 3 | 3 | 6 |
| 2 | 5 | 5 | 5 | |
| 3 | 0 | 0 | | 1,10,6,4,8,9 |
| 4 | 10 | 10 | 10,3 | |
| 5 | 0 | 0 | | 2,7 |
| 6 | 1 | 1 | 1,3 | |
| 7 | 5 | 5 | 5 | |
| 8 | 10 | 10 | 10,3 | |
| 9 | 10 | 10 | 10,3 | |
| 10 | 3 | 3 | 3 | 4,8,9 |
+----+-----------+---------------------+-----------------+-------------------+
10 rows in set (0.01 sec)
Probieren Sie es jetzt !!!
Alle Eltern eines angegebenen Knotens abrufen:
WITH RECURSIVE tree AS (
SELECT id,
name,
parent_id,
1 as level
FROM the_table
WHERE name = 'foo'
UNION ALL
SELECT p.id,
p.name,
p.parent_id,
t.level + 1
FROM the_table p
JOIN tree t ON t.parent_id = p.id
)
SELECT *
FROM tree
Um den Wurzelknoten zu erhalten, können Sie z. ORDER BY level und nimm die erste Reihe
Alle untergeordneten Elemente eines angegebenen Knotens abrufen:
WITH RECURSIVE tree AS (
SELECT id,
name,
parent_id,
1 as level
FROM the_table
WHERE name = 'foo'
UNION ALL
SELECT p.id,
p.name,
p.parent_id,
t.level + 1
FROM your_table p
JOIN tree t ON t.id = p.parent_id
)
SELECT *
FROM tree
(Beachten Sie die vertauschte Bedingung für den Join im rekursiven Teil der Anweisung.)
Meines Wissens unterstützen die folgenden DBMS rekursive CTEs:
- FirebirdSQL 2.1 (tatsächlich das erste OpenSource-DBMS, das sie implementiert)
- PostgreSQL 8.4
- DB2 (nicht sicher, welche genaue Version)
- Oracle (seit 11.2)
- SQL Server 2005 und höher
- Teradata
- H2
- Sybase (weiß nicht welche Version genau)
Bearbeiten
Basierend auf Ihren Beispieldaten werden im Folgenden alle Teilbäume aus der Tabelle abgerufen, einschließlich des vollständigen Pfads für jeden Knoten als zusätzliche Spalte:
with recursive obs_tree as (
select id, parent_id, '/'||cast(id as varchar) as tree
from observations
where parent_id is null
union all
select t.id, t.parent_id, p.tree||'/'||cast(t.id as varchar)
from observations t
join obs_tree p on t.parent_id = p.id
)
select id, parent_id, tree
from obs_tree
order by tree
Die Ausgabe wäre folgende:
Id | parent_id | Baum ---- + ----------- + --------- 3 | | /3 1 | 3 | /3/1 6 | 1 | /3/1/6 10 | 3 | /3/10 4 | 10 | /3/10/4 8 | 10 | /3/10/8 9 | 10 | /3/10/9 5 | | /5 2 | 5 | /5/2 7 | 5 | /5/7
Die GetFamilyTree-Funktion in Rolandos Antwort funktioniert nicht, wenn die angegebene ID mehr als 4 Ganzzahlen beträgt, da die FORMAT MySQL-Funktion Kommas für tausend Trennzeichen hinzufügt. Ich habe die gespeicherte Funktion GetFamilyTree so geändert, dass sie mit großen Ganzzahl-IDs wie folgt funktioniert:
WHILE queue_length > 0 DO
IF queue_length = 1 THEN
SET front_id = queue;
SET queue = '';
ELSE
SET front_id = SUBSTR(queue,1,LOCATE(',',queue)-1);
SET pos = LOCATE(',',queue) + 1;
SET q = SUBSTR(queue,pos);
SET queue = q;
END IF;
front_id innerhalb der if else-Schleife definiert.