태그 보관물: hierarchy

hierarchy

최고 수준의 계층 적 필드 찾기 : 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    |                |
+------------+--------------+------+-----+---------+----------------+

가 주어지면 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


답변