Set Theory & Relations

1. Overview

집합론과 관계(Set Theory & Relations, STR)는 단순히 수학의 한 분야가 아니라, 관계형 데이터베이스(RDBMS)의 뼈대이자 소프트웨어에서 다루는 모든 데이터 묶음을 수리적으로 정의하는 가장 완벽하고 엄밀한 '데이터의 물리적 명세서'입니다.

학습자는 데이터를 중복 없이 가두는 **집합(Set)**의 본질과, 교집합/합집합을 통해 데이터의 범위를 조작하는 **집합 연산(Set Operations)**의 물리를 해부합니다. 나아가 데이터 A와 데이터 B가 어떻게 수리적으로 엮여 있는지를 증명하는 **관계(Relations)**와 그 특성(반사성, 대칭성, 추이성)을 배우며, 이를 통해 SQL의 JOIN 연산이 왜 특정 인덱스(Index) 구조에서 폭발적인 성능 저하를 일으키는지(Cartesian Product) 증명할 수 있는 데이터 아키텍처 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 집합의 물리학 (Set Mechanics): 유한 집합(Finite Set), 무한 집합(Infinite Set), 멱집합(Power Set)의 폭발적 크기($2^N$) 증가.
• 집합 연산 역학 (Set Operations): 합집합($\cup$), 교집합($\cap$), 차집합($\setminus$), 데카르트 곱(Cartesian Product, $\times$).
• 관계의 수리적 특성 (Relational Properties): 이항 관계(Binary Relation), 반사적(Reflexive), 대칭적(Symmetric), 추이적(Transitive) 성질.
• 동치와 순서 (Equivalence & Order): 동치 관계(Equivalence Relation)와 파티셔닝(Partitioning), 부분 순서 집합(Poset), Hasse Diagram.

Out-of-Scope

• 관계형 데이터베이스의 구체적 SQL 튜닝: 오라클(Oracle)이나 MySQL의 실행 계획(Explain Plan)을 보는 법 $\rightarrow$ 06. Data & Information Management 영역.
• 논리 회로의 물리적 납땜: AND/OR 게이트를 물리적인 실리콘 기판 위에 어떻게 그리는가 $\rightarrow$ 02. Computer Architecture 영역.

Boundaries

• STR vs. Logic (01-02): 논리학(01-02)이 "명제가 참인가 거짓인가"를 판별하는 수리적 기계라면, STR은 "참/거짓을 따질 대상(데이터)들을 어떻게 분류하고 묶어둘 것인가"를 규정하는 그릇입니다.

3. Counterexample

• 데카르트 곱의 재앙 (Cartesian Product Fallacy): 두 집합 A와 B를 아무 생각 없이 조인(JOIN)하여 모든 가능한 조합($|A| \times |B|$)을 만들어버리는 초보적 실수. 유저 1만 명의 테이블과 상품 1만 개의 테이블을 ON 조건 없이 조인하면 메모리 상에 1억 개의 행(Row)이 물리적으로 생성되어 서버가 그 자리에서 OOM(Out of Memory)으로 터져버립니다. 이는 집합론의 튜플 생성 공식을 몰라서 발생하는 전형적인 수학적 무지입니다.
• 추이성 맹신 (Transitive Trust Fallacy): "A가 B를 신뢰하고, B가 C를 신뢰하면, A는 C를 신뢰한다"는 추이성(Transitivity)을 분산 보안 시스템에 함부로 적용하는 행위. 암호학에서 신뢰(Trust) 관계는 수학적 추이성을 만족하지 않습니다(비추이적). 이를 잘못 모델링하면 해커(C)가 B를 탈취했을 때 시스템 전체(A)가 뚫리는 구조적 붕괴가 발생합니다.

4. Prerequisites

• 기초 수학 (Basic): 고등학교 수준의 수학적 기호 표현과 명제에 대한 기본적 거부감이 없어야 합니다.
• 기초 프로그래밍 (Recommended): 배열(Array)과 루프(Loop)를 다뤄보아야 집합을 코드로 표현할 때의 메모리 구조를 이해할 수 있습니다. (05. PLC)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 집합의 수리적 정의와 메모리 제어 (Set Mechanics)

