資料庫作業五

• 姓名：張議隆
• 學號：F74082125

TOC

• 資料庫作業五
  • 15.19
    • Database schema design
    • Functional dependencies
  • 15.24
  • 15.27
  • 21.23
    • S1
    • S2

15.19

Suppose we have the following requirements for a university database that is used to keep track of students’ transcripts:

a. The university keeps track of each student's name (Sname), student number (Snum), social security number (Ssn), current address (Sc_addr) and phone (Sc_phone), permanent address (Sp_addr) and phone (Sp_phone), birth date (Bdate), sex (Sex), class (Class) (freshman, sophomore, …, graduate), major department (Major_code), minor department (Minor_code) (if any), and degree program (Prog) (‘b.a.’, ‘b.s.’, …, ‘ph.d.’). Both Ssn and student number have unique values for each student.

b. Each department is described by a name (Dname), department code (Dcode), office number (Doffice), office phone (Dphone), and college (Dcollege). Both name and code have unique values for each department.

c. Each course has a course name (Cname), description (Cdesc), course number (Cnum), number of semester hours (Credit), level (Level), and offering department (Cdept). The course number is unique for each course.

d. Each section has an instructor (Iname), semester (Semester), year (Year), course (Sec_course), and section number (Sec_num). The section number distinguishes different sections of the same course that are taught during the same semester/year; its values are 1, 2, 3, …, up to the total number of sections taught during each semester.

e. A grade record refers to a student (Ssn), a particular section, and a grade (Grade).

Design a relational database schema for this database application. First show all the functional dependencies that should hold among the attributes. Then, design relation schemas for the database that are each in 3NF or BCNF. Specify the key attributes of each relation. Note any unspecified requirements, and make appropriate assumptions to render the specification complete.

Database schema design

• STUDENT

Sname	Snum	Ssn	Bdate	Sex

• CURRENT_ADDRESS

Snum	Sc_addr	Sc_phone

• PERNAMENT_ADDRESS

Snum	Sp_addr	Sp_phone

• DEGREE

Snum	Class	Major_code	Minor_code	Prog

• DEPARTMENT

Dname	Dcode	Doffice	Dphone	Dcollege

• COURSE

Cname	Cdesc	Cnum	Credit	Level	Cdept

• SECTION

Iname	Semester	Year	Sec_course	Sec_num

• GRADE

Serial_no	Ssn	Sec_num	Grade

我把地址、學位狀況從學生基本資料中拆出來並加上 Snum，讓 STUDENT 可以比較乾淨。
GRADE 內在題目的敘述內會找不到 key attribute，因此補上流水號(Serial_no)作為 key attribute。

Functional dependencies

STUDENT 的 Snum

$\to$ CURRENT_ADDRESS 的 Snum
STUDENT 的 Snum

$\to$ PERNAMENT_ADDRESS 的 Snum
STUDENT 的 Snum

$\to$ DEGREE 的 Snum
DEPARTMENT 的 Dcode

$\to$ COURSE 的 Cdept
COURSE 的 Cnum

$\to$ SECTION 的 Sec_course
SECTION 的 Sec_num

$\to$ GRADE 的 Sec_num
STUDENT 的 Ssn

$\to$ GRAGE 的 Ssn

我這個設計已經同時達成 3NF 以及 BCNF 的要求，因此不再另外提供對應要求的設計。

schema design 的呈現方式是以表格的形式，在 hackmd 上面要生成只有一行的表格只能使用 header 欄位，因此字體皆變成粗體。
如果使用一般的 body 欄位，呈現方式會變成以下：

Sname	Snum	Ssn	Bdate	Sex

我認為多一行空格不太美觀，因此最後採用皆為粗體的形式。

15.24

Consider the universal relation

$R=A,B,C,D,E,F,G,H,I$ and the set of functional dependencies F = { {A, B}

$\to$ {C}, {A}

$\to$ {D, E}, {B}

$\to$ {F}, {F}

$\to$ {G, H}, {D}

$\to$ {I, J} }. What is the key for R? Decompose R into 2NF, then 3NF relations.

