Graph Database Physics (Nodes & Edges)

1. Overview

그래프 데이터베이스 역학(Graph Database Physics)은 "데이터 그 자체보다, 데이터 간의 **관계(Relationship)**가 더 중요하다"는 철학으로, RDBMS의 복잡한 조인(Join)과 NoSQL의 고립된 계층 모델을 파괴하고 탄생한 수학적 그래프 이론 기반의 저장 엔진을 해부합니다.

학습자는 노드(Node, 정점)와 엣지(Edge, 간선)라는 1급 시민(First-class Citizen)으로 현실 세계의 소셜 네트워크, 추천 시스템, 사기 탐지망을 직관적으로 스케치하는 **속성 그래프 모델(Property Graph Model)**을 뜯어봅니다. 나아가 RDBMS처럼 인덱스나 PK를 타지 않고 메모리 상의 물리적 포인터를 징검다리 건너듯 직접 타고 넘어가는 **Index-Free Adjacency (인덱스 없는 인접성)**의 고속 그래프 탐색 물리 엔진을 해부합니다. 마지막으로 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)의 알고리즘 렌즈를 통해 Cypher 같은 그래프 쿼리 언어의 동작 방식과 최단 경로, 커뮤니티 탐지 메커니즘을 장악하여 초연결 데이터(Connected Data) 모델링 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 속성 그래프 모델 (Property Graph): 노드(Node/Vertex), 엣지(Edge/Relationship), 레이블(Label), 프로퍼티(Property/Key-Value 속성), 방향성 엣지(Directed Edge).
• 스토리지 엔진 (Storage Physics): 인덱스 없는 인접성(Index-Free Adjacency), 메모리 내 포인터 홉핑(Pointer Hopping), RDBMS 조인 비용과의 빅오(Big-O) 비교.
• 그래프 탐색과 알고리즘 (Traversal & Algorithms): DFS, BFS, 최단 경로(Shortest Path: Dijkstra), 페이지랭크(PageRank), 사이클 탐지.
• 쿼리 언어 패러다임 (Query Paradigm): 패턴 매칭 쿼리 (Neo4j Cypher 형태의 아스키 아트 매칭: (u:User)-[:KNOWS]->(f:User)).

Out-of-Scope

• 시맨틱 웹 및 RDF 삼원조 (RDF Triples): 학술/온톨로지 목적의 SPARQL 및 시맨틱 웹 그래프 DB(블레이즈그래프 등) 심화 → 속성 그래프(Property Graph, Neo4j 중심) 실무 환경으로 제한.
• 알고리즘 증명 수학: 다익스트라나 페이지랭크의 행렬 고유값 증명 → 04-04 Graph Foundations 알고리즘 구현 영역.

Boundaries

• RDBMS 다대다(N) 매핑 vs Graph DB 엣지: RDBMS는 '사람'과 '사람'의 '친구' 관계를 만들려면 무조건 중간 교차 테이블(Mapping Table)을 두어야 합니다. 친구의 친구의 친구(3 Depth)를 찾으려면 교차 테이블과 사람 테이블을 6번 조인해야 하며, 데이터가 많을수록 교집합 연산(Join)의 데카르트 곱 폭발로 쿼리가 영원히 끝나지 않습니다. 반면 Graph DB는 관계(Edge) 자체가 하드디스크/메모리 상에 상대 노드의 주소 포인터를 들고 있는 물리적 연결선입니다. 연결을 따라가는 탐색은 $O(1)$ 포인터 이동 비용만 발생하므로 깊은 뎁스(Deep Depth)의 관계 분석 쿼리 속도에서 RDBMS를 압살합니다.

3. Counterexample

