[Database] Relational Algebra | 관계 대수 (4장)

Relational Algebra

관계 대수

- Relational Query Language의 기반이 되는 이론이다.
- Qurey Evaluation Plan들을 표현하기에 용이하다.
- DBMS는 사용자로부터의 Query를 관계 대수로 변환한다.
- DBMS의 Query Optimizer는 가장 Cost가 낮은 Query Evaluation Plan를 선택하여 수행한다.

* Relational Algebra
- Operational(절차적)하며, Execution Plan을 표현하는 데 최적화되어 있다.
- 관계 대수에 대한 피연산자, 연산 결과 모두 Relation이다.
※ 연산 결과로는 단순한 Rows, Columns가 아닌, Table Relation으로 리턴된다.
  (이러한 특성으로 인해, 복합 연산을 구성할 수 있게 된다.)

* Relational Calculus
- Declarative(선언적)하며, 사용자가 원하는 바를 기술하는 데 초점이 맞춰져 있다.

---

Basic Operation (기본 연산)

※ 질의의 결과 또한, Relation Instance이기 때문에, 어느 연산 결과에 다른 연산을 적용할 수 있다.

1) Selection (\(\sigma_c (R)\))
- Relation R에서 조건 c를 만족하는 튜플을 리턴한다. (수평분할)
- DBMS는 Index(B+ Tree, Hash 등)를 이용하거나, File Scan과 같은 방법으로 Selection 연산을 수행한다.

Example. Selection (\(\sigma_{rating > 8} (S2)\))

Table: \(S2\)				→	\(\sigma_{rating > 8} (S2)\)
sid	sname	rating	age		sid	sname	rating	age
28	yuppy	9	35.0		28	yuppy	9	35.0
31	lubber	8	55.5		58	rusty	10	35.0
44	guppy	5	35.0
58	rusty	10	35.0

---

2) Projection (\(\pi_a (R)\))
- Relation R에서 주어진 속성들의 값으로만 구성된 튜플을 리턴한다. (수직분할) 
- Relation R에서 필요한 Column만 추출한다.

Example. Projection (\(\pi_{sname, rating} (S2)\))

Table: \(S2\)				→	\(\pi_{sname, rating} (S2)\)
sid	sname	rating	age		sname	rating
28	yuppy	9	35.0		yuppy	9
31	lubber	8	55.5		lubber	8
44	guppy	5	35.0		guppy	5
58	rusty	10	35.0		rusty	10

Example. Selection and Projection (\(\pi_{sname, rating} (\sigma_{rating > 8} (S2))\))

Table: \(S2\)				→	\(\pi_{sname, rating} (\sigma_{rating > 8} (S2))\)
sid	sname	rating	age		sname	rating
28	yuppy	9	35.0		yuppy	9
31	lubber	8	55.5		rusty	10
44	guppy	5	35.0
58	rusty	10	35.0

※ 일반적으로 Selection(수평분할)후에 Projection(수직분할)을 수행한다. (시간 효율성을 위해서이다.)

---

3) Cross-Product (\(R \times S\)) (=Cartesian Product)
- Relation R의 각 튜플과 Relation S의 각 튜플을 모두 연결하여 새로운 튜플을 리턴한다.
  (Matrix 곱셈과 유사하다.)

Example. Cross-Product Operation

S1					R1
sid	sname	rating	age		sid	bid	day
22	dustin	7	45.0		22	101	10/10/96
31	lubber	8	55.5		58	103	11/12/96
58	rusty	10	35.0

 

\(S1 \times R1\)
(sid)	sname	rating	age	(sid)	bid	day
22	dustin	7	45.0	22	101	10/10/96
22	dustin	7	45.0	58	103	11/12/96
31	lubber	8	55.5	22	101	10/10/96
31	lubber	8	55.5	58	103	11/12/96
58	rusty	10	35.0	22	101	10/10/96
58	rusty	10	35.0	58	103	11/12/96

- 위 예시에서는 S1의 sid와 R1의 sid의 이름이 중복되어 Conflict가 발생한다.
  (이 경우, Renaming Operation(\(\rho\))이 수반되어야 한다.)
- \(\rho( C(1 \to sid1, 5 \to sid2), S1 \times R1) \qquad (C : Column)\)

---

4) Set-Difference (\(R - S\))
- Relation R과 Relation S의 차집합을 리턴한다.

---

5) Union (\(R \cup S\))
- Relation R과 Relation S의 합집합을 리턴한다.
- 기본적으로, 중복되는 Tuple들은 제거된다.
  (대표로 한 Tuple만 리턴된다.)

