관계 대수

SQL을 사용하면 무엇을 원하는지만 말합니다. 그러면 DBMS가 어떻게 실행할지를 결정합니다. 이때 DBMS의 쿼리 옵티마이저가 사용하는 이론적 기반이 바로 관계 대수(Relational Algebra)입니다. 관계 대수는 관계형 데이터베이스의 수학적 토대이며, 릴레이션을 입력받아 릴레이션을 출력하는 연산들의 집합입니다. SQL이 어떤 데이터가 필요한가를 선언하는 언어라면, 관계 대수는 그 데이터를 어떻게 구하는가를 절차적으로 표현하는 언어입니다.

관계 대수의 위치

관계 대수를 이해하기 위해, 먼저 관계형 데이터베이스에서 데이터를 다루는 두 가지 이론적 언어를 비교해야 합니다.

관계 대수 (Relational Algebra)
  - 절차적 언어 (Procedural)
  - "어떻게" 데이터를 구하는가
  - 연산들의 조합으로 표현
  - σ, π, ⋈, ∪, ∩, −, ×
  - DBMS 내부: 쿼리 실행 계획

관계 해석 (Relational Calculus)
  - 비절차적 언어 (Non-procedural)
  - "무엇을" 원하는가
  - 조건(predicate)으로 표현
  - { t | P(t) } 형식
  - SQL의 이론적 기반

SQL은 관계 해석에 가까운 언어이고, DBMS의 쿼리 옵티마이저는 SQL을 관계 대수 표현식으로 변환하여 실행합니다. 관계 대수와 관계 해석의 표현력은 동일합니다(관계 완전, Relationally Complete). 하나로 표현할 수 있는 것은 다른 하나로도 반드시 표현할 수 있습니다.

핵심 연산 개요

관계 대수의 연산은 단항 연산(릴레이션 1개 입력)과 이항 연산(릴레이션 2개 입력), 그리고 집합 연산으로 분류됩니다.

관계 대수 연산              SQL 대응             분류
──────────────────────────────────────────────────────
σ (SELECT, 선택)          → WHERE 절             단항
π (PROJECT, 투영)         → SELECT 컬럼 목록     단항
ρ (RENAME, 이름변경)      → AS 별칭              단항
⋈ (JOIN, 조인)           → JOIN ... ON          이항
÷ (DIVISION, 나눗셈)      → NOT EXISTS 패턴      이항
∪ (UNION, 합집합)         → UNION                이항(집합)
∩ (INTERSECTION, 교집합)  → INTERSECT            이항(집합)
− (DIFFERENCE, 차집합)    → MINUS / EXCEPT       이항(집합)
× (CARTESIAN, 곱)         → CROSS JOIN           이항(집합)

각 연산의 핵심은 릴레이션이 입력이고, 릴레이션이 출력이라는 것입니다. 이를 폐쇄 성질(Closure Property)이라 합니다. 연산의 결과가 다시 릴레이션이므로, 연산을 중첩하여 복잡한 질의를 구성할 수 있습니다. 마치 함수의 출력을 다른 함수의 입력으로 넣는 함수 합성과 같습니다.

선택 연산 (σ, Selection)

선택(σ, Selection)은 릴레이션에서 주어진 조건을 만족하는 튜플만 골라내는 연산입니다. 행(Row)을 필터링하는 수평적 부분 집합 연산입니다. SQL의 WHERE 절에 대응됩니다.

σ <조건> (릴레이션)

σ(학과='컴퓨터')(학생)
  = 학생 릴레이션에서 학과가 '컴퓨터'인 튜플만 선택

SQL 대응:
  SELECT * FROM 학생 WHERE 학과 = '컴퓨터'

선택 조건에는 비교 연산자(=, >, <, ≥, ≤, ≠)와 논리 연산자(∧ AND, ∨ OR, ¬ NOT)를 사용할 수 있습니다.

σ(학과='컴퓨터' ∧ 학년≥3)(학생)
  = 컴퓨터 학과의 3학년 이상 학생

SQL: SELECT * FROM 학생 WHERE 학과 = '컴퓨터' AND 학년 >= 3

σ(학과='컴퓨터' ∨ 학과='전자')(학생)
  = 컴퓨터 또는 전자 학과 학생

