Relations

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 8

Intuition

관계(Relation)는 집합의 원소들 사이에 존재하는 '연결성'을 수학적 집합(순서쌍의 부분집합)으로 추상화한 것이며, 이를 통해 데이터베이스 관리, 작업 스케줄링, 객체 분류 등을 수행한다.

One-liner

집합 원소들 사이의 관계를 수학적 구조로 정의하고, 그 성질(반사성, 대칭성, 추이성 등)에 따라 동치 관계와 부분 순서로 분류하여 응용한다.

Prerequisites

• Sets: 집합의 정의, 부분집합, 합집합, 교집합, 차집합 (Ch. 2)
• Cartesian Product: 두 집합의 원소를 짝지어 만드는 순서쌍의 집합 $A \times B$ (Ch. 2)
• Functions: 함수가 관계의 특수한 형태(일대일 대응 관계)임을 이해하기 위한 기초 지식 (Ch. 2)
• Matrices: 행렬의 기본 연산 및 Boolean 행렬 연산 (Ch. 3, 8.3절 representation)

Goals

• 이항 관계(Binary Relation)와 n-ary 관계의 정의를 이해한다.
• 관계의 주요 성질(반사성, 대칭성, 반대칭성, 추이성)을 판별한다.
• 행렬과 유향 그래프(Digraph)를 이용하여 관계를 표현한다.
• 관계의 폐쇄(Closure)와 Warshall 알고리즘의 작동 원리를 파악한다.
• 동치 관계(Equivalence Relation)와 분할(Partition)의 상호 관계를 이해한다.
• 부분 순서 집합(Poset)에서 Hasse diagram을 그리고 위상 정렬(Topological sorting)을 수행한다.

Core Concepts

8.1 Relations and Their Properties

Definition: Binary Relation

집합 $A$에서 집합 $B$로의 이항 관계 (Binary Relation)는 곱집합 $A \times B$의 부분집합이다. (p.519)

• 표기: $(a, b) \in R$이면 $aRb$라고 쓴다.

• Relation on a Set: 집합 $A$에서 $A$로의 관계, 즉 $A \times A$의 부분집합을 말한다. (p.521)
• 주요 성질 (Properties): (p.522-524)
  1. Reflexive (반사성): 모든 $a \in A$에 대해 $(a, a) \in R$.
  2. Symmetric (대칭성): 모든 $a, b \in A$에 대해 $(a, b) \in R \implies (b, a) \in R$.
  3. Antisymmetric (반대칭성): 모든 $a, b \in A$에 대해 $(a, b) \in R$이고 $(b, a) \in R \implies a = b$.
  4. Transitive (추이성): 모든 $a, b, c \in A$에 대해 $(a, b) \in R$이고 $(b, c) \in R \implies (a, c) \in R$.

8.2 n-ary Relations and Their Applications

Definition: n-ary Relation

집합 $A_1, A_2, \dots, A_n$에 대한 n-ary 관계는 $A_1 \times A_2 \times \dots \times A_n$의 부분집합이다. 이때 $n$을 관계의 Degree(차수)라고 한다. (p.530)

• Relational Data Model: 데이터베이스를 n-ary 관계로 표현하는 모델이다. 각 열(Column)은 Attribute(속성)라고 한다. (p.531)
• Primary Key: 해당 도메인의 값이 전체 n-tuple을 유일하게 결정하는 속성이다. (p.531)
• Operations: (p.532-534)
  • Selection ($s_C$): 특정 조건 $C$를 만족하는 튜플만 선택한다.
  • Projection ($P_{i_1, \dots, i_m}$): 튜플에서 특정 필드만 남기고 나머지는 삭제한다.
  • Join ($J_p$): 공통된 필드를 기준으로 두 관계를 합쳐 더 큰 차수의 관계를 만든다.

8.3 Representing Relations

• Zero-One Matrices: 집합 $A, B$가 유한할 때, $a_i R b_j$이면 $m_{ij} = 1$, 아니면 $0$으로 표시하는 행렬 $M_R$로 표현한다. (p.538)
  • 반사적 관계: 주대각선 원소가 모두 1.
  • 대칭적 관계: 전치 행렬과 동일 ($M_R = M_R^T$).
• Directed Graphs (Digraphs): 집합의 원소를 정점(Vertex), 관계 $(a, b)$를 화살표 간선(Edge)으로 표현한다. (p.541)

8.4 Closures of Relations

