2. Relational Model

Relational Database and Relational Model

• Relational Database(관계형 데이터베이스)는 "Tables"의 모음
• Relational Model(관계형 모델)에서
  • "Relation"이라는 용어는 table을 지칭하는 데 사용
  • "Tuple"이라는 용어는 table의 row(행)를 지칭하는 데 사용
  • "Attribute(속성)"라는 용어는 table의 column(열)을 지칭하는 데 사용

Relation Schema and Instance

• $A_1, A_2, ..., A_n$은 attributes
• $R = (A_1, A_2, ..., A_n)$은 relation schema(관계 스키마)
• 예: instructor = (ID, name, dept_name, salary)
• schema $R$에 대해 정의된 relation instance(관계 인스턴스) $r$은 $r(R)$로 표기
• relation의 현재 값들은 table에 의해 명시

Attributes

• 각 attribute에 허용되는 값들의 집합을 해당 attribute의 domain이라 칭함
• Attribute 값들은 (보통) atomic(원자성), 즉 분해 불가능해야 함
• Atomicity는 데이터베이스에서 domain 요소를 어떻게 사용하느냐에 따라 달라짐
• 예: Phone number = country code + area code + local number
  • 데이터베이스에서 각 코드/번호를 개별적으로 사용하면 atomic하지 않게 됨
  • 전체 전화번호를 그대로 사용하면 atomic함
• 특수 값 null은 모든 domain의 멤버
  • 값이 알 수 없음을 나타냄
  • null 값은 많은 연산의 정의에서 복잡성을 야기함

Relations are Unordered

• Relation은 tuple들의 'set'(집합)
• Tuple의 순서는 무관 (tuple은 임의의 순서로 저장될 수 있음)
• 예: 순서 없는 tuple을 가진 instructor relation

Database Schema

• Database schema(데이터베이스 스키마):
  • 데이터베이스의 논리적 구조, relation schemas의 집합
• Database instance(데이터베이스 인스턴스):
  • 주어진 특정 시점의 데이터베이스 data snapshot
• 예: University database
• Database schema:
  • instructor(ID, name, dept_name, salary)
  • department(dept_name, building, budget)
  • course(course_id, title, dept_name, credits)
  • section(course_id, sec_id, semester, year, building, room_number, time_slot_id)
  • prereq(course_id, prereq_id)
  • teaches(ID, course_id, sec_id, semester, year)
  • student(ID, name, dept_name, tot_cred)
  • adviser(s_id, i_id)
  • takes(ID, course_id, sec_id, semester, year, grade)
  • classroom(building, room_number, capacity)
  • time_slot(time_slot_id, day, start_time, end_time)

Keys: Superkey, Candidate Key and Primary Key

• $K \subseteq R$ (relation schema $R$의 attribute의 부분집합)라고 가정
• 만약 $K$의 값들이 각 가능한 relation instance $r(R)$의 고유한 tuple을 식별하기에 충분하다면, $K$는 $R$의 superkey임.
• 예: {ID}와 {ID, name}은 모두 instructor의 superkey
• Superkey $K$는 $K$가 minimal할 때 candidate key(후보 키)임
• 예: {ID}는 Instructor의 candidate key이지만, {ID, name}은 아님
• Candidate keys 중 하나가 primary key(기본 키)로 선택됨
• Attribute 값들이 절대 또는 거의 변경되지 않도록 선택되어야 함
• 여권의 영문 이름을 바꾸기 어려운 이유?
  • 한국에서는 모든 국민이 고유 ID 번호(주민등록번호)를 가지고 있어 이름이 데이터베이스의 key로 사용되지 않음
  • 그러나 외국에서는 종종 (이름, 생년월일) 쌍으로 각 개인을 식별 (즉, 이러한 쌍이 데이터베이스에서 key로 사용됨)
  • 여권의 영문 이름을 변경하는 것은 다른 나라의 출입국 데이터베이스에서 key 값을 변경해야 할 수 있는 것이며, 당연히 이는 쉽게 받아들여지지 않음

Keys: Foreign Key