---

Additional Operation (보조 연산)

6) Intersection (\(R \cap S\))
- Relation R과 Relation S의 교집합을 리턴한다.

※ Union Compatible
- 차집합, 합집합, 교집합 연산은 두 Relation이 필드의 개수, 필드의 Type이 같아야 한다는 조건이 있다.
- 이 조건들을 만족시킬 때, 두 Relation을 "Union compatible하다."라고 표현한다.

---

7) Join (R ▷◁ S)
- 공통 속성을 이용해 Relation R과 S의 튜플들을 연결하여 만들어진 튜플들을 리턴한다.
  (Cross-Product 후, 조건에 맞는 Selection 혹은 Projection)

a) Conditional Join (\(\Theta\) Join)
\(R ▷◁_{c} \; S \equiv \sigma_{c} \; (R \times S) \qquad \mathrm{(c \; : \; Condition)}\) 
- 대소 관계를 비교하여 Selection하는 연산이다.

b) Equi Join
\(R ▷◁_{f} \; S \equiv \sigma_{R.f = S.f} \; (R \times S)\)
- 동등 관계를 비교하여 Selection하는 연산이다.
  (즉, Equi Join은 Conditional Join의 Special Case이다.)
- 특정 필드값이 같은 레코드를 Cross Product하므로, 해당 필드를 한 번만 나타낸다.
  (Conditional Join처럼 한 필드를 중복해서 출력하지 않는다.

c) Natural Join (Default Join)
\(R ▷◁ S\)
(Primary Key와 Foreign Key 값이 같은 레코드를 Join하는 것이므로, 따로 조건(c)을 명시하지 않는다.)
- 한 테이블의 Primary Key와 다른 테이블의 Foreign Key가 같은 레코드들만 Join하여 리턴하는 연산이다.
  (가장 자연스러운 형태의 Join 연산이다.)
- Equi Join은 데이터 타입이 일치하기만 한다면 Key Field가 아니여도 Join이 가능하다는 점에서
  Natural Join과 차이가 있다.
- Natural Join은 항상 같은 필드값(PK, FK)을 기준으로 Join하기 때문에, Key 필드가 중복되어 나타나지 않는다.

Example. Conditional Join and Equi Join Operation

S1					R1
sid	sname	rating	age		sid	bid	day
22	dustin	7	45.0		22	101	10/10/96
31	lubber	8	55.5		58	103	11/12/96
58	rusty	10	35.0

 

\(S1 \times R1\)
(sid)	sname	rating	age	(sid)	bid	day
22	dustin	7	45.0	22	101	10/10/96
22	dustin	7	45.0	58	103	11/12/96
31	lubber	8	55.5	22	101	10/10/96
31	lubber	8	55.5	58	31	11/12/96
58	rusty	10	35.0	22	101	10/10/96
58	rusty	10	35.0	58	103	11/12/96

 

\(S1 ▷◁_{S1.sid < R1.sid} R1\) (\(\Theta\)-Join)
(sid)	sname	rating	age	(sid)	bid	day
22	dustin	7	45.0	58	103	11/12/96
31	lubber	8	55.5	58	31	11/12/96

 

\(S1 ▷◁_{S1.sid = R1.bid} R1\) (Equi-Join)
(sid)	sname	rating	age	(sid)	bid	day
31	lubber	8	55.5	58	31	11/12/96

- 동일한 필드간의 Equi Join 필드값이 같은 레코드끼리의 Cross Product이므로,
  Conditional Join과 달리, 해당 필드를 중복해서 표현하지 않는다.
 

\(S1 ▷◁ R1\) (Natural Join)
sid	sname	rating	age	bid	day
22	dustin	7	45.0	101	10/10/96
58	rusty	10	35.0	103	11/12/96

- Natural Join은 항상 동일한 필드간의 Join 연산이므로, 위와 같이 필드가 중복되어 나타나지 않는다.
  (위 테이블에서 \(sid\) 필드가 하나임에 유의하자!)
- \(S1 ▷◁_{sid} R1\) 와 같이, Equi Join을 수행해도 결과는 같다.
  (즉, Equi Join으로 Natural Join을 수행할 수 있다.)

---

8) Division (\(R \div S\))
- Relation S의 모든 튜플과 관련이 있는 Relation R의 튜플들을 리턴한다.
- SQL에서는 지원되지 않는 연산이다.
- Division Operation은 모든 경우에 해당되는 레코드를 추출할 때 유용하다.