• Why to Learn: 배열(Array)에 중복 데이터를 잔뜩 넣어두고 O(N)으로 매번 검색하는 바보 같은 코드를 버리고, 메모리 주소 기반의 O(1) 검색을 하기 위해서입니다.
• What to Learn:
  • Concepts: 원소(Element), 부분집합(Subset), 공집합(Empty Set), 전체집합(Universal Set).
  • Skills: 집합의 표기법(조건제시법, 원소나열법), 해시 테이블(Hash Table)을 이용한 집합의 물리적 구현, 멱집합(Power Set) 계산.
  • Tools: Python set(), Java HashSet.
  • Trade-offs: 중복을 허용하지 않고 순서도 없는 Set 데이터 구조의 초고속 조회 속도 vs 넣은 순서대로 꺼낼 수 없는 수리적 무질서도(Entropy).
• How to Learn:
  • 1단계: 조건제시법 $A = \{x \mid x \in \mathbb{N}, x \le 10\}$이 실제 코드에서 filter(x -> x <= 10) 함수로 어떻게 1<1> 물리적 매핑이 되는지 확인합니다.
  • 2단계: 크기가 $N$인 집합의 멱집합 크기가 $2^N$이 되는 지수적 폭발을 계산하고, 이를 무심코 코드로 짰을 때 시스템의 메모리(RAM)가 1초 만에 꽉 차는 임계점($N \approx 30$)을 추산합니다.
• Implement: 100만 개의 문자열이 들어있는 배열에서 중복을 제거할 때, for 문으로 찾는 방식과 Set으로 캐스팅하는 방식의 물리적 CPU 소요 시간(ms) 차이를 측정하는 벤치마크 코드 작성.

Recommended

Core Topic 02: 집합 연산과 비트 벡터 (Set Operations & Bitmaps)

