Bài giảng Thiết kế cơ sở dữ liệu: Chương 2

ĐH CÔNG NGHỆ THÔNG TIN

http://sites.google.com/site/khaiphong

Số tiết lý thuyết: 45 tiết Số tiết thực hành: 30 tiết GVHD: Dương Khai Phong – Email khaiphong@gmail.com

http://sites.google.com/site/khaiphong

 Nội dung môn học:

 Chương 1: Giới thiệu tổng quan

 Chương 2: Mô hình dữ liệu và các phụ thuộc dữ liệu

 Chương 3: Phương pháp chuẩn hóa Lược đồ CSDL

 Chương 4: Lý thuyết đồ thị quan hệ

 Chương 5: Thiết kế CSDL ở mức vật lý

2 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu

Các phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu (ôn)

Phụ thuộc hàm

Hệ tiên đề Amstrong

Bài toán tìm khóa và Bài toán PTH

3 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

Xét bài toán: quản lý lịch dạy của các giáo viên và lịch học của các lớp, một trường tổ chức như sau: Mỗi giáo viên có một mã số duy nhất, trường sẽ tổ chức lưu thông tin các giáo viên bao gồm: họ và tên giáo viên, số điện thoại gồm 10 số. Mỗi giáo viên có thể dạy nhiều môn cho nhiều khoa nhưng chỉ thuộc sự quản lý hành chánh của một khoa nào đó.

1. Thuộc tính?

2. Quan hệ?

3. Khóa?

4. Bộ - Phép chiếu?

4 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

1. Thuộc tính

3. Khóa

2. Quan hệ

4. Bộ - Phép chiếu

5 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

Xét bài toán: quản lý lịch dạy của các giáo viên và lịch học của các lớp, một trường tổ chức như sau: Mỗi giáo viên có một mã số duy nhất, trường sẽ tổ chức lưu thông tin các giáo viên bao gồm: họ và tên giáo viên, số điện thoại gồm 10 số. Mỗi giáo viên có thể dạy nhiều môn cho nhiều khoa nhưng chỉ thuộc sự quản lý hành chánh của một khoa nào đó.

Thuộc tính

Quan hệ

6 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

GV01

Nguyen A

123

CSDL

HTTT

GV02

Tran

456

THĐC

CNPM

MAGV HO TEN SODT TENMH TENKHOA

GV02 Le C 789 Mạng MMT

GV01 Nguyen A 123 TKCSDL HTTT

- Tên gọi (ví dụ TenSV, TenGV,..) - Kiểu dữ liệu (Type): số, văn bản, Boolean... - Miền giá trị (Domain): Ký hiệu MGT(A)

1. Thuộc tính (Attribute) là thông tin đặc thù của mỗi đối tượng được quản lý - Thuộc tính đươc xác đỉnh bởi:

7 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

GV01

Nguyen A

123

CSDL

HTTT

GV02

Tran

456

THĐC

CNPM

MAGV HO TEN SODT TENMH TENKHOA

GV02 Le C 789 Mạng MMT

GV01 Nguyen A 123 TKCSDL HTTT

- Ký hiệu: Q(A1, A2, .. , An) - Ký hiệu: Q+ dùng biểu diễn tập thuộc tính {A1, A2, .. , An} - Mỗi quan hệ Q đều kèm theo một tân từ IIQII dùng để mô tả mối liên hệ ngữ nghĩa của các thuộc tính trong Q.

2. Quan hệ (Relation) Một quan hệ Q được định nghĩa trên một tập thuộc tính {A1, A2, .. , An} là một sự biểu diễn tập đối tượng cớ chung các thuộc tính.

Ví du: KetOuaHTYMSSV. MSMon. HocKy, DiemLl, DiemL2) Tân từ: Mỗi môn học (MSMon) trong một học kỳ (HocKy) sinh viên (MSSV) được thi tối đa 2 lần (DiemLl, DiemL2).

8 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

GV01

Nguyen A

123

CSDL

HTTT

GV02

Tran

456

THĐC

CNPM

MAGV HO TEN SODT TENMH TENKHOA

GV02 Le C 789 Mạng MMT

GV01 Nguyen A 123 TKCSDL HTTT

3. Bộ (Tuple) Một bộ q của quan hệ Q(A1, A2,..,An) là một tổ hợp giá trị (a1, a2,..,an) thoả 2 điều kiện:

(1) Ai  Q+, ai  MGT(Ai) (2) Tân từ IIQ(a1, a2,..,an) II phải được thoả

Ví dụ: quan hệ GIAOVIEN thì có các bộ

q1=(GV01, Nguyen, A, 123, CSDL, HTTT)

* Thể hiện (instance) của quan hệ Q, ký hiệu TQ, là một tập các bộ của Q TQ = { q= (a1, a2,..,an) / ai  MGT(Ai), IIQ(q)ll = TRUE }

9 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

GV01

Nguyen A

123

CSDL

HTTT

GV02

Tran

456

THĐC

