[DB] 관계대수 - 셀렉션, 프로젝션, 집합연산, 조인, 디비전

1. 관계대수

관계대수(Relational Algebra)는 원하는 결과를 얻기 위해 릴레이션에 어떤 연산을 어떤 순서로 적용해야 하는지를 명시하는 절차적인 질의 언어이다. 여기서 절차적이라는 말은, 결과를 얻기까지의 과정을 단계별로 명시해야 한다는 뜻이다. 이는 우리가 흔히 쓰는 SQL이 무엇을 원하는지만 선언하면 되는 선언적 언어인 것과 대조된다.

관계대수의 핵심적인 특징은 연산의 입력과 출력이 모두 릴레이션이라는 점이다. 즉 하나 또는 두 개의 릴레이션에 연산을 적용하면, 그 결과도 항상 릴레이션의 형태로 나온다. 이 덕분에 여러 연산을 자유롭게 조합하고 중첩해서 사용할 수 있다.

관계대수는 연산하는 대상의 개수에 따라 크게 두 가지로 나눌 수 있다. 하나의 릴레이션을 대상으로 하는 단항 연산에는 셀렉션과 프로젝션이 있고, 두 개의 릴레이션을 대상으로 하는 이항 연산에는 집합연산(합집합, 교집합, 차집합, 카티션 프로덕트), 조인, 디비전이 있다.

2. 셀렉션과 프로젝션

셀렉션

셀렉션(Selection)은 릴레이션에서 주어진 조건을 만족하는 튜플(행)만 추출하는 연산이다. 기호로는 그리스 문자 시그마(σ)를 사용하며, 다음과 같은 형식으로 표현한다.

σ조건(릴레이션명)

예를 들어 학생 릴레이션에서 학년이 2인 학생만 추출하고 싶다면 σ학년=2(학생)이라고 표현한다. 셀렉션은 릴레이션을 가로로 잘라내는 연산이라고 이해하면 쉽다. 모든 속성(열)은 그대로 유지되고, 조건을 만족하는 행만 골라낸다.

셀렉션 관련 예제

프로젝션

 

프로젝션(Projection)은 릴레이션에서 원하는 속성(열)만 추출하는 연산이다. 기호로는 그리스 문자 파이(π)를 사용하며, 다음과 같은 형식으로 표현한다.

π속성리스트(릴레이션명)

예를 들어 학생 릴레이션에서 이름과 학년만 보고 싶다면 π이름,학년(학생)이라고 표현한다. 프로젝션은 릴레이션을 세로로 잘라내는 연산이라고 이해하면 쉽다. 모든 튜플(행)은 그대로 유지되고, 지정한 속성(열)만 남긴다.

프로젝션 관련 예제

3. 집합 연산

관계대수의 집합연산은 두 릴레이션을 수학적인 집합처럼 다루는 연산이다. 단, 두 릴레이션에 집합연산을 적용하려면 합병 가능성(Union Compatibility)이라는 조건을 만족해야 한다. 이는 두 릴레이션의 차수(속성의 개수)가 같고, 대응되는 각 속성의 도메인이 서로 같아야 한다는 조건이다.

합집합

합집합(Union, ∪)은 두 릴레이션에 속한 튜플을 모두 합쳐서 하나의 릴레이션으로 만드는 연산이다. 이때 중복된 튜플은 한 번만 포함된다.

교집합

교집합(Intersection, ∩)은 두 릴레이션에 공통으로 속한 튜플만 추출하는 연산이다.

차집합

차집합(Difference, −)은 한 릴레이션에는 속하지만 다른 릴레이션에는 속하지 않는 튜플을 추출하는 연산이다. A − B는 A에는 있지만 B에는 없는 튜플들을 의미하며, 이 연산은 순서가 바뀌면 결과도 달라진다.

 

카티션 프로덕트

