DBMS: Basic RA Operations

INTRO 🙌

저번 시간에는 File Organization and Indexing에 대하여 알아보았다.

이번 시간에는 Relational Algebra Operations에 개념에 대해 알아보자.

---

배경지식 🗂

Relational Data Operation

• 원하는 데이터를 얻기 위해 Relation에 필요한 Query를 수행하는 것

Relational Algebra(관계 대수)

• 절차식 언어로 원하는 결과를 얻기 위해 데이터 처리 과정을 순서대로 기술한다.

Relational Calculus(관계 해석)

• 비절차식 언어로 원하는 결과를 얻기 위해 처리를 원하는 데이터가 무엇인지만 기술

---

직관 ✔

    Employees(eid, ename, city, state)
    Departments(did, dname, mid)

    Select E.ename
    From Employees E, Departments D
    Where E.eid = D.mid and E.city = ‘Madison’

어떻게 상기 쿼리를 실핼할 수 있나?

• 가능한 계획 수립
• plan 별 runtime 예측
• 가장 빠른 plan 선택 & 실행

여기서 우리는 어떻게 plan을 선택해야 하는지에 대한 궁금증이 피어날 것이다.

plan 선택을 위해, 아래 SQL 컴파일러의 내부 동작 과정을 이해해볼 필요가 있다.

SQL Compiler: compile 내부 동장 과정

1. compile 실행시, 전체 코드를 graph 형태로 변환
2. 해당 graph를 최적화
3. 최적화된 graph를 execute

---

RA Operations 5가지

1. Union

\(R1 U R2\)

• 모든 tuples in R1 or R2
• R1, R2, (R1 U R2) 각각과 동일한 schema를 공유한다.
  • i.e., ActiveEmployees U RetiredEmployees

2. Set difference

\(R1 - R2\)

• Tuples in R1, not in R2
• R1, R2, (R1 - R2) 각각과 동일한 schema를 공유한다.
  • i.e., ActiveEmployees - RetiredEmployees

3. Selection

\(\sigma_{c}(R)\)

• 선택할 tuples 특정 조건 만족
• c = a condition (i.e., =, <, >, and, or, not)
• Output schema = input schema

연봉 $40,000 이상은 모든 직원 검색: \(\sigma_\{Salary > 40000\} (Employee)\).

4. Projection

\(\prod_\{A1,…,An\}(R)\)

• Unary operation: returns certain columns
• Eliminates duplicate tuples
• Input schema \(R(B1,…,Bm)\).
• Condition: \(\{A1, …, An\} \subseteq \{B1, …, Bm\}\).
• Output schema \(S(A1,…,An)\).

Project social-security number and names:

5. Cartesian product (= Cross-product)

\(R1 X R2\)

• Each tuple in R1 with each tuple in R2
  • \(A=\{a,b\},\ B=\{1,2\}, AXB=\{a1,a2,b1,b2\}\).
• Input schemas: \(R1(A1,…,An), R2(B1,…,Bm)\).
• Condition: \(\{A1,…,An\} \cap \{B1,…Bm\} = \emptyset\).
• Output schema: \(S(A1, …, An, B1, …, Bm)\).
• Very rare in practice; but joins are very common

[Employee x Dependents]

한계점

상기 이미지는 서로 다른 두 그룹이 동일한 column를 포함하는 경우이다.

해당 경우, 동일한 column에 대해 collision이 발생한다.

따라서, 각 col에 대해 알맞게 이름 변경 필요한데, 이러한 한계점 해결하고자 Renaming이 도입되었다 (하기 참조).

Renaming

\(\rho_\{B1,…,Bn\}(R)\)

• relational instance 변경 X
• relational schema 변경 O
• Input schema: \(R(A1, …, An)\).
• Output schema: \(S(B1, …, Bn)\).

시험 출제 ★★★

1. 6가지 operator 기말고사 무조건 출제★★

2. 하기 형태 이해할 수 있어야 됨

\(\prod\sigma_\{A1,…,An\}(Employee)\).

---

Derived RA Operations 🎄

1. Intersection

\(R1 \cap R2\)

\[R1 \cap R2 = R1 – (R1 – R2)\]

• Difference: all tuples both in R1 and in R2
• R1, R2, \(R1 \cap R2\) must have the same schema

\[UnionizedEmployees \cap RetiredEmployees\]

2. Join (Most importantly)

특징

• JOIN은 서로 다른 3개 이상의 테이블이 존재할 때, 그들의 연관성을 유지하면서 selection할 때 굉장히 효율적이다.
• Extremely costly
• Derived operator

Theta join (= Condition join)

어느 operator 다 가능 (>=, ==, etc.)

중복 허용

\[R1 \infty_{\theta} R2, where\ \theta\ is\ a\ condition\]

• A join that involves a predicate
  • Cross-product 기반
• Input schemas: \(R1(A1,…,An),\ R2(B1,…,Bm)\).
• Condition: \(\{A1,…An\} \cap \{B1,…,Bm\} = \emptyset\).
• Output schema: \(S(A1,…,An,B1,…,Bm)\).

[Derived operator]

\[R1 \infty_\theta R2 = \sigma_\theta(R1 * R2)\]

Equi-join

theta join에서 operator가 ==인 경우

중복 허용

\[R1\ \infty_\{A=B\}R2\]

• Natural join = equi-join의 한 종류
  • Natural Join은 index column 중복 제거
• A lot of research on how to do it efficiently

Natural join

equi-join에서 중복 컬럼 제거한 경우

중복 제거

\[R1 \infty R2\]

• combine all pairs of tuples in R1 and R2 that agree on the attributes
• 같은 값 존재 x (모두 다 join condition 의해 합쳐짐)

\[\{A1,…,An\} \cap \{B1,…, Bm\} (called\ the\ join\ attributes)\]

• Input Schema: \(R1(A1, …, An), R2(B1, …, Bm)\).
• Output Schema: \(S(C1,…,Cp), where \{C1, …, Cp\} = \{A1, …, An\} \cup \{B1, …, Bm\}\). Equivalent to a cross product followed by selection

\[Employee\ \infty\ Dependents\]

시험 출제 ★★★★★★

시험에서 이런 식으로 expression 적게 될거임!!! ★★★★★★

Midterm에서는 SQL 직접 적었는데 FINAL 에서는 위 표현식으로 물어보는 문제 나옴

실습1

• Given the schemas R(A, B, C, D), S(A, C, E), what is the schema of R ∞ S?
• Given R(A, B, C), S(D, E), what is R ∞ S?
• Given R(A, B), S(A, B), what is R ∞ S?

다양한 실습

Find the names of sailors who have reserved a red boat.

Find the colors of boats reserved by Lubber

Find the names of sailors who have reserved at least one boat.

Find the names of sailors who have reserved a red or a green boat.

기타

• Semi-join
• Inner join
• Outer join
• etc.

해당 course에서는 안 다룸. 나중에 배워도 됨!

Division

Tuple Relational Calculus

\({ T | p(T) }\)

(Q11) Find all sailors with a rating above 7.

다음 시간에는 Relational Algebra에 대해 알아보자.

---

Reference

Database Management Systems by Raghu Ramakrishnan and Johannes Gehrke

Relational Operators