• Foreign key constraint(외래 키 제약 조건):
  • Relation $r_1$의 attribute(들) $A$에서 relation $r_2$의 primary key $B$로
  • 어떤 database instance에서도, $r_1$의 각 tuple에 대한 $A$의 값은 $r_2$의 어떤 tuple에 대한 $B$의 값이기도 해야 함을 명시
  • 즉, 한 relation의 값들이 다른 relation에 나타나야 함
• Attribute(들) $A$는 $r_2$를 참조하는 $r_1$의 foreign key라 불림
• $r_1$은 foreign key constraint의 referencing relation(참조하는 관계)이라 불림
• $r_2$는 referenced relation(참조되는 관계)이라 불림
• 예:
  • instructor의 dept_name은 department를 참조하는 instructor의 foreign key
• Referential integrity constraint(참조 무결성 제약 조건):
  • Referencing relation의 어떤 tuple의 명시된 attributes에 나타나는 값들은 referenced relation의 최소 한 tuple의 명시된 attributes(반드시 primary key가 아닐 수 있음)에도 나타남
  • Foreign key constraint의 일반화된 버전

Schema Diagram (for University Database)

• 밑줄 친 attributes는 relation의 Primary-key
• ID는 student를 참조하는 takes의 foreign key
• 네 개의 attributes를 가진 foreign key

Relational Query Languages

• Procedural(절차적) vs non-procedural(비절차적) or declarative(선언적)
• "Pure" languages:
  • Relational algebra(관계 대수) (procedural)
  • Tuple relational calculus(튜플 관계 해석) (non-procedural)
  • Domain relational calculus(도메인 관계 해석) (non-procedural)
• 위 3개의 pure languages는 계산 능력 면에서 동등
• 이 장에서는 relational algebra에 집중할 것임
• Turing-machine equivalent가 아님
• 6개의 기본 연산으로 구성

Relational Algebra

• 하나 또는 두 개의 relations를 입력으로 받고, 새로운 relation을 결과로 생성하는 연산들의 집합으로 구성된 procedural language
• 여섯 가지 기본 연산자:
  • select: $\sigma$
  • project: $\Pi$
  • union: $\cup$
  • set difference: $-$
  • Cartesian product: $\times$
  • rename: $\rho$

Select Operation

• Select 연산은 주어진 predicate(술어)를 만족하는 tuple들을 선택
• 표기법: $\sigma_p(r)$
• $p$는 selection predicate이라 불림
• 예:
  • instructor relation에서 Physics department에 속한 instructor들의 tuple을 선택
  • Query: $\sigma_\text{dept\_name="Physics"} (\text{instructor})$
• Selection predicate에서 $=, \neq, >, \geq, <, \leq$를 사용한 비교 허용
• 여러 predicate를 connective(접속사) $\land$(and), $\lor$(or), $\neg$(not)를 사용하여 더 큰 predicate로 결합 가능
• 예:
  • 급여가 $90,000 이상인 Physics 소속 instructor 찾기: $\sigma_{\text{dept\_name="Physics"} ~\land ~\text{salary} > 90000}(\text{instructor})$
• Select predicate는 두 attribute 간의 비교를 포함할 수 있음
• 예: 이름이 building name과 같은 모든 department 찾기:
  • $\sigma_{\text{dept\_name=building}} (\text{department})$
  • department=(dept_name, building, budget)

Project Operation

• 특정 attributes를 제외하고 argument relation을 반환하는 단항 연산
• 표기법: $\Pi_{A_1, A_2, A_3, ..., A_k}(r)$
  • 여기서 $A_1, A_2, ..., A_k$는 attribute 이름이고 $r$은 relation 이름
• 결과는 나열되지 않은 column들을 지워서 얻어지는 k개의 column을 가진 relation으로 정의됨
• Relation은 집합이므로 중복된 row는 결과에서 제거됨

Project Operation Example

• 예: instructor의 dept_name attribute 제거
• Query: $\Pi_\text{ID, name, salary}(\text{instructor})$

Composition of Relational Operations

