1. 그래프의 구조

노드, 에지

그래프는 노드와 에지 두 가지 요소를 사용해 사건의 관련성 등을 표현할 수 있는 수학적인 데이터 구조다.

일반적인 그래프는 다양한 형태의 에지를 연결할 수 있다.

인접

어떤 노드와 노드 사이에 에지가 존재하면 이 두 개의 노드는 인접하고 있다고 한다. 또는 연결 이라고 한다.

차수

어떤 노드에 인접한 노드 수를 차수 라고 한다.

보행, 트레일, 길

어떤 노드에서 다른 노드에 이르는 유한한 에지의 열을 보도(Walk)라고 한다. 보행은 임의의 유한한 ㅇㄹ이며 반복적으로 같은 노드를 통과해도 같은 에지를 따라가도 상관없다.

보행 중에 같은 에지를 두 번 통과하지 않는 것을 트레일(Trail)이라고 한다. 또한, 같은 노드를 두 번 통과하지 않는 것을 길(Path)라고 한다.

보통 디렉토리 경로 라는 말을 쓰는데 그 경로라는 단어가 그래프 이론의 Path 를 의미한다.

다중 에지

어떤 한 개의 노드에서 다른 노드로 여러 개의 에지가 연결된 상태를 다중 에지 라고 한다. 일반적인 그래프는 다중 에지가 어느 정도 있어도 괜찮다. 물론 다중 에지를 허용할지 허용하지 않을지에 따라서 그래프의 성질이 크게 달라진다.

다중 에지를 가진 그래프에서는 de와 같은 노드 쌍이 여러 개 생기게 된다. 이와 같은 표현은 에지를 고유하게 식별할 수 없으므로 에지 그 자체에 라벨을 붙여 에지를 식별한다.

루프

어떤 노드에서 같은 노드 자신으로 연결된 에지를 루프 라고 한다. 루프는 한번 통과해도 같은 노드에 이르는 것이 특징이다.

닫힌 보행

어떤 노드에서 같은 노드에 이르는 경로를 닫힌 보행 이라고 한다. 루프도 닫힌 보행의 일종이다. 또한, 다중 에지를 가진 두 개의 노드도 닫힌 보행이다.

시작과 끝이 되는 노드가 같고 게다가 같은 노드를 두 번 통과한다는 것이 요점이다.

연결

그래프 상의 모든 두 점 사이에 경로가 존재할 때, 그 때에 한해서 그 그래프는 연결돼 있다고 한다. 좀 더 알기 쉽게 말하자면 연결이란 그래프가 하나로 연결된 것이다.

부분 그래프

어떤 그래프에서 임의의 에지나 노드를 제거할 때 생기는 그래프를 부분 그래프라고한다.

컷세트, 브리지

어떤 연결 그래프에서 일부가 제거되어 그 부분 그래프의 연결이 없어진 에지의 집합을 비연결화 집합이라고 한다.

비연결화 집합 중에 어떤 에지가 없어도 비연결화 집합이 되지 않는 것, 다시 말하면 진 부분 집합만으로 연결을 해제할 수 없는 것, 기약인 것을 컷세트라고 한다.

컷세트 중에 가지고 있는 에지가 한 개뿐인 것을 브리지라고 한다.

에지의 방향과 가중치

그래프를 응용한 예

• 소셜 네트워크
• 웹 페이지의 링크
• 게시판
• 파일 시스템 등등

관계형 모델에서는 제대로 모델링 할 수 없을 가능성이 있다. 그리고 대상 그래프가 어떤 종류의 그래프인지 판별하는 것이 중요하다.

2. 그래프의 종류

일반 그래프

에지의 연결 방법에 특별한 제한이 없는 그래프를 일반 그래프 또는 단순하게 그래프라고 한다. 제한이 없으면 자유도가 높고 법칙을 발견하기 어려워 다루기가 어렵다.

단순 그래프

다중 에지 및 루프가 없는 그래프를 단순 그래프 라고 한다. 단순 그래프는 일반 그래프보다 다루기 쉽다.

연결 그래프 / 비연결 그래프

완전 그래프

