[데이터베이스] 10. 관계 대수

질의언어 (Query Language) 는 데이터베이스로부터 데이터를 가져오고 조작하는 언어이다.

질의언어는 모든 알고리즘을 표현할 수 없는, Turing Complete 하지 않은 언어이다.

 

쿼리는 relation instance 에 적용되며, 쿼리의 적용결과 역시 relation instance 이다.

또한 관계 대수를 정의할 때 각 릴레이션(테이블)의 필드는 위치 기반 또는 이름 기반으로 표현할 수 있는데, SQL에서는 두 방법 모두 사용가능하며, 상황에 맞게 적절하게 사용하면 된다.

 

 

 

관계 대수를 정리하기 위해 위 그림과 같은 테이블을 준비하였다.

S1, S2 는 같은 스키마를 가진 Sailors 테이블이고, R1 테이블은 Reserves 테이블이다.

선원과 선원이 예약한 보트에 대한 정보를 볼 수 있는 테이블이다.

 

 

관계 대수는 기본적으로 위와 같이 5가지 연산을 제공한다.

 

1. Selection 

릴레이션에서 특정 행들을 선택한다.

SQL 에서의 select 를 생각하며 안된다. 오히려 where 절에 해당하는 역할이다.

 

2. Projection

릴레이션에서 특정 열들을 선택한다.

SQL 에서의 select 를 생각하면 된다.

 

3. Cross-product

카르테시안 곱을 생각하면 된다. 두 릴레이션의 모든 조합을 말한다.

 

4. Set-Difference

차집합 연산으로, 왼쪽 릴레이션에서 오른쪽 릴레이션에 존재하는 행을 제거한다.

 

5. Union

합집합 연산으로, 두 릴레이션에 있는 모든 튜플을 합한다.

 

 

위와 같은 5가지 기본 연산 외에도, Intersection (교집합), Join, Division, Renaming 과 같은 추가 연산이 존재한다.

또한 이 연산들은 모두 릴레이션을 입력으로 받아서 릴레이션을 내보내는, 릴레이션에 대해 닫혀있는 연산이다.

 

Projection

SQL 에서 간단한 것이 select 문 이듯, 관계대수에서는 프로젝션이 가장 간단하다.

 

 

 

S2 릴레이션에서 위와 같이 관계대수를 작성하면, 그 결과로 위와 같은 그림의 결과가 나온다.

S2 릴레이션에서 sname, rating 필드만 조회하겠다는 의미이다.

 

참고로 프로젝션 연산은 그 실행결과로 중복된 행을 제거하고 보여준다.

 

 

따라서 S2 테이블에서 age 필드만 프로젝션하면, 이렇게 2개의 행만 남는다.

 

 

Selection

특정 조건에 맞는 행만을 선택하는 연산이다.

 

 

위와 같이 작성하면 S2 릴레이션에서 rating > 8 인 행들만 추려서 보여주게 된다.

 

 

앞에서 정리한 projection 연산자와 함께 사용하면 위와 같이 쓸 수 있다.

먼저 셀렉션 연산의 결과 역시 릴레이션이므로, S2 가 들어가는 위치에 관계 대수 식이 그대로 들어갈 수 있다.

따라서 위 연산은 그 위에서 간단하게 본 selection 연산의 실행 결과로 만들어진 테이블에 대해 한번 더 sname, raiting 을 선별하는 작업을 수행하는 것을 나타낸다.

 

 

합집합, 차집합, 교집합

 

이때 위 연산들의 대상이 되는 릴레이션은 모두 Union-Compatible 해야 한다.

즉, 각 필드의 개수와 각 타입이 모두 일치해야 한다.

 

 

Cross Product

 

cross product 는 두 릴레이션의 각각의 행에 대해, 다른 행과 조합을 맺는 것을 말한다.

만약 (a, b) 라는 행과 (1, 2, 3) 이라는 행이 있었다면

 

(a, 1)

(a, 2)

(a, 3)

(b, 1)

(b, 2)

(b, 3)

 

이렇게 모든 경우를 조합한다.

이때 위 그림에서 보는 것처럼 조합하다보면 같은 필드 이름이 중복될 수도 있다.

이 경우에는 그 결과 릴레이션 인스턴스에 대해서 이름이 만들어지지 않고, 위치로만 언급될 수 있다.

따라서 명시적인 이름을 매기고 싶다면 다음과 같은 이름 재정의 연산을 해야 한다.

 

ρ( C(1 -> sid1, 5->sid2), S1 X R1 )

 

이름 재정의 연산은 로우(RHO) 라는 그리스 문자를 사용한다.

위 식은 S1 x R1 연산의 결과로 나오는 릴레이션을 C 라는 이름으로 부르며, 그 C에서 1번째 필드 이름을 sid1, 5번째 필드 이름을 sid2로 명명한다는 의미이다.

 

 

조인 (Join)

두 테이블의 정보를 조합하는 연산이다.

Cross Product 단순히 두 테이블을 조합한 모든 경우의 수를 나타내지만, Join 은 여기에 다양한 조건을 명시할 수 있다.

 