카티션 프로덕트(Cartesian Product, ×)는 두 릴레이션에 속한 모든 튜플들을 가능한 모든 조합으로 짝지어 결합하는 연산이다. 합병 가능성을 요구하지 않으며, 결과 릴레이션의 차수는 두 릴레이션의 차수를 더한 값이 되고, 결과 튜플의 개수는 두 릴레이션의 카디널리티를 곱한 값이 된다. 예를 들어 3개의 튜플을 가진 릴레이션과 2개의 튜플을 가진 릴레이션을 카티션 프로덕트하면 6개의 튜플이 만들어진다. 다만 이렇게 만들어진 조합 중에는 의미 없는 결합도 많이 포함되기 때문에, 보통은 카티션 프로덕트 뒤에 셀렉션을 적용해서 의미 있는 조합만 걸러내는 방식으로 활용한다. 사실 조인이 바로 이 카티션 프로덕트와 셀렉션을 결합한 형태라고 볼 수 있다.

4. 조인

 

조인(Join, ⋈)은 두 릴레이션에서 공통된 속성의 값이 일치하는 튜플들을 결합해서 하나의 튜플로 만드는 연산이다. 앞서 설명한 카티션 프로덕트가 모든 가능한 조합을 만들어내는 것과 달리, 조인은 두 릴레이션을 연결하는 조건(보통 외래키와 기본키의 일치)을 만족하는 조합만 결합한다.

예를 들어 학생 릴레이션과 수강 릴레이션이 학번이라는 공통 속성을 가지고 있다면, 두 릴레이션을 학번을 기준으로 조인해서 어떤 학생이 어떤 과목을 수강하는지 하나의 결과로 볼 수 있다.

조인은 결합 조건의 형태나 결과를 어떻게 구성하느냐에 따라 여러 종류로 나뉜다.

세타 조인

세타 조인(Theta Join)은 조인 조건에 등호(=)뿐만 아니라 부등호(>, <, >=, <= 등) 같은 일반적인 비교 연산자를 사용할 수 있는, 가장 넓은 범위의 조인이다. 세타(θ)라는 이름은 비교 연산자 자리에 일반적인 조건을 의미하는 기호로 θ를 사용한 데서 왔다. 다음에 설명할 동등 조인은 이 세타 조인에서 비교 연산자를 등호로 한정한 특수한 경우라고 볼 수 있다.

동등 조인

동등 조인(Equi Join)은 세타 조인 중에서도 비교 연산자로 등호(=)만 사용하는 조인이다. 두 릴레이션의 특정 속성 값이 정확히 일치하는 튜플들만 결합한다. 다만 동등 조인의 결과에는 조인에 사용된 두 속성이 중복되어 그대로 남아있다는 특징이 있다. 예를 들어 학생.학번과 수강.학번을 기준으로 동등 조인을 하면, 결과 릴레이션에는 학번 속성이 두 번 나타난다.

자연 조인

자연 조인 연산의 예시

자연 조인(Natural Join)은 동등 조인의 결과에서 중복되는 속성을 하나로 합쳐서 보여주는 조인이다. 실무에서 두 릴레이션을 연결할 때 가장 흔하게 사용하는 형태가 바로 이 자연 조인이다. 앞서 학생과 수강 릴레이션을 학번 기준으로 결합했던 그림의 결과가 바로 이 자연 조인의 형태로, 학번이라는 중복 속성이 하나로 합쳐져서 나타난다.

외부 조인

지금까지 설명한 조인들은 모두 양쪽 릴레이션에서 조건을 만족하는 짝을 찾은 튜플만 결과에 남긴다는 공통점이 있다. 이런 형태를 내부 조인(Inner Join)이라고 부른다. 그런데 짝을 찾지 못한 튜플이라도 결과에 포함시키고 싶을 때가 있는데, 이를 위한 것이 외부 조인(Outer Join)이다.

외부 조인은 짝을 찾지 못한 속성 값을 NULL로 채워서라도 원래 릴레이션의 튜플을 결과에 남긴다. 어느 쪽 릴레이션을 기준으로 보존하느냐에 따라 다시 세 가지로 나뉜다.

왼쪽 외부 조인(Left Outer Join)은 왼쪽 릴레이션의 모든 튜플을 보존하고, 오른쪽 릴레이션에 짝이 없으면 그 부분을 NULL로 채운다.

