관계 대수

관계형 데이터베이스에서 정보를 얻기 위해선 여러 명령어를 사용할 수 있고, 이를 수학적으로 정의할 수 있음

SELECT

• SELECT 연산은 Relation(table)에서 특정 조건을 만족하는 튜플(행)을 선택하는 연산.
• Relation의 수평 분할(필터링, 원본 Relation과 속성 구조 동일)
• 표기법
  • $\sigma(R)$
  • $R$: Relation
  • $condition$: 선택 조건에 대한 불리언 표현식
• 성질
  • 교환 법칙 $\sigma(\sigma(R)) = \sigma(\sigma(R))$
  • 연쇄 법칙 $\sigma\sigma((R)) = \sigma<condition1 \land condition2>(R)$

• 예시: 학생 테이블(Student)

  학번	이름	학년	전공
  123	철수	2	컴퓨터공학부
  456	영희	2	수리과학부
  789	민수	4	언어학과

  조건: “학년이 2인 학생”

  \[\sigma_{학년=2}(Student)\]

  학번	이름	학년	전공
  456	철수	2	컴퓨터공학부
  789	영희	2	수리과학부

PROJECT

• PROJECT 연산은 Relation(table)에서 특정 속성(열)만 선택하는 연산.
• Relation의 수직 분할(속성 선택, 원본 Relation과 튜플 구조 동일)
• 표기법
  • $\pi(R)$
  • $R$: Relation
  • $attributes$: 선택할 속성들의 집합
• 성질
  • 중복 제거
    $\pi(R)$은 결과에서 중복된 튜플을 제거함. 따라서 PROJECT 연산 후의 튜플의 개수는 항상 원본의 튜플의 개수보다 작거나 같음
  • 순서 무관
    $\pi(\pi(R)) = \pi<attributes1 \cap attributes2>(R)$
  • 포함관계 $\pi(R) \subseteq \pi(R) \quad if \quad attributes1 \subseteq attributes2$ 선택된 속성들의 집합이 다른 집합의 부분집합일 경우, 결과 Relation도 포함관계를 가짐.

• 예시

  학번	이름	학년	전공
  123	철수	2	컴퓨터공학부
  456	영희	2	수리과학부
  789	민수	4	언어학과

  조건: “학번과 이름만 선택”

  \[\pi_{학번, 이름}(Student)\]

  학번	이름
  123	철수
  456	영희
  789	민수

  조건: “학년만 선택”

  \[\pi_{학년}(Student)\]

  학년
  2
  4

RENAME

• RENAME 연산은 Relation(table) 또는 속성(열)의 이름을 변경하는 연산.
• Relation의 구조는 변경되지 않으며, 이름만 변경됨.
• 표기법
  • $\rho_{newName(newAttr1, newAttr2, \dots)}(R)$
    • $R$: Relation
    • $newName$: 새로운 Relation 이름
    • $newAttr1, newAttr2, \dots$: 새로운 속성 이름들
  • $\rho_{newName}(R)$
    Relation의 이름만 변경
  • $\rho_{(newAttr1, newAttr2, \dots)}(R)$
    속성 이름만 변경
• 성질
  • 이름 변경은 Relation의 데이터나 구조에 영향을 주지 않음.
  • 다른 연산과 결합하여 사용 가능.

• 예시

  학번	이름	학년	전공
  123	철수	2	컴퓨터공학부
  456	영희	2	수리과학부
  789	민수	4	언어학과

  조건: “Student Relation의 이름을 Enrolled로 변경”

  \[\rho_{Enrolled}(Student)\]

  Enrolled 테이블

  학번	이름	학년	전공
  123	철수	2	컴퓨터공학부
  456	영희	2	수리과학부
  789	민수	4	언어학과

  조건: “속성 이름을 변경 (학번 → ID, 이름 → Name)”

  \[\rho_{ID, Name, 학년, 전공}(Student)\]

  ID	Name	학년	전공
  123	철수	2	컴퓨터공학부
  456	영희	2	수리과학부
  789	민수	4	언어학과

UNION, INTERSECTION, SET MINUS

• 관계 대수에서 집합 연산은 Relation 간의 데이터를 조합하거나 비교하는 데 사용됨.
• Relation은 집합으로 간주되므로, 중복된 튜플은 제거됨.
• 조건
  • $R_1$과 $R_2$는 동일한 속성 구조를 가져야 함.
  • 속성 이름이 다르더라도, $dom(A_i) = dom(B_i) \ \forall i$ 라면 같은 속성구조라고 할 수 있음