• Relational-algebra 연산의 결과는 relation이므로, relational-algebra 연산들은 relational-algebra expression(관계 대수 표현식)으로 함께 구성될 수 있음
• Query 고려:
  • Physics department의 모든 instructor 이름 찾기: $\Pi_{name}(\sigma_\text{dept\_name="Physics"}(\text{instructor}))$
• Projection 연산의 인자로 relation name을 주는 대신에, relation으로 evaluate되는 표현식을 제공

Cartesian-Product Operation

• Cartesian-product 연산($\times$로 표기)은 임의의 두 relation의 정보를 결합하게 함
• 예: instructor와 teaches relations의 Cartesian product는 다음과 같이 작성: instructor $\times$ teaches
• instructor relation의 각 tuple과 teaches relation의 각 tuple의 가능한 모든 쌍의 조합이 결과의 tuple이 됨
• instructor.ID가 두 relation 모두에 나타나므로, attribute가 원래 속했던 relation의 이름을 붙여 이 attribute들을 구별
  • instructor.ID
  • teaches.ID

The instructor $\times$ teaches table

• 이 tuple은 관련 없는 데이터 항목들을 결합
• Srinivasan 교수는 2017년 가을 학기에 PHY-101 과목을 가르친 적이 없음

Join Operation

• Cartesian-Product instructor $\times$ teaches는 instructor의 모든 tuple들을 teaches의 모든 tuple들과 연관시킴
• 결과로 나오는 대부분의 row는 특정 과목을 가르치지 않은 (즉, 무관한) instructor에 대한 정보를 가지게 됨
• Instructor와 그들이 가르친 과목에 진짜 관련된 "instructor $\times$ teaches"의 tuple들만 얻기 위해서는:

$$\sigma_\text{instructor.id = teaches.id}(\text{instructor} \times \text{teaches})$$

• Instructor와 그들이 가르친 과목에 관련된 "instructor $\times$ teaches"의 tuple들만 얻게 됨
• $\sigma_\text{instructor.id = teaches.id}(\text{instructor} \times \text{teaches})$에 해당하는 table
• 결과는 데이터 항목들이 서로 관련된 tuple들만 포함
• 예: EE 학과의 Kim 교수는 2017년 봄 학기에 EE-181 과목을 가르침

Natural-Join Operation

• 표기법: $r \bowtie s$
• $r$과 $s$를 각각 schema $R$과 $S$ 위의 relation이라 가정. 결과는 schema $R \cup S$ 위의 relation이며, $r$의 각 tuple $t_r$과 $s$의 각 tuple $t_s$를 고려하여 얻어짐
• 만약 $t_r$과 $t_s$가 $R \cap S$의 각 attribute에서 동일한 값을 가지면, 결과에 tuple $t$가 추가됨, 여기서
  • $t$는 $r$에서 $t_r$과 동일한 값을 가짐
  • $t$는 $s$에서 $t_s$와 동일한 값을 가짐
• 예:
  • $R= (A, B, C, D)$
  • $S= (E, B, D)$
  • 결과 스키마 $= (A, B, C, D, E)$
  • $r \bowtie s$는 다음과 같이 정의됨:

$$\Pi_{A, r.B, C, r.D, E}(\sigma_{r.B = s.B \land r.D = s.D}(r \times s))$$

Natural Join Operation – Example

• Relations $r$, $s$와 그들의 natural join $r \bowtie s$
  (그림 생략)

Natural Join의 속성

• $\Pi_{A_1, ..., A_k}(r) \cap \Pi_{A_1, ..., A_k}(s) = \Pi_{A_1, ..., A_k}(r \bowtie s)$
  • ($A_1, ..., A_k$: 공통 attributes)
• $(r \bowtie s) \bowtie t = r \bowtie (s \bowtie t)$: associative(결합법칙) 성립
• 만약 $R \cap S = \emptyset$ 이면 $r \bowtie s = r \times s$ (중요! $r \bowtie s \neq \emptyset$)
• 만약 $R = S$ 이면, $r \bowtie s = r \cap s$

Theta Join

