관계대수가 필요한 이유

왜 필요한가

06편에서 릴레이션은 “튜플들의 집합”이라고 정의했다. 그렇다면 “이 릴레이션에서 원하는 조건의 튜플만 뽑아내는” 작업, 즉 질의(query)도 집합에 대한 연산으로 표현할 수 있지 않을까? 이 아이디어를 형식화한 것이 관계대수(relational algebra)다. 관계대수는 릴레이션을 입력받아 새로운 릴레이션을 출력하는 연산들의 모음이며, “어떤 순서로 어떤 연산을 적용해야 하는가”까지 명시하는 절차적(procedural) 질의 언어다. 이는 09편에서 다룰 “무엇을 원하는지만 논리식으로 서술하는” 관계해석(비절차적 언어)과 대비된다.

관계대수가 중요한 이유는 이론적인 데 그치지 않는다. SQL 문장이 실제 DBMS(Database Management System, 데이터베이스 관리 시스템) 내부에서 실행될 때, DBMS의 옵티마이저(optimizer, 질의 최적화기)는 SQL을 관계대수 수식으로 변환한 뒤, 그 수식을 더 효율적인 형태로 재작성해 실제 실행 계획을 만든다. 즉 관계대수는 SQL의 “내부 언어”이자 실행 원리를 이해하는 열쇠이며, 19편의 질의 처리·최적화에서 이 내용을 다시 사용한다.

쉽게 말하면: 관계대수는 “표에서 원하는 부분만 골라내고, 표끼리 합치는” 작업을 수학 기호로 정확하게 적어 놓은 것이다.

예제로 쓸 릴레이션

이 편과 08편에서는 아래 세 릴레이션을 계속 예제로 사용한다.

STUDENT(학번, 이름, 학년, 학과)

COURSE(과목코드, 과목명, 학점)

ENROLL(학번, 과목코드, 성적)

선택 연산: 조건에 맞는 튜플 골라내기

왜 필요한가

가장 먼저 필요한 연산은 “조건을 만족하는 행만 남기는” 작업이다. SQL의 WHERE 절에 해당하는 이 연산을 관계대수에서는 선택(selection)이라 부른다.

쉽게 말하면: 선택은 “표에서 조건에 맞는 행만 가로로 잘라내는” 연산이다.

정의

선택 연산은 그리스 문자 시그마 $\sigma$(시그마)를 사용해 다음과 같이 표기한다.

• $\sigma$: 선택 연산을 나타내는 기호
• $condition$: 살아남을 튜플이 만족해야 하는 조건식(05편의 명제논리 연산자 ∧·∨·¬로 여러 조건을 결합할 수 있다)
• $R$: 연산을 적용할 대상 릴레이션

선택 연산의 결과 릴레이션은 원본 $R$과 차수(속성 개수)는 같고, 기수(튜플 개수)는 같거나 줄어든다. 조건을 만족하는 행만 남기고 나머지 행을 버리는 것이므로, 열의 구조는 그대로 유지된 채 행의 개수만 줄어드는 것이 자연스럽다.

계산·적용

“학과가 CS인 학생을 모두 찾아라”는 질의는 다음과 같이 쓴다.

이 수식을 STUDENT 릴레이션에 적용하는 과정을 단계별로 보이면 다음과 같다.

1. STUDENT의 튜플을 하나씩 훑으며 조건 “학과 = ‘CS‘“를 검사한다.
2. S01(학과 CS) → 조건 만족, 결과에 포함
3. S02(학과 CS) → 조건 만족, 결과에 포함
4. S03(학과 EE) → 조건 불만족, 제외
5. S04(학과 CS) → 조건 만족, 결과에 포함

결과 릴레이션은 다음과 같다.

결과 해석

선택 연산의 결과는 원본과 차수가 같은(속성 4개 그대로) 릴레이션이지만 기수는 4에서 3으로 줄었다. 05편에서 배운 명제논리를 이용하면 여러 조건을 한 번에 걸 수도 있다. 예를 들어 “학과가 CS이고 학년이 2 이상인 학생”은 $\sigma_{학과='CS' \land 학년 \ge 2}(STUDENT)$로 쓴다.