CNPM

MAGV HO TEN SODT TENMH TENKHOA

GV02 Le C 789 Mạng MMT

GV01 Nguyen A 123 TKCSDL HTTT

 q1, q2  TQ, q1.S = q2.S thì q1 = q2

4. Siêu khóa (Super key): siêu khóa trên quan hệ Q là một tập thuộc tính S  Q+ nếu mỗi giá trị của S có thể xác định duy nhất một bộ của Q

* Khóa chỉ định (Candidate Key): hay khóa nội của Q là một siêu khóa ít thuộc

tính nhất, không chứa bất kỳ một siêu khóa nào.

* Thuộc tính khóa và thuộc tính không khóa: các thuộc tính tham gia vào khóa gọi là thuộc tính khóa, các thuộc tính không tham gia vào khóa gọi là các thuộc tính không khóa.

10 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

GV01

Nguyen A

123

CSDL

HTTT

GV02

Tran

456

THĐC

CNPM

MAGV HO TEN SODT TENMH TENKHOA

GV02 Le C 789 Mạng MMT

GV01 Nguyen A 123 TKCSDL HTTT

 q1, q2  TQ, q1.S = q2.S thì q1 = q2

4. Siêu khóa (Super key): siêu khóa trên quan hệ Q là một tập thuộc tính S  Q+ nếu mỗi giá trị của S có thể xác định duy nhất một bộ của Q

* Khóa chỉ định (Candidate Key): hay khóa nội của Q là một siêu khóa ít thuộc

tính nhất, không chứa bất kỳ một siêu khóa nào.

11 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu

DATABASE

𝑡

trị tương ứng với tập thuộc tính X

 Một CSDL là 1 tập hợp các quan hệ, Ký hiệu: 𝑐 = {𝑄𝑖}𝑖=1  Phép chiếu của một bộ q lên tập thuộc tính X  Q+ là phép trích ra từ bộ q các giá

Ký hiẽu: q.x hay q[X] Ví dụ: q.[MAGV, TEN, TENMH] = {(GV01,A,CSDL), (GV02,B,THĐC),…}

 Chiếu một quan hệ Q lên tập thuộc tính X  Q+ sẽ tạo thành một quan hệ Q' có

Ký hiệu: x(Q) hay Q[X].

tập thuộc tính X và TQ'={q' / q  TQ q.X = q'}

12 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu

Các phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu (ôn)

Phụ thuộc hàm

Hệ tiên đề Amstrong

Bài toán tìm khóa và Bài toán PTH

13 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Phụ thuộc hàm

1. Xét bài toán: quản lý lịch bay các chuyến bay như sau

PhanCong PHICONG MAYBAY NGAYKH GIOKH

Cushing Cushing Clark Clark Clark Chin Chin Copely Copely Copely

83 116 281 301 83 83 116 281 281 412

9/8 10/8 8/8 12/8 11/8 13/8 12/8 9/8 13/8 15/8

10:15a 1:25p 5:50a 6:35p 10:15a 10:15a 1:25p 5:50a 5:50a 1:25p

CÁC RÀNG BUỘC NÀY ĐƯỢC GỌI LÀ PHỤ THUỘC HÀM

Quan hệ PhanCong diễn tả phi công nào lái máy bay nào và máy bay khởi hành vào thời gian nào. Không phải sự phối hợp bất kỳ nào giừa phi công, máy bay và ngày giờ khởi hành cũng đều được chấp nhận mà chúng có các điều kiện ràng buộc qui định sau: + Mỗi máy bay có một giờ khởi hành duy nhất. + Nếu biết phi công, biết ngày giờ khởi hành thì biết được máy bay đo phi công ấy lái. + Nếu biết máy bay, biết ngày khởi hành thì biết phi công lái chuyến bay đó.

14 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Phụ thuộc hàm

1. Xét bài toán: quản lý lịch bay các chuyến bay như sau + Mỗi máy bay có một giờ khởi hành duy nhất. + Nếu biết phi công, biết ngày giờ khởi hành thì biết được máy bay đo phi công ấy lái. + Nếu biết máy bay, biết ngày khởi hành thì biết phi công lái chuyến bay đó. Được phát biểu lại như sau:

+ MAYBAY xác định GIOKH. + {PHICONG,NGAYKH,GIOKH} xác định MAYBAY. + {MAYBAY,NGAYKH} xác định PHICONG.

+ GIOKH phụ thuộc hàm vào MAYBAY. + MAYBAY phụ thuộc hàm vào {PHICONG,NGAYKH,GIOKH}. + PHICONG phụ thuộc hàm vào {MAYBAY,NGAYKH}.

Và được ký hiệu:

+ {MAYBAY}  GIOKH. + {PHICONG,NGAYKH,GIOKH}  MAYBAY. + {MAYBAY,NGAYKH}  PHICONG.

15 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Phụ thuộc hàm

2. Định nghĩa:

 Cho một quan hệ Q(X, Y, Z) với X,Y, Z là các tập thuộc tính

