0x02. 관계 대수

Relational Algebra란?

데이터베이스에 질의를 던질 때, 내부적으로는 어떤 연산이 일어날까? SQL 문을 작성하면 DBMS가 알아서 처리해주지만, 그 이면에는 Relational Algebra(관계 대수)라는 수학적 체계가 존재한다.

먼저 대수(Algebra)란 피연산자(Operand)와 연산자(Operator)로 구성된 수학적 체계다. 피연산자에 연산자를 적용하면 새로운 값이 만들어진다. 산술 대수에서 숫자와 +, -, x 연산자가 있는 것과 같은 원리다.

Relational Algebra는 이 개념을 관계형 데이터베이스에 적용한 것이다. 하나 또는 두 개의 릴레이션을 입력으로 받아, 새로운 릴레이션을 출력하는 연산들의 집합이다. SQL이 "무엇을 원하는지"를 선언하는 언어라면, Relational Algebra는 "어떤 순서로 처리할지"를 기술하는 절차적 언어(Procedural Language)에 해당한다.

기본 연산자

Selection

Selection은 릴레이션에서 주어진 조건(Predicate)을 만족하는 튜플만 골라내는 연산이다.

$\sigma_p(r)$

여기서 $p$ 는 조건식이며, 조건식 안에서 $\wedge$ (and), $\vee$ (or), $\lnot$ (not) 같은 논리 연산자를 사용할 수 있다.

예를 들어 instructor 릴레이션에서 컴퓨터과학과 교수만 뽑고 싶다면 $\sigma_\{dept\_name = "Comp. Sci."\}(instructor)$ 와 같이 쓴다. SQL의 WHERE 절에 대응된다고 보면 된다.

Projection

Projection은 릴레이션에서 특정 속성(열)만 추출하는 단항 연산이다.

$\prod_\{A_1, A_2, \ldots, A_k\}(r)$

핵심은 결과에서 중복 튜플이 자동으로 제거된다는 점이다. SQL에서 SELECT DISTINCT column1, column2 ...와 유사하다.

Selection이 행(row)을 필터링한다면, Projection은 열(column)을 필터링한다고 이해하면 쉽다.

Cartesian Product

Cartesian Product는 두 릴레이션의 모든 튜플 조합을 생성하는 이항 연산이다.

릴레이션 $r$ 에 $n$ 개의 튜플이 있고 $s$ 에 $m$ 개의 튜플이 있다면, $r \times s$ 의 결과는 $n \times m$ 개의 튜플을 갖는다. 모든 가능한 쌍을 만들어내기 때문에 결과가 매우 커질 수 있다.

참고로 $\sigma$ 와 $\prod$ 는 단항 연산자(Unary Operator)이고, $\times$ 는 이항 연산자(Binary Operator)다.

Join

Join은 Cartesian Product와 Selection을 하나로 합친 연산이다.

$r \bowtie_\theta s = \sigma_\theta(r \times s)$

Cartesian Product로 모든 조합을 만든 뒤, 조건 $\theta$ 에 맞는 튜플만 걸러내는 것이다. 실무에서 Cartesian Product를 단독으로 쓰는 경우는 드물고, 대부분 Join 형태로 사용한다. SQL의 JOIN ... ON ... 구문에 직접 대응된다.

집합 연산자

관계형 모델에서 릴레이션은 본질적으로 튜플의 집합이다. 따라서 수학의 집합 연산을 그대로 적용할 수 있다. 단, 집합 연산을 수행하려면 두 릴레이션이 다음 조건을 만족해야 한다.

두 릴레이션의 속성 개수가 동일해야 한다 (같은 Arity)
대응하는 속성의 도메인이 호환되어야 한다 (같은 타입의 값)

Union

Union은 두 릴레이션을 합쳐서 양쪽 모두에 속하는 튜플을 포함하는 릴레이션을 만든다.

$r \cup s$

집합 연산이므로 중복 튜플은 자동으로 제거된다. SQL의 UNION에 해당한다.

Set Intersection

Set Intersection은 두 릴레이션에 공통으로 존재하는 튜플만 추출한다.

$r \cap s$

SQL의 INTERSECT에 대응된다.

Set Difference

Set Difference는 한 릴레이션에는 있지만 다른 릴레이션에는 없는 튜플을 찾는다.

$r - s$

$r - s$ 와 $s - r$ 은 결과가 다르다는 점에 주의해야 한다. SQL의 EXCEPT에 해당한다.

보조 연산자

Assignment

복잡한 Relational Algebra 표현식을 한 줄로 쓰면 가독성이 떨어진다. Assignment 연산을 사용하면 중간 결과를 임시 변수에 저장하여 순차적인 프로그램처럼 작성할 수 있다.

프로그래밍에서 변수에 값을 대입하는 것과 같은 개념이다.

Rename

Rename 연산은 릴레이션이나 속성에 새로운 이름을 부여한다.

$\rho_\{new\_name\}(E)$

여기서 $E$ 는 릴레이션 또는 속성이다. 같은 릴레이션을 두 번 참조해야 하는 Self Join 같은 경우에 유용하다.

예제: 최고 급여 교수 찾기

배운 연산들을 조합하여 "가장 높은 급여를 받는 교수의 레코드를 찾아라"라는 문제를 풀어보자.

전략: "자신보다 급여가 높은 교수가 존재하는 교수"를 먼저 구한 뒤, 전체 교수에서 이들을 빼면 된다.

$tmp_1 \leftarrow \rho_\{inst1\}(instructor) \times \rho_\{inst2\}(instructor)$

$tmp_2 \leftarrow \sigma_\{inst1.salary < inst2.salary\}(tmp_1)$

$tmp_3 \leftarrow \prod_\{inst1.ID,\ inst1.name,\ inst1.dept\_name,\ inst1.salary\}(tmp_2)$

$Answer = instructor - tmp_3$

1단계에서 instructor 릴레이션을 $inst1$ , $inst2$ 로 이름을 바꿔 Cartesian Product를 수행한다. 2단계에서 $inst1$ 의 급여가 $inst2$ 보다 작은 경우만 Selection한다. 3단계에서 $inst1$ 쪽 속성만 Projection한다. 이렇게 하면 $tmp_3$ 에는 "자기보다 급여가 높은 교수가 한 명이라도 있는 교수"가 담긴다. 마지막으로 전체 instructor에서 $tmp_3$ 를 빼면, 최고 급여를 받는 교수만 남는다.

HGU 전산전자공학부 홍참길 교수님의 23-1 Database System 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.