투영 연산: 원하는 속성만 남기기

왜 필요한가

선택이 “행을 거르는” 연산이라면, “열(속성)을 거르는” 연산도 필요하다. SQL의 SELECT 속성목록 부분에 해당하는 이 연산이 투영(projection)이다.

쉽게 말하면: 투영은 “표에서 원하는 열만 세로로 잘라내는” 연산이다.

정의

투영 연산은 그리스 문자 파이 $\pi$(파이)를 사용해 다음과 같이 표기한다.

• $\pi$: 투영 연산을 나타내는 기호
• $A_1, A_2, \ldots, A_k$: 결과에 남길 속성들의 목록
• $R$: 연산을 적용할 대상 릴레이션

투영 연산의 결과는 원본 $R$과 차수는 지정한 속성 개수만큼 줄어들고(또는 같고), 기수는 원래보다 같거나 줄어들 수 있다. 이는 투영 후 릴레이션이 여전히 집합이어야 하므로, 남은 속성들만 봤을 때 완전히 같은 값을 가진 튜플이 여러 개 생기면 하나로 합쳐지기(중복 제거) 때문이다.

계산·적용

“모든 학생의 학과 목록을 구하라”는 질의는 다음과 같다.

1. STUDENT의 각 튜플에서 “학과” 값만 남긴다: CS, CS, EE, CS
2. 릴레이션은 집합이므로 중복된 값을 하나로 합친다.

결과 릴레이션은 다음과 같다.

자주 틀리는 점

선택과 투영을 함께 쓰는 시험형 문제

계산·적용

“CS 학과 학생의 이름만 구하라”는 두 연산을 조합해야 한다. 관계대수 수식은 안쪽부터 바깥쪽으로 읽는다.

1. 안쪽 먼저 계산: $\sigma_{학과='CS'}(STUDENT)$를 앞에서 이미 구했다. 결과는 (S01, 김민준, 2, CS), (S02, 이서연, 3, CS), (S04, 최지우, 1, CS) 세 튜플이다.
2. 바깥쪽 계산: 이 결과에 $\pi_{이름}$을 적용해 “이름” 속성만 남긴다.

최종 결과는 다음과 같다.

자주 틀리는 점

집합 연산: 합집합·교집합·차집합

왜 필요한가

05편에서 다룬 집합의 합·교·차 연산을 릴레이션에 그대로 적용한 것이 관계대수의 집합 연산이다. 다만 릴레이션은 “속성을 가진” 튜플의 집합이므로, 순수 집합과 달리 연산이 가능하려면 합집합 호환(union-compatible) 조건을 만족해야 한다.

정의

두 릴레이션 $R$, $S$가 합집합 호환이려면 다음 두 조건을 모두 만족해야 한다.

1. $R$과 $S$의 차수(속성 개수)가 같아야 한다.
2. 대응하는 각 속성끼리 도메인이 같아야 한다.(속성 이름이 달라도 되지만, $i$번째 속성끼리는 같은 종류의 값이어야 한다.)

이 조건이 만족될 때만 다음 세 연산을 정의할 수 있다.

계산·적용

이번 학기(CURRENT_ENROLL)와 지난 학기(PAST_ENROLL)에 수강 신청한 학번만 남긴 두 릴레이션이 있다고 하자.

CURRENT_ENROLL(학번): {S01, S02, S04} PAST_ENROLL(학번): {S01, S03}

두 릴레이션은 모두 “학번” 속성 하나만 가지므로(차수 1, 같은 도메인) 합집합 호환이다.

“이번 학기와 지난 학기 모두 수강 신청한 학생”은 교집합으로 구한다.

“이번 학기에는 신청했지만 지난 학기에는 신청하지 않은 학생”은 차집합으로 구한다.

결과 해석