UNION (합집합)

• 두 Relation의 튜플을 합친 결과를 반환.
• 표기법
  • $R_1 \cup R_2$
  • $R_1, R_2$: Relation
• 성질
  • 교환 법칙
    $R_1 \cup R_2 = R_2 \cup R_1$
  • 결합 법칙
    $(R_1 \cup R_2) \cup R_3 = R_1 \cup (R_2 \cup R_3)$

• 예시
  Student1

  학번	이름	학년
  123	철수	2
  456	영희	2

  Student2

  학번	이름	학년
  789	민수	4
  123	철수	2

  \[Student1 \cup Student2\]

  학번	이름	학년
  123	철수	2
  456	영희	2
  789	민수	4

INTERSECTION (교집합)

• 두 Relation에 공통으로 존재하는 튜플을 반환.
• 표기법
  • $R_1 \cap R_2$
  • $R_1, R_2$: Relation
• 성질
  • 교환 법칙
    $R_1 \cap R_2 = R_2 \cap R_1$
  • 결합 법칙
    $(R_1 \cap R_2) \cap R_3 = R_1 \cap (R_2 \cap R_3)$

• 예시
  Student1

  학번	이름	학년
  123	철수	2
  456	영희	2

  Student2

  학번	이름	학년
  789	민수	4
  123	철수	2

  \[Student1 \cap Student2\]

  학번	이름	학년
  123	철수	2

SET MINUS (차집합)

• 첫 번째 Relation에 존재하지만 두 번째 Relation에는 없는 튜플을 반환.
• 표기법
  • $R_1 - R_2$
  • $R_1, R_2$: Relation
• 성질
  • $R_1 - R_2 \neq R_2 - R_1$ (비교환적)

• 예시
  Student1

  학번	이름	학년
  123	철수	2
  456	영희	2

  Student2

  학번	이름	학년
  789	민수	4
  123	철수	2

  \[Student1 - Student2\]

  학번	이름	학년
  456	영희	2

Cartesian product

• Cartesian product 연산은 두 Relation의 모든 튜플 조합을 생성하는 연산.
• 두 Relation의 속성을 결합하여 새로운 Relation을 생성.
• 표기법
  • $R_1(A_1, A_2, \dots, A_n) \times R_2(B_1, B_2, \dots, B_m)$
  • $R_1, R_2$: Relation
  • $A_i, B_i$: Attributes
• 성질

  • 결과 Relation의 튜플 수는 $

    R_1

    \times

    R_2

    $ (튜플의 곱)

  • 결과 Relation의 속성 수는 $

    attributes(R_1)

    +

    attributes(R_2)

    $ (속성의 합)

  • Cartesian product는 중간 연산으로 사용되며, SELECT 또는 PROJECT 연산과 결합하여 사용됨.

• 예시 : 여성 교수의 담당과목 구하기
  교수 테이블(Professor)

  전공	이름	성별
  컴퓨터공학부	김박사	남성
  언어학과	이박사	여성

  과목 테이블(Course)

  과목코드	과목명	주관 학과
  CS101	데이터베이스	컴퓨터공학부
  LN101	통사론	언어학과

  \[Professor \times Course\]

  전공	이름	성별	과목코드	과목명	주관 학과
  컴퓨터공학부	김박사	남성	CS101	데이터베이스	컴퓨터공학부
  컴퓨터공학부	김박사	남성	LN101	통사론	언어학과
  언어학과	이박사	여성	CS101	데이터베이스	컴퓨터공학부
  언어학과	이박사	여성	LN101	통사론	언어학과

  조건: “여성 교수의 담당과목 구하기”

  \[\sigma_{성별='여성' \land 전공=주관 학과}(Professor \times Course)\]

  전공	이름	성별	과목코드	과목명	주관 학과
  언어학과	이박사	여성	LN101	통사론	언어학과

JOIN

• JOIN 연산은 두 Relation의 튜플을 결합하여 새로운 Relation을 생성하는 연산.
• 두 Relation의 공통 속성을 기준으로 튜플을 결합.
• 표기법
  • $R_1 \bowtie_{condition} R_2$
  • $R_1, R_2$: Relation
  • $condition$: 결합 조건($A_i\theta B_j,$ $A_i$와 $B_j$는 각각 같은 도메인의 $R_1, R_2$의 속성, $\theta$는 비교 연산자)