• Theta join 연산은 select 연산과 Cartesian-Product 연산을 단일 연산으로 결합하게 함
• Relations $r(R)$과 $s(S)$에 대해서
• "theta($\theta$)"를 스키마 $R \cup S$의 attributes에 대한 predicate라 가정. Join 연산 $r \bowtie_\theta s$는 다음과 같이 정의됨: $r \bowtie_\theta s = \sigma_\theta(r \times s)$
• 따라서 $\sigma_\text{instructor.id = teaches.id}(\text{instructor} \times \text{teaches})$는 다음과 동등하게 작성될 수 있음:

$$\text{instructor} \bowtie_\text{Instructor.id = teaches.id} \text{teaches}$$

Union Operation

• Union(합집합) 연산은 두 relation을 결합하게 함
• 표기법: $r \cup s$
• $r \cup s$가 유효하기 위해:
  1. $r, s$는 동일한 arity(동일한 수의 attributes)를 가져야 함
  2. Attribute domains는 호환 가능해야 함 (예: $r$의 두 번째 column은 $s$의 두 번째 column과 같은 유형의 값을 다룸)
• 예:
  • 2017년 가을 학기, 또는 2018년 봄 학기, 또는 두 학기 모두에 개설된 모든 과목의 ID 찾기:

$$\Pi_\text{course\_id}(\sigma_{\text{semester}="Fall" \land \text{year}=2017}(\text{section})) \cup \Pi_\text{course\_id}(\sigma_{\text{semester}="Spring" \land \text{year}=2018}(\text{section}))$$

• section relation의 schema: section (course_id, sec_id, semester, year, building, room_number, time_slot_id)

Set-Intersection Operation

• Set-intersection(교집합) 연산: 두 입력 relation 모두에 있는, 공통된 tuple을 반환함
• 표기법: $r \cap s$
• 가정:
  1. $r$과 $s$는 동일한 arity를 가짐
  2. $r$과 $s$의 attributes는 호환 가능함
• 예: 2017년 가을과 2018년 봄 학기 모두에 개설된 모든 과목의 집합 찾기:

$$\Pi_\text{course\_id}(\sigma_{semester="Fall" \land year=2017}(\text{section})) \cap \Pi_\text{course\_id}(\sigma_{semester="Spring" \land year=2018}(\text{section}))$$

Set Difference Operation

• Set-difference(차집합) 연산: 한 relation에는 있지만 다른 relation에는 없는 tuple을 반환함
• 표기법: $r - s$
• Set differences는 호환 가능한 relations 사이에서 수행되어야 함
  1. $r$과 $s$는 동일한 arity를 가져야 함
  2. $r$과 $s$의 attribute domains는 호환 가능해야 함
• 예:
  • 2017년 가을 학기에는 개설되었지만 2018년 봄 학기에는 개설되지 않은 모든 과목 찾기:

$$\Pi_{course\_id}(\sigma_{semester="Fall" \land year=2017}(section)) - \Pi_{course\_id}(\sigma_{semester="Spring" \land year=2018}(section))$$

The Assignment Operation

• 때로는 relational-algebra expression의 일부를 임시 relation 변수에 할당하여 작성하는 것이 편리함
• Assignment(할당) 연산은 $\leftarrow$로 표기되며 프로그래밍 언어의 할당처럼 작동
• 예: "Physics"와 "Music" department의 모든 instructor 찾기
  • Physics $\leftarrow \sigma_{dept\_name="Physics"}(instructor)$
  • Music $\leftarrow \sigma_{dept\_name="Music"}(instructor)$
  • Physics $\cup$ Music
• Assignment 연산 없는 동일한 expression:

$$\sigma_{dept\_name="Physics"}(instructor) \cup \sigma_{dept\_name="Music"}(instructor)$$

• Assignment 연산을 사용하면 query를 일련의 assign과 그 결과가 query의 결과로 표시되는 expression으로 구성된 순차적 프로그램으로 작성할 수 있음

The Rename Operation