세 연산 모두 결과 릴레이션의 차수는 입력과 같은 1이지만, 기수는 연산의 종류에 따라 다르게 나온다. 합집합은 두 릴레이션의 튜플을 모으되 중복(S01)을 한 번만 세므로 기수가 4이고, 교집합은 겹치는 튜플만 남으므로 기수가 1이며, 차집합은 05편에서 강조했듯 순서에 민감하므로 $CURRENT\_ENROLL - PAST\_ENROLL$과 $PAST\_ENROLL - CURRENT\_ENROLL$의 결과가 서로 다르다(후자는 {S03}이 된다).

자주 틀리는 점

카티전 곱

정의

카티전 곱(Cartesian product)은 곱셈 기호 $\times$로 표기하며, $R \times S$는 $R$의 튜플 하나와 $S$의 튜플 하나를 모든 조합으로 이어 붙인 릴레이션이다. 05편에서 배운 집합의 카티전 곱을 릴레이션 단위로 그대로 확장한 것이다.

결과 릴레이션의 차수는 $R$과 $S$의 차수를 더한 값이고, 기수는 $R$과 $S$의 기수를 곱한 값이다.

계산·적용

STUDENT(차수 4, 기수 4)와 COURSE(차수 3, 기수 3)를 카티전 곱하면 다음과 같다.

즉 결과 릴레이션은 속성 7개(학번, 이름, 학년, 학과, 과목코드, 과목명, 학점), 튜플 12개(모든 학생·과목 조합)를 갖는다. 이 12개 튜플 중에는 “김민준이 실제로 수강하지 않은 과목”과 짝지어진, 의미 없는 조합도 대부분 섞여 있다. 이 문제를 해결하는 것이 다음 절의 조인 연산이다.

조인: 세타 조인·동등 조인·자연 조인

왜 필요한가

카티전 곱은 두 릴레이션의 모든 조합을 만들어 버리므로, 그중 실제로 의미 있는 조합만 걸러내려면 선택 조건을 추가로 걸어야 한다. “카티전 곱 후 선택”이라는 두 단계를 하나의 연산으로 묶은 것이 조인(join)이다.

쉽게 말하면: 조인은 “두 표를 관련 있는 열 값끼리 짝지어 이어 붙이는” 연산이다.

정의

1. 세타 조인(theta join): $R \Join_{\theta} S$로 표기하며, $\theta$(세타) 자리에 등호(=)뿐 아니라 부등호를 포함한 임의의 비교 조건을 넣을 수 있는 가장 일반적인 조인이다. 정의상 세타 조인은 카티전 곱 뒤에 선택 연산을 붙인 것과 완전히 같다.

2. 동등 조인(equijoin): 세타 조인에서 비교 조건이 오직 등호(=)만으로 이루어진 특수한 경우다. 즉 세타 조인의 부분집합이다.
3. 자연 조인(natural join): $R \Join S$로 표기하며(세타를 생략), 두 릴레이션에서 이름이 같은 속성끼리 자동으로 동등 비교를 수행하고, 중복되는 속성은 결과에서 하나로 합쳐 한 번만 남기는 조인이다. 동등 조인과 자연 조인의 차이는, 동등 조인은 중복 속성이 결과에 두 번 남는 반면 자연 조인은 자동으로 하나로 합친다는 점이다.

계산·적용: 자연 조인으로 학생과 성적 연결하기

“각 학생이 수강한 과목의 성적을 함께 보고 싶다”는 질의는 STUDENT와 ENROLL을 자연 조인으로 연결한다. 두 릴레이션은 공통으로 “학번” 속성을 갖고 있으므로 자연 조인이 자동으로 이 속성을 기준으로 짝짓는다.

1. STUDENT와 ENROLL에서 공통 속성인 “학번”을 찾는다.
2. 학번 값이 같은 튜플끼리만 짝짓는다: S01끼리, S02끼리, S03끼리(S04는 ENROLL에 없으므로 짝이 없어 결과에서 빠진다).
3. 짝지어진 튜플을 이어 붙이되, 공통 속성인 “학번”은 한 번만 남긴다.

결과 릴레이션은 다음과 같다.

결과 해석