• 종류
  • Natural Join
    공통 속성을 기준으로 자동으로 결합.
    표기법: $R_1 \bowtie R_2$
  • Theta Join
    특정 조건을 기준으로 결합.
    표기법: $R_1 \bowtie_{condition} R_2$
  • Equi Join
    Theta Join의 특수한 경우로, 조건이 등호(=)인 경우.
    조건에 사용된 속성이 중복해서 나타남.
  • Outer Join
    결합 조건을 만족하지 않는 튜플도 포함.
    • Left Outer Join: $R_1 \bowtie_{condition}^L R_2$
    • Right Outer Join: $R_1 \bowtie_{condition}^R R_2$
    • Full Outer Join: $R_1 \bowtie_{condition}^F R_2$
• 성질
  • JOIN 연산은 Cartesian product와 SELECT 연산의 조합으로 표현 가능.
    $R_1 \bowtie_{condition} R_2 = \sigma_{condition}(R_1 \times R_2)$
  • Natural Join은 중복된 속성을 제거.

• 예시
  Student

  학번	이름	학년
  123	철수	2
  456	영희	2
  789	민수	3

  Enrollment

  수강생 학번	과목코드	학점
  123	CS101	A
  456	LN101	B
  999	CS102	C

  • Natural Join
    \(Student \bowtie Enrollment\)

  학번	이름	학년	과목코드	학점
  123	철수	2	CS101	A
  456	영희	2	LN101	B

  • Equi Join
    조건: “학번 = 수강생 학번”
    \(Student \bowtie_{학번 = 수강생 학번} Enrollment\)

  학번	이름	학년	수강생 학번	과목코드	학점
  123	철수	2	123	CS101	A
  456	영희	2	456	LN101	B

  기준이 되는 특성들이 합병이 되지 않고 그대로 남아있음

  • Left Outer Join
    \(Student \bowtie^L Enrollment\)

  학번	이름	학년	과목코드	학점
  123	철수	2	CS101	A
  456	영희	2	LN101	B
  789	민수	3	NULL	NULL

  • Right Outer Join
    \(Student \bowtie^R Enrollment\)

  학번	이름	학년	과목코드	학점
  123	철수	2	CS101	A
  456	영희	2	LN101	B
  NULL	NULL	NULL	CS102	C

  • Full Outer Join
    \(Student \bowtie^F Enrollment\)

  학번	이름	학년	과목코드	학점
  123	철수	2	CS101	A
  456	영희	2	LN101	B
  789	민수	3	NULL	NULL
  NULL	NULL	NULL	CS102	C

대수 연산의 핵심 연산 집합

관계 대수의 모든 연산들은 ${\sigma, \pi, \cup, -, \times}$로 표현 가능

예시: JOIN 연산 표현

JOIN 연산은 Cartesian product와 SELECT 연산으로 표현 가능.
\(R_1 \bowtie_{condition} R_2 = \sigma_{condition}(R_1 \times R_2)\)

Student

학번	이름	학년
123	철수	2
456	영희	2

Enrollment

수강생 학번	과목코드	학점
123	CS101	A
456	LN101	B

조건: “학번 = 수강생 학번”

\(Student \bowtie_{학번 = 수강생 학번} Enrollment\)
\(= \sigma_{학번 = 수강생 학번}(Student \times Enrollment)\)

결과:

학번	이름	학년	과목코드	학점
123	철수	2	CS101	A
456	영희	2	LN101	B

예시: INTERSECTION 연산 표현

INTERSECTION 연산은 UNION과 SET MINUS 연산으로 표현 가능.
\(R_1 \cap R_2 = R_1 - (R_1 - R_2)\)

학생 테이블(Student1)

학번	이름	학년
123	철수	2
456	영희	2

학생 테이블(Student2)

학번	이름	학년
123	철수	2
789	민수	4

\[Student1 \cap Student2 = Student1 - (Student1 - Student2)\]

결과:

학번	이름	학년
123	철수	2

Division

• Division 연산은 두 Relation 간의 특정 조건을 만족하는 튜플을 반환하는 연산.
• 주로 “모든” 조건을 만족하는 튜플을 찾는 데 사용됨.
• cross join의 역원
• 표기법
  $R_1(Z) \div R_2(X) = T(Y)$
  • $R_1$: 나눠지는 Relation
  • $R_2$: 나누는 Relation
  • $Z$: $R_1$의 속성 집합
  • $X$: $R_2$의 속성 집합
  • $Y$: $Z - X$ (결과 Relation의 속성 집합)

