참고 :이 질문은 현재 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 | |
+------------+--------------+------+-----+---------+----------------+가 주어지면 name최상위 부모를 어떻게 쿼리 할 수 있습니까?
주어진 name, id의 레코드와 관련된 모든을 어떻게 쿼리 할 수 name = '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 Stored Procedure Language를 통해 스크립트를 작성해야합니다.
다음은 GetParentIDByID검색 할 ID가 지정된 ParentID를 검색하기 위해 호출 된 저장 함수입니다.
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 ;다음은 GetAncestry1 세대부터 시작하여 상위 ID가 주어진 모든 계층 구조에서 ParentID 목록을 검색하기 위해 호출되는 저장 함수 입니다.
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로 대기열에서 제외
- parent_id = front_id 인 queue_children에 모든 ID를 검색하십시오.
- queue_children을 retval_list에 추가 (rv)
- 큐에 대기
- queue와 child_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로 대기열에서 제외
- parent_id = front_id이고 방문한 = 0 인 queue_children에 모든 ID를 검색하십시오.
- 방금 검색 한 모든 queue_children을 visited = 1로 표시하십시오.
- queue_children을 retval_list에 추가 (rv)
- 큐에 대기
- queue와 child_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 > 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)지금보십시오!
답변
지정된 노드의 모든 부모 가져 오기 :
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루트 노드를 얻으려면 예를 들어 ORDER BY level첫 번째 행을 취할 수 있습니다
지정된 노드의 모든 하위 가져 오기 :
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(문의 재귀 부분에서 조인에 대한 교환 조건에 유의하십시오)
내 지식으로는 다음 DBMS는 재귀 CTE를 지원합니다.
- FirebirdSQL 2.1 (실제로이를 구현 한 최초의 OpenSource DBMS)
- PostgreSQL 8.4
- DB2 (어떤 정확한 버전인지 확실하지 않음)
- 오라클 (11.2부터)
- SQL Server 2005 이상
- 테라 데이타
- H2
- Sybase (정확한 버전을 모름)
편집하다
샘플 데이터를 기반으로 다음은 각 노드의 전체 경로를 추가 열로 포함하여 테이블에서 모든 하위 트리를 검색합니다.
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결과는 다음과 같습니다.
아이디 | parent_id | 나무 ---- + ----------- + --------- 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
답변
FORMAT MySQL 함수는 천 단위 구분 기호에 쉼표를 추가하기 때문에 주어진 id가 4보다 큰 정수이면 Rolando의 답변 에서 GetFamilyTree 함수 가 작동하지 않습니다. 저장된 정수 GetFamilyTree를 다음과 같이 큰 정수 ID로 작동하도록 수정했습니다.
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