SQL: SELECT * FROM 학생 WHERE 학과 IN ('컴퓨터', '전자')

선택 연산의 중요한 성질은 다음과 같습니다.

• 교환 법칙: σ<c1>(σ<c2>(R)) = σ<c2>(σ<c1>(R)). 선택의 순서를 바꿔도 결과가 같습니다.
• 결합 법칙: σ<c1∧c2>(R) = σ<c1>(σ<c2>(R)). 복합 조건을 단일 선택이나 중첩 선택으로 표현할 수 있습니다.
• 결과 크기: 원래 릴레이션의 차수(열 수)는 유지되고, 카디널리티(행 수)는 줄어들거나 같습니다.

투영 연산 (π, Projection)

투영(π, Projection)은 릴레이션에서 원하는 속성(열)만 골라내는 연산입니다. 열(Column)을 필터링하는 수직적 부분 집합 연산입니다. SQL의 SELECT 절의 컬럼 목록에 대응됩니다.

π <속성 목록> (릴레이션)

π(이름, 학과)(학생)
  = 학생 릴레이션에서 이름과 학과 열만 추출

SQL 대응:
  SELECT DISTINCT 이름, 학과 FROM 학생

투영의 중요한 특성은 중복 튜플이 자동 제거된다는 것입니다. 관계 대수에서 릴레이션은 수학의 집합이므로 중복 원소가 존재하지 않습니다. 그러나 SQL에서는 성능상의 이유로 기본적으로 중복을 허용하며, 중복 제거가 필요하면 DISTINCT 키워드를 명시해야 합니다.

학생:
  학번 | 이름   | 학과
  001  | 김철수 | 컴퓨터
  002  | 이영희 | 전자
  003  | 박민수 | 컴퓨터
  004  | 최지은 | 전자

π(학과)(학생):
  학과
  컴퓨터
  전자        ← 중복 제거! (관계 대수)

SQL: SELECT 학과 FROM 학생     → 4행 (중복 포함)
SQL: SELECT DISTINCT 학과 FROM 학생  → 2행 (중복 제거)

선택과 투영의 조합

선택과 투영을 조합하면 특정 조건의 행에서 원하는 열만 추출할 수 있습니다. 관계 대수의 폐쇄 성질 덕분에 연산을 자연스럽게 중첩할 수 있습니다.

π(이름)(σ(학과='컴퓨터')(학생))
  = 학생 중 컴퓨터 학과인 사람의 이름만 추출

순서:
  1. σ(학과='컴퓨터')(학생) → 컴퓨터 학과 학생만 필터링
  2. π(이름)(결과)        → 이름 열만 추출

SQL 대응:
  SELECT 이름 FROM 학생 WHERE 학과 = '컴퓨터'

이 표현에서 선택을 먼저 하고 투영을 나중에 하는 것이 일반적입니다. 선택으로 행을 줄인 후 투영하면 처리할 데이터가 적어지기 때문입니다.

이름 변경 연산 (ρ, Rename)

이름 변경(ρ, Rename)은 릴레이션이나 속성의 이름을 변경하는 연산입니다. 자기 조인(Self Join)이나 복잡한 질의에서 같은 릴레이션을 여러 번 참조할 때 필요합니다.

ρ(S)(R)
  = 릴레이션 R의 이름을 S로 변경

ρ(상사(사원번호, 이름))(직원)
  = 직원 릴레이션의 이름을 '상사'로, 속성을 '사원번호, 이름'으로 변경

SQL 대응:
  SELECT * FROM 직원 AS 상사

집합 연산

관계 대수는 릴레이션을 집합으로 다루므로, 수학의 집합 연산을 그대로 적용할 수 있습니다. 집합 연산의 전제 조건은 두 릴레이션이 합병 가능(Union Compatible)해야 한다는 것입니다. 합병 가능이란 두 릴레이션의 속성 수가 같고, 대응되는 속성의 도메인이 같은 것을 의미합니다.

합집합 (∪, Union)

컴퓨터학과_학생 ∪ 수학특기_학생
  = 컴퓨터 학과이거나 수학 특기인 학생 (중복 제거)