• 단순 집계 쿼리에 Graph DB 오용 (Full Scan Aggregation): "전체 사용자들의 평균 나이를 구하라" 또는 "매출액이 100만원 이상인 결제 건수를 집계하라" 같은 쿼리에 Graph DB를 투입하는 경우. Graph DB는 포인터를 따라가는 '로컬 관계 탐색'에 극단적으로 최적화되어 있습니다. 전체 노드 리스트를 처음부터 끝까지 풀스캔(Full Scan)하며 집계 연산(Sum, Avg)을 하는 행위는 RDBMS나 컬럼형 데이터베이스(Data Warehouse)보다 물리적 저장 구조상 턱없이 느립니다. 무조건 Graph DB가 좋다는 오해에서 비롯된 안티 패턴입니다.
• 비대한 노드 속성과 초거대 노드(Super Node) 문제: 트위터의 일론 머스크 계정처럼 팔로워 엣지(Edge)가 수억 개인 노드 하나가 존재. 이 노드를 한 번 거치는 쿼리를 실행할 때마다 메모리 탐색 스레드가 수억 개의 엣지 포인터를 모두 메모리에 올리려 시도하다가 OOM(Out of Memory)으로 서버가 크래시. Graph DB 스키마 설계 시 극단적으로 엣지가 몰리는 허브(Hub/Supernode)를 미리 인지하고, 애플리케이션 레벨에서 분산 모델링이나 캐싱을 반드시 접목해야 합니다.

4. Prerequisites

• RDBMS 조인의 원리 (Basic): 교차 테이블(Mapping Table)과 $O(N \times M)$ 연산 비용. (06-01-02 SQL Engineering)
• 자료구조 그래프 (Basic): 정점, 간선, 인접 리스트(Adjacency List) 기초. (04-01-02 Linked Lists & 04-04-01 Graph Foundations)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 칠판의 그림이 코드가 되다, 속성 그래프 모델 (Property Graph)

• Why to Learn: RDBMS의 딱딱한 정규화 테이블 설계도에서 벗어나, "이 사람은 저 상품을 어제 샀고, 저 상품은 이 카테고리에 속한다"는 현실 세계의 맥락 그대로를 저장하는 유연한 데이터 모델링을 체득하기 위함입니다.
• What to Learn:
  • Concepts: 노드(Node, 정점), 엣지(Edge, 관계/간선), 방향성(Direction: Inbound/Outbound), 레이블(Label: 객체 타입), 프로퍼티(Property: 내부 Key-Value 메타데이터).
  • Skills: 화이트보드 개념도를 속성 그래프 ER 다이어그램으로 일대일 매핑하기.
• How to Learn:
  • 1단계: 노드와 엣지의 1급 시민화: RDBMS에서는 데이터(행)만이 진짜고 관계(외래키)는 논리적 규칙일 뿐. 반면 Graph DB는 [Alice] 노드와 [Bob] 노드를 연결하는 [KNOWS] 엣지 자체가 고유 ID와 속성(예: since="2020")을 가지는 물리적 실체로 취급됨을 해부합니다.
  • 2단계: 유연한 레이블링: 하나의 노드가 여러 레이블(Person, Employee, Admin)을 뗐다 붙였다 할 수 있는 유연함. 특정 스키마나 널(Null) 컬럼 지옥 없이 원하는 속성(JSON 형태)을 마음대로 쑤셔 넣는 Schemaless 자유도를 뜯어봅니다.
• Implement: 파이썬 객체로 속성 그래프(Property Graph) 기본 뼈대 짜보기. Node(id, labels[], properties{}), Edge(id, type, from_node, to_node, properties{}) 클래스 2개 정의. Alice와 Bob 객체 생성 후 "KNOWS(since: 2023)" 엣지 객체 생성. 전체 그래프를 딕셔너리에 담아 print(edge) 시 양쪽 노드 정보와 관계가 출력되는 장난감 메모리 그래프 데모.

Recommended

Core Topic 02: 조인을 파괴하는 포인터 점프, 인덱스 없는 인접성 (Index-Free Adjacency)

• Why to Learn: 100만 명의 유저 네트워크에서 '친구의 친구의 친구'를 찾는 연산이 RDBMS에선 10분이 걸리는데 Graph DB에선 어떻게 10밀리초 만에 끝나는지, 그 물리적 스토리지 엔진의 비밀을 장악하기 위함입니다.
• What to Learn:
  • Concepts: RDBMS Join Overhead(해시 조인/B-Tree 인덱스 탐색 반복), 인덱스 없는 인접성(Index-Free Adjacency), 로컬 데이터 탐색(Local Traversal), 포인터 홉(Pointer Hopping).
  • Skills: 관계형 쿼리의 뎁스 증가에 따른 시간 복잡도($O(N^3)$)와 그래프 탐색 시간 복잡도의 차이 설명.