단순 그래프 중 모든 노드가 서로 에지에 인접해 있는 그래프를 완전 그래프라고 한다. 노드 수 n에 대해 n - 1의 노드와 인접하므로 완전 그래프의 에지는 정확히 $n(n - 1) / 2$ 가 된다.

정규 그래프

모든 노드의 차수가 같은 그래프를 정규 그래프라 한다. 완전 그래프는 정규 그래프다. 정다면체와 같은 형태가 되는 그래프도 정규 그래프다.

평면 그래프

어떤 에지도 교차하지 않는 그래프를 평면 그래프다. 이것은 평면상에 기술할 수 있다는 의미이며 예를 들자면 회로 기판 등은 평면 그래프다.

유향 그래프 / 무향 그래프

에지의 연결이 단방향인 것을 유향 그래프, 방향이 정해지지 않은 것을 무향 그래프라 한다.

가중 그래프

각 에지에 가중치를 부여하ㅐ 노드 사이의 거리나 도달 시간 등을 비용을 표현한 모델을 가중 그래프라 한다.

트리(나무)

트리라는 구조는 데이터를 표현할 때에 자주 사용되지만 사실 트리는 단순 그래프의 매우 특별한 경우다.

3. SQL과 그래프의 상성 문제

노드의 집합과 에지의 다중 집합(단순 그래프라면 집합으로 가능)을 각각 저장하면 충분하다.

→ 인접 리스트 모델 이라고 한다.

단순히 그래프를 인접 리스트로 DB에 저장하는 것만으로는 그래프 특유의 쿼리에 대한 해답을 얻기 힘들다.

그래프의 쿼리

그래프에 대한 질의는 아주 많지만, 인접 리스트에서 그 답을 얻기 위한 쿼리를 SQL로 표현하는 것은 불가능하다.

무향 그래프를 표현할수 있을까?

‘a에서 f에 이르는 최단 경로는 어떤 것인가?’ 문제.

먼저 그래프를 RDB에 표현해야 한다. 인접 리스트를 사용해 표현하면 다음과 같다.

nodes // edges

해당 DB 설계에는 한가지 문제가 있다. 그것은 edges 테이블이 1NF가 아니라는 점이다. node1, node2는 반복 패턴이므로 1NF의 조건을 충족하지 않는다. 에지의 모델링은 일반적인 수단으로 다루기 어렵다.

원래 에지는 한 개의 단위로 되어 있으므로 두 개의 컬럼을 사용해 표현하는 것이 아니라 한 개의 컬럼 값으로 표현해야 한다. 에지를 표현할 수 있는 데이터 형은 요소 수가 두 개인 집합이다.

SQL에 그런 데이터형은 존재하지 않으므로 사용할 수 없다.

유향 그래프를 이용한 표현

유향 그래프라면 에지의 시작점과 끝점을 startnode, endnode 등으로 표현할 수 있다.

edges

릴레이션 관점에서 모델을 이해하자

무향 그래프를 전이주으이 유향 그래프로 표현하는 것은 그래프 이론의 모델과 다르다. 그러나 관계형 모델에서는 1NF가 아닌 표현보다도 바람직하다고 할 수 있다.

관계형 모델에서는 릴레이션, 즉 SQL에서 테이블에 저장하는 것은 ‘참이 되는 명제의 집합’ 이다. ‘a에서 b까지 비용 3으로 도달할 수 있다’ 라는 사실과 ‘b에서 a까지 비용 3으로 도달할 수 있다’ 라는 두 가지 사실은 ‘a와 b가 비용 3에 인접해 있다’ 는 사실에서 유추할 수 있는 사실이다.

릴레이션은 알려진 사실의 집합이므로 직접 다룰 수 없는 모델이어도 더욱 세세한 사실의 집합으로 분해해 취급한다는 접근 방법은 관계형 모델과의 친화성을 높인다고 생각한다.

행렬을 이용한 표현

그래프의 표현을 이용할 수 있는 수학적 모델로는 리스트 외에도 행렬이 있다.

edges - 행렬

각 노드를 연결하는 에지의 가중치를 요소로 표현한 것으로 인접 행렬이라고 한다. 이 행렬을 테이블에 적용은 잘 되지 않는다. 그 이유는 릴레이션과 행렬은 전혀 다른 개념이기 때문이다.