SQL:
  SELECT * FROM 학생 WHERE 학과 = '컴퓨터'
  UNION
  SELECT * FROM 학생 WHERE 특기 = '수학'

교집합 (∩, Intersection)

컴퓨터학과_학생 ∩ 수학특기_학생
  = 컴퓨터 학과이면서 동시에 수학 특기인 학생

SQL:
  SELECT * FROM 학생 WHERE 학과 = '컴퓨터'
  INTERSECT
  SELECT * FROM 학생 WHERE 특기 = '수학'

교집합은 차집합으로 표현할 수 있습니다. R ∩ S = R − (R − S). 따라서 교집합은 기본 연산이 아닌 유도 연산입니다.

차집합 (−, Difference)

전체_회원 − 주문한_회원
  = 주문을 한 번도 하지 않은 회원

SQL:
  SELECT * FROM 회원
  EXCEPT
  SELECT 회원.* FROM 회원 JOIN 주문 ON 회원.id = 주문.회원id

카테시안 곱 (×, Cartesian Product)

카테시안 곱(×, Cartesian Product)은 두 릴레이션의 모든 튜플 조합을 만드는 연산입니다. R의 튜플 수가 m이고 S의 튜플 수가 n이면, R × S의 튜플 수는 m × n입니다.

학생 (3튜플):              과목 (2튜플):
  001, 김철수               CS101, 데이터베이스
  002, 이영희               CS102, 알고리즘
  003, 박민수

학생 × 과목 (3 × 2 = 6튜플):
  001, 김철수, CS101, 데이터베이스
  001, 김철수, CS102, 알고리즘
  002, 이영희, CS101, 데이터베이스
  002, 이영희, CS102, 알고리즘
  003, 박민수, CS101, 데이터베이스
  003, 박민수, CS102, 알고리즘

카테시안 곱 자체는 의미 있는 데이터를 만들지 않습니다. 보통 카테시안 곱 후에 선택 연산을 적용하여 조건에 맞는 튜플만 골라내는데, 이것이 바로 조인의 정의입니다.

조인 연산 (⋈, Join)

조인(⋈, Join)은 두 릴레이션에서 관련 있는 튜플을 결합하는 연산입니다. 관계형 데이터베이스에서 가장 핵심적인 연산이며, 카테시안 곱 + 선택으로 정의됩니다.

R ⋈ <조건> S = σ <조건> (R × S)

조인 = 카테시안 곱 후 조건에 맞는 행을 선택

세타 조인 (Theta Join)

임의의 비교 조건(θ)을 사용하는 조인입니다.

R ⋈ (R.a θ S.b) S    (θ = >, <, ≥, ≤, =, ≠)

직원 ⋈ (직원.급여 > 부서.평균급여) 부서
  = 자기 부서의 평균 급여보다 많이 받는 직원

동등 조인 (Equi Join)

세타 조인에서 조건이 등호(=)인 경우입니다. 가장 흔한 형태의 조인입니다.

학생 ⋈ (학생.학번 = 수강.학번) 수강
  = 학생과 수강 정보를 학번으로 결합

SQL: SELECT * FROM 학생 JOIN 수강 ON 학생.학번 = 수강.학번

동등 조인의 결과에는 조인 속성(학번)이 두 번 나타납니다. 학생.학번과 수강.학번이 모두 결과에 포함됩니다.

자연 조인 (Natural Join)

동등 조인에서 같은 이름의 속성을 자동으로 매칭하고, 중복 속성을 제거하는 조인입니다. 가장 많이 사용되는 조인 형태입니다.

학생 ⋈ 수강
  = 학생과 수강에서 같은 이름의 속성(학번)으로 자동 조인
  = 결과에 학번은 한 번만 나타남

학생:                    수강:
  학번 | 이름 | 학과      학번 | 과목코드 | 성적
  001  | 김철수| 컴퓨터    001  | CS101   | A+
  002  | 이영희| 전자      001  | CS102   | B+
  003  | 박민수| 컴퓨터    002  | CS101   | A0