con của Q+ và với X,Y khác rỗng.

 Mọi thể hiện TQ của Q đều thoả phụ thuộc hàm X  Y nếu: q1,q2  TQ: q1.x = q2.x thì q1.Y = q2.Y

Khi đó ta nói: X xác định hàm Y hay Y phụ thuộc hàm vào X

Quy ước:  Nếu Y không phụ thuộc hàm vào X thì ta ký hiệu: X  Y  X  Y là phụ thuộc hàm hiển nhiên nếu Y  X

16 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Phụ thuộc hàm

2. Định nghĩa:

 Tập phụ thuộc hàm của một quan hệ:

 Tập hợp các PTH không hiển nhiên của Q, ký hiệu là FQ

FQ = { fi : XY xác định trên Q} Qui ước: chỉ mô tả các phụ thuộc hàm không hiển nhiên trong tập F.

Ví dụ: Xét quan hệ Giảng dạy: GD(MsGV, Hoten, MsMH,

TenMH, Phòng, Giờ) Tập phụ thuộc hàm của GD được cho như sau: F={f1:MsGVHoten ; f2:MsMHTenMH;

f3: Phong,Gio  MSMH; f4: MsGV,GiờPhòng}

17 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Phụ thuộc hàm 3. Ý nghĩa của PTH:

 PTH là công cụ dùng để biểu diễn một cách hình thức mối

quan hệ dữ liệu của các thuộc tính bên trong CSDL.

 Thông qua cách biểu diễn PTH, xác định khóa của quan hệ  vai trò quan trọng trong các phương pháp thiết kế một lược đồ quan niệm của CSDL: • Tạo ra những quan hệ độc lập. • Giảm thiểu sự trùng lắp, dư thừa dữ liệu lưu trữ  giảm bớt các sai sót khi cập nhật dữ liệu của người sử dụng.

 Đánh giá chất lượng bản thiết kế CSDL.

18 ĐH CÔNG NGHỆ THÔNG TIN

http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 1

R A B C D

Cho quan hệ R (A, B, C, D) như và thể hiện R như hình bên, cho biết PTH nào liệt kê dưới đây thỏa quan hệ:

a 1 X 2

a) f1: AA

b 2 X 1

b) f2: AB

c) f3: AC

d) f4: ACC

e) f5: AD

f) f6: DA

b 2 Y 1

20 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 2

Cho lược đồ quan hệ PHANCONG(PHICONG,MAYBAY, NGAYKH,

GIOKH) liệt kê các tập con có thể có của tập thuộc tính:

PHANCONG+={PHICONG,MAYBAY, NGAYKH, GIOKH} .

 Hướng dẫn giải:

Nhận xét số tập con có thể có của Q+= {A1, A1,.. ,An}là 2n

PHICONG

MAYBAY

NGAYKH

GIOKH

{PHICONG}

{MAYBAY}

{NGAYKH}

{GIOKH}



{PHI CONG,MAYBAY}

{PHICONG,NGAYKH}

{PHICONG,GIOKH}

{MAYBAY,NGAYKH}

{MAYBAY,GIOKH}

{PHI CONG,MAYBAY,NGAYKH}

{PHI CONG,MAYBAY,GIOKH}

{NGAYKH,GIOKH}

{PHICONG,NGAYKH,GIOKH}

{MAYBAY,NGAYKH,GIOKH}

{PHI CONG,MAYBAY,NGAYKH,GIOKH}

21 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 3

Cho lược đồ quan hệ PHANCONG(PHICONG,MAYBAY, NGAYKH,

GIOKH) liệt kê các PTH có thể có của PHANCONG.

 Hướng dẫn giải:

o Nhận xét số tập con có thể có của Q+= {A1, A1,.. ,An}là 2n o Ứng với mỗi tập con này lại sẽ có 2n PTH có thể có.  Số PTH có thể có: 2n x 2n = 2n x n

PHICONG

MAYBAY

NGAYKH

GIOKH

{PHICONG}

{MAYBAY}

{NGAYKH}

{GIOKH}



{PHI CONG,MAYBAY}

{PHICONG,NGAYKH}

{PHICONG,GIOKH}

{MAYBAY,NGAYKH}

{MAYBAY,GIOKH}

{PHI CONG,MAYBAY,NGAYKH}

{PHI CONG,MAYBAY,GIOKH}

{NGAYKH,GIOKH}

{PHICONG,NGAYKH,GIOKH}

{MAYBAY,NGAYKH,GIOKH}

{PHI CONG,MAYBAY,NGAYKH,GIOKH}

Có 24 x 24 = 256 PTH

 Tập thuộc tính con rỗng  sẽ có 24 PTH  Tập thuộc tính con {PHICONG} sẽ có 24 PTH  …

22 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 3

Cho lược đồ quan hệ PHANCONG(PHICONG,MAYBAY, NGAYKH,

GIOKH) liệt kê các PTH có thể có của PHANCONG.

 Hướng dẫn giải:

PHICONG

MAYBAY

NGAYKH

GIOKH

{PHICONG}

{MAYBAY}

{NGAYKH}

{GIOKH}



{PHI CONG,MAYBAY}

{PHICONG,NGAYKH}

{PHICONG,GIOKH}

{MAYBAY,NGAYKH}

{MAYBAY,GIOKH}

{PHI CONG,MAYBAY,NGAYKH}

{PHI CONG,MAYBAY,GIOKH}

{NGAYKH,GIOKH}

{PHICONG,NGAYKH,GIOKH}

{MAYBAY,NGAYKH,GIOKH}

{PHI CONG,MAYBAY,NGAYKH,GIOKH}

Liệt kê: 1.    2.   {PHICONG} .. 16.   {PHI CONG,MAYBAY,NGAYKH,GIOKH}

Tương tự cho {PHICONG}, {MAYBAY}, {MAYBAY,PHICONG},…

23 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 4 a) Cho lược đồ quan hệ Q(A,B,C) liệt kê các tập con của Q+ và các PTH

có thể có của Q.

b) Cho lược đồ quan hệ Q(A,B,C,D) liệt kê các tập con của Q+ và các

PTH có thể có của Q.

Bài 5

Cho quan hệ R (A, B, C, D, E) và thể hiện R như hình bên, cho biết PTH nào liệt kê dưới đây thỏa quan hệ:

a) f1: AD

b) f2: ABD

a1 b1 a1 b2 a2 b1 a2 b1 a3 b2

c1 d1 e1 c2 d2 e1 c3 d3 e1 c4 d3 e1 c5 d1 e1

c) f3: CBDE

d) f4: EA

e) f5: AE

R A B C D E

http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu

Các phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu (ôn)

Phụ thuộc hàm

Hệ tiên đề Amstrong

Bài toán tìm khóa và Bài toán PTH

25 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

1. Bài toán:

Tập F có tối ưu chưa?

Cho lược đồ quan hệ R = {ABCDEGH] và tập PTH F = {ABD ; BE ; EG ; DEC; CDGH; HA; BG}

PTH ABH có suy diễn được từ tập F

BE EG BG: dư thừa

26 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

2. Phát biểu hệ tiên đề Amstrong:

Cho lược đồ quan hệ Q và X, Y, Z, W  Q+.

 Hệ tiên đề Amstrong

 Luật dẫn 1: Luật phản xạ

Y  X  X  Y

 Luật dẫn 2: Luật thêm vàoNếu X  Y và Z  W thì X, W  Y, Z

 Luật dẫn 3: Luật bắc cầu Nếu X  Y và Y  Z thì X  Z

 Một số luật dẫn suy từ Hệ tiên đề Amstrong

 Luật dẫn 4: Luật phân rã Nếu X  Y, Z thì X  Y và X  Z

 Luật dẫn 5: Luật hội

Nếu X  Y và X  Z thì X  Y, Z

 Luật dẫn 6: Luật bắc cầu giả Nếu X  Y và Y, Z  W thì X, Z  W

27 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

3. Bao đóng của tập phụ thuộc hàm:  Định nghĩa: Cho một quan hệ Q có tập phụ thuộc hàm FQ + Bao đóng của FQ, ký hiệu FQ , là tập hợp tất cả các PTH có thể suy diễn từ FQ dựa vào hệ luật dẫn Amstrong. = { XY | F |= X  Y}

+ Ký hiệu FQ

+?  Ví dụ: Q(A,B,C) và FQ = {f1: AB ; f2: B  C}. Tính FQ + = { A  A ; A  B ; A  C ; A  AB ; A  AC ; A  BC ; AABC ; 𝐹𝑄

B B ; B C; B BC ; C C ; AB  AB ; ABA ; ABB ; ABC ; AB  AC ; ABBC ; ABABC ; ACA ; ACB ; ACC ; ACAB ; ACAC ; ACBC; ACABC; BCB ; BCC ; BCBC ; ABCA ; ABCB ; ABCC ; ABCAB ; ABCAC ; ABCBC; ABCABC ; }

28 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

3. Bao đóng của tập phụ thuộc hàm:  Nhận xét tính ứng dụng của bao đóng tập PTH:

 Xác định được tập các thuộc tính phụ thuộc vào một

tập thuộc tính X cho trước.

+ ?

 Kiểm tra một PTH nào đó có thuộc FQ

 Các bước thực hiện:

B1: Tìm tất cả các tập con của Q+. B2: Tìm tất cả các phụ thuộc hàm của Q. +. B3: Vận dụng hệ tiên đề Amstrong để xác định FQ

 Tips: Việc xây dựng bao đóng FQ

+ tốn rất nhiều thời gian. Để giải quyết các bài toán trên người ta dựa vào 1 khái niệm mới, Bao đóng của một tập thuộc tính.

29 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

3. Bao đóng của tập thuộc tính:  Định nghĩa:

Cho 1 LĐQH Q có tập các phụ thuộc hàm FQ={f1, f2,.., fn} và X  Q+. Bao đóng của tập thuộc tính X dựa trên FQ, ký +, là tập các thuộc tính phụ thuộc hàm vào X dựa hiệu XF trên F.

+ = { Y  Q+ : X Y  F+}

 Nhận xét: +.  X  XF + +  f: X Y  FQ  Y  XF

Dựa vào nhận xét 2  giải quyết bài toán thành viên (bài toán kiểm tra sự tồn tại của 1 pth)  xác định bao đóng của tập thuộc tính bên vế trái của pth đó.

30 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

3. Bao đóng của tập thuộc tính: +  Thuật toán xác định: XF

Đầu vào: tập PTH F và tập thuộc tính X trên R. Begin + = X; XF Repeat

+  VP(fi)

+ Then XF

+:= XF

+ X' = XF For i:=1 To m Do { m = card(F)} If VT(fi)  XF + = X');

Until ( XF

End; Ghi chú:

 VT(fi): vế trái của phụ thuộc hàm fi  VP(fi): vế phải của phụ thuộc hàm fi

31 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

3. Bao đóng của tập thuộc tính:  Ví dụ 1: Cho Q(ABCDEGH) và tập PTH F ={f1:BA ; f2:DACE ; f3:D  H ; f4:GH  C; f5:AC  D} a) Tìm bao đóng của tập thuộc tính X1 = {BD} b) Tìm bao đóng của tập thuộc tính X2 = {BCG}

+ = BDA + = BDACE + = BDACEH

+ = BCGA + = BCGAD + = BCGADE + = BCGADEH

Hướng dẫn a: + = BD • X1F • Do f1: BA X1F • Do f2: DACE X1F • Do f3: D  H X1F + = BDACEH Vậy X1F

+ = BCGADEH

Hướng dẫn b: + = BCG • X2F • Do f1: BA X2F • Do f5: AC  D X2F • Do f2: DACE X2F • Do f3: D  H X2F • Vậy X2F

32 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Hệ tiên đề Amstrong

3. Bao đóng của tập thuộc tính:  Ví dụ 2: Cho Q(ABCDEF) và F = {f1: ABC ; f2: AED ; f3:BCD ; f4:CE ; f5:EDF} Kiểm tra AB  EF có thuộc vào F+ hay không?

Hướng dẫn: + = AB • (AB)F + = ABC • Do f1: ABC (AB)F + = ABCD • Do f3: BCD (AB)F + = ABCDE • Do f4: CE (AB)F + = ABCDEF • Do f5: EDF (AB)F + = ABCDEF Nhận xét thấy (EF)  (AB)F Kết luận vậy AB  EF có thuộc vào F+

33 ĐH CÔNG NGHỆ THÔNG TIN

http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 1 Cho F = {ABC ; BD ; CDE ; CEGH ; GA} a) Chứng minh PTH ABE và ABG được suy diễn từ F

nhờ luật dẫn Amstrong. b) Tìm bao đóng của (AB).

Bài 2 Cho F = {AD ; ABDE ; CEG ; EH} Tìm bao đóng của (AB).

Bài 3 Cho F = {ABE ; AGI ; BEI ; EG ; GIH} a) Chứng minh PTH ABGH được suy diễn từ F nhờ luật

dẫn Amstrong.

b) Tìm bao đóng của (AB).

35 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 4: Cho F = {AD ; ABE ; BIE ; CDI ; EC} Tìm bao đóng của (AE).

Bài 5: Cho lược đồ (R,F) với R (ABCDEGH) và F = {ABC ; BD ; CDE ; CEGH ; GA} Tìm các chuỗi suy diễn: a) AB  E b) BG  C c) AB  G

Bài 6: Cho lược đồ (R,F) với R (ABCDEGKIJ) và F = {AGJ ; ABE ; EG ; BEI ; GIK} Tìm chuỗi suy diễn: AB  GK

36 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 7: Cho lược đồ (R,F) với R (ABCDEG) và F = {ABC ; DEG ; CA ; BEC ; BCD ; CGBD ; ADCB ; CEAG} Tìm bao đóng của (AB) và (BD).

Bài 8: Cho lược đồ (R,F) với R (ABCDE) và F = {AC ; BCD ; DE ; EA} Tìm bao đóng của (AB), (BD) và (D).

Bài 9: Cho lược đồ (R,F) với R (ABCDEG) và F = {BC ; ACD ; DG ; AGE} Kiểm tra các PTH sau có thuộc vào F+: a) ABG b) BDAD

37 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu

Các phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu (ôn)

Phụ thuộc hàm

Hệ tiên đề Amstrong

Bài toán tìm khóa và Bài toán PTH

38 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán tìm khóa:  Định nghĩa: Cho LĐQH Q và tập PTH FQ={f1,f2,..,fn}  S  Q+, S là siêu khóa của Q nếu SQ+  FQ  K  Q+, K là khóa chỉ định nếu K là siêu khóa và pth KQ+ là pth nguyên tố. (Không tồn tại K’ là con thật sự của K để K’--> Q+)

