Relational Algebra (관계대수)

Relational operators

relational operators는 relation에 대해 닫혀 있음

(input도 relation, 연산 결과 output도 relation)

 

6 basic operators

• select: σ
• project: Π
• union: ∪
• set difference: –
• cartesian product: ×
• rename: ρ

 

additional operators

• set intersection
• join, natural join
• assignment

(+ outer join, generalized projection, aggregate functions)

 

 

 

Select operation

p: selection predicate. AND, OR, NOT 등으로 여러 term 연결해 쓸 수 있음

조건(p)를 만족하는 row(tuple)들을 select

 

example

⇒ instructor relation에서 dept_name="Physics"인 row들만 select

 

SQL example

select dept_name
from instructor
where dept_name="Physics";

 

 

 

Project operation

A1, A2, ..., Ak: attributes name

(중복 제외하고) 지정한 k개의 column들을 project

 

example

⇒ instructor relation에서 ID, name, salary column들만 project

 

SQL example

select distinct (ID, name, salary)
from instructor;

* SQL은 multi set을 기반으로 하기 때문에, 중복 제거하려면 명시적으로 명령 추가 필요함

 

 

 

Cartesian product operation

r × s = { t q | t∈r AND q∈s }

직관적으로 두 relation r, s를 하나로 만드는 방법.

r의 첫 번째 튜플과 s의 모든 튜플을 concatenate → r의 두 번째 튜플과 s의 모든 튜플을 concatenate → ….

r의 attributes r(R)과 s의 attributes s(S)들이 서로 disjoint하다는 가정 하에 연산 (아닌 경우 겹치는 attribute를 rename 필요)

 

 

SQL example

select *
from r, s;

 

 

 

Natural join operation

Cartesian product 진행 시 의미 없는 데이터가 너무 많이 생겨 비효율적! 처음부터 의미 있는 데이터만 합치려는 방법

relation r, s의 공통된 attribute 있는지 확인 후, 그 attribute에서 같은 값인 tuple들만 골라서 R ∪ S

r(R)과 s(S)의 공통 원소 없는 경우, cartesian product와 같은 결과

 

natural join은 basic operator가 아니기에, basic operator들로만 natural join을 rewrite할 수 있음

example

r(R) = (A, B, C, D)

s(S) = (E, B, D)

r⨝s 의 result schema = (A, B, C, D, E)

rewrite r⨝s with basic operators:

 

 

 

Union operation

r ∪ s = { t | t∈r OR t∈s }

union operator 사용할 수 있는 조건 2가지:

1. r, s의 attribute 개수 같을 것 (same arity)

2. r, s의 attribute들의 domain은 같은 data type으로 합쳐질 수 있을 것 (compatible)

 

SQL example

(select * from r)
union
(select * from s);

 

 

 

Intersection operation

r ∩ s = { t | t∈r AND t∈s }

intersection operator 사용할 수 있는 조건: union과 같음

 

basic operator가 아니기에, basic operator들로만 rewrite할 수 있음

example

r ∩ s = r - (r - s)

 

 

 

Set difference operation

r - s = { t | t∈r and t∉s }

set difference operator 사용할 수 있는 조건: union과 같음

 

SQL example

(select A, B from r)
except
(select A, B from s);

 

 

 

Assignment operation

복잡한 query들을 나타낼 때 유용함

 

example

 

 

 

Rename operation

expression E를 x로 rename

 

example

 

 

 

 

---

본 포스트 내용은 고려대학교 컴퓨터학과 "데이터베이스"강의 내용 일부를 개인 공부 목적으로 정리한 것입니다.