Definition: Closure

관계 $R$이 성질 $P$를 만족하지 않을 때, $R$을 포함하면서 성질 $P$를 만족하는 가장 작은 관계 $S$를 $R$의 $P$-폐쇄라고 한다. (p.544)

• Reflexive Closure: $R \cup \Delta$, 여기서 $\Delta = \{(a, a) | a \in A\}$. (p.545)
• Symmetric Closure: $R \cup R^{-1}$, 여기서 $R^{-1} = \{(b, a) | (a, b) \in R\}$. (p.545)
• Transitive Closure: 관계의 모든 경로를 포함하는 Connectivity Relation $R^*$와 같다. (p.548)
• Warshall's Algorithm: $O(n^3)$ 비트 연산으로 추이 폐쇄를 구하는 효율적인 알고리즘이다. (p.553)

8.5 Equivalence Relations

Definition: Equivalence Relation

관계 $R$이 반사적, 대칭적, 추이적일 때 이를 동치 관계라고 한다. (p.555)

• Equivalence Class: 원소 $a$와 관계가 있는 모든 원소의 집합 $[a]_R = \{s | (a, s) \in R\}$. (p.558)
• Partition: 집합 $S$의 분할은 서로소인 비어 있지 않은 부분집합들의 모임으로, 이들의 합집합은 $S$가 된다. (p.560)
• Fundamental Theorem: 집합 $A$ 위의 동치 관계는 $A$의 분할을 형성하며, 반대로 $A$의 임의의 분할은 대응하는 동치 관계를 정의한다. (p.561)

8.6 Partial Orderings

Definition: Partial Ordering (Poset)

관계 $R$이 반사적, 반대칭적, 추이적일 때 이를 부분 순서라고 하며, 집합 $S$와 순서 $\le$의 쌍 $(S, \le)$를 Poset이라 한다. (p.566)

• Hasse Diagrams: 반사성(루프)과 추이성(중간 간선)에 의한 중복 정보를 생략하고 위쪽 방향으로 그린 그래프이다. (p.571)
• Extremal Elements: (p.572-574)
  • Maximal/Minimal: 그보다 더 크거나 작은 원소가 없는 원소 (유일하지 않을 수 있음).
  • Greatest/Least: 모든 원소보다 크거나 작은 원소 (존재한다면 유일함).
  • Upper/Lower Bound: 부분집합의 모든 원소보다 크거나 작은 원소.
• Lattice: 모든 원소 쌍이 Least Upper Bound(LUB)와 Greatest Lower Bound(GLB)를 가지는 Poset이다. (p.574)
• Topological Sorting: 부분 순서에 모순되지 않게 모든 원소를 일직선으로 나열(Total Ordering)하는 과정이다. (p.576)

Notation

기호	의미
$a R b$	원소 $a$가 관계 $R$에 의해 $b$와 관련됨
$M_R$	관계 $R$을 나타내는 0-1 행렬
$R^*$	관계 $R$의 추이 폐쇄 (Connectivity relation)
$[a]_R$	원소 $a$의 동치류 (Equivalence class)
$(S, \le)$	집합 $S$와 부분 순서 $\le$로 이루어진 Poset
$a \prec b$	$a \le b$이고 $a \ne b$임
$a \ll b$	$a$가 $b$를 덮음 (Covering relation: $a < b$ 사이에 원소가 없음)

Key Theorems & Formulas

Theorem: Powers and Transitivity

조건: 집합 $A$ 위의 관계 $R$

결론: $R$이 추이적(Transitive)일 필요충분조건은 모든 $n=1, 2, 3, \dots$에 대해 $R^n \subseteq R$인 것이다. (p.527)

Theorem: Transitive Closure and Connectivity

조건: 집합 $A$ 위의 관계 $R$

결론: $R$의 추이 폐쇄는 연결성 관계 $R^* = \bigcup_{n=1}^{\infty} R^n$와 같다. (p.548)

Theorem: Equivalence and Partition

조건: 집합 $S$ 위의 관계 $R$

결론: $R$이 동치 관계이면 $R$의 동치류들은 $S$의 분할을 형성한다. (p.561)

Intuitions

