CS학습2026.10.096 min read

Graph Database: 관계를 일급 시민으로 다루는 인덱스 프리 인접성 탐색

그래프 데이터베이스(Graph Database)는 데이터를 노드(Node)와 간선(Edge)으로 저장하고, 관계 탐색을 핵심 연산으로 최적화한 데이터베이스다. 관계형 DB에서 다중 JOIN으로 표현하던 연결 질의를 경로 탐색으로 자연스럽게 표현할 수 있다. 이 글에서는 속성 그래프 모델, 저장과 탐색 원리, PostgreSQL 재귀 CTE 예제, 성능 특성

By 송민성

1. 개념

그래프 데이터베이스(Graph Database)는 데이터를 노드(Node, 정점) 와 간선(Edge, 관계) 으로 저장하고, 둘 사이의 연결 구조를 질의의 중심에 두는 데이터베이스다.

가장 널리 쓰이는 데이터 모델은 속성 그래프(Property Graph) 다.

노드: 엔티티를 나타낸다. 하나 이상의 레이블(Label)과 키-값 속성(Property)을 가진다.
간선: 노드 사이의 관계를 나타낸다. 방향(Direction)과 타입(Type)이 있고, 속성을 가질 수 있다.

text

(Alice:Person {name:"Alice"}) -[:FOLLOWS {since:2024}]-> (Bob:Person {name:"Bob"})

또 다른 모델로 RDF(Resource Description Framework) 가 있다. 데이터를 주어-술어-목적어 트리플(Triple)로 표현하며, SPARQL로 질의한다. 이 글은 속성 그래프를 중심으로 설명한다.

2. 왜 사용하는가

관계형 데이터베이스(RDBMS)에서 "친구의 친구의 친구"를 찾으려면 같은 테이블을 여러 번 JOIN해야 한다. 깊이가 늘수록 쿼리가 복잡해지고, 실행 계획도 비싸지기 쉽다.

그래프 데이터베이스는 다음 상황에서 이점이 있다.

다단계 관계 탐색: 깊이가 가변적인 경로 질의를 간결하게 표현한다.
스키마 유연성: 노드와 관계 타입을 추가해도 테이블 구조를 대규모로 바꿀 필요가 적다.
질의와 모델의 일치: 화이트보드에 그린 도식이 그대로 저장 모델과 질의 패턴이 된다.

반대로 단순한 CRUD, 집계 중심 분석, 정형 트랜잭션 처리에서는 RDBMS가 대체로 더 적합하다.

3. 동작 원리

인덱스 프리 인접성(Index-free Adjacency)

네이티브 그래프 저장소(예: Neo4j)는 각 노드가 자신과 연결된 간선에 대한 참조를 직접 가진다. 이웃 노드를 찾을 때 전역 인덱스를 조회하지 않고 포인터(참조)를 따라간다.

RDBMS의 JOIN: 외래 키 값으로 인덱스(예: B-Tree)를 조회해 대응 행을 찾는다.
네이티브 그래프: 현재 노드에서 연결 정보를 따라 인접 노드로 이동한다.

이 때문에 탐색 비용은 전체 데이터 크기보다 실제로 방문하는 부분 그래프의 크기에 더 의존한다. 시작 노드를 찾을 때는 여전히 인덱스를 사용한다.

탐색 알고리즘

그래프 질의의 기반은 다음과 같은 탐색이다.

너비 우선 탐색(BFS): 시작점에서 가까운 노드부터 방문한다. 최단 경로(가중치 없음)에 쓰인다.
깊이 우선 탐색(DFS): 한 경로를 끝까지 따라간 뒤 되돌아온다.

질의 언어

선언형 패턴 매칭 언어를 쓴다. Cypher(Neo4j에서 출발, openCypher로 공개), Gremlin(Apache TinkerPop의 명령형 탐색 언어), SPARQL(RDF용)이 대표적이다. 또한 SQL:2023에는 SQL/PGQ가 포함되어 관계형 테이블 위에서 그래프 패턴 질의를 표준화했다.

4. 코드 예제

Cypher: 친구의 친구 찾기

shell

cat <<'EOF'
MATCH (me:Person {name: 'Alice'})-[:FOLLOWS*2]->(fof:Person)
WHERE NOT (me)-[:FOLLOWS]->(fof) AND me <> fof
RETURN DISTINCT fof.name;
EOF

위 쿼리는 Alice에서 FOLLOWS 관계를 정확히 2단계 따라간 사람 중, 아직 팔로우하지 않은 사람을 반환한다. (Cypher 텍스트를 출력하는 예시이며, 실제 실행은 Neo4j 같은 엔진에서 한다.)

PostgreSQL: 재귀 CTE로 같은 탐색 구현

별도 그래프 엔진 없이도 PostgreSQL에서 재귀 CTE(Common Table Expression)로 그래프 탐색을 할 수 있다.

sql

CREATE TABLE person (
    id   INT PRIMARY KEY,
    name TEXT NOT NULL
);

CREATE TABLE follows (
    src INT NOT NULL REFERENCES person(id),
    dst INT NOT NULL REFERENCES person(id),
    PRIMARY KEY (src, dst)
);

CREATE INDEX idx_follows_dst ON follows(dst);

INSERT INTO person VALUES
  (1,'Alice'),(2,'Bob'),(3,'Carol'),(4,'Dave'),(5,'Erin');