이 결과에서 S04(최지우)는 등장하지 않는데, ENROLL 릴레이션에 S04의 수강 기록이 없어서 짝지을 튜플이 없기 때문이다. 이는 자연 조인(그리고 세타·동등 조인)이 기본적으로 양쪽 릴레이션에 모두 대응 튜플이 있는 경우만 결과에 남기는 성질(내부 조인, inner join) 때문이다. “수강 기록이 없는 학생도 결과에 포함하고 싶다”는 요구는 외부 조인(outer join)이 필요한데, 기본 관계대수에는 포함되지 않는 확장 연산이며 12·13편의 SQL LEFT OUTER JOIN 등에서 실무적으로 다룬다.

동등 조인과 자연 조인의 차이를 표로 정리하면 다음과 같다.

자주 틀리는 점

관계대수 표현 규칙과 연산 우선순위

정의

여러 연산이 한 수식에 섞여 있을 때는 다음 우선순위를 따른다.

1. 단항 연산(unary operation): 선택($\sigma$), 투영($\pi$), 이름 변경(rename, $\rho$)이 가장 먼저 계산된다.
2. 카티전 곱($\times$)과 조인($\Join$)이 그다음이다.
3. 교집합($\cap$)이 그다음이다.
4. 합집합($\cup$)과 차집합($-$)이 가장 나중에 계산된다(둘은 같은 우선순위이며, 이 경우 왼쪽에서 오른쪽 순서로 계산한다).

이 순서는 사칙연산에서 곱셈·나눗셈을 덧셈·뺄셈보다 먼저 계산하는 규칙과 비슷하며, 괄호를 사용하면 이 우선순위를 무시하고 원하는 순서로 강제할 수 있다.

계산·적용: 우선순위대로 단계별 풀이

“CS 학과 학생 중 C01 과목을 수강한 학생의 이름을 구하라”는 다음 수식으로 표현할 수 있다.

이 수식은 괄호로 순서가 명확하지만, 실제 시험에서는 이런 단계를 하나씩 짚어 계산하는 절차 자체를 묻는다.

1. $\sigma_{학과='CS'}(STUDENT)$: STUDENT에서 학과가 CS인 튜플만 남긴다 → S01, S02, S04
2. $\sigma_{과목코드='C01'}(ENROLL)$: ENROLL에서 과목코드가 C01인 튜플만 남긴다 → (S01, C01, A), (S02, C01, A)
3. 두 결과를 자연 조인($\Join$)한다. 공통 속성인 “학번”이 같은 튜플끼리 짝짓는다 → S01(김민준)과 S02(이서연)가 각각 짝지어진다. S04는 2단계 결과에 학번이 없으므로 빠진다.
4. $\pi_{이름}$을 적용해 “이름” 속성만 남긴다.

최종 결과는 다음과 같다.

자주 틀리는 점

핵심 정리

• 선택($\sigma$)은 조건에 맞는 튜플(행)을 걸러내는 연산으로 차수는 그대로, 기수는 같거나 줄어든다. 투영($\pi$)은 지정한 속성(열)만 남기는 연산으로 차수는 줄고, 중복 제거 때문에 기수도 줄어들 수 있다.
• 합집합·교집합·차집합은 두 릴레이션이 합집합 호환(차수와 도메인이 같음)일 때만 적용할 수 있으며, 차집합은 피연산자 순서에 따라 결과가 달라진다.
• 카티전 곱은 두 릴레이션의 모든 조합을 만들어 차수는 합, 기수는 곱이 되는 연산이며, 세타 조인은 카티전 곱 뒤에 선택 조건을 붙인 것과 같다.
• 동등 조인은 등호만 쓰는 세타 조인이고, 자연 조인은 공통 속성을 자동으로 찾아 등호 비교하고 중복 속성을 하나로 합치는 조인이다.
• 여러 연산이 섞인 수식은 단항 연산(σ, π, ρ) → 카티전 곱·조인 → 교집합 → 합집합·차집합 순서로 계산하며, 괄호로 순서를 명시적으로 강제할 수 있다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 
• Oracle Database SQL Language Reference