[database] Relational Algebra (selection, projection, cross-product, set-difference, union)

본 게시글은

서울대학교 데이터사이언스대학원 이상원 교수님의

데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 강의를

학습을 목적으로 재구성하였습니다

---

오늘 강의는 Relational Database에서

SQL의 기본 원리가 된

Relation Algebra에 관한 내용이다

 

 

 

우선 RDB의 쿼리 언어인 SQL의

역사에 대해 잠깐 알아보자

 

E. F. Codd 박사가 제안한

Relational Algebra를 기반으로

IBM의 SystemR팀에서 개발한 것이 SEQUEL이고

이것이 발전을 거쳐 지금의 SQL이 되었다

 

 

 

SQL은 2가지 수학적 쿼리 언어로부터 형성되었는데

Relational Algebra(RA)와 Relational Calculus(RC)이다

 

위 두 언어는 둘다 Relational Database의 쿼리 언어로 개발되었는데

Relational Algebra가 조금 더 절차적인 언어라고한다

사람이 쓰기에 더 편한 언어는

Relational Calculus이고

두 언어는 각각 1대1 대응이 되는데

이를 relationally complete하다고 표현한다

 

 

 

그렇다면 Algebra는 무엇일까?

우리가 흔히 Algebra라고 하면

공대에서 배우는 Linear Algebra에 대해서 떠올릴 것이다

 

Algebra는 대수체계를 말하고

이러한 대수 체계는

Operands, Operators, Axioms

3가지로 구성되어있다

 

operands는 연산을 하기 위한 대상인

변수 혹은 values를 얘기하고

operators는 operands를 입력받아

연산을 수행하는 함수를 얘기하고

axioms은 연산의 성질을 보장하는 규칙을 얘기한다

 

 

위 세가지의

operands, operators, axioms를

관계 대수에 대해서 살펴보자

 

관계 대수에서 operands는

연산의 대상이 되는 것들이므로

relations 혹은 variables을 뜻한다

 

그러고 operators는 database에서

relation을 이용해서 수행할 수 있는

가장 보편적인 것들로 구성되어있다

 

여기서 closedness라는 개념이 나오는데

relational operator의 모든 연산자는

input도 relation으로 받고

output도 relation으로 반환하기 때문에

연산을 계속해서 연결해서 사용할 수 있고

이를 closedeness(폐쇄성)이라고 한다

 

마지막으로 axioms은 크게 3가지가 있는데

commutativeness(교환법칙)

Associativeness(결합법칙)

Distributiveness(분배법칙)

이 성립한다

 

 

관계대수가 수행될 때의 전제에 대해서 알아보자

쿼리는 relation instance에 대해서 수행되고

그 쿼리의 결과 역시 relation instance이다

input으로 들어가는 relation의 스키마는 고정되어있고

output으로 나오는 스키마도 역시 고정되어있다

 

또 한가지 기억해야될 점은

RDB에서는 모든 값을 위치 기반이 아닌 value 기반으로 찾는다

하지만 아주 예외적인 경우에 편의에 따라

positional(위치) 기반으로 값을 찾는 경우도 있다고한다

 

그럼 이제 본격적으로 관계대수에 대해서 살펴보자

관계대수의 기본 연산에는 아래 5가지가 있다

Selection

Projection

Cross-product

Set-difference

Union

 

각각에 대해서 우선 간단하게 살펴보자

 

selection은 하나의 테이블 안에서

조건을 줘서 만족하는 tuple을 선택하는 것이다

 

projection은 하나의 table 안에서

원하는 column을 지정해서 선택하는 것이다

 

cross-product는 cartesian product라고도 불리는데

2개의 relation을 곱하는 것이다

 

set-difference는 차집합인데

R1에만 있고 R2에는 없는 것들을

남기겠다는 뜻이다

 

마지막 union은 합집합을 의미한다

 

 

앞의 기본 다섯가지 연산자 이외에도

다른 연산자들도 존재한다

 

intersection, join, division, renaming, aggregation 등이 있다

 

앞에서 설명했던 closedeness 속성 때문에

각각의 연산자들을 조합하여 연산을 수행할 수 있다

 

 

 

이제 각 연산에 대해서 더 자세하게 살펴보자

우선은 projection이다

 

projection list에 없는 attributes는 제외한다

sname과 rating만 뽑아서 오른쪽과 같이

projection이 된다

 

projection은 보통 기호 파이로 표현한다

 

 

 

그렇다면 projection을 수행했을 때

중복 데이터에 대한 처리는 어떻게 할까?

 

projection은 원칙적으로 중복을 제거한 뒤

결과를 반환한다

 

이렇게 하는 이유는

관계형 데이터 모델의 기본 원칙을 지키기 위해서인데

관계형 데이터모델은 집합(set)을 원칙으로 하기 때문에

