관계 대수

아래 글은 단국대학교 컴퓨터공학과 나연묵 교수님 2022-1학기 데이터베이스 수업 강의 자료입니다.

관계 모델의 연산

DBMS 엔진 내부에서 사용자 질의를 처리하는 방법을 대수(algebra)를 기반으로 표현하면 관계대수, 해석(calculus)를 기반으로 표현하면 관계해석이다.

관계 대수와 관계 해석의 표현력은 동일하며, 사용자 질의 쿼리 가 주어지면 관계대수로도, 관계해석으로도 표현이 가능하다.(표현력은 100% 동일)

대수표현은 절차적이며, 해석표현은 선언적(비절차적)이다.

관계 해석은 튜플 관계 해석 과 도메인 관계 해석으로 나뉘며, 각각을 바탕으로 데이터 언어가 존재함

관계대수

관계 대수는 DBMS 내부의 언어이다. 즉 쿼리를 파싱하여 내부적인 표현으로 바꿀 때 관계대수의 형태를 사용함. SQL의 키워드는 전부 걷어내고, 쿼리를 구성하는 핵심 조건을 관계대수 형태로 바꿔서 내부적으로 표현하고, 쿼리 옵티마이저(최적화 도구)를 사용해서 관계 대수 표현을 최적화하는 과정을 거침.

• 관계 대수 : 릴레이션을 피연산자로 하는 연산의 집합

릴레이션은 튜플의 집합이며, 이를 피연산자로 하는 연산들의 집합이 관계 대수이다. 예를 들어 1+1 = 3 인 정수연산에서 피연산자는 연산이다.

관계 대수의 기본연산

1. 일반 집합 연산자

릴레이션은 집합이기 때문에 집합 연산자를 사용할 수 있다.

• 합집합, 교집합, 차집합, 카티잔 프로덕트(곱집합)

1. 순수 관계 연산