행렬의 구성은 2차원이고, 행과 열은 각각의 순서가 정해져 있으며 요소는 2차원적으로 배열돼 있다. 한편 릴레이션은 속성에도 튜플에도 순서가 없다. SQL의 속성에 해당하는 컬럼에는 순서가 있지만, 쌍에 해당하는 행에는 순서가 없다.

또 다른 이유로 테이블은 쉽게 컬럼을 늘릴 수 없다. 노드가 늘어날 때 ALTER TABLE tbl_name ADD… 를 실행하고 처리한다면 처리에 시간이 너무 걸려 구현하기 어렵다. 릴레이션은 사전에 형을 정의해 사용한다.

동적으로 컬럼을 추가해야 하는 것은 데이터를 컬럼 정의라는 메타 데이터에 포함시키려고 하기 때문이다.

→ 이와 같은 설계는 메타 데이터 트리블 이라는 안티 패턴이다.

그래프에 대한 쿼리

유향 그래프를 표현한 테이블을 생각해보자. a에서 f에 이르는 최단 경로는 어떤 것인가? 라는 질의에 응항 쿼리는 어떻게 작성할까?

우선 a에 인접한 노드 리스트는 다음과 같다.

SELECT end_node
FROM edges
WHERE start_node = 'a';

이 쿼리에서 얻은 노드는 b와 e다. 이 다음 노드를 구하려면 어떻게 해야 할까?

선언형 언어에서 쿼리는 한 번에 작성해야 한다. 한가지 답으로 생각할 수 있는 것은 결합(같은 테이블에 JOIN)을 사용하는 것이다.

SELECT end_node
FROM edges e1
JOIN edges e2
ON e1.end_node = e2.start_node
WHERE e1.start_node = 'a';

마찬가지로 3회, 4회.. 로 JOIN 횟수를 늘리면 a에서 f에 이르는 경로를 얻을 수 있다.그러나 이 방법에는 문제가 있다.

가장 큰 문제는 JOIN을 몇 번 실시해야 답을 얻을 수 있는지 미리 알 수 없다.

SQL은 선언적 프로그래밍 언어로 ‘어느 데이터가 필요한가?’ 를 작성한다. 주어진 조건에 따라 쿼리는 실행하지만 쿼리를 실행한 겨로가, 얻은 데이터의 내용에 따라 후속 처리의 내용은 영향을 받지 않는다.

SELECT는 최초에 제시한 조건에 맞는 데이터를 집합 연산으로 도출해 반환할 뿐이다. 따라서 SELECT 구문을 제대로 정해두지 않으면 안되므로 ‘임의의 횟수의 JOIN을 수행한다’는 할 수 없다.

모든 노드를 조사하려면 최대 n - 1회의 JOIN이 필요하다. 이렇게 하여 f에 도달할 수 있는 모든 경로를 찾고 이를 정렬하지 않으면 최단 경로를 찾을 수 없을 것이다.

절차형에 의한 해법

다익스트라 알고리즘 등을 적용하여 구해야 한다.

단일 SELECT만으로 해결할 수 없으므로 최소한 스토어드 프로시저를 사용해 절차적 알고리즘을 구현해야 한다.

## 다익스트라 알고리즘 구현
mysql> call dijkstra('a', 'f');

WITH 절을 사용한 재귀적인 쿼리의 호출을 지원하는 RDB 제품도 있지만, 그 기능을 사용해도 다익스트라 알고리즘은 구현할 수 없다.

이처럼 그래프에 대한 질의는 스토어드 프로시저를 사용해 구현하는 편이 잘 될 때가 많다. 물론 질의의 복잡성, 즉 필요로 하는 알고리즘에 따라 여러 개의 SELECT 로 표현할 수 있는 것도 있지만 다양한 조건에 따라 그래프를 탐색할 때는 역시 절차형 처리가 필요하다.

그래프 DB

노드와 에지만으로 데이터를 표현하는 DB로는 그래프 DB가 있다. 만약 문제의 중심이 그래프이고 관계형 DB를 설계할 필요가 없을 때는 그래프 DB를 사용해야 한당. 그래프 DB는 그래프의 검색을 효과적으로 작성할 수 있다는 이점이 있다.