중복을 허용하지 않는다

 

또한, 관계 대수의 closedness를 유지하기 위해서

projection 후 중복을 제거하여

relation의 형태를 유지하려고 하는 것이다

 

따라서 위 ppt의 예시의 경우

그냥 select age from S2를 하는 경우

중복이 포함된 4개의 row를 가진 column이 반환되겠지만

projection을 하는 경우

35.0이 중복제거로 인해 한개만 나오고

35.0, 55.5만 반환되게된다

 

 

이제 selection에 대해서 살펴보자

selection은 특정 조건에 맞는 tuple만 가져오는 것이다

 

위 예시에서는 S2 table에서

rating이 8이 이상인 것만

selection을 수행해줬다

그러면 rating이 9와 10인 rows만

결과로 나오는 것을 볼 수 있다

 

selection은 기호로는 시그마를 사용하며

중복을 허용하지 않는다

(원래 table도 중복이 없으니깐)

 

또한 tuple들만 추출하는 것이기 때문에

input relation과 output relation의

스키마가 동일하다

 

또한, 다른 관계 대수 opeartion을

같이 수행할 수 있기 때문에

ppt 마지막의 예시처럼

projection과 selection을 동시에 사용하여

sname과 rating column만 뽑는

결과를 가져올 수도 있다

 

 

이번엔 union, intersection, set-difference에

관한 내용이다

 

이 세 가지 연산자는 모두

집합과 관련된 연산자이다

 

set-difference는 차집합

union은 합집합

intersection은 교집합을 의미한다

 

연산을 할 때 input이 2개가 필요한

연산자를 binary operator라고 하는데

이 세가지 연산자는 binary operator이고

이 input과 output은 각각 스키마가 서로 동일해야한다

한 마디로 서로 양립가능(compatible)해야한다

 

 

이번엔 cross-product,

caretesian product에 대해서 알아보자

 

cross-product는 한국어로는 교차곱이라고 불리며

두 개의 테이블을 모든 가능한 조합으로

결합하는 연산이다

 

위의 예시를 봤을 때

S1 table과 R1 table이 있을 때

이 두 table을 교차곱시켜주면

위와같이 3 * 2의 6개의 조합을 가진

교차곱 Table이 결과로 나온다

 

그렇다면 교차곱을 시켜줄 두개의 table에서

이름이 같은 column이 있으면 어떻게 될까?

보통 DBMS에서는 각각 table의 이름을

접두사로 추가하여 해결한다

 

하지만 미리 충돌할 것 같은 이름을

다른 이름으로 지정해줘

name conflict를 예방해주면 좋다

 

 

SQL은 이러한 관계 대수들의 조합으로 만들어진

쿼리 언어이다

 

그렇다면 SQL을 보면서 각각 관계 대수가

어떻게 활용되고있는지 살펴보자

 

SELECT 뒤에 내가 보고싶은

column이름을 지정해주는 것은

projection 연산이다

그런 다음 FROM 뒤에 여러 가지 table이 나오는 것은

cartesian product이다

마지막 WHERE 뒤에 붙여주는 조건은

selection 연산이다

 

기본적으로 우리가 가장 많이 사용하는 SQL의

SELECT ~~ FROM ~~ WHERE ~~

의 구절에 이러한 semantic이 들어가있다

 

그럼 이런 연산을 어떤 순서로 수행할까?

정말 naive하게 한다면

FROM 뒤의 table들로

cartesian을 먼저 수행해준 다음

WHERE의 조건으로 selection을 수행하고

그 다음 proejction을 통해 필요한 column만 추출할 것이다

 

이게 실제로 이런 방식으로 이뤄진다기보다는

정말 naive한 방식일 것이다

 

 

 

이제 기본 관계 대수가 아닌 다른 연산도 알아보자

그 중에서 가장 많이 사용되는

join 연산에 대해서 살펴보자

 

join은 relational DB에서

가장 common하게 사용되는 연산이다

 

join에는 여러 가지 종류가 있는데

우선 첫 번째로 살펴볼 condition join에 대해 보자

 

condition join은 특정 조건에 따라

결합하는 join 방식이다

 

condition join의 결과는 cross-product 결과와 동일한데

그 중에서 조건을 만족하는 것만 뽑아낸 것이다

 

 

두 번째인 Equi-Join을 보자

Equi-Join은 동일한 것만 뽑는 join이다

위 예시에서는 sid에 대해서 S1과 R1을

Equi-Join을 해줬으면

양 테이블의 sid가 동일한 row만 출력이된다

 

 

마지막은 natural join이다

natural join은 equi-join과 동일한데

모든 이름이 동일한 column에 대해서

equi-join을 수행해주는 것이다

 

위 예시는 이름이 같은 column이

sid밖에 없으므로

equi-join과 동일한 결과가 나오게된다