Terminology

Formal Definition of Relation

• $A_1, A_2, \dots, A_n$ 를 attributes.
• $D_1, D_2, \dots, D_n$ 를 attributes의 domains.
  • atomic이 요구된다.
• 주어진 집합 $D_1, D_2, \dots, D_n$ 에서 relation r는 $D_1\times D_2 \times \dots \times D_n$의 subset이다.
  • relation은 $n$ -tuples ($a_1, a_2, \dots, a_n$)의 집합이다.

Schema and Instance

• Database Schema: 데이터베이스의 논리 디자인

• Database Instance: 실제로 들어있는 값

• 주어진 attributes $A_1, A_2, \dots, A_n$ 의 relation schema는 다음과 같이 표현한다.

  • $r(A_1, A_2, \dots, A_n)$
  • e.g., instructor(ID, name, dept_name, salary)

• 현재 값들을 relation instance라고 한다.

Keys

• $K \subseteq R$ 라고 하자.

• K가 relation $R$ 의 superkey라는 것은, K의 값만으로 relation $r(R)$ 의 각 튜플(tuple)을 유일하게 식별할 수 있다는 뜻이다.

  • 예: {ID}와 {ID, name}은 모두 instructor의 superkey이다.

• Superkey K가 최소(minimal)라면, K를 candidate key라고 한다.

  • 즉, K에서 어떤 속성 하나라도 빼면 더 이상 튜플을 유일하게 식별할 수 없어야 한다.
  • 예: {ID}는 instructor의 candidate key이다.
    • {ID, name}은 superkey이긴 하지만, name을 빼도 {ID}만으로 충분하므로 candidate key는 아니다.

• Candidate key들 중 하나를 선택한 것이 primary key이다.

• Foreign key 제약조건:

  • 한 relation의 값이 다른 relation에도 반드시 존재해야 한다.
  • Referencing relation: 외래키를 가지고 있는 테이블
  • Referenced relation: 그 외래키가 참조하는 테이블

예를 들어:

student(student_id, name, dept_id)
department(dept_id, dept_name)

여기서 student.dept_id는 department.dept_id를 참조하는 foreign key이다.

• student = referencing relation
• department = referenced relation

즉, student에 있는 dept_id 값은 반드시 department 테이블에 실제로 존재해야 한다.

Relational Algebra

• Six basic operations
  • Select: $\sigma$
  • Project: $\Pi$
  • Union: $\cup$
  • Set difference: $-$
  • Cartesian product: $\times$
  • Rename: $\rho$

Select ($\sigma$)

Relation $r$

Select tuples with A = B and D > 5

Projection ($\Pi$)

Select columns.

Relation $r$
Select A and C

Cartesian Product ($\times$)

Relation $r, s$

Natural Join ($\bowtie$)

자연 조인(Natural Join)은 두 테이블에서 이름이 같은 속성(attribute)들을 기준으로 자동으로 조인하는 연산이야.

즉, r과 s라는 relation이 있을 때, 두 relation에 공통으로 존재하는 컬럼들 $R \cap S$ 의 값이 같은 행들만 합친다.

예를 들어

student(student_id, name, dept_id)
department(dept_id, dept_name)

student와 department 둘 다 dept_id라는 공통 컬럼을 가지고 있으므로

는 사실상

와 같은 뜻이다.

예를 들어 데이터가

student
+------------+-------+---------+
| student_id | name  | dept_id |
+------------+-------+---------+
| 1          | Kim   | CS      |
| 2          | Lee   | EE      |
+------------+-------+---------+

department
+---------+-----------+
| dept_id | dept_name |
+---------+-----------+
| CS      | Computer  |
| EE      | Electrical|
+---------+-----------+

이면 자연 조인 결과는

+------------+------+---------+-------------+
| student_id | name | dept_id | dept_name   |
+------------+------+---------+-------------+
| 1          | Kim  | CS      | Computer    |
| 2          | Lee  | EE      | Electrical  |
+------------+------+---------+-------------+

이렇게 된다.

중요한 점은

• 공통 컬럼 값이 같은 행만 남는다.
• 공통 컬럼(dept_id)은 결과에 한 번만 나타난다.
• 공통 컬럼 이름이 여러 개면, 그 모든 컬럼 값이 같아야 조인된다.

슬라이드의 말을 그대로 풀면:

1. r의 각 튜플 $t_r$ , s의 각 튜플 $t_s$ 를 하나씩 비교한다.
2. 공통 속성 $R \cap S$ 들의 값이 모두 같으면
3. 두 튜플을 합쳐서 새로운 튜플 $t$ 를 결과에 넣는다.

Natural Join and Theta Join

첫 번째 식

Π_{name, title} ( σ_{dept_name="Comp. Sci."} ( instructor ⋈ teaches ⋈ course ) )

의 의미는 다음과 같다.

1. instructor ⋈ teaches ⋈ course

   • instructor, teaches, course relation을 자연 조인한다.
   • 결과적으로 어떤 교수가 어떤 과목을 가르치는지, 그리고 그 과목의 제목이 무엇인지에 대한 정보가 하나의 relation으로 합쳐진다.

2. σ_{dept_name="Comp. Sci."}

   • 그 중에서 dept_name이 "Comp. Sci."인 튜플만 선택한다.
   • 즉, 컴퓨터공학과 소속 교수만 남긴다.

3. Π_{name, title}

   • 마지막으로 교수 이름(name)과 과목 제목(title)만 출력한다.

따라서 전체 식은 “컴퓨터공학과 교수들의 이름과 그들이 가르치는 과목 제목”을 구하는 연산이다.

예를 들어 결과는 다음과 같을 수 있다.

+------+----------------+
| name | title          |
+------+----------------+
| Kim  | Database       |
| Kim  | Operating Sys. |
| Lee  | AI             |
+------+----------------+

또한 자연 조인에는 다음과 같은 성질이 있다.

• 결합법칙(associative)

(instructor ⋈ teaches) ⋈ course
=
instructor ⋈ (teaches ⋈ course)

즉, 먼저 instructor와 teaches를 조인한 뒤 course를 조인하든, 먼저 teaches와 course를 조인한 뒤 instructor를 조인하든 결과는 동일하다.

• 교환법칙(commutative)

instructor ⋈ teaches
=
teaches ⋈ instructor

즉, 조인의 순서를 바꾸어도 결과는 동일하다.

마지막으로 theta join((\bowtie_\theta))은 자연 조인보다 일반적인 조인이다.

r ⋈_θ s = σ_θ (r × s)

의 의미는 다음과 같다.

1. 먼저 (r \times s) 를 수행하여 r과 s의 모든 튜플 조합을 만든다.
2. 그 중에서 조건 (\theta)를 만족하는 튜플만 선택한다.

예를 들어

student \bowtie_{student.dept\_id = department.dept\_id} department

은

\sigma_{student.dept\_id = department.dept\_id}(student \times department)

와 동일한 의미이다.

자연 조인은 “이름이 같은 속성들에 대해 자동으로 equality 조건을 적용하는 특별한 theta join”이라고 볼 수 있다.