그러나 전체적으로 봤을 때 관계형 모델의 DB 설계가 필요하다면 전부를 그래프 DB로 표현하는 것은 무리가 있다. → RDB와 그래프 DB를 병행하도록 하자.

그래프 DB는 다익스트라 알고리즘 등이 구현돼 있으며 그러한 용도가 있을 때는 매우 편리하다. 또한, 계산량이 많은 알고리즘이 필요할 때는 RDB에서 부하를 분산하는 용도로도 활용할 수 있다.

FlockDB

FlockDB는 RDB의 중 하나로 MySQL을 백엔드로 사용하는 그래프 DB이다. 트위터에서 개발했으며, 아파치 라이선스 2.0에 공개돼 있다. 트위터는 FlockDB를 사용해 130억 개 이상의 에지를 관리하고 있다.

FlockDB가 그래프 DB라고 해도 그래프를 탐색하는 쿼리를 작성할 수 없다는 중대한 결점이 있다. 일반적인 그래프의 문제를 해결하기 위해서는 제구실은 못하지만 트위터와 같은 초 거대한 소셜 그래프 데이터를 여러 대의 서버에 수평 분산해 관리하는 드으이 방법으로 택하고 있다.

그 외의 문제

그래프는 RDB가 가진 최대의 매력인 데이터의 정합성을 담보하기 어렵다는 문제가 있다.

예를 들어 다음과 같은 조건을 보장하는 제약은 어떻게 작성해야 할까?

• 에지를 추가한 다음에 루프나 닫힌 보행이 없는가
• 에지를 삭제해도 그래프가 연결돼 있는가
• 평면인가

관계형 모델은 술어논리를 기반으로 하는 데이터 모델이다. 위 제약을 확인하려면 그래프 이론에 근거하는 알고리즘이 필요하다. 단순한 논리 연산으로는 확인할 수 없다.

그러나 한 쌍의 노드 사이에 최대 한 개의 에지만 있는, 즉 단순 그래프처럼 매우 간단한 것이라면 DB의 제약으로 표현할 수 있다.

4. 트리

트리는 그래프의 일종

트리는 그래프의 일종으로 다음의 특징이 있다.

• 닫힌 보행이 없이 연결돼 있다.
• 모든 에지는 브릿지다.
• 임의 두 개의 노드를 연결하는 경로는 한 개뿐이다.
• 인접하지 않은 어떤 두 개의 노드를 연결해도 닫힌 보행이 될 수 없다.

컴퓨터에서 모델링할 때 사용되는 트리는 다음과 같은 조건을 가지고 있다.

• 부모 자식 관계가 있는 유향 그래프다.
• 어떤 노드로 향하는 에지는 한 개뿐이다.
• 모든 노드에 출발점이 되는 노드가 있다.(뿌리 or Root)
• 뿌리에서 거리의 깊이로 표현한다.(계층구조)

트리도 그래프의 일종이므로 관계형 모델에서는 잘 처리할 수 없다. 그러나 트리는 일반적인(넓은 의미의) 그래프와 다르고, 앞서 언급한 것처럼 좋은 조건이 있다. 그래프 전반을 능숙하게 처리한다는 시도는 어렵지만 트리라는 형식만을 대상으로 하면 비교적 쉽게 처리할 수 있다.

인접 리스트 모델

트리도 인접 리스트를 이용해 표현할 수 있다. 그러나 에지에 대해서는 부모의 방향으로 한 개만 있으면 충분하므로 노드에 ‘부모의 노드 ID’로 표현하는 경우가 많다.

tree

이 테이블에는 parent_id가 NULL인 행이 있다.

NULL이 허용되는 이유

이 NULL은 어떤 의미에선 어쩔 수없다. 이전의 그래프 예처럼 노드와 에지는 다른 테이블에 저장해야 하는데, 이를 무리하게 같은 테이블에 넣었기 때문이다. → 비정규화된 상태

인접 리스트 모델은 최대 한 개의 부모밖에 없다는 트리의 특징을 우연히 이용하고 있는 것에 지나지 않다.

엄밀히 트리를 인접 리스트 모델로 관리하려면 테이블을 나눠야 하지만 나눌 경우 root의 노드에 대한 데이터가 저장되지 않으므로 root에 대한 정보를 별도로 저장해야한다.

nodes

edges