\(A / B = \{<x> | \exists <x, y>  \in  A, \forall <y>  \in B\}\)
(\(B\)의 모든 필드 값들을 갖고 있는 \(A\)의 레코드들을 리턴한다.)

\(\mathrm{Disqualified} \; x \; \mathrm{Values} : \pi_{x} ((\pi_{x} (A) \times B) - A)\)
\(A / B = \pi_x (A - \mathrm{All \; Disqualified \; Records})\)

Example. Division Operation

Given Tables Below:

Table: A			Table: B1		Table: B2		Table: B3
sno	pno		pno		pno		pno
s1	p1		p2		p2		p1
s1	p2				p4		p2
s1	p3						p4
s1	p4
s2	p1
s2	p2
s3	p2
s4	p2
s4	p4

Division Output Below:

A / B1		A / B2		A / B3
sno		sno		sno
s1		s1		s1
s2		s4
s3
s4

---

9) Renaming (\(\rho\))

---

Qurey Evaluation Plan Examples

- 아래 예시들에서 보이다시피, 하나의 질의에 대한 다수의 Solutions들을 통칭하여 Query Evaluation Plan이라 부른다.

Example. Query Optimization 1

S1					R1
sid	sname	rating	age		sid	bid	day
22	dustin	7	45.0		22	101	10/10/96
31	lubber	8	55.5		58	103	11/12/96
58	rusty	10	35.0
28	yuppy	9	35.0
44	guppy	5	35.0

Query : 

SELECT S1.name
FROM Sailors S1, Reserves R1
WHERE R1.bid = 103 AND R1.sid = S1.sid

--- 103번 배를 예약한 선원의 이름은?

Solution 1 : Selection → Natural Join → Projection
\(\pi_{sname} (S1 \; ▷◁ \; (\sigma_{bid = 103} \; R1))\)

- 먼저, Selection을 통해 R1 테이블을 Reduction한 후에 Join 연산을 수행하므로, I/O Cost가 작다.
  (메인 메모리에서 Storage로 적재하는 테이블의 크기가 작다.)

Solution 2 : Natural Join → Selection → Projection
\(\pi_{sname} (\sigma_{bid = 103} \; (S1 ▷◁ R1))\)

- 먼저, 두 테이블을 Join하므로, 테이블의 크기가 커진 상태에서 Selection을 진행하므로, I/O Cost가 크다.
  (메인 메모리에서 Storage로 적재하는 테이블의 크기가 크다.)

Solution 3 : 임시 테이블에 Selection 결과를 저장 → 또 다른 임시 테이블에 Join 결과를 저장 → Projection
\(\rho(Temp_1, \sigma_{bid=103} \; R1)\)
\(\rho(Temp_2, Temp_1 \; ▷◁ \; S1)\)
\(\pi_{sname} \; (Temp_2)\)

- 먼저 임시 테이블 \(Temp_1\)에 \(bid\)가 103인 R1의 레코드를 저장하여 Storage에 내보내고, (I/O 연산 수행)
  그 후, \(Temp_1\) 과 \(S1\)을 Join한 결과를 임시 테이블 \(Temp_2\)에 저장하여 Storage에 내보낸 다음, (I/O 연산 수행)
  \(Temp_2\)를 메인 메모리로 적재한 후, \(sname\)을 추출한다. (I/O 연산 수행)
- I/O Cost가 매우 크다.

※ DBMS는 질의에 대한 최적의 계산 순서를 선택하여 수행한다. (Query Optimizing; 질의 최적화)

---

Example. Query Optimization 2

S1					R1
sid (PK)	sname	rating	age		sid (PK, FK)	bid (PK, FK)	day (PK)
22	dustin	7	45.0		22	101	10/10/96
31	lubber	8	55.5		58	103	11/12/96
58	rusty	10	35.0
28	yuppy	9	35.0		* R1의 PK = sid + bid + day (만약, PK = sid + bid 이었다면, 다른날 같은 배를 빌릴 수 없게 된다.)
44	guppy	5	35.0

 

B1
bid (PK)	color	make
101	red	A
102	blue	B

Query :

SELECT S1.name
FROM Sailors S1, Reserves R1, Boats B1
WHERE B1.color = 'red' AND B1.bid = R1.bid AND R1.sid = S1.sid

--- 'red' 색상의 배를 예약한 선원의 이름은?