왼쪽 외부 조인 연산 예시

오른쪽 외부 조인(Right Outer Join)은 반대로 오른쪽 릴레이션의 모든 튜플을 보존하고, 왼쪽 릴레이션에 짝이 없으면 NULL로 채운다.

완전 외부 조인(Full Outer Join)은 양쪽 릴레이션의 모든 튜플을 보존하며, 어느 한쪽에 짝이 없더라도 NULL로 채워서 결과에 포함시킨다.

이 외부 조인의 세 가지 형태는 SQL에서 LEFT JOIN, RIGHT JOIN, FULL OUTER JOIN이라는 문법으로 그대로 구현된다.

세미 조인

세미 조인 예시

세미 조인(Semi Join)은 조인 조건은 동일하게 사용하지만, 결과로는 한쪽 릴레이션의 속성만 남기는 조인이다. 즉 다른 릴레이션과 조인 조건을 만족하는 튜플이 존재하는지만 확인하는 용도로 사용되며, 결과 릴레이션의 구조는 한쪽 릴레이션의 구조와 동일하게 유지된다.

세미 조인은 실제 SQL에서는 보통 EXISTS 같은 서브쿼리 형태로 구현된다.

5. 디비전

디비전(Division, ÷)은 비교적 복잡한 개념이지만 활용도가 높은 연산이다. 디비전은 한 릴레이션(피제수)에서, 다른 릴레이션(제수)에 있는 모든 값들과 일일이 빠짐없이 짝을 이루고 있는 값만 추출하는 연산이다.

다음과 같은 상황을 생각해보자. 수강 릴레이션에는 학번과 과목명이 들어있고, 필수과목 릴레이션에는 반드시 들어야 하는 과목명들이 들어있다. 이때 수강 ÷ 필수과목을 계산하면, 필수과목에 있는 모든 과목을 예외 없이 전부 수강한 학번만 결과로 남게 된다.

디비전 연산 예시 1

디비전 연산 예시 2

6. 관계대수 예제

지금까지 배운 연산들을 종합해서, 다음과 같은 학생 릴레이션과 수강 릴레이션이 있다고 가정하고 몇 가지 질의를 관계대수로 표현해보겠다.

 

학생 릴레이션

학번	이름	학년	학과
2024001	김민준	2	컴퓨터공학
2024002	이서연	1	전자공학
2024003	박지호	2	컴퓨터공학

 

수강 릴레이션

학번	과목명
2024001	데이터베이스
2024001	자료구조
2024002	데이터베이스
2024003	데이터베이스
2024003	자료구조

예제 1: 컴퓨터공학과 학생의 이름만 조회

먼저 학과가 컴퓨터공학인 학생을 셀렉션으로 골라낸 다음, 그 결과에서 이름만 프로젝션으로 추출한다.

π이름(σ학과='컴퓨터공학'(학생))

이 연산을 수행하면 김민준과 박지호라는 이름만 결과로 남는다.

예제 2: 데이터베이스를 수강하는 학생의 이름 조회

수강 릴레이션에서 과목명이 데이터베이스인 튜플을 셀렉션으로 골라낸 다음, 학생 릴레이션과 학번을 기준으로 조인하고, 마지막으로 이름만 프로젝션으로 추출한다.

π이름(학생 ⋈ σ과목명='데이터베이스'(수강))

이 연산을 수행하면 데이터베이스를 수강하는 김민준, 이서연, 박지호 세 명의 이름이 결과로 남는다.

예제 3: 데이터베이스와 자료구조를 모두 수강하는 학생의 학번 조회

이번에는 디비전 연산을 활용한다. 먼저 데이터베이스와 자료구조라는 두 과목명을 가진 임시 릴레이션(필수과목)을 만들고, 수강 릴레이션을 이 필수과목으로 나눈다.

π학번,과목명(수강) ÷ 필수과목

이 연산을 수행하면 데이터베이스와 자료구조를 모두 수강한 2024001과 2024003 학번이 결과로 남는다.