root_nodes

이와 같이 나누면 여러 개의 root가 있는 트리도 쉽게 관리할 수 있다.

인접 리스트 모델이 재귀적인 SQL의 표현(with recursive 등)을 지원하는 RDB 제품이라면 간단하게 작성할 수 있다. 다음 쿼리는 ‘노드 f의 계층 깊이는 얼마인가?‘를 구하는 쿼리다.

WITH RECURSIVE r AS (
	SELECT 1 AS level, node_id, parent_id
	FROM tree
	WHERE parent_id IS NULL
UNION ALL
	SELECT r.level + 1, t.node_id, t.parent_id
	FROM r JOIN tree t
	ON r.node_id = t.parent_id)
SELECT * FROM r WHERE node_id = 'f';

경로 열거 모델

트리는 임의의 두 개의 노드 사이에 경로가 한 개만 존재하지 않는다. 이 성질을 이요하면 ‘각 노드의 root에서의 경로’를 이용해 트리를 표현할 수 있다. 다음은 트리를 경로 열거 모델로 표현한 것이다.

tree

경로 열거 모델은 미리 경로가 있어야 하므로 임의의 노드 사이의 부모 관계를 한 번에 알 수 있다.

그러나 경로 열거 모델로 이용하는 경로는 비정규화 된 데이터외에는 없기 때문에 그 외의 질의는 어렵다.

해당 테이블은 경로의 구분 문자로 슬래시(/)를 사용하고 있다. 어떤 노드가 포함돼 있는지 알아보려면 문자열을 분해해 노드를 취득하지 않으면 안 된다. 따라서 인덱스를 효율적으로 사용할 수 없고 갱신할 때 데이터의 부정합이 생길 가능성이 생긴다.

다만 경로 열거 모델은 트리의 성질을 잘 활용하므로 경로의 검색 자체는 비교적 쉽게 수행 할 수 있다.

다음 쿼리는 ‘b의 자식 노드는 어떤 것인가?’ 이다.

SELECT *
FROM tree
WHERE path LIKE CONCAT((
	SELECT path
	FROM tree
	WHERE node_id = 'b'), '%');

이 쿼리는 path에 인덱스가 설정돼 있다면 LIKE 절을 사용한 범위 검색으로 비교적 빠르게 처리할 수 있다. 이와 같은 쿼리를 작성할 수 있는 이유는 같은 노드를 통과하는 경로의 표현이 같다는 성질을 기반으로 하고 있다.

한편 갱신 처리는 꽤 번거롭다. 예를 들어 ‘노드 b를 삭제하고 그 자식을 b의 부모 노드에 연결한다’는 처리는 어떻게 할까? → 당연히 b가 포함된 경로, 즉 b의 자식 경로를 모두 갱신해야 한다.

자식을 구하기 위한 검색 조건은 조금 전과 같아도 괜찮다. 자식의 경로에서 b를 포함하지 않는 것을 재작성하려면 SUBSTRING() 함수를 사용해 b 이하의 경로를 잘라서 b의 부모의 경로와 연결하는 작업이 필요하다.

이렇게 번거로운 처리가 필요한 이유는 path가 비정규화된 컬럼이기 때문이다. 따라서 사용자 자신의 손으로 컬럼의 내용을 분해, 가공, 결합해야한다.

경로 열거 모델은 관계형 모델의 좋은 점을 망칠 위험성을 내포하고 있어서 그 점을 잘 피할 수 있는지 여구바 경로 열거 모델을 사용 여부를 결정하는 관건이 된다.

중첩 집합 모델

중첩 집합이라는 데이터 구조를 사용해 트리를 표현한 것이다. 트리를 직접 표현하는 모델은 아니라서 조금 이해하기 어려운 모델이다.

중첩 집합 모델을 이해하려면 사고의 전환이 두 번 필요하다. 첫 번째는 중첩 집합은 ‘부모 노드에 자식 노드가 포함돼 있다’는 규칙에 따라 트리를 집합으로 바꾸었다는 점이다.

두 번째 사고의 전환은 집합에서 수치로 매핑한다는 점이다. 중첩 집합은 같은 계층이 노드에 ‘왼쪽 노드의 최댓값보다, 오른쪽 노드의 최솟값이 크다는 상태가 된다.