• Antisymmetric의 직관: 화살표가 왕복하는 경우가 오직 자기 자신에게 돌아오는 루프뿐일 때 성립한다. 즉, '일방통행'이거나 '제자리걸음'만 허용된다.
• Equivalence Class의 직관: 같은 학교 출신, 같은 나머지 값 등 특정 기준에 의해 세상을 '서로 겹치지 않는 방'들로 나누는 것과 같다.
• Poset과 Hasse Diagram의 직관: 가계도나 회사 조직도처럼 '누가 누구 위에 있는가'를 보여주는 구조이며, 모든 원소가 서로 비교 가능할 필요는 없다.

Worked Examples

Example 1: Transitive Closure (Warshall)

문제: $M_R = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix}$의 추이 폐쇄를 구하라. (p.549)

핵심 단계:

1. $M_R^{[2]} = M_R \odot M_R = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}$.
2. $M_R^{[3]} = M_R^{[2]} \odot M_R = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}$.
3. $M_{R^*} = M_R \vee M_R^{[2]} \vee M_R^{[3]} = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}$.

요점: $R^*$는 단계를 거쳐 도달 가능한 모든 경로(Direct + Indirect)를 행렬로 통합한 것이다.

Example 2: Topological Sort

문제: 작업 의존성 $\{1<2, 1<5, 2<4, 5<4, 4<12, 4<20\}$을 가진 작업들을 순서대로 나열하라. (p.577)

핵심 단계:

1. Minimal element인 1을 선택하고 제거.
2. 남은 $\{2, 4, 5, 12, 20\}$ 중 minimal인 2나 5 중 하나(예: 5) 선택 후 제거.
3. 남은 $\{2, 4, 12, 20\}$ 중 minimal인 2 선택 후 제거.
4. 이 과정을 반복하여 $1, 5, 2, 4, 20, 12$ 등의 순서를 얻음.

요점: 위상 정렬은 부분 순서를 유지하면서 전체 원소를 일렬로 세우는 방법이며, 결과는 유일하지 않을 수 있다.

Common Pitfalls

Pitfall

Symmetric vs Antisymmetric: 이 둘은 반대 개념이 아니다. 어떤 관계는 둘 다일 수 있고(예: $\{(a, a)\}$), 둘 다 아닐 수도 있다. (p.523)

Pitfall

Transitive Closure의 수동 계산: $(a, b)$와 $(b, c)$가 있어서 $(a, c)$를 추가했다고 해서 바로 끝나는 것이 아니다. 새로운 $(a, c)$로 인해 또 다른 추이적 쌍이 생길 수 있으므로 더 이상 추가할 것이 없을 때까지 반복해야 한다. (p.545)

Connections

• 선행 개념: Ch. 2.1-2.2 Sets, Ch. 3.4 Integers and Algorithms (Congruence modulo m).
• 후속 개념: Ch. 9 Graphs (관계의 시각적 도구), Ch. 11 Boolean Algebra (Lattice의 심화).
• 응용 분야: Relational Databases (SQL), Compiler Design (Variable scoping), Project Management (PERT/CPM).

Critical Notes

교재가 강조하는 것

• 관계의 추상적 성질을 행렬(Matrix)과 그래프(Graph)라는 구체적인 도구로 연결하여 컴퓨터가 처리할 수 있게 만드는 지점.
• 동치 관계와 분할의 수학적 동치성.

실제로 중요한 것

• Warshall's Algorithm: 복잡도 $O(n^3)$를 이해하는 것은 알고리즘 설계 관점에서 매우 중요하다.
• Partial Orders & Lattices: 컴퓨터 과학에서 자료구조의 계층이나 보안 모델(Information flow)을 설계할 때 핵심적인 역할을 한다.

교재가 생략하거나 얼버무리는 것

• 무한 집합에서의 추이 폐쇄 계산은 알고리즘적으로 다루기 어렵지만, 본 장은 유한 집합에 집중한다.
• SQL의 SELECT가 수학의 'Selection'이 아니라 'Projection'이라는 명칭상의 혼란을 언급하지만, 실무적인 SQL 문법 깊숙이는 들어가지 않는다.

Open Questions

이해하지 못한 것

• 전산학에서의 위상(Topology) 정의와 수학에서의 위상 수학(Topology) 정의 사이의 본질적 차이점.

더 알고 싶은 것

• Lattice 구조가 실제 컴파일러의 데이터 흐름 분석(Data-flow analysis)에서 어떻게 구체적으로 사용되는지.
• Fuzzy Relation(퍼지 관계)처럼 '관계가 있음'이 0과 1이 아닌 확률로 정의되는 경우의 수학적 처리.