• How to Learn:
  • 1단계: RDBMS의 O(log N) 굴레: A의 친구 B를 찾으려면 A의 외래키를 들고 전체 관계 테이블의 B-Tree 인덱스를 루트 노드부터 리프 노드까지 $O(\log N)$ 탐색. 3단계 뎁스면 이 무거운 검색을 기하급수적으로 반복해야 하는 조인 지옥을 해부합니다.
  • 2단계: 포인터 홉핑의 O(1) 매직: Graph DB에서 A 노드의 하드디스크 데이터 블록 안에는 B 노드로 가는 실제 '메모리/디스크 번지수(주소 리스트)'가 적혀 있습니다. 전체 인덱스를 뒤질 필요 없이, 그저 주소표를 보고 다음 블록으로 $O(1)$ 점프(Hop)만 하면 되는 "인덱스리스(Index-free)" 탐색 엔진을 뜯어봅니다.
• Implement: 파이썬 리스트/인덱싱 룩업 성능 벤치마크. 1) '관계 테이블(Tuple 리스트)' 배열에서 루프를 돌며 ID를 매칭하는 RDBMS 조인 모사 (매번 전체 데이터 길이만큼 루프). 2) 객체 자체에 neighbors = [참조 메모리 리스트]를 담고 참조 변수만 .으로 타고 넘어가는 포인터 모사. 노드 1만 개 생성 후 깊이 3 탐색 속도 비교 결과(후자가 수백 배 빠름) 콘솔 증명.

Practical

Core Topic 03: 화살표로 그림을 그리다, 쿼리 패턴 매칭 (Graph Query Paradigm)

• Why to Learn: 복잡한 비즈니스 로직(예: 나와 친구이고, 5년 이상 거래한 식당을 3번 이상 방문한 사람 탐색)을 SQL의 암호문 같은 JOIN 절 대신, 직관적인 시각적 패턴 언어(Cypher)로 작성하는 패러다임 전환을 겪기 위함입니다.
• What to Learn:
  • Concepts: 패턴 매칭 쿼리(Pattern Matching), Neo4j Cypher 언어(또는 Gremlin), 아스키 아트 문법: (), [], ->, 방향 탐색 패턴 설계.
  • Skills: MATCH (a)-[r]->(b) RETURN 구문 해석, 복잡한 경로 제약조건 설계.
• How to Learn:
  • 1단계: ASCII Art 쿼리: MATCH (u:User {name:'Alice'})-[:FOLLOWS]->(f:User)-[:LIKES]->(p:Post). 괄호 ()는 둥근 노드를, 각괄호 []와 화살표 ->는 엣지를 직관적으로 형상화합니다. 코드를 읽는 것 자체가 화이트보드 그림을 읽는 것과 동일한 우아한 선언적 문법을 해부합니다.
  • 2단계: 가변 길이 경로(Variable Length Path): "A에서 B까지 최소 1칸에서 최대 5칸 떨어진 모든 경로를 찾아라." SQL로는 무한 재귀 조인(CTE)이 필요한 극악의 쿼리를, Cypher에서는 MATCH (a)-[*1..5]->(b) 라는 기적 같은 단 6글자로 해결하는 엔진 래핑을 뜯어봅니다.
• Implement: 파이썬 정규표현식을 이용한 초간단 Cypher 문법 파서 장난감. 문자열 "(User)-[KNOWS]->(Admin)" 입력. 정규식 캡처 그룹으로 Source Node: User, Edge: KNOWS, Target Node: Admin 파싱 및 딕셔너리로 반환. "패턴 매칭" 쿼리 분석기의 최전선(프론트엔드 파서) 단계를 흉내 내는 스크립트 시연.

Advanced

Core Topic 04: 관계 속에 숨겨진 금광 캐기, 내장 그래프 알고리즘 (Graph Algorithms in DB)