자연 조인 결과:
  학번 | 이름  | 학과  | 과목코드 | 성적
  001  | 김철수| 컴퓨터| CS101   | A+
  001  | 김철수| 컴퓨터| CS102   | B+
  002  | 이영희| 전자  | CS101   | A0

  ※ 학번이 한 번만, 박민수(003)는 수강 기록 없으므로 제외

외부 조인 (Outer Join)

자연 조인에서 매칭되지 않는 튜플도 결과에 포함시키며, 매칭되지 않는 속성은 NULL로 채우는 조인입니다.

왼쪽 외부 조인 (⟕)
  왼쪽 릴레이션의 모든 튜플을 포함

오른쪽 외부 조인 (⟖)
  오른쪽 릴레이션의 모든 튜플을 포함

완전 외부 조인 (⟗)
  양쪽 릴레이션의 모든 튜플을 포함

학생 ⟕ 수강 (LEFT OUTER JOIN)
  학번 | 이름  | 학과  | 과목코드 | 성적
  001  | 김철수| 컴퓨터| CS101   | A+
  001  | 김철수| 컴퓨터| CS102   | B+
  002  | 이영희| 전자  | CS101   | A0
  003  | 박민수| 컴퓨터| NULL    | NULL  ← 수강 기록 없어도 포함!

세미 조인 (Semi Join)

조인 조건을 만족하는 튜플만 남기되, 한쪽 릴레이션의 속성만 결과에 포함하는 조인입니다.

학생 ⋉ 수강
  = 수강 기록이 있는 학생만 추출 (학생의 속성만 결과에 포함)
  = π(학생.*)(학생 ⋈ 수강)

SQL: SELECT DISTINCT 학생.* FROM 학생 WHERE EXISTS
     (SELECT 1 FROM 수강 WHERE 수강.학번 = 학생.학번)

나눗셈 연산 (÷, Division)

나눗셈(÷, Division)은 "모든 것을 만족하는" 튜플을 찾는 연산입니다. "모든 과목을 수강한 학생"을 찾을 때 사용합니다.

R ÷ S = "S의 모든 튜플과 연관된 R의 튜플"

수강 ÷ 과목 = 모든 과목을 수강한 학생

수강:                 과목:
  학번 | 과목코드       과목코드
  001  | CS101         CS101
  001  | CS102         CS102
  002  | CS101
  003  | CS101
  003  | CS102

수강 ÷ 과목 = {001, 003}
  001: CS101 ✓, CS102 ✓ → 포함
  002: CS101 ✓, CS102 ✗ → 제외
  003: CS101 ✓, CS102 ✓ → 포함

나눗셈에 대응되는 SQL은 NOT EXISTS의 이중 부정 패턴입니다.

-- "모든 과목을 수강한 학생" = "수강하지 않은 과목이 없는 학생"
SELECT DISTINCT s.학번
FROM 수강 s
WHERE NOT EXISTS (
    SELECT c.과목코드
    FROM 과목 c
    WHERE NOT EXISTS (
        SELECT 1 FROM 수강 e
        WHERE e.학번 = s.학번 AND e.과목코드 = c.과목코드
    )
);

관계 대수의 등가 변환

쿼리 옵티마이저는 관계 대수의 등가 변환 법칙을 이용하여 더 효율적인 실행 계획을 만듭니다. 주요 법칙은 다음과 같습니다.

선택 푸시다운 (Selection Push-Down)

가장 중요한 최적화 규칙입니다. 선택 연산을 가능한 한 먼저 수행하여 처리할 데이터량을 줄입니다.

비효율
  σ(학과='컴퓨터')(학생 ⋈ 수강)
  → 조인(비용 높음)을 먼저 하고, 선택

최적화
  σ(학과='컴퓨터')(학생) ⋈ 수강
  → 선택을 먼저 하여 학생 수를 줄이고, 조인
  → 조인할 튜플 수가 줄어 비용 절감!

투영 푸시다운 (Projection Push-Down)

필요한 속성만 먼저 골라내어 처리할 데이터 크기를 줄입니다.

비효율
  π(이름)(학생 ⋈ 수강)
  → 조인 시 모든 속성을 포함한 채로 처리

최적화
  π(이름)(π(학번,이름)(학생) ⋈ π(학번)(수강))
  → 필요한 속성만 먼저 골라 조인
  → 중간 결과의 크기가 줄어 메모리/I/O 절감