INSERT INTO follows VALUES
  (1,2),(2,3),(3,4),(2,5),(5,1);

-- Alice(1)에서 최대 3단계까지 도달 가능한 사람과 최단 깊이
WITH RECURSIVE walk AS (
    SELECT dst AS id, 1 AS depth, ARRAY[src, dst] AS path
    FROM follows
    WHERE src = 1
  UNION ALL
    SELECT f.dst, w.depth + 1, w.path || f.dst
    FROM walk w
    JOIN follows f ON f.src = w.id
    WHERE w.depth < 3
      AND f.dst <> ALL (w.path)   -- 순환(cycle) 방지
)
SELECT p.name, MIN(w.depth) AS min_depth
FROM walk w
JOIN person p ON p.id = w.id
GROUP BY p.name
ORDER BY min_depth, p.name;

path 배열로 이미 방문한 노드를 기록해 순환 그래프에서 무한 재귀를 막는다. depth 제한도 함께 두는 것이 안전하다.

Python: 인접 리스트와 BFS

python

from collections import deque

graph = {
    "Alice": ["Bob"],
    "Bob": ["Carol", "Erin"],
    "Carol": ["Dave"],
    "Dave": [],
    "Erin": ["Alice"],
}

def shortest_path(graph, start, goal):
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(path + [nxt])
    return None

print(shortest_path(graph, "Alice", "Dave"))
# ['Alice', 'Bob', 'Carol', 'Dave']

그래프 DB의 최단 경로 질의도 개념적으로는 이와 같은 BFS 계열 탐색에 기반한다.

5. 시간 복잡도 또는 성능 특성

정점 수를 V, 간선 수를 E라 하자.

연산	복잡도
BFS / DFS (인접 리스트)	O(V + E)
한 노드의 이웃 순회	O(해당 노드의 차수(degree))
인덱스로 시작 노드 찾기	인덱스 종류에 따라 다름 (B-Tree면 O(log N))

핵심 성능 특성은 다음과 같다.

지역 탐색(시작점 주변 몇 단계)은 전체 데이터 크기와 상대적으로 무관하게, 방문하는 부분 그래프 크기에 비례한다.
깊이가 k이고 평균 차수가 d이면 방문 후보가 최대 약 d^k개까지 늘어날 수 있다. 깊이 제한이 없으면 비용이 급증한다.
전체 그래프를 대상으로 하는 집계나 분석(예: PageRank)은 별도의 그래프 분석 엔진이나 배치 처리가 적합한 경우가 많다.

6. 실무 사용 사례

소셜 네트워크: 친구 추천, 공통 관계 탐색.
추천 시스템: "이 상품을 산 사람이 함께 산 상품" 같은 협업 필터링 패턴.
사기 탐지(Fraud Detection): 계좌, 기기, 주소를 연결해 공유 자원으로 얽힌 의심 집단을 찾는다.
지식 그래프(Knowledge Graph): 엔티티와 관계를 연결해 검색, 질의응답, RAG의 맥락 검색에 활용한다.
권한/조직 구조: 계층과 상속이 깊은 접근 제어 관계 질의.
네트워크/IT 인프라 의존성 분석: 장애 영향 범위 추적.

대표 제품으로 Neo4j, Amazon Neptune, JanusGraph, ArangoDB(멀티모델) 등이 있다.

7. 주의할 점

슈퍼 노드(Super Node): 간선이 수백만 개씩 붙은 노드를 지나는 탐색은 느려진다. 모델링 단계에서 관계를 분리하거나 중간 노드를 두는 방식을 검토한다.
깊이 제한 없는 가변 길이 경로: * 같은 무제한 패턴은 결과가 폭발할 수 있다. 상한을 명시한다.
수평 확장(샤딩)의 어려움: 그래프는 데이터를 분할하면 파티션 사이를 가로지르는 간선이 생기므로 분산 구성이 상대적으로 까다롭다.
용도 불일치: 관계가 단순하거나 집계 중심 워크로드라면 RDBMS가 더 단순하고 성숙한 선택이다. 관계 깊이가 얕다면 JOIN만으로 충분한 경우가 많다.
재귀 CTE 사용 시: 순환 방지와 깊이 제한을 반드시 넣어야 무한 재귀를 막을 수 있다.
모델링 비용: 노드로 둘지 속성으로 둘지, 관계 방향과 타입을 어떻게 정할지가 질의 성능과 가독성을 좌우한다.

8. 핵심 정리

그래프 데이터베이스(Graph Database)는 노드, 간선, 속성으로 데이터를 저장하며 관계 탐색에 최적화되어 있다.
네이티브 그래프 저장소는 인덱스 프리 인접성(Index-free Adjacency)으로 이웃 노드를 참조를 따라 탐색한다.
지역 탐색 비용은 방문하는 부분 그래프의 크기에 비례하고, 기본 탐색 알고리즘 BFS/DFS는 O(V + E)다.
다단계 관계, 경로 탐색, 연결 패턴 분석에 강하고, 단순 CRUD나 집계 중심 워크로드에는 RDBMS가 더 적합하다.
PostgreSQL에서도 재귀 CTE로 소규모 그래프 탐색이 가능하지만, 순환 방지와 깊이 제한이 필수다.
슈퍼 노드, 무제한 경로 패턴, 분산 확장은 실무에서 먼저 점검할 위험 요소다.