Nhận xét: Nếu đồ thị biểu diễn của tập pth F không chứa chu trình thì Q chỉ có duy nhất một khóa.

Ví dụ: Cho (R,F) với R(BDISQO) và tập phụ thuộc hàm F = {f1: S  D ; f2: IS  Q ; f3: I  B ; f4: B  O}

S Q f2

B O f3 f4

39 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán tìm khóa:  Ý tưởng tìm khóa:

 Gọi N là tập thuộc tính nguồn, chỉ chứa thuộc tính không

có bên vế phải của các phụ thuộc hàm.

 Gọi M là tập thuộc tính trung gian, chứa các thuộc tính

vừa xuất hiện bên vế phải vừa xuất hiện bên vế trái.

+= Q+ thì N chính là khóa chỉ định của

 Nếu bao đóng NF

Q và là khóa duy nhất.

 Ngược lại, ta lần lượt hội N với từng tập con của M để

kiểm tra có là khóa chỉ định hay không.

40 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán tìm khóa:  Ví dụ: Cho quan hệ Giảng dạy: GD(MsGV, Hoten, MsMH, TenMH, Phòng, Giờ) và F={f1:MsGVHoten ; f2: MsMHTenMH ; f3: Phong,GioMsMH; f4: MsGV,Giờ Phòng}. Tìm khóa của quan hệ GD.

Hướng dẫn giải:

+ ? + = {MsGV, Gio}

+ = {MsGV, Gio,HoTen} + = {MsGV, Gio,HoTen,Phong} + = {MsGV, Gio,HoTen,Phong,MsMH} + = {MsGV, Gio,HoTen,Phong,MsMH,TenMH}

+ = Q+

Bước 1: xác định N,M N = {MsGV, Gio} M= {MsMH, Phong}

Bước 2: Tính NF • NF • Do f1: NF • Do f4: NF • Do f3: NF • Do f3: NF Vậy NF

Bước 3: Vậy quan hệ GD có khóa duy nhất là {MsGV, Gio}

41 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán tìm khóa:  Thuật toán tìm tất cả các khóa:

Input:

  Output: K {Tập các khóa của quan hệ Q}  Thuật toán: Begin

B1: Xây dựng tập N và M. B2: Xây dựng 2m tập con của tập M với m = Card(M) B3: Xây dựng tập K chứa các khóa

K = 0; For i:=l to 2m do begin

Ki := N  Mi; If Ki không chứa các khóa đã xác định trước đó và Ki,F+ = Q+ then

Ki là 1 khóa của Q: K = K  Ki.

end;

End

42 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán tìm khóa:  Ví dụ: Cho quan hệ Q(ABCDEFG) và FQ = { f1: ECB ; f2: ABC;

f3: EBA ; f4: BGA; f5: AEG}. Xác định các khóa của quan hệ Q.

Hướng dẫn giải:

G f4

Bước 1: xác định N,M N = {D,E,F} M= {A,B,C,G}

B f3 f2 D DEFBCAG

Đồ thị biểu diễn tập PTH

F C E

43 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bước 2: xác định tập khóa dùng thuật toán

K+I.F Siêu khóa Khóa Ki

DEF DEFG DEFGBAC= Q+ DEFC DEFC

DEFBACG= Q+ DEFB DEFB

Ki = N  Ki DEF DEFG DEFC DEFCG DEFB DEFBG

DEFA

DEFBC

DEFA DEFAG DEFAC

DEFACGB= Q+ DEFAC

DEFABCG = Q+ DEFAB DEFAB

ABCG 0000  0001 G 0010 C 0011 CG 0100 B 0101 BG 0110 BC 0111 BCG DEFBCG 1000 A 1001 AG 1010 AC 1011 ACG DEFACG 1100 AB 1101 ABG DEFABG 1110 ABC DEFABC 1111 ABCG DEFABCG

44 ĐH CÔNG NGHỆ THÔNG TIN

http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 1 Cho Q(ABCD) có F = {f1:AC ; f2:DC ; f3:B A}. Xác định khoá của Q.

Bài 2 Q(ABCDEHK) và F= {f1:ABC ; f2:CDE ; f3:AHK ; f4:AD ; f5:BD} Xác định khóa của Q.

Bài 3 Cho quan hệ Q(ABCDEG) và tập pth: F = {ABC ; C  A ; BCD ; ACDB ; DEG; BEC ; CGBD ; CEAG} a) Tìm bao đóng {BD} b) Tìm khóa của Q

46 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài 4 Cho Cho quan hệ Q(ABCEIH) và tập pth F = {ABE ; ACI ; BEI ; EC ; CI->H} a) Chứng minh: AB  GH b) Tìm khóa của Q

Bài 5 Cho F = {ABC ; BD ; CDE ; CEGH ; GA} Tìm khóa của quan hệ ứng với tập F trên.