조인 순서 변경

여러 릴레이션을 조인할 때, 결과가 가장 작아지는 순서로 조인합니다.

A (1000행) ⋈ B (100행) ⋈ C (10000행)

순서 1: (A ⋈ B) ⋈ C
  A ⋈ B → 중간 결과 작음 (100행 기준)
  → C와 조인

순서 2: (A ⋈ C) ⋈ B
  A ⋈ C → 중간 결과 큼 (10000행 기준)
  → B와 조인

→ 순서 1이 훨씬 효율적
→ 옵티마이저가 카디널리티 추정으로 최적 순서 결정

왜 관계 대수를 알아야 하는가

SQL을 작성하면 DBMS의 옵티마이저가 관계 대수 표현식으로 변환하고, 다양한 실행 계획을 생성하여 가장 비용이 낮은 것을 선택합니다.

원래 쿼리:
  π(이름)(σ(학과='컴퓨터')(students ⋈ enrollments))
  → 조인을 먼저 하고, 선택하고, 투영

최적화 후:
  π(이름)(σ(학과='컴퓨터')(students) ⋈ enrollments)
  → 선택을 먼저 하여 조인할 튜플 수를 줄임 (Push-down)

선택을 먼저 하면 조인할 데이터가 줄어든다는 최적화 규칙이 관계 대수의 등가 변환 법칙에서 나옵니다. 이 원리를 이해하면 실행 계획을 읽을 때 옵티마이저가 왜 그런 선택을 했는지 납득할 수 있습니다.

실행 계획 읽기

관계 대수를 이해하면 EXPLAIN 명령으로 출력되는 실행 계획을 읽을 수 있습니다.

EXPLAIN SELECT s.이름
FROM 학생 s
JOIN 수강 e ON s.학번 = e.학번
WHERE s.학과 = '컴퓨터';

-- 실행 계획 (개념적):
-- 1. 학생 테이블에서 학과='컴퓨터' 필터 (σ, Selection → WHERE)
-- 2. 수강 테이블과 Nested Loop Join (⋈, Join)
-- 3. 이름 속성만 추출 (π, Projection → SELECT)

-- 옵티마이저의 판단:
-- "학생 테이블에 학과 인덱스가 있으므로 먼저 필터링(σ)"
-- "필터링된 결과가 작으므로 Nested Loop Join이 효율적"

관계 대수 연산 정리

관계 대수의 기본 연산 5개는 σ, π, ∪, −, ×이며, 나머지(⋈, ∩, ÷)는 이 5개로 표현할 수 있는 유도 연산입니다. 이 5개의 기본 연산만으로 관계형 데이터베이스에서 필요한 모든 질의를 표현할 수 있습니다.

관계 대수와 SQL의 차이

관계 대수와 SQL은 밀접하게 관련되어 있지만 몇 가지 차이가 있습니다.

SQL이 관계 대수보다 표현력이 넓은 이유는 집계 함수, 그룹화, 정렬 등 관계 대수에 없는 기능을 추가로 제공하기 때문입니다. 이러한 확장된 기능까지 포함한 것을 확장된 관계 대수(Extended Relational Algebra)라 하며, 집계 함수(γ, Aggregation)와 정렬(τ, Sort) 등의 연산이 추가됩니다.

γ (학과), COUNT(학번) (학생)
  = 학과별 학생 수를 계산

SQL: SELECT 학과, COUNT(학번) FROM 학생 GROUP BY 학과

τ (이름 ASC) (학생)
  = 이름 오름차순으로 정렬

SQL: SELECT * FROM 학생 ORDER BY 이름 ASC

관계 대수는 SQL의 밑바닥이자 설계 도면입니다. SQL을 작성할 때 관계 대수를 직접 사용하지는 않지만, 쿼리가 내부적으로 어떻게 처리되는지 이해하려면 관계 대수가 필수적입니다. 실행 계획을 읽고, 느린 쿼리의 원인을 분석하고, 옵티마이저의 선택을 이해하는 데 관계 대수의 지식이 큰 도움이 됩니다.

다음 장에서는 데이터베이스의 구조를 정의하는 SQL DDL을 다루겠습니다.