• 셀렉트(릴레이션에서 원하는 부분만을 선택(σ), 프로젝션(릴레이션에서 원하는 칼럼을 수직으로 선택(π), 조인, 디비전(릴레이션을 다른 릴레이션으로 나눔)

관계 대수는 피연산자가 릴레이션이며 연산결과도 릴레이션인 폐쇄 성질을 갖는다.

튜플의 수를 카디널리티, 애트리뷰트의 수를 차수

• 합집합

$RUS = {t|t∈R V t∈S}$

|R U S|≤ |R| + |S| - 카디널리티를 의미. 즉 유니온 결과 릴레이션의 튜플의 수는 R의 튜플 수와 S의 튜플 수를 더한 것보다 작거나 같다. 즉 중복 튜플이 제외된다.

• 교집합

$R∩S = {t|t ∈R ∧t∈S}$

|R N S| ≤ min{|R|, |S|} - 교집합 연산의 카디널리티는 두 집합의 최소 카디널리티 이하이다.

• 차집합

|R-S| ≤ |R| - 차집합 연산의 최대 카디널리티는 R

• 카티선 프로덕트(곱집합)

RXS = {r*s | r<R N s<S}

일반 연산의 성질

• 합병가능한 릴레이션(Union-Compatible) - ∩, U, - (합집합, 교집합, 차집합)

두 릴레이션의 위해서는 릴레이션의 구조가 동일해야 한다. 즉,

1. 차수가 같아야 한다. (애트리뷰트의 수)
2. 대응 애트리뷰트의 쌍 별로 도메인이 같아야 한다.

• ∩, U, X 연산은 결합적이다.(합집합, 교집합, 곱집합)

$R U S U T = (RUS)UT = RU(SUT)$

• ∩, U, X 연산은 교환적이다.

$RUS = SUR$

하지만 차집합은 교환법칙과 결합법칙이 적용되지 않는다.

관계 대수의 순수 관계 연산

릴레이션의 표기 - $R(X) = R(A1,A2,A3,....An)$ - 릴레이션 스키마

애트리뷰트 A1, A2, A3,...An의 집합을 X라고 하여 릴레이션 스키마를 R(X)로 표기할 수 있음

R의 튜플 r: $<a1,a2,a3,...an>$, 릴레이션 R ={ ${r|r = <a1,a2,...an>}$}

ai : 튜플 r에 대한 애트리뷰트 A의 값, $ai = r.Ai = r[Ai]$ 로 객체나 집합의 표기처럼 표현함.

따라서

$<r.A1,r.A2,r.A3,...r.An> = <r[A1],r[A2],r[A3],...r[An]> = r[A1,A2,A3,...An] = r[X]$

즉 튜플과 튜플에서 애트리뷰트 집합을 잘라낸 값은 같다.

1. 셀렉트(실렉트라고도 함)

실제 데이터 언어의 select와 다름. 셀렉트는 데이터언어에서 where에 해당

실렉트는 어떤 릴레이션의 수평 부분집합을 구하는 연산

다음과 같이 일반적으로 표현함

A,B가 릴레이션 R의 애트리뷰트일 때,

$σAθB(R) = {r|r∈R Λ r.Aθr.B}$

$σAθv(R) = {r|r∈R Λ r.Aθv}$

θ는 관계대수에서 6가지 비교연산자를 말한다. 즉, A라는 애트리뷰트와 B라는 애트리뷰트의 값의 비교 조건을 만족하는 튜플의 집합 / 혹은 v라는 상수와의 비교 조건을 만족하는 튜플의 집합 등이다.

σ학과='컴퓨터' 등으로 표현

$σ학과='컴퓨터'$

셀렉트는 결합법칙, 교환법칙이 성립한다.

• 선택도 selectivity : 선택 조건에 의해 검색되는 튜플의 비율. 선택도를 정확히 추정함으로써 쿼리 최적화를 수행함.

2. 프로젝트(프로젝션)

π로 표현. 셀렉트가 릴레이션에 대해 수평적인 부분집합이라면 프로젝트는 수직 부분집합. 수직방향으로 원하는 칼럼(애트리뷰트)를 선택함

다음과 같이 표현

릴레이션 R(X)에서 Y⊂X 일 때(릴레이션 스키마의 부분집합, 애트리뷰트의 집합)

Y= {B1,B2,B3,....Bm} 이면,

즉 전체 릴레이션에서 원하는 칼럼만을 잘라낸 것이므로 전체 튜플을 가짐.

이 때, 전체 튜플은 기본키에 의해서 유일성이 보장이 되지만, 프로젝트 연산이 기본키를 포함하지 않는 경우 튜플간의 유일성이 보장이 되지 않기 때문에 중복 튜플을 제거한다.

이는 관계대수의 성질인 폐쇄 성질에 따라 연산의 피연산자가 집합이면 결과도 집합 이여야 하기 때문이다.

프로젝션의 수행결과는 다음과 같은 성질을 가진다.

즉 일련의 프로젝션 연산이 있을 때 결과는 항상 마지막 프로젝션의 수행결과와 같다.

3. 세타 조인(theta join)

⋈로 표시한다.

R(X), S(Y)인 릴레이션 R,S의 애트리뷰트 집합 X,Y에 대하여 A∈X, B∈Y 인 애트리뷰트 A,B가 있을 때

AθB라는 조인 조건으로 R과 S를 조인한 결과는 튜플 r과 s의 세타 조건을 만족하는 r*s( concatenation 접합기호, 카티선 프로덕트)의 집합.

A, B는 조인 애트리뷰트이며, 조인 연산의 결과 차수는 R의 차수와 S의 차수를 더한 값과 같다.

$결과 차수 = R의 차수+ S의 차수$이

이 때 결과 릴레이션의 애트리뷰트와 원 소속 릴레이션의 애트리뷰트의 이름을 구분해주기 위해 결과 릴레이션 애트리뷰트 앞에 원 소속 릴레이션을 한정어로 붙여서 일관성을 유지

예:) 학생.학번 학생.이름 학생.학년, 등록.학번, 등록.성적

그러나 학년과 성적같이 각 릴레이션에 고유한 애트리뷰트는 앞에 한정어를 붙일 필요가 없음.

이 때 세타조인에서 세타 조건이 equal인 경우를 특수하게 동일 조인(equijoin) 이라고 한다.

equijoin일 경우 기본키 - 외래 키 조합을 많이 사용함.

equijoin에서 세타 조인의 조건이 되었던 속성(애트리뷰트)는 중복되므로 하나를 제거한 것을 자연조인(natural join)이라고 함

즉 자연 조인은 다음과 같이 표현한다.

이는 다음과도 같다.Z가 R과 S의 조인 애트리뷰트라고 할 때,

$= πXUY(σZ=Z(R X S))$

$= πXUY(R⋈Z=Z S)$

조인 조건을 만족하는 r*s 접합 튜플 중 두 릴레이션 애트리뷰트의 합집합이다. 동일조인 연산은 카티산 프로덕트의 조인 조건 셀렉트 연산으로도 표현 가능하다.

4. 디비전(division)

릴레이션 R(X), S(Y)에서 Y ⊂ X일 때 R(X)= R(D,Y)

$R÷S = {t|t∈πD(R) Λ t*s ∈ R for all s∈S}$

즉 릴레이션 R에 대한 (S와의) 차집합의 프로덕션과 S에 존재하는 모든 튜플에 대한 접합튜플 중 릴레이션 R에 존재하는 튜플들의 집합이다.

S에 대한 모든 튜플의 접합 튜플 중 릴레이션 R에 존재하는 튜플 집합에 대한 차집합 프로덕션이다.

이 때 디비전 결과를 다시 카티잔 프로덕트를 하면 피연산 릴레이션의 부분집합이 된다.

$((R÷S)×S) ⊂ R$