• Why to Learn: Graph DB는 데이터를 넣고 빼는 저장소(Storage)를 넘어, 네트워크 데이터 안에 숨겨진 영향력자(인플루언서), 사기 조직 환치기 고리, 최단 배달 경로를 실시간으로 연산(Compute)해내는 분석 엔진임을 장악하기 위해서입니다.
• What to Learn:
  • Concepts: 그래프 탐색(BFS/DFS 응용), 최단 경로(Shortest Path: Dijkstra, A*), 중심성(Centrality: PageRank, Betweenness), 커뮤니티 탐지(Community Detection: Louvain 알고리즘).
  • Skills: Graph DB의 알고리즘 플러그인(Neo4j GDS 등) 적용 시나리오, 사기 탐지(Fraud Detection) 및 추천 엔진(Recommendation) 아키텍처.
• How to Learn:
  • 1단계: 추천과 사기 탐지(BFS 응용): '나와 유사한 유저 찾기' = 특정 유저 노드에서 출발해 너비 우선 탐색(BFS)으로 2칸(구매한 상품 → 그걸 구매한 다른 사람) 퍼져 나가는 연산. '대포통장 환치기 링' = 계좌 A에서 출발해 송금 엣지를 타다가 다시 A로 돌아오는 '순환(Cycle) 닫힘' 구조를 탐지하는 공간 탐색 알고리즘을 해부합니다.
  • 2단계: 영향력 분석(PageRank): 구글 검색엔진의 기원. 화살표(엣지)를 많이 받은 노드가 중요하고, 중요한 노드로부터 화살표를 받으면 더 중요한 노드라는 재귀적 수학 연산을 Graph DB 엔진 내부에서 병렬로 뿌려 '가장 핵심적인 사내 여론 주도자'를 찾아내는 연산을 뜯어봅니다.
• Implement: 메모리 네트워크 그래프 기반 미니 추천 엔진 작성. User 3명, Movie 4개 노드, LIKES 엣지로 이분 그래프(Bipartite Graph) 구성. Collaborative_Filter("UserA") 함수 호출 시, 파이썬 코드상 인접 리스트(BFS 2 Depth 탐색)를 뒤져 "UserA와 영화 취향이 가장 많이 겹치는 UserB가 좋아하지만 UserA는 아직 안 본 영화"를 찾아내 콘솔에 영화 제목을 프린트하는 추천 알고리즘 로직 데모.

7. Terminology

8. References

Primary

• [P1] CS2023 - Algorithms and Complexity (AL) - Graph Algorithms
• [P5] SFIA - Data Analytics (INAN) - Graph Data Modeling

Secondary

• [Graph Databases] Ian Robinson, Jim Webber - The physical layer of graph databases
• [Introduction to Algorithms] CLRS - BFS, DFS, and Shortest Paths Theory

Industry

• [Neo4j Documentation] - Cypher Query Language Reference & Graph Data Science (GDS)
• [Amazon Neptune Documentation] - Property Graph Data Modeling Best Practices

9. Final Checklist

Primary

• RDBMS에서 다대다(N) 매핑 테이블이 유발하는 조인 오버헤드와, Graph DB 엣지가 이를 해결하는 포인터 물리법칙을 설명할 수 있는가?
• 화이트보드에 그린 개체 관계 개념도를 속성 그래프(Property Graph)의 노드, 엣지, 방향성, 레이블 설계도로 완벽히 변환할 수 있는가?

Secondary

• Index-Free Adjacency 엔진이 $O(1)$ 의 포인터 홉(Pointer Hop)으로 어떻게 5단계 깊이 이상의 초거대 네트워크 탐색 병목을 파괴하는지 증명할 수 있는가?
• Cypher 언어의 ()-[]->() 패턴 매칭 문법을 해석하고, 가변 길이 경로([*1..5]) 탐색이 SQL 재귀 CTE 대비 가지는 압도적 우위를 논증할 수 있는가?

Industry

• 단순한 CRUD를 넘어, Graph DB 엔진 내장 알고리즘을 이용해 사기 탐지망(순환 사이클 탐지)이나 추천 시스템(협업 필터링 BFS)을 아키텍처링 할 수 있는가?
• 단일 노드에 수백만 개의 엣지가 집중된 '슈퍼 노드(Super Node)'가 쿼리 수행 시 어떻게 Out Of Memory(OOM)를 유발하는지 해부하고 모델링 방어책을 세울 수 있는가?