\[T(Y) = \{\, t \in \pi_Y(R_1) \mid \forall s \in R_2,\; t \bowtie s \in R_1 \,\}\]

• 성질

  • Division 연산은 Cartesian product와 SELECT, PROJECT 연산으로 표현 가능.

    \[R_1 \div R_2 = \pi_Y(R_1) - \pi_Y((\pi_Y(R_1) \times R_2) - R_1)\]

    의미 : $R_1 \times R_2$ 중 $R_1$에 존재하지 않는 튜플만 뽑아서 $\pi_Y(R_1)$에서 걸러내기

예시

학생 테이블(Student)

학번	과목코드
123	CS101
123	CS102
456	CS101
456	CS102
789	CS101

과목 테이블(Course)

과목코드
CS101
CS102

조건: “모든 과목을 수강한 학생”

\[Student \div Course\]

학번
123
456

Aggregate Functions & Grouping

• Aggregate Functions
  관계 대수에서 집계 함수는 Relation의 데이터를 요약하거나 계산하는 데 사용됨.
  • 주요 함수:
    • COUNT: 튜플의 개수를 계산
    • SUM: 속성 값의 합을 계산
    • AVG: 속성 값의 평균을 계산
    • MIN: 속성 값의 최소값을 반환
    • MAX: 속성 값의 최대값을 반환

  • 표기법:
    \(<grouping \ attributes> \boldsymbol{\mathfrak F} <function \ list>(R)\)
    $R$: Relation
    $grouping \ attributes$: 그룹화할 속성
    $function \ list$: 집계 함수

  • 예시
    학생 테이블(Student)

    학번	이름	학년	전공	학점
    123	철수	1	컴퓨터공학부	4.0
    456	영희	2	수리과학부	3.5
    789	민수	4	언어학과	3.8
    101	지수	4	컴퓨터공학부	3.9

    조건: “전공별 평균 학점 계산”

    \[<전공> \boldsymbol{\mathfrak F} <AVG(학점)>(Student)\]

    결과:

    전공	AVG(학점)
    컴퓨터공학부	3.95
    수리과학부	3.5
    언어학과	3.8

    조건: “학년별 학생 수 계산”

    \[<학년> \boldsymbol{\mathfrak F} <COUNT(*)>(Student)\]

    결과:

    학년	COUNT(*)
    1	1
    2	1
    4	2

    조건: “학년별 학생 수가 1명 이상인 학년”

    \[\sigma_{COUNT(*) \geq 1}(<학년> \boldsymbol{\mathfrak F} <COUNT(*)>(Student))\]

    결과:

    학년	COUNT(*)
    4	2

Recursive Closure

재귀 관계에 있는 모든 튜플을 찾는 연산.
트리 구조나 계층 구조에서 특정 노드의 모든 자손을 찾는 데 유용.

• 예시
  직원 테이블(Employee)

  직원ID	이름	매니저ID
  000	정재혁	100
  100	김민수	200
  200	이선옥	300
  300	배용남	NULL
  400	조정구	200

  조건: “이선옥(직원ID 200)의 모든 부하 직원을 찾기”

  1. Base Relation 정의:
     \(R_0 = \sigma_{매니저ID = '200'}(Employee)\)
     $R_0$: 이선옥의 바로 아래 부하 직원

     직원ID	이름	매니저ID
     100	김민수	200
     400	조정구	200

  2. Recursive Relation 정의:
     \(R_{i+1} = \pi_{직원ID, 이름, 매니저ID}(Employee \bowtie_{Employee.매니저ID = R_i.직원ID} R_i)\) $R_{i+1}$: $R_i$에 속한 직원의 바로 아래 부하 직원

  3. Recursive Closure:
     \(R^* = R_0 \cup R_1 \cup R_2 \cup \dots\)

     $R^*$: 이선옥의 모든 부하 직원

     각 $R_i$를 계산하여 $R^*$를 얻음.

     • $R_1$:

       직원ID	이름	매니저ID
       000	정재혁	100

     • $R_2$:

       직원ID	이름	매니저ID
       (비어있음)

     $R^* = R_0 \cup R_1 \cup R_2 \cup \dots$ = $R_0$

     직원ID	이름	매니저ID
     000	정재혁	100
     100	김민수	200
     400	조정구	200

---

해당 포스트는 서울대학교 산업공학과 박종헌 교수님의 데이터관리와 분석 25-1학기 강의를 정리한 내용입니다.