R 的 key 為

$A,B,D,F$
轉成 2NF 為以下內容：
{A, B}

$\to$ {C} (我很像沒辦法刪除 A 或是 B，除非有更多的內容可以讓我了解是否可以刪除)
{A}

$\to$ {D}
{A}

$\to$ {E}
{B}

$\to$ {F}
{F}

$\to$ {G}
{F}

$\to$ {H}
{D}

$\to$ {I}
{D}

$\to$ {J}

再將上述內容轉成 3NF:
{A, B}

$\to$ {C}
{A}

$\to$ {I}
{A}

$\to$ {J}
{B}

$\to$ {G}
{B}

$\to$ {H}
做完以上整理後最後得到 primary key 為

$A,B$

15.27

Consider a relation

$R(A,B,C,D,E)$ with the following dependencies:

$AB\to C,CD\to E,DE\to B$

Is

$AB$ a candidate key of this relation? If not, is

$ABD$? Explain your answer.

我在 stack overflow 上面找到一個很有趣的解法，我想要嘗試拿來使用解這個問題：
一開始將所有 attribute 都選起來 (

$ABCDE$ )

• 有
  $AB\to C$，因此可以改為
  $ABDE$
• 有
  $CD\to E$，因此可以改為
  $ABCD$
• 有
  $DE\to B$，因此可以改為
  $ACDE$
• 有
  $AB\to C$ 取得
  $C$ 和
  $CD\to E$，因此可以改為
  $ABD$
• 有
  $DE\to B$ 取得
  $B$ 和
  $AB\to C$，因此可以改為
  $ADE$
• 有
  $CD\to E$ 取得
  $E$ 和
  $DE\to B$，因此可以改為
  $ACD$

因此 Cadidate key 總共有三種，

$ABD$、

$ADE$ 和

$ACD$。

$AB$ 不是 Candidate key，而

$ABD$ 是 Candidate key

stack overflow 的這篇也有提到，不存在於箭頭右邊的必然包含在 Candidate key 裡面。
以這題為例，由於

$A$ 和

$D$ 都沒出現在箭頭右邊，因此這兩個永遠都包含在 Candidate key 裡面。

21.23

Consider the three transactions T1, T2, and T3, and the schedules S1 and S2 given below. Draw the serializibility (precedence) graphs for S1 and S2 and state whether each schedule is serializable or not. If a schedule is serializable, write down the equivalent serial schedule(s).

• T1: r1(X); r1(Z); w1(X);
• T2: r2(Z); r2(Y); w2(Z); w2(Y);
• T3: r3(X); r3(Y); w3(Y);
• S1: r1(X); r2(Z); r1(Z); r3(X); r3(Y); w1(X); w3(Y); r2(Y); w2(Z); w2(Y);
• S2: r1(X); r2(Z); r3(X); r1(Z); r2(Y); r3(Y); w1(X); w2(Z); w3(Y); w2(Y);

我的回答參照 testbook 的作法以及 GeeksforGeeks 的解釋：

S1

T1	T2	T3
Read(X)
	Read(Z)
Read(Z)
		Read(X)
		Read(Y)
Write(X)
		Write(Y)
	Read(Y)
	Write(Z)
	Write(Y)

S1 is serializable(no cycle).
equivalent serial schedule: T3 -> T1 -> T2

S2

T1	T2	T3
Read(X)
	Read(Z)
		Read(X)
Read(Z)
	Read(Y)
		Read(Y)
Write(X)
	Write(Z)
		Write(Y)
	Write(Y)

S2 is not serializable.
There are two cycles:

1. T3 -> T2 -> T3
2. T3 -> T1 -> T2 -> T3

serializibility (precedence) graphs 也是透過 graphviz 這個套件繪製，但是相較於上次作業的圖形好看很多。
物件數量會嚴重影響圖形的可讀性，這個部份我也難以解決。

tags: 1112_courses database