Mysql
查找分層欄位的最高級別：有 vs 沒有 CTE
注意：這個問題已經更新，以反映我們目前正在使用 MySQL，這樣做後，我想看看如果我們切換到支持 CTE 的數據庫會容易得多。
我有一個帶有主鍵
id和外鍵的自引用表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 | | +------------+--------------+------+-----+---------+----------------+給定 a
name，我如何查詢頂級父級？給定 a
name，我如何查詢所有id與 的記錄相關聯的 ’sname = 'foo'？*背景：*我不是 dba，但我打算請 dba 實現這種類型的層次結構，並想測試一些查詢。Kattge et al 2011描述了這樣做的動機。
以下是表中 id 之間關係的範例：
-- ----------------------------------------------------- -- Create a new database called 'testdb' -- ----------------------------------------------------- SET @OLD_UNIQUE_CHECKS=@@UNIQUE_CHECKS, UNIQUE_CHECKS=0; SET @OLD_FOREIGN_KEY_CHECKS=@@FOREIGN_KEY_CHECKS, FOREIGN_KEY_CHECKS=0; SET @OLD_SQL_MODE=@@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 SQL_MODE=@OLD_SQL_MODE; SET FOREIGN_KEY_CHECKS=@OLD_FOREIGN_KEY_CHECKS; SET UNIQUE_CHECKS=@OLD_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);
你肯定必須通過 MySQL 儲存過程語言編寫腳本
這是一個儲存函式
GetParentIDByID，用於檢索給定要搜尋的 ID 的 ParentIDDELIMITER $$ 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 ;這是一個儲存函式
GetAncestry，用於檢索從第一代開始的父 ID 列表，所有的層次結構都給定一個 ID 開始：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 ;這是生成範例數據的內容：
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;這是它生成的內容：
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)以下是函式為每個值生成的內容：
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)故事寓意：遞歸數據檢索必須在 MySQL 中編寫腳本
更新 2011-10-24 17:17 EDT
這是 GetAncestry 的反面。我稱之為GetFamilyTree。
這是算法：
將給定 ID 放入隊列
環形
- 出隊到 front_id
- 將所有 id 檢索到 parent_id = front_id 的 queue_children
- 將 queue_children 附加到 retval_list (rv)
- 入隊 queue_children
- 重複直到 queue 和 queue_children 同時為空
我相信從我在大學的資料結構和算法課程中，這被稱為前序/前綴樹遍歷。
這是程式碼：
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 $$這是每行產生的內容
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)只要沒有循環路徑，該算法就可以乾淨地工作。如果存在任何循環路徑，則必須在表中添加“已訪問”列。
添加訪問列後，以下是阻止循環關係的算法：
將給定 ID 放入隊列
用 0 標記所有訪問過
環形
- 出隊到 front_id
- 將所有 id 檢索到 queue_children 中，其 parent_id = front_id 並且visited = 0
- 使用visited = 1 標記剛剛檢索到的所有queue_children
- 將 queue_children 附加到 retval_list (rv)
- 入隊 queue_children
- 重複直到 queue 和 queue_children 同時為空
更新 2011-10-24 17:37 EDT
我創建了一個名為觀察的新表並填充了您的範例數據。我將儲存過程更改為使用觀察而不是 pctable。這是您的輸出：
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)更新 2011-10-24 18:22 EDT
我更改了 GetAncestry 的程式碼。
WHILE ch > 1應該有WHILE ch > 0mysql> 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)現在就試試 ！！！