관계 대수

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

관계 대수의 위치

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

SQL은 관계 해석에 가까운 선언형 언어이고, DBMS의 쿼리 옵티마이저는 SQL을 논리적 관계 대수 표현식으로 바꾸어 실행 계획을 만듭니다. 관계 대수와 안전한 관계 해석은 같은 수준의 표현력을 갖는다고 설명합니다(관계 완전, Relationally Complete). 즉 한쪽에서 표현할 수 있는 관계형 질의는 다른 쪽에서도 대응되는 방식으로 표현할 수 있습니다.

핵심 연산 개요

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

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

선택 연산 (σ, Selection)

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

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

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

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

투영 연산 (π, Projection)

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

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

선택과 투영의 조합

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

이 예시에서는 투영하려는 최종 열은 이름이지만 선택 조건에 학과가 필요하므로, 먼저 학과 조건으로 행을 고른 뒤 이름만 남깁니다. 실제 DBMS 옵티마이저는 필요한 속성을 보존하는 범위에서 선택과 투영의 순서를 재배치할 수 있습니다.

이름 변경 연산 (ρ, Rename)

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

속성 이름을 바꿀 때는 새 이름의 전체 목록이나 사번 → 사원번호처럼 명확한 매핑을 함께 적어야 어떤 속성이 어떤 이름으로 바뀌는지 혼동하지 않습니다.

집합 연산

관계 대수는 릴레이션을 집합으로 다루므로, 수학의 집합 연산을 적용할 수 있습니다. 합집합, 교집합, 차집합의 전제 조건은 두 릴레이션이 합병 가능(Union Compatible)해야 한다는 것입니다. 합병 가능이란 두 릴레이션의 속성 수가 같고, 대응되는 속성의 도메인이 같은 것을 의미합니다. SQL의 집합 연산은 보통 컬럼 위치를 기준으로 대응시키며, UNION은 기본적으로 중복을 제거하고 UNION ALL은 중복을 보존합니다. 반면 카테시안 곱은 합병 가능 조건 없이 모든 튜플 조합을 만듭니다.

합집합 (∪, Union)

교집합 (∩, Intersection)

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

차집합 (−, Difference)

카테시안 곱 (×, Cartesian Product)

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

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

조인 연산 (⋈, Join)

조인(⋈, Join)은 두 릴레이션에서 관련 있는 튜플을 결합하는 연산입니다. 관계형 데이터베이스에서 가장 핵심적인 연산이며, 세타 조인은 카테시안 곱 + 선택으로 정의할 수 있습니다. 자연 조인처럼 결과 스키마에서 중복 속성을 정리하는 조인은 투영이나 이름 변경까지 함께 생각해야 합니다.

세타 조인 (Theta Join)

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

동등 조인 (Equi Join)

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

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

자연 조인 (Natural Join)

동등 조인에서 같은 이름의 속성을 자동으로 매칭하고, 중복 속성을 제거하는 조인입니다. 관계 대수에서 조인의 결과 스키마 차이를 설명할 때 자주 다루는 형태입니다. 실무 SQL에서는 의도하지 않은 같은 이름의 컬럼까지 매칭될 수 있으므로 명시적인 JOIN ... ON 조건을 더 선호하는 경우가 많습니다.

외부 조인 (Outer Join)

조인 조건에 매칭되지 않는 튜플도 결과에 포함시키며, 반대편에서 찾지 못한 속성은 NULL로 채우는 조인입니다. NULL을 사용하는 SQL의 실무 조인을 설명하기 위해 확장 관계 대수에서 다루는 연산으로 볼 수 있습니다.

세미 조인 (Semi Join)

조인 조건을 만족하는 튜플만 남기되, 기준으로 삼은 한쪽 릴레이션의 속성만 결과에 포함하는 조인입니다. SQL에서는 EXISTS나 IN으로 표현하는 경우가 많고, 기본 연산으로도 유도할 수 있습니다.

나눗셈 연산 (÷, Division)

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

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

-- "모든 과목을 수강한 학생" = "수강하지 않은 과목이 없는 학생"
SELECT 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)

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

조인 순서 변경

여러 릴레이션을 내부 조인할 때, 중간 결과와 예상 비용이 작아지도록 조인 순서를 바꿉니다.

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

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

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

실행 계획 읽기

관계 대수를 이해하면 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개로 표현할 수 있는 유도 연산입니다. 이름 변경(ρ)은 복잡한 식이나 자기 조인을 명확히 쓰기 위해 별도로 포함해 설명하기도 합니다. 이 기본 연산들로 관계 완전한 질의를 표현할 수 있고, SQL의 집계·정렬·NULL 같은 실무 기능은 확장 관계 대수에서 추가 연산으로 설명합니다.

관계 대수와 SQL의 차이

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

SQL이 기본 관계 대수보다 실무 표현 범위가 넓은 이유는 집계 함수, 그룹화, 정렬 등 기본 연산에 없는 기능을 추가로 제공하기 때문입니다. 이러한 기능을 관계 대수식으로 설명하기 위해 확장된 관계 대수(Extended Relational Algebra)에서는 집계 함수(γ, Aggregation)와 정렬(τ, Sort) 등의 연산을 추가로 사용합니다.

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

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