테이블 상에 표현하기 위해서 각 집합이 가진 ‘수치’의 ‘왼쪽의 값과 오른쪽의 값’이라는 수치를 사용해 표현한다.

→ 이 집합에 포함된 수치의 최솟값과 최댓값은 무엇인가? 로 바꿔 말할 수 있다.

이 수치를 사용해 자식 노드의 최솟값보다 부모 노드의 최솟값을 작게 할당하고, 자식 노드의 최댓값보다 부모 노드의 최댓값을 크게 할당해 집합의 포함 관계를 표현한 것이다.

중첩 집합을 테이블로 표현

자식 노드의 값의 범위가 부모 노드의 값의 범위에 포함돼있는 것을 알 수 있을 것이다. 중첩 집합이란 이처럼 수치의 범위를 사용해 마치 집합 이론의 포함 관계처럼 부모 관계를 나타낸 모델이다.

중첩 집합 모델은 어떤 노드의 left와 right의 값의 사이에 다른 노드의 left와 right의 값이 있는지를 이용해 부모/자식 관계를 나타낸다.

중첩 집합 테이블(tree)

노드 b의 자식을 구하는 쿼리다.

SELECT t1.node_id
FROM tree t1 JOIN tree t2
WHERE t2.node_id = 'b'
	AND t1.left BETWEEN t2.left AND t2.right;

노드 b의 부모를 구하는 쿼리다.

SELECT t1.node_id
FROM tree t1 JOIN tree t2
WHERE t2.node_id = 'b'
	AND t1.left < t2.left AND t1.right > t2.right;

관계형 모델과 궁합이 나쁜 이유

중첩 집합 모델은 집합을 이용한다고 하지만 집합 이론을 기반으로 한 관계형 모델과 친화성이 높은 것은 아니다. 오히려 궁합은 최악이다.

1. left와 right는 반복 패턴이므로 중첩 집합이 있는 테이블은 1NF의 요건을 만족하지 않는다.

문제가 되는 것은 left와 right는 양쪽 모두 같은 수직선 상의 수치를 표현하고 있다. 양쪽의 벡터는 같고 이 두 개의 컬럼은 직교하지 않으므로 반복 패턴이 된다. 관계형 모델은 릴레이션의 각 속성이 직교하지 않으면 안된다. 속성끼리 상관관계가 있어서는 안된다.

2. left와 right의 값은 전부 트리를 표현하기 위해서 사용되며, 그 외의 다른 컬럼 값과의 관련성도 없다.

RDB가 가진 외부키 제약 등을 적용할 수 없고, left와 right의 의미는 중첩 집합의 내부에서만 적용된다. 응용프로그램에서 중첩 집합의 로직을 바르게 구현하지 못하면 데이터의 정합성을 보장할 수 없게 된다.

3. 트리의 갱신 처리가 매우 복잡하다.

중첩 집합에서 자식 노드를 추가하려면 자식 노드가 들어갈 공간을 만들기 위해서 많은 노드를 갱신해야 한다.

4. 가장 큰 문제점은 집합이라고 해도 중첩 집합과 릴레이션과는 성질이 다르다.

중첩 집합은 집합의 포함 관계를 테이블에 각 행으로 표현한 모델이다. 한 개의 행이 한 개의 집합에 대응하고 있다고 할 수 있다.

관계형 모델은 릴레이션 그 자체가 집합이 되므로 집합의 사용법이 완전히 다르다.

클로저 테이블

클로저 테이블은 모든 노드에 대해 ‘노드 x는 노드 y의 부모다’ 라는 정보를 조사하고, 저장한 테이블이다. 닫힌 보행인 그래프는 이와 같은 관계를 표현할 수 없으므로 이것 또는 트리의 특성을 잘 사용한 모델이라고 할 수 있다.

클로저 테이블(tree)

클로저 테이블은 계통에 연결이 있는 노드에 대한 정보를 저장하므로 크기가 매우 크다. x라는 노드에 n개의 자식 노드가 있다면 테이블에 n행의 데이터가 저장된다.

→ root 노드에는 다른 모든 노드와의 관계가 기록된다.

