Closure pattern
hierarchy 구조를 저장하는 방법중 그래도 꽤 괜찮은 방법이다.
핵심은 데이터는 데이터대로 저장하는데 데이터 간의 관계(vertex)를 별도의 테이블에 저장하는 방식이다.
그런데 단순히 저장만 하는 것이 아니라 모든 관계를 다 저장한다 parent → child 심지어 자기 자신까지도 저장한다.
대신 두개의 테이블이 필요하다. 다음의 나오는 코드는 SQL antipattern 의 순전한 트리 챕터를 참고했다.
CREATE TABLE Comments (
comment_id SERIAL PRIMARY KEY,
author varchar(50) NOT NULL,
comment TEXT NOT NULL
);
insert into Comments(comment_id, path, author, comment)values(1, '1/', 'Fran', '이 버그의 원인이 뭘까?' ), (2, '1/2/', 'Ollie', '널 포인터 때문인 것 같아'),(3, '1/2/3/', 'Fran', '아니, 그건 확인해봤어.'), (4, '1/4/', 'Kukla', '입력값이 효한지 확인할 필요가 있어'),(5, '1/4/5/', 'Ollie', '그래, 그게 버그야'), (6, '1/4/6/', 'Fran', '그래, 확인하는 코드를 추가해'),(7, '1/4/6/7/', 'Kukla', '수정됐어.');
SQL
복사
쇠파이프 에서 user 에 해당하는 테이블이고
CREATE TABLE TreePaths (
ancestor BIGINT UNSIGNED NOT NULL,
descendant BIGINT UNSIGNED NOT NULL,
PRIMARY KEY(ancestor, descendant),
FOREIGN KEY (ancestor) REFERENCES Comments(comment_id),
FOREIGN KEY (descendant) REFERENCES Comments(comment_id)
);
insert into TreePaths values (1, 1), (1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(2,2),(2,3),(3,3),(4,4),(4,5),(4,6),(4,7),(5,5),(6,6),(6,7),(7,7);
SQL
복사
위의 댓글 중 4번에 해당하는 댓글들을 가져오려면 다음과 같이 질의 하면 된다.
code block 에 테스트해볼 수 있는 데이터를 넣어두었으니, 실행해보자
SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.descendant
WHERE t.ancestor = 4;
SQL
복사
6번에 해당하는 상위 댓글들을 가져오려면 다음과 같이 질의한다.
SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.ancestor
WHERE t.descendant = 6;
SQL
복사
새로운 노드 추가
1.
5의 reply 글을 작성한다 → commend id: 8
2.
8이 8을 참조하는 path 를 만들어 저장하고
3.
5를 descendant 로 참조하는 모든 행을 복사해 descandant 를 새로운 comment id 8 로 바꾸어 저장한다.
•
그래야 1 → 4 → 5 → 8 로 path 를 저장한다.
insert into comments(comment_id, author, commend) value (8, 'koko', 'ㅋㅋㅋㅋㅋ');
INSERT INTO TreePaths (ancestor, descendant)
SELECT t.ancestor, 8
FROM TreePaths AS t
WHERE t.descendant = 5
UNION ALL
SELECT 8, 8;
SQL
복사
leaf 노드 삭제
DELETE FROM TreePaths WHERE descendant = 7;
SQL
복사
그냥 해당하는 node 의 path 를 제거한다.
중간 node 삭제
서브트리, 4번을 삭제한다고 가정하면, 4를 descendant 로 가지는 모든 path 와 4의 ancestor 모두를 제거한다.
DELETE FROM TreePaths
WHERE descendant IN
(SELECT descendant FROM TreePaths WHERE ancestor = 4);
SQL
복사
위 두 과정에서 comment 자체를 삭제하는 것이 아니다. 오로지 path 만 삭제하는 것임을 유의 하자
트리 옮기기
1.
서브트리의 최상위 노드와 그 노드의 자손들을 참조하는 행을 삭제한다.
•
자신을 포함하는 참조는 삭제하지 않도록 한다.
•
위의 6을 자손으로 포함하는 모든 노드의 참조 제거
•
6의 후손을 전체 노드에서 자손으로 포함하는 모든 노드의 참조 제거
•
삭제 대상: (1, 6), (1, 7), (4, 6), (4, 7)
2.
새로운 위치의 조상들과 서브트리의 자손들을 붙인다.
•
CROSS JOIN 문법으로 카테시안 곱을 생성해 모든 노드를 만들어낸다.
•
생성: (1, 6), (2, 6), (3, 6), (1, 7), (2, 7), (3, 7)
삭제
DELETE FROM TreePaths
WHERE descendant IN (SELECT descendant
FROM TreePaths
WHERE ancestor = 6)
AND ancestor IN (SELECT ancestor
FROM TreePaths
WHERE descendant = 6
AND ancestor != descendant);
SQL
복사
생성
INSERT INTO TreePaths (ancestor, descendant)
SELECT supertree.ancestor, subtree.descendant
FROM TreePaths AS supertree
CROSS JOIN TreePaths AS subtree
WHERE supertree.descendant = 3
AND subtree.ancestor = 6;
SQL
복사
개선
pathlength 속성을 추가해 테이블을 개선할 수 있다. 자기 자신에 대한 pathlength 는 0, 자식은 1, 손자는 2 로 설정해둘 수 있다. 책에서는 이렇게 나왔지만, 이건 테이블에 실제 저장하는 값이 아니라 sub query 를 사용해 해결해야 하는 문제가 아닐까 싶다.
SELECT *
FROM TreePaths
WHERE ancestor = 4 AND path_length = 1;
SQL
복사
이렇게 질의하면 바로 질의가 가능하다
다음 글은 hierarchy 로 검색하다 찾은 글을 이다.
Managing Hierarchical Data in MySQL 100% 그대로 번역하지 않고 이해한 것을 바탕으로 요약 하였으니 꼭 원문을 읽어보는 것을 추천한다.
계층형(hierarchical) 데이터를 mysql 에서 관리하기
SELECT * FROM category ORDER BY category_id;
+-------------+----------------------+--------+
| category_id | name | parent |
+-------------+----------------------+--------+
| 1 | ELECTRONICS | NULL |
| 2 | TELEVISIONS | 1 |
| 3 | TUBE | 2 |
| 4 | LCD | 2 |
| 5 | PLASMA | 2 |
| 6 | PORTABLE ELECTRONICS | 1 |
| 7 | MP3 PLAYERS | 6 |
| 8 | FLASH | 7 |
| 9 | CD PLAYERS | 6 |
| 10 | 2 WAY RADIOS | 6 |
+-------------+----------------------+--------+
10 rows in set (0.00 sec)
SQL
복사
tree 로 select 하는 방법은 self join 을 사용한다. (JPA 보단 jooq, jpql 을 사용 하는 것이 좋겠다.)
SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';
SQL
복사
각 row (node) 는 parent id 값을 가지고 있으며, parent id 값이 null 이라면 그 node 는 root 가 된다.
select leaf nodes
SELECT t1.name FROM
category AS t1 LEFT JOIN category as t2
ON t1.category_id = t2.parent
WHERE t2.category_id IS NULL;
SQL
복사
t1 은 데이터가 있는 node 이고, t1 을 parent 로 가지고 있는 node 들을 찾는 것이다.
leaf node 는 가장 밑에 있는 node 이므로, 그 무엇도 parent 로 가지지 않는다. 따라서 t2.parent 가 null 인 (부모로 참조하지 않는 데이터) node 를 가져온다.
select one node path
SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';
SQL
복사
상단에 잘 그려진 tree 이미지 를 확인하면 eletronics → portable eletronics → mp3 player → flash 로 옴을 확인할 수 있다.
nested 모델(join 을 줄일 수 있다)
CREATE TABLE nested_category (
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL
);
SQL
복사
INSERT INTO nested_category VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
(4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
(9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);
SQL
복사
SELECT * FROM nested_category ORDER BY category_id;
+-------------+----------------------+-----+-----+
| category_id | name | lft | rgt |
+-------------+----------------------+-----+-----+
| 1 | ELECTRONICS | 1 | 20 |
| 2 | TELEVISIONS | 2 | 9 |
| 3 | TUBE | 3 | 4 |
| 4 | LCD | 5 | 6 |
| 5 | PLASMA | 7 | 8 |
| 6 | PORTABLE ELECTRONICS | 10 | 19 |
| 7 | MP3 PLAYERS | 11 | 14 |
| 8 | FLASH | 12 | 13 |
| 9 | CD PLAYERS | 15 | 16 |
| 10 | 2 WAY RADIOS | 17 | 18 |
+-------------+----------------------+-----+-----+
SQL
복사
여기서 column 명 lft 는 left 이다. 하지만, mysql 에서 left, right 는 예약어가 존재한다.
leaf node 검색
SELECT name FROM nested_category WHERE rgt = lft + 1;
SQL
복사
leaf node 의 특징은 right = left + 1 이 성립된다.
Single path 검색
SELECT parent.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'FLASH'
ORDER BY parent.lft;
SQL
복사
flash node 의 left 값을 n으로 가정할 때 parent.left < n < parent.right 인 parent.node 를 반환한다.
nested 인 이유는 root 가 모든 node 의 left, right 값을 root.left < 모든 노드의 left, right < root.right 가 성립하기 때문이다.
node 의 depth 계산하기
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name, node.lft
ORDER BY node.lft;
SQL
복사
위와 같이 depth 값을 알아낸다면, indent 를 추가하여 반환하는 것도 query 를 통해서 실행할 수 있다.
SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name, node.lft
ORDER BY node.lft;
SQL
복사
특정 지점의 하위 노드를 모두 가져오기
root 를 제외하고 node 를 찾으면 query 의 결과가 깨지는데 이러한 문제를 해결하기 위해 sub_parent 라는 테이블을 임의로 만들어 join 한다.
SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
nested_category AS parent,
nested_category AS sub_parent,
(
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'PORTABLE ELECTRONICS'
GROUP BY node.name, node.lft
ORDER BY node.lft
)AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name, node.lft, sub_tree.depth
ORDER BY node.lft;
SQL
복사
새로운 노드 추가하기
여기서 televisions 과 portable electronics 사이에 새로운 node 를 추가한다고 하면 어떻게 해야 할까?
1.
lock 을 건다.
2.
portable 에 해당하는 모든 node 의 left, right 값이 +2 씩 되어야 하고
3.
원래 portable 의 left 값이 새로운 노드의 left, right 는 left + 1 이 되어야 한다.
4.
lock 을 푼다.
LOCK TABLE nested_category WRITE;
SELECT @myRight := rgt FROM nested_category // 9 반환(television 의 right 값)
WHERE name = 'TELEVISIONS';
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO nested_category(name, lft, rgt) VALUES
('GAME CONSOLES', @myRight + 1, @myRight + 2);
UNLOCK TABLES;
SQL
복사
노드 삭제
추가와 맞찬가지로 node 가 제거되는 데는 lgt, lft -2 가 필요하다
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
UNLOCK TABLES;
SQL
복사