Condition Join

 

조건 조인은 위와 같이 나비넥타이 모양 기호를 사용하고, C 라는 조건을 아래에 명시한다.

두 릴레이션의 크로스 프로덕트에 Selection 연산을 취한 것과 같은 효과를 갖는다.

 

 

이렇게 작성하면, S1, R1 을 크로스 프로덕트한 결과에서 위 조건을 만족하는 행만 추린다.

 

 

따라서 실행결과는 크로스 프로덕트의 스키마와 동일하다.

조건 조인은 다른 이름으로 세타 조인 (theta join) 이라고도 부른다.

 

 

Equi-Join

동등 조인은 조건 조인에서 등호가 들어간 조건만을 사용하는 조인을 말한다.

 

 

어차피 등호를 사용하므로, 조건식의 자세한 내용을 생략하고 등호로 같다고 비교할 필드명 하나를 지정하여 나타낼 수 있다.

 

Natural Join

자연 조인은 동등 조인에서 더 특별한 경우로, 두 릴레이션에서 모든 공통 필드에 대해 동등 조인을 걸은 것과 같다.

이 경우에는 조건이 명확하므로 조건을 생략하고 나비넥타이 기호만 사용한다.

 

 

 

Division

디비전은 A / B 와 같이 나눗셈 기호처럼 표현한다.

관계 대수에서 디비전은 다음과 같이 정의한다.

 

 

 

A 릴레이션에는 (x, y) 필드로 구성된 튜플들이 있고, B 릴레이션에는 (y) 필드로 구성된 튜플들이 있을 때,

B 릴레이션에 나오는 모든 종류의 y 값과 관계를 맺는 (x) 튜플 집합

 

디비전 연산을 적용하여 문제를 푸는 것은 '모든 배를 예약한 선원의 이름을 찾는다' 와 같은 문제를 푸는데 사용된다.

즉, 모든 배(y)를 예약한 선원(x)의 이름을 찾는다고 볼 수 있다.

 

테이블을 통해 구체적인 예시를 살펴보자.

 

 

 

A / B1 의 경우, (p2) 와 모두 관계를 맺는 sno 값을 고르면 되므로 s1, s2, s3, s4 가 해당된다.

A / B2 의 경우, (p2, p4) 와 모두 관계를 맺는 sno값을 고르면 되므로 s1, s4 가 해당된다.

A / B3 의 경우, (p1, p2, p4) 모두와 관계를 맺는 sno값을 고르면 되므로 s1 이 해당된다.

 

 

디비전 연산은 '기본 연산자' 가 아니라 보조적인 연산자이다.

따라서 이 연산자는 '기본 연산자' 만을 사용해서 같은 연산을 충분히 진행할 수 있어야 한다.

 

디비전 연산을 기본 연산자만을 사용하여 표현해보자.

이때의 아이디어는 디비전 연산의 결과를 찾을 때 여집합으로 구하는 방법이다.

디비전 연산의 결과는 A / B 에서 B 에 속하는 원소 중 하나라도 관계를 맺지 않으면 제외된다.

 

먼저 πₓ (A) X B 를 연산하면 모든 종류의 x 와 B 조합을 구할 수 있다.

(selection 연산을 취하면 x 값을 고르고 중복을 제거한다!)

기존의 A는 (x, y) 로 구성되어 있으므로 위 연산의 결과와 놓고보면 union-compatiable 하다.

 

따라서 이 연산에서 A 를 빼주면 가능한 모든 (x, y) 조합 중, A 에서 등장하지 않은 조합이 나온다.

여기에서 x 만 다시 선택해주면 가능한 모든 x 중 모든 y 와 조합을 맺지 않은 x 들이 선별된다.

 

정리하면 다음과 같이 나타낼 수 있다.

 

πₓ ((πₓ (A) X B) - A)

 

 

예를 들어, x 값으로 가능한 값이 { 1, 2, 3 } 이고 y 값으로 가능한 값이 { 1, 2 } 라고 해보자.

이때 A 릴레이션에서 (1, 1), (1, 2) 로 1 이라는 x 값은 모든 종류의 y 값과 관계를 맺었다고 해보자.

 

그러면 πₓ (A) X B 를 통해 계산한 모든 종류의 (x, y) 쌍

 

(1, 1)

(1, 2)

(2, 1)

(2, 2)

(3, 1)

(3, 2)

 

에 대해서 A를 빼면서 (1, 1), (1, 2) 를 제외하면

 

(2, 1)

(2, 2)

(3, 1)

(3, 2)

 

로 x = 1 인 경우는 존재하지 않게 된다.

 

만약 x = 1 이  y 값과 하나로도 관계를 맺지 않았다면 차집합 연산 결과에서 남았을 것이고,

이 상태에서 x로 selection 연산을 취하면 1 도 남는다.

 

 

마지막으로 디비전 연산은 이렇게 구한 '모든 B 원소와 관계를 맺지 않은 x 값' 의 여집합을 구하면 되므로

 

πₓ (A) - πₓ ((πₓ (A) X B) - A)

 

이렇게 구하면 된다.