• Relational-algebra expressions의 결과는 참조하는 데 사용할 수 있는 이름이 없음
• Rename(이름 변경) 연산자, $\rho$가 그 목적으로 제공됨
• Expression: $\rho_x(E)$는 expression $E$의 결과를 $x$라는 이름으로 반환
• Attributes 이름도 다음과 같이 할당 가능: $\rho_{x(A_1,A_2, .. An)} (E)$

Equivalent(동등한) Queries

• Relational algebra에서 query를 작성하는 방법은 하나 이상 존재
• 예: 급여가 90,000보다 많은 Physics department의 instructor에 대한 정보 찾기
  • Query 1: $\sigma_{dept\_name="Physics" \land salary > 90000}(instructor)$
  • Query 2: $\sigma_{dept\_name="Physics"}(\sigma_{salary > 90000}(instructor))$
• 예: Physics department의 instructor가 가르치는 과목에 대한 정보 찾기
  • Query 1: $\sigma_{dept\_name="Physics"}(instructor \bowtie_{instructor.ID = teaches.ID} teaches)$
  • Query 2: $(\sigma_{dept\_name="Physics"}(instructor)) \bowtie_{instructor.ID = teaches.ID} teaches$
• 두 query는 동일하지는 않지만, 동등함
  • 어떤 데이터베이스에서도 동일한 결과를 제공하기 때문.

Modification of the Database

• 데이터베이스의 내용은 다음 연산들을 사용하여 수정될 수 있음:
  • Deletion
  • Insertion
  • Updating
• 이 모든 연산은 assignment 연산자를 사용하여 표현됨

Deletion

• Delete(삭제) 요청은 query와 유사하게 표현되지만, 사용자에게 tuple을 표시하는 대신 선택된 tuple이 데이터베이스에서 제거됨
• 전체 tuple만 삭제 가능. 특정 attributes의 값만 삭제 불가
• Deletion은 relational algebra에서 다음과 같이 표현됨: $r \leftarrow r - E$
  • 여기서 $r$은 relation이고 $E$는 relational algebra query
• 예:
  • Perryridge 지점의 모든 계좌 기록 삭제: $\text{account} \leftarrow \text{account} - \sigma_{branch-name = "Perryridge"}(\text{account})$
  • 금액이 0에서 50 사이인 모든 대출 기록 삭제: $\text{loan} \leftarrow \text{loan} - \sigma_{amount \geq 0 \land amount \leq 50}(\text{loan})$

Insertion

• Relation에 데이터를 삽입하기 위해:
  • 삽입할 tuple을 명시하거나
  • 결과가 삽입될 tuple들의 집합인 query를 작성
• Relational algebra에서 insertion은 다음과 같이 표현됨: $r \leftarrow r \cup E$
  • 여기서 $r$은 relation이고 $E$는 relational algebra expression
• 단일 tuple의 삽입은 $E$를 하나의 tuple을 포함하는 상수 relation으로 하여 표현됨
• 예:
  • Smith가 Perryridge 지점의 A-973 계좌에 $1200를 가지고 있다는 정보를 데이터베이스에 삽입
  • $\text{account} \leftarrow \text{account} \cup \text{("Perryridge", A-973, 1200)}$
  • $\text{depositor} \leftarrow \text{depositor} \cup \text{("Smith", A-973)}$

Updating

• Tuple의 모든 값을 변경하지 않고 tuple의 값을 변경하는 메커니즘
• 이 작업을 수행하기 위해 generalized projection operator(일반화된 프로젝션 연산자)를 사용
• $r \leftarrow \Pi_{F_1, F_2, ..., F_n}(r)$
• 각 $F_i$는,
  • i번째 attribute가 업데이트되지 않으면 $r$의 i번째 attribute이거나,
  • 만약 attribute가 업데이트되어야 한다면, $F_i$는 상수와 $r$의 attributes만을 포함하는 expression으로, attribute의 새로운 값을 제공
• 예:
  • 모든 잔액을 5% 증가시켜 이자 지급하기

    $$\text{account} \leftarrow \Pi_\text{AN, BN, BAL - 1.05}(\text{account})$$

  • 여기서 AN, BN, BAL은 각각 account-number, branch-name, balance를 의미