Bài 6 Cho F = {ABE ; AGI ; BEI ; EG ; GIH} Tìm khóa của quan hệ ứng với tập F trên.

Bài 7: Cho lược đồ (R,F) với R (ABCDEG) và F = {BC ; ACD ; DG ; AGE} Tìm khóa của quan hệ ứng với tập F trên.

47 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: a. PTH có vế trái dư thừa:  Định nghĩa: Cho LĐQH Q và tập PTH FQ={f1,f2,..,fn}

 Phụ thuộc hàm f: Z  Y  FQ có vế trái dư thừa (phụ

thuộc không đầy đủ) nếu tồn tại A  Z sao cho:

′  (FQ – {f: Z  Y })  {(Z - A)  Y} FQ

 Ngược lại gọi PTH f: Z  Y là PTH có vế trái không

dư thừa hay Y phụ thuộc hàm đầy đủ vào Z.

Ví dụ 1: cho Q(A, B, C) và F = {AB  C ; B  C} - Nhận xét: PTH AB  C

A  C

AB  C là PTH không đầy đủ

B  C: đã tồn tại trong F  B dư thừa

 F’ = {A  C ; B  C}

- Nhận xét: PTH B  C là PTH đầy đủ

48 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: a. PTH có vế trái dư thừa:

Ví dụ 2: cho Q(A, B, C, D) và F = {A  BD ; B  C ; AB  D}

- Nhận xét:

• PTH A  BD là PTH đầy đủ • PTH B  C là PTH đầy đủ • AB  D là PTH không đầy đủ vì AD: tính (A)+ dựa trên tập F1 = {ABD ; BC}

+ (A)+ = ABCD  A  D  F1

B: là thuộc tính dư thừa

 F’ = {A  BC ; B  C ; A  D }

 Tips: Thuật toán loại khỏi F các PTH có vế trái dư thừa B1: lần lượt thực hiện bước 2 cho các PTH XY  F B2: với mọi tập thuộc tính con X’   của X

Nếu X’Y  F’+ thì thay XY  F bằng X’Y và thực hiện lại B2

49 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: b. Tập PTH có vế phải một thuộc tính:

Ví dụ: cho Q(A, B, C, D) và F = {A  BC ; B  C ; AB  D } Nhận xét: hiển nhiên có một tập PTH G tương đương với F (ký hiệu G  F) mà vế phải của các PTH  G chỉ gồm 1 thuộc tính  G = {A  B ; A  C ; B  C ; AB  D }

c. Tập PTH không dư thừa:

F là tập PTH không dư thừa nếu không tồn tại F’  F sao cho F’  F. Ngược lại F là tập PTH dư thừa Ví dụ: cho Q(A, B, C, D) và F = {A  BC ; B  D ; AB  D } Nhận xét: F là tập PTH dư thừa vì tồn tại F’  F: F’ = {A  BC ; B  D}

 Tips: Thuật toán loại khỏi F các PTH dư thừa B1: lần lượt thực hiện bước 2 cho các PTH XY  F B2: nếu XY là thành viên của F – {XY} thì loại XY khỏi F

50 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: d. Tập PTH tối thiểu: (minimal cover)  Định nghĩa: F được gọi là tập PTH tối thiểu (phủ tối thiểu)

nếu F thỏa đồn thời 3 điều kiện sau:  F là tập PTH có vế trái không dư thừa.  F là tập PTH có vế phải một thuộc tính.  F là tập PTH không dư thừa.

 Ý nghĩa:

 Giảm bớt số thuộc tính của vế trái.  Giảm bớt số PTH.

51 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: d. Tập PTH tối thiểu: (minimal cover)  Thuật toán tìm phủ tối thiểu của một tập PTH:

B1: loại khỏi F các PTH có vế trái dư thừa.

B2: tách các PTH mà vế phải có trên một thuộc tính thành các PTH có vế phải một thuộc tính.

B3: loại khỏi F các PTH dư thừa.

 Tips: Thuật toán trên sẽ cho ra các kết quả khác nhau nếu thứ tự loại bỏ

các PTH trong F là khác nhau.

52 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: d. Tập PTH tối thiểu: (minimal cover)  Ví dụ tìm phủ tối thiểu của một tập PTH:

1) Cho Q(A, B, C, D) và F = {AB  CD ; B  C ; C  D }

B1: loại khỏi F các PTH có vế trái dư thừa. • PTH AB  CD có vế trái dư thừa?

ACD: tính (A)+ dựa trên tập F1 = {B  C ; C  D }

+ (A)+ = ACD  A  D  F1  Loại bỏ thuộc tính A.

BCD: tính (B)+ dựa trên tập F2 = {B  C ; C  D}

+ (B)+ = BCD  A  D  F2  Không loại bỏ thuộc tính B.

 Thay F  F’ = {B  CD ; B  C ; C  D}

53 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: d. Tập PTH tối thiểu: (minimal cover)  Ví dụ tìm phủ tối thiểu của một tập PTH:

1) Cho Q(A, B, C, D) và F = {AB  CD ; B  C ; C  D }

B2: tách các PTH mà vế phải có trên một thuộc tính thành các PTH có vế phải một thuộc tính. F’ = {B  CD ; B  C ; C  D}

BC

BCD

BD

 F” = {B  D ; B  C ; C  D}

54 http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Bài toán tìm khóa và Bài toán PTH

1. Bài toán PTH: d. Tập PTH tối thiểu: (minimal cover)  Ví dụ tìm phủ tối thiểu của một tập PTH:

1) Cho Q(A, B, C, D) và F = {AB  CD ; B  C ; C  D }

B3: loại khỏi F” = {B  D ; B  C ; C  D} các PTH dư thừa

+ = B

Xét BD  G+? với G = F” - {B  D } = {B  C ; C  D} Tính (B)𝐺

= BC (do có B  C) = BCD (do có C  D)

" = {B  C ; C  D}

Vậy BD G+  pth BD dư thừa trong F” (loại khỏi F”) Vậy thay F” = F1

" - {B  C } = {C  D}: không loại được

Xét BC G+? với G = F1

" - {C  D } = {B  C}: không loại được

Xét CD G+? với G = F1 Kết luận: vậy phủ tối thiểu của F = {B  C ; C  D}

55 ĐH CÔNG NGHỆ THÔNG TIN

http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu – Phụ thuộc dữ liệu

Xác định khóa và tập phủ tối thiểu:

1) Q(ABCD) và F = {AB ; BCD ; DA }

2) Q(ABCDGH) và F = {AH ; ABC ; BCD ; GB }

3) Q(ABCSXYZ) và F = {SA ; AXB ; SB ; BYC ; CZX}

4) Q(ABCSXYZ) và F = {SA ; AXB ; BYC ; YZ ; CZX}

5) Q(ABCDEG) và F = {ABC ; CDE ; AGB ; BD ; AD}

6) Q(ABCDE) và F = {ACB ; EB ; BCA ; DA ; DEC}

DI}

7) Q(ABCDEGHIJ) và F = {BGD ; GJ ; AIC ; CEH ; BDG ; JHA ;

8) Q(ABCMNOP) và F = {AMN ; BNC ; AMB ; AP ; PM ; BNM ;

PCA ; POA}

9) Q(MNOPRSTU) và F = {MS ; MRT ; TR ; ORT ; MU ; MTP ;

NPO ; SUR}

10) Q(ABCDEGHIJ) và F = {BHI ; GCA ; IJ ; AEG ; DB ; IH}

Bài giảng Thiết kế cơ sở dữ liệu: Chương 2 - GV. Dương Khai Phong

ĐH CÔNG NGHỆ THÔNG TIN

http://sites.google.com/site/khaiphong

http://sites.google.com/site/khaiphong

 Nội dung môn học:

2

http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu

Các phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu (ôn)

Phụ thuộc hàm

Hệ tiên đề Amstrong

Bài toán tìm khóa và Bài toán PTH

3

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

1. Thuộc tính?

2. Quan hệ?

3. Khóa?

4. Bộ - Phép chiếu?

4

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

1. Thuộc tính

3. Khóa

2. Quan hệ

4. Bộ - Phép chiếu

5

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

Thuộc tính

Quan hệ

6

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

7

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

8

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

(1) Ai  Q+, ai  MGT(Ai) (2) Tân từ IIQ(a1, a2,..,an) II phải được thoả

9

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

10

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

11

http://sites.google.com/site/khaiphong

Các khái niệm mô hình dữ liệu

DATABASE

12

http://sites.google.com/site/khaiphong

 Chương 2: Mô hình dữ liệu

Các phụ thuộc dữ liệu

Các khái niệm mô hình dữ liệu (ôn)

Phụ thuộc hàm

Hệ tiên đề Amstrong

Bài toán tìm khóa và Bài toán PTH

13

http://sites.google.com/site/khaiphong

Phụ thuộc hàm

1. Xét bài toán: quản lý lịch bay các chuyến bay như sau

PhanCong PHICONG MAYBAY NGAYKH GIOKH

14

http://sites.google.com/site/khaiphong

Phụ thuộc hàm

15

http://sites.google.com/site/khaiphong

Phụ thuộc hàm

2. Định nghĩa:

Quy ước:  Nếu Y không phụ thuộc hàm vào X thì ta ký hiệu: X  Y  X  Y là phụ thuộc hàm hiển nhiên nếu Y  X

16

http://sites.google.com/site/khaiphong

Phụ thuộc hàm

2. Định nghĩa:

FQ = { fi : XY xác định trên Q} Qui ước: chỉ mô tả các phụ thuộc hàm không hiển nhiên trong tập F.

Ví dụ: Xét quan hệ Giảng dạy: GD(MsGV, Hoten, MsMH,

f3: Phong,Gio  MSMH; f4: MsGV,GiờPhòng}