테이블에 저장해야 할 데이터의 양은 트리가 깊어지면 깊어질수록 늘어난다. 최악의 경우는 모든 노드가 한 개의 자식 노드만 가질 때다. 이 같은 경우 클로저 테이블의 행 수는 $[n(n+1)]/2$ 가 된다.

반대로 최소의 깊이가 1 이내의 트리로 root 이외의 모든 노드가 root 바로 아래의 자식 노드일 때다.

→ 클로저 테이블의 행수는 $n - 1$ 이 된다.

데이터양은 많아지지만 클로저 테이블은 관계형 모델에 대한 친화성이 높은 것이 특징이다. 클로저 테이블은 정규화되어 있고 정합성을 보장하므로 외부키를 쓸 수 있다.(외부키로 노드가 실제로 존재하는 것을 보장함)

클로저 테이블의 작성은 ‘노드 x는 노드 y의 부모다’이며 평가한 결과가 참이 되는 x와 y가 저장돼 있다.

→ 클로저 테이블에 대한 질의는 관계형 모델에 맞는 쿼리이므로 직관적으로 이해하기 쉽다.

다음은 ‘c의 자식은 어느 것인가?‘에 대한 쿼리다.

SELECT descendant
FROM tree
WHERE ancestor = 'c';

응용프로그램은 이 결과를 사용해 트리를 그리는 경우가 많을 것이다. 요점은

얻은 정보를 바탕으로 트리를 재구성할 필요가 있다.

RDB가 다루는 것은 어디까지나 사실의 집합이며 쿼리로 얻을 수 있는 것은 사실에서 논리적인 연역에 의해 도출되는 새로운 사실의 집합이다. 이 사실의 집합을 가공해 표현하는 것은 응용프로그램의 역할이다.

응용프로그램이 데이터를 저장할 때 응용프로그램이 인식하고 있는 구조화된 데이터를 사실의 집합으로 분해해야 한다.

다음은 ‘b는 f의 부모인가?’ 라는 질문에 대한 쿼리다.

SELECT
	CASE WHEN COUNT(1) = 0 THEN 'no'
	ELSE 'yes' END
FROM tree
WHERE ancestor = 'b'
AND descendant = 'f';

‘g의 깊이’를 구하는 쿼리다.

SELECT COUNT(1)
FROM tree
WHERE descendant = 'g';

부모 자식 관계에 있는 임의의 노드 사이의 거리를 구하는 것은 쌍방의 깊이를 계산하고 차를 구하면 된다. 깊이를 다시 계산하는 것이 늦어질 때는 미리 깊이에 대한 정보를 저장하는 컬럼을 추가해두는 것도 하나의 방법이다.

특히 깊이에 관계가 있는 쿼리를 자주 작성할 때, ‘c의 자식노드(직접 연결되는 자식)는 어느 것인가?‘라는 질의에 자주 대답해야 할 때에 유용하다. 또한, 깊이의 정보를 이용하면 응용프로그램이 트리를 재구축할 때 도움이 된다.

트리와 SQL에 관한 고찰

트리는 일반적인 그래프보다 훨씬 구조가 간단해서 구현에 따라 RDB에서 능숙하게 다룰 수 있다. 특히 클로저 테이블은 관계형 모델과 친화성이 높고, 저자가 추천하는 방법이다. 그다음은 단순 인접 리스트 모델이다.

그러나 이러한 모델과 같은 트리 구조는 RDB 외부의 세계다. 클로저 테이블이라도 트리 구조를 이해하여 데이터를 저장하고 있지 않는다는 점에 주의해야 한다.

노드의 인접에 모순이 없는지 등을 RDB가 보장할 수 없다.

트리의 특성이 만족하는 조건(닫힌 보행이 없이 연결돼 있다)을 만족하도록 RDB쪽에서 보장해주는 구조는 없다.

→ 응용프로그램에서 주의 깊게 모순이 생기는 변경이 일어나지 않도록 로직을 작성하는 등의 대책이 필요하다.

요약

그래프는 관계형 모델에 없는 개념이므로 RDB에서 잘 다루기는 어렵다. 특히 쿼리에 따라서 어떤 데이터가 필요한지가 요점이므로 임의의 깊이 탐색이 필요없다면 FlockDB와 같은 그래프 DB를 사용하는 것도 좋다.