Solution 1 : Selection → Projection → Natural Join → Projection → Natural Join → Projection
\(\pi_{sname} \; (\pi_{sid} \; ((\pi_{bid} \; \sigma_{color = 'red'} \; B1) \; ▷◁ \; R1) \; ▷◁ \; S1)\)

- Join 연산 이전에, 중간중간 계속해서 테이블의 크기를 줄여가며 연산을 진행하므로 I/O Cost가 작다.

Solution 2 : Selection → Natural Join → Natural Join → Projection
\(\pi_{sname} \; (\sigma_{color = 'red'} \; B1) \; ▷◁ \; R1 \; ▷◁ \; S1\)

- Join 연산 이전에, 테이블의 크기를 줄이지 않아, I/O Cost가 크다.

Solution 3 : Natural Join → Natural Join → Projection 
\(\pi_{sname} \; (B1 \; ▷◁ \; R1 \; ▷◁ \; S1)\)

- 연속된 Join 연산으로 인해 테이블의 크기가 매우 커지므로 I/O Cost가 매우 크다.

※ Join 연산 이전에, 테이블의 크기를 최소한으로 줄인 다음 join 연산을 진행해야 한다.
※ Join시에, Natural Join임을 상기하고, Natural Key와 Foreign Key가 연결되어 Join되어야 함을 명심하고 연산을 명령해야 한다.

---

Example. Query Optimization 3

i) Query : OR의 경우 

SELECT S1.name
FROM Sailors S1, Reserves R1, Boats B1
WHERE (B1.color = 'red' OR B1.color = 'green') AND B1.bid = R1.bid AND R1.sid = S1.sid

--- 'red' 혹은 'green' 색상의 배를 예약한 선원의 이름은?

Solution 1 :

\(\rho(\mathrm{Tempboats}, \; (\sigma_{color = 'red' \; \lor \; color = 'green'} \; B1))\)
\(\pi_{sname} \; (\mathrm{Tempboats} \; ▷◁ \; R1 \; ▷◁ \; S1)\)

Solution 2 :

\(\rho(\mathrm{TempRed}, \pi_{sid} \; ((\sigma_{color = 'red'} \; B1) \; ▷◁ \; R1))\)
\(\rho(\mathrm{TempGreen}, \pi_{sid} \; ((\sigma_{color = 'green'} \; B1) \; ▷◁ \; R1))\)
\(\pi_{sname} \; ((\mathrm{TempRed} \cup \mathrm{TempGreen}) \; ▷◁ \; S1)\)

- I/O Cost가 매우 크다.

ii) Query : AND의 경우 

SELECT S1.name
FROM Sailors S1, Reserves R1, Boats B1
WHERE (B1.color = 'red' AND B1.color = 'green') AND B1.bid = R1.bid AND R1.sid = S1.sid

--- 'red'와 'green' 색상의 배를 예약한 선원의 이름은?

Solution 1 :

\(\rho(\mathrm{TempRed}, \pi_{sid} \; ((\sigma_{color = 'red'} \; B1) \; ▷◁ \; R1))\)
\(\rho(\mathrm{TempGreen}, \pi_{sid} \; ((\sigma_{color = 'green'} \; B1) \; ▷◁ \; R1))\)
\(\pi_{sname} \; ((\mathrm{TempRed} \cap \mathrm{TempGreen}) \; ▷◁ \; S1)\)

(\(\mathrm{TempRed}\)와 \(\mathrm{TempGreen}\)은 Union Compatible하므로, 교집합 연산(\(\cap\))이 가능하다.)

※ Query의 내용 중 AND이냐, OR이냐에 따라 관계 대수의 연산 형태가 크게 다를 수 있다는 것을 명심해야 한다.

iii) Query : ALL의 경우

Query : 모든 배를 예약한 선원의 이름은?

Solution 1 :
\(\rho(\mathrm{TempSids}, (\pi_{sid, bid} \; R1) \; / \; (\pi_{bid} \; B1))\)
\(\pi_{sname} \; (\mathrm{TempSids} \; ▷◁ \; S1)\)

iv) Query : 특정 필드값에 대한 ALL의 경우

Query : 모든 'Interlake' 배를 예약한 선원의 이름은?

Solution 1 :
\(\rho \; (\mathrm{TempSids}, (\pi_{sid, bid} \; R1 \; / \; (\pi_{bid} \; (\sigma_{bname = 'Interlake'} \; B1))\)

※ Division Operation은 모든 경우에 해당되는 레코드를 추출할 때 유용하다.

---

Reference: Database Management Systems 3E (Raghu Ramakrishnan, Johannes Gehrke 저, McGrawHill, 2003)