• Why to Learn: 대규모 유저 데이터베이스에서 '20대이면서 서울에 사는 유저'를 CPU의 1클럭(Clock) 만에 찾아내는 비트 연산의 마법을 쥐기 위함입니다.
• What to Learn:
  • Concepts: 합집합($\cup$), 교집합($\cap$), 차집합($\setminus$), 여집합($A^c$).
  • Skills: 비트마스크(Bitmask), 비트 벡터(Bit Vector), 드모르간의 법칙(De Morgan's Laws), 데카르트 곱(Cartesian Product).
  • Tools: Redis (Bitmaps).
  • Trade-offs: 집합 연산을 포인터 기반의 객체 묶음으로 처리하는 방식의 유연성 vs 0과 1로 압축하여 CPU 레지스터에 박아버리고 AND, OR 논리 게이트로 한 방에 처리하는 비트 벡터의 극한 성능과 메모리 제약.
• How to Learn:
  • 1단계: '운동을 좋아하는 사람(A)'과 '독서를 좋아하는 사람(B)'의 합집합을 구하는 것이, 비트 연산의 A OR B와 물리적으로 동일한 회로 연산임을 증명합니다.
  • 2단계: 데카르트 곱($A \times B$)이 왜 2차원 평면의 격자 좌표(x, y)를 만들어내며, 이것이 RDBMS의 Cross Join으로 번역되어 시스템 자원을 갉아먹는지 뜯어봅니다.
• Implement: 10만 명의 유저 출석 데이터를 32-bit 정수형 비트마스크 배열로 저장한 뒤, 7일 연속 출석한 유저의 교집합을 비트 연산(&)으로 추출하여 $O(N)$에서 $O(N/32)$로 성능을 압축하는 모듈 작성.

Practical

Core Topic 03: 관계의 수학적 모델링 (Relational Modeling)

• Why to Learn: 무질서하게 흩어진 데이터들 사이의 '연결 고리(Edge)'를 행렬(Matrix)로 바꿔서 컴퓨터가 수학적으로 분석할 수 있게 만들기 위함입니다.
• What to Learn:
  • Concepts: 이항 관계(Binary Relation), 정의역(Domain)과 치역(Range).
  • Skills: 관계 행렬(Relational Matrix), 방향 그래프(Directed Graph)와의 매핑, 관계의 합성(Composition of Relations).
  • Tools: SQL JOIN 절.
  • Trade-offs: 관계를 (A, B) 쌍의 리스트로 저장할 때의 메모리 절약(Sparse) vs $N \times N$ 불리언 행렬로 저장하여 두 노드 간의 연결 여부를 $O(1)$로 빠르게 조회하는 속도(Dense).
• How to Learn:
  • 1단계: '페이스북 친구 맺기'라는 관계가 대칭적(Symmetric) 특성을 가지는 반면, '인스타그램 팔로우'는 비대칭적 특성을 가짐을 수학적으로 정의하고, 이를 관계 행렬의 전치(Transpose) 물리로 해부합니다.
  • 2단계: A가 B를 알고($R_1$), B가 C를 안다($R_2$)고 할 때, A를 통해 C를 찾는 '관계의 합성($R_1 \circ R_2$)'이 행렬의 곱셈 연산과 어떻게 수리적으로 일치하는지 증명합니다.
• Implement: $1,000 \times 1,000$ 크기의 인접 행렬(Adjacency Matrix)을 코드로 띄워놓고, 두 관계 행렬을 합성 연산하여 '2다리 건너 아는 사람' 집합을 물리적으로 도출하는 인-메모리 그래프 프로세서 작성.

Advanced

Core Topic 04: 동치 관계와 부분 순서 (Equivalence & Posets)

• Why to Learn: 10억 개의 로그 데이터를 같은 속성을 가진 덩어리(Partition)로 찢어서 분산 처리하거나, 작업의 실행 순서(Dependency)를 꼬이지 않게 수학적으로 정렬하기 위함입니다.
• What to Learn:
  • Concepts: 동치 관계(Equivalence Relation), 분할(Partition), 부분 순서 집합(Partially Ordered Set, Poset).
  • Skills: 반사성(Reflexivity), 대칭성(Symmetry), 추이성(Transitivity), Hasse Diagram, 위상 정렬(Topological Sorting).
  • Tools: Apache Spark (HashPartitioner), DAG Task Scheduler.
  • Trade-offs: 데이터를 크기순으로 일렬로 세우는 전순서(Total Order)의 강력한 예측 가능성 vs 서로 의존성이 없는 작업들은 동시에 실행(병렬 처리)할 수 있게 여지를 두는 부분 순서(Partial Order)의 런타임 하드웨어 효율성.
• How to Learn:
  • 1단계: 어떤 관계가 반사적, 대칭적, 추이적 특성을 모두 만족할 때(동치 관계), 전체 집합이 서로 교집합이 없는 덩어리(Partition)로 완벽하게 쪼개지는 수학적 마법을 분산 데이터베이스의 샤딩(Sharding) 물리와 결합하여 뜯어봅니다.
  • 2단계: A 작업을 끝내야 B를 할 수 있다는 '추이성'과 '반대칭성'만 있는 부분 순서(Poset)를 Hasse Diagram으로 그리고, 이를 기반으로 병렬 처리가 가능한 태스크들을 골라내는 위상 정렬(Topological Sort)을 배웁니다.
• Implement: 10개의 빌드(Build) 작업이 서로 의존성($A \rightarrow B$)을 가질 때, 부분 순서 집합의 추이성을 검사하여 순환 참조(Deadlock) 에러를 뱉어내거나, 올바른 병렬 실행 순서(DAG)를 리스트로 반환하는 수리적 스케줄러 구현.

7. Terminology

8. References

Primary References

• [P1] CS2023 - DS/Sets, Relations, and Functions — The core mathematical foundation.
• [P2] SWEBOK v4.0 - Computing Foundations / Discrete Mathematics — Applied math for SE.

Secondary References

• [Discrete Mathematics and Its Applications] Kenneth Rosen — The "Gold Standard" textbook.
• [MIT 6.042J - Mathematics for Computer Science] — High-density pedagogical resource.

Industry References

• [Relational Model for Database Management] E.F. Codd — Set theory in practice.
• [Type Theory in Programming Languages] — Set theory as the basis of types.

9. Final Checklist

Primary Checklist

• '부분집합'과 '멱집합(Power Set)'의 크기 관계를 수학적으로 증명하고, 이것이 연산 복잡도에 미치는 물리적 영향을 설명할 수 있는 가? (P1)
• 이항 관계의 성질 중 '추이성'이 무너졌을 때 발생할 수 있는 데이터 정합성 오류를 구체적인 사례를 들어 기술 가능한가? (P1)

Secondary Checklist

• 하세 도표(Hasse Diagram)를 보고 해당 관계가 격자(Lattice) 구조를 형성하는지 여부를 물리적으로 판별할 수 있는가?
• 집합의 분할(Partition)과 동치 관계(Equivalence Relation)가 수학적으로 동일한 개념임을 논리적으로 소통 가능한가?

Industry Checklist

• 데이터베이스 설계 시, 특정 속성들 간의 관계를 집합론적으로 분석하여 제3정규형(3NF) 이상의 정규화 타당성을 입증할 수 있는가? (SFIA)
• 복잡한 권한 시스템(RBAC)을 설계할 때, 사용자 그룹 간의 계층을 부분 순서(Partial Order) 모델로 정의하여 권한 상속 로직을 설계할 수 있는가?