on thi cao hoc « kimchidhcns blog

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (135.12 KB, 10 trang )

(1)<div class='page_container' data-page=1>

NỘI DUNG ÔN THI CAO HỌC
MÔN: HỆ CSDL

NĂM: 2018-2019
PHẦN 1:

1) Cho hai tập phụ thuộc hàm F và G 
F = { D  CE , EI  AB , E  D }

G = { D  CE , DI  ABC , E  DC , EI  C }
Chứng minh rằng G tương đương với F ?
Giải

Chứng minh G được suy dẫn từ F+ :

Ta có D  CE  F
Ta có (DI)+

F = {DICEAB } , vậy ABC  (DI)+F  DI  ABC  F+

Ta có (E)+

F = {EDC } , vậy DC  (E)+F  E  DC  F+

 E  C  F+  EI  C  F+
Chứng minh F được suy dẫn từ G+ :

Ta có D  CE  G 
Ta có (EI)+

G = {EICDAB } , vậy AB  (EI)+G  EI  AB  G+

Từ E  DC  G ,và theo luật phân rã  E  D  G+
2) Cho lược đồ quan hệ R= {Q,F} với Q={ABCDEFGH} và

F= {ABCH, CDE, HD, BFGH, EF, HAB}

Chứng minh F tuơng đương với G={ABEFG, BF GH, AB CD, CDEF,
HAB, EF}

PHẦN 2:

1) Tìm một phủ tối thiểu của F (có diễn giải)

F = { AB  DE , BD  CH, AC  B , AC  D , ABC  D , ABC  H }
B1 : Biến đổi F thành tập các phụ thuộc hàm vế phải chỉ có 1 thuộc tính

F = { AB  E , AB  D , BD  C , BD  H , AC  B , AC  D , ABC  D , ABC  H }
B2 : Biến đổi F thành tập các phụ thuộc hàm có vế trái khơng dư thừa

Xét AB  E . Trong các tập con thực sự của AB ta có :
A+ = {A} không chứa E

</div>
(2)<div class='page_container' data-page=2>

Vậy AB  E không dư thừa ở vế trái
Tương tự , AB  D không dư thừa ở vế trái

Xét BD  C . Trong các tập con thực sự của BD ta có :
B+ = {B} không chứa C

D+ = {D} không chứa C

Vậy BD  C không dư thừa ở vế trái
Tương tự, BD  H không dư thừa ở vế trái

Xét AC  B . Trong các tập con thực sự của AC ta có :
A+ = {A} không chứa B

C+ = {C} không chứa B

Vậy AC  B không dư thừa ở vế trái 
Tương tự, AC  D không dư thừa ở vế trái

Xét ABC  D . Trong các tập con thực sự của ABC ta có :
A+ = {A} không chứa D

B+ = {B} không chứa D

C+ = {C} không chứa D

AB+ = {ABEDCH} chứa D

AC+ = {ACBDEH} chứa D

BC+ = {BC} không chứa D

Vậy ABC  D dư thừa ở vế trái .

Ta thay thế ABC  D bằng AB  D hoặc AC  D

Xét ABC  H . Trong các tập con thực sự của ABC ta có :
A+ = {A} không chứa H

B+ = {B} không chứa H

C+ = {C} không chứa H

AB+ = {ABEDCH} chứa H

AC+ = {ACDBEH} chứa H

BC+ = {BC} không chứa H

</div>
(3)<div class='page_container' data-page=3>

Ta thay thế ABC  H bằng AB  H hoặc AC  H

Vậy ta có 2 tập phụ thuộc hàm tương đương với F có vế trái không dư thừa
như sau :

F1 = { AB  E , AB  D , BD  C , BD  H , AC  B , AC  D , AB  H }
G1 = { AB  E , AB  D , BD  C , BD  H , AC  B , AC  D , AC  H }

(Vì chỉ cần tìm một phủ tối thiểu ,học sinh có thể chọn biến đổi tiếp từ F1 hoặc G1

Đáp án nêu cách biến đổi tiếp từ F1 )

B3 : Loại khỏi F1 các phụ thuộc hàm dư thừa
(AB)+

F1 \ {AB  E} = {ABDCH} không chứa E. Vậy AB  E không dư thừa trong F1

(AB)+

F1 \ {AB  D} = {ABEH} không chứa D. Vậy AB  D không dư thừa trong F1

(BD)+

F1 \ {BD  C} = {BDH} không chứa C. Vậy BD  C không dư thừa trong F1

(BD)+

F1 \ {BD  H} = {BDC} không chứa H. Vậy BD  H không dư thừa trong F1

(AC)+

F1 \ {AC  B} = {ACD} không chứa B. Vậy AC  B không dư thừa trong F1

(AC)+

F1 \ {AC  D} = {ACBEDH} chứa D. Vậy AC  D dư thừa trong F1

Đặt F2 = F1 \ {AC  D} 
(AB)+

F2 \ {AB  H} = {ABEDCH} chứa H. Vậy AB  H dư thừa trong F2

Đặt F3 = F2 \ {AB  H}

Vậy một phủ tối thiểu của F là

F3 = { AB  E , AB  D , BD  C , BD  H , AC  B }
2) Tìm phủ tối thiểu của tập phụ thuộc hàm sau:

F= {A→ E, ADF → BE, BCF → C, B → E, CE → DF}
Bước 1: biến đổi tất cả FD thành vế phải thuộc tính đơn

F1= {A→ E, ADF → B, ADF E, BCF → C, B → E, CE → D, CE F}
Vì BCF C là PTH tầm thường, nên đượcc loại bỏ khỏi tập F1.
F1= {A→ E, ADF → B, ADF E, B → E, CE → D, CE F}
Bước 2: Loại bỏ thuộc tính dư thừa ở vế trái của các FD

- Xét ADF  B
Vì +¿AD=ADE

F 1
¿ ,

+¿=AFE

AFF 1¿ ,

+¿=DF

DF¿F 1 , nên phụ thuộc hàm ADF B không dư
thừa vế trái

</div>
(4)<div class='page_container' data-page=4>

Vì +¿A=AE
F 1

¿ nên phụ thuộc hàm ADF B có thuộc tính DF dư thừa vế trái
Sau khi loại bỏ thuộc tính dư thừa, tập phụ thuộc hàm mới sẽ là

F2= {A→ E, ADF → B, B → E, CE → D, CE F}

- Xét CED và CEF

Vì +C¿=C
F 2

¿ và

+¿=E

E¿F 1 , nên các phụ thuộc hàm CED, CEF đều không dư
thừa vế trái.

Bước 3: Loại bỏ phụ thuộc hàm dư thừa

F3= {A→ E, ADF → B, B → E, CE → D, CE F}
- Thử loại bỏ AE

F4= { ADF → B, B → E, CE → D, CE F}

Vì +¿A=A
F 4

¿ nên A E không dư thừa

Xét tương tự chó các PTH khác, tất cả PTH đều khơng dư thừa
Kết luận: F3 là phủ tối thiểu

3) Tìm phủ tối thiểu của tập phụ thuộc hàm sau:
F1={DE  A; B  C; E AD; AB D}

- Bước 1: tách vế phải thành một thuộc tính
F1={DE  A; B  C; E A; E  D; AB D}

- Bước 2: Kiểm tra vế trái dư thừa
o Xét DE  A

D+ = D (không chứa A => E không dư)

E+ = EAD (chứa A => D dư)

DE  A (phụ thuộc hàm dư thừa)
o Xét AB D

A+ = A (không chứa D => B không dư)

B+ = BC (không chứa D => A không dư)

DE  A không dư thừa vế trái
F2={B  C; E A; E  D; AB D}

- Bước 3: Kiểm tra phụ thuộc hàm dư thừa

o Xét B  C: B+=B (không chứa C => BC không dư)

o Xét E  A : E+=ED (không chứa A => E  A không dư)

</div>
(5)<div class='page_container' data-page=5>

o Xét AB D : AB+=ABC (Không chứa D => AB  D không dư)
F2={B  C; E A; E  D; AB D}

PHẦN 3

Bài 1: Cho quan hệ R(ABCDEH) và tập các phụ thuộc hàm 
F = { AB  ED , BD  CH , AC  BD , ABC  DH }

1) Tìm tất cả các khoá của R suy ra từ tập phụ thuộc hàm
TN = {A } , TG = {BCD}

TG TN  TG (TN  TG)+ Siêu khoá Khoá

 A A

B AB ABEDCH AB AB

C AC ACBDEH AC AC

D AD AD

BC ABC ABCEDH ABC

BD ABD ABDCHE ABD

CD ACD ACDBEH ACD

BCD ABCD DBCEAH ABCD

Kết luận : R có hai khố {AB} và {AC}

2) Xác định dạng chuẩn cao nhất của R (có chứng minh)
Tập thuộc tính khơng khố là {DEH}

Bước 1 : R đương nhiên đạt dạng chuẩn 1

Bước 2 : Xét các tập con thực sự của các khoá AB, AC
Ta thấy (A)+

F = {A} và (B)+F = {B}

(A)+

F = {A} và (C)+F = {C}

không chứa các thuộc tính khơng khố. Vây R đạt dạng chuẩn 2
Bước 3 : Xét phụ thuộc hàm BD  CH có vế trái (BD) khơng chứa siêu

khố, vế phải chứa H là thuộc tính khơng khố . Vây R không đạt dạng
chuẩn 3

Kết luận : R đạt dạng chuẩn 2

Bài 2: Khảo sát bảng dữ liệu chứa thơng tin của thí sinh nộp hồ sơ vào một trường đại
học như sau:

THISINH
Số
Báo

Họ Tên Ngày

Sinh

Mã
trườn

Tên Trường Mã
Tỉn

Tên
tỉnh

</div>
(6)<div class='page_container' data-page=6>

danh g
PTTH

0560 Lê Thị Tý 1/1/1999 A12 Lê Hồng Phong 08 HCMC A
0342 Trần Hào 12/5/199

B12 Ngô Quyền 04 Hà nội B

0101 Trần Thị Ba 4/6/1999 C01 Lê Hồng Phong 49 Đà lạt C
0100 Ngô Văn Ba 18/5/199

9 B12 Ngô Quyền 04 Hà nội D

Mỗi thí sinh có một sơ báo danh duy nhất. Các thí sinh có thể trùng tên trùng họ và có
thể cùng học một trường THPT. Mỗi thí sinh đăng ký dự thi một trong các khối thi
A,B,C hoặc D và chỉ được phép thi 1 khối duy nhất. Mỗi trường có mã trường riêng
biệt, tên trường của các tỉnh thành có thể trùng nhau. Một tỉnh thành có thể nhiều

trường THPT.

Tên TrườngMã Tỉnh

Số Báo danh Họ, Tên, Ngày Sinh, Mã trường PTTH, Tên
Trường, Mã Tỉnh, Tên tỉnh, Khối thi

Họ, Tên Tên Trường

Mã trường PTTH, Mã Tỉnh  Tên Trường
Mã Tỉnh  Tên tỉnh

a) Xác định dạng chuẩn của bảng.

b) Nếu bảng không đạt chuẩn 3 NF thì bạn sẽ phân rã quan hệ THISINH thành
các quan hệ nào để cơ sở dữ liệu tối ưu hơn.

Đáp án:

Khóa chính: Số Báo Danh

Vì bảng có khóa chính là khóa đơn, nên bảng đạt chuẩn 2NF.

Thuộc tính khóa là số báo danh, các thuộc tính cịn lại là thuộc tính khơng khóa

PTH 2 và 3 có vế trái khơng phải là khóa, vế phải khơng phải là thuộc tính khóa, nên vi
phạm chuẩn 3NF.

Chuẩn cao nhất của bảng là 2NF.
b) Phân rã lược đồ

TINH (Mã Tỉnh, Tên Tỉnh)

TRUONGHOC (Mã trường, Mã Tỉnh, Tên Trường)

THISINH(Số báo danh, Họ, Tên, Ngày Sinh, Mã trường, Khối thi)

</div>
(7)<div class='page_container' data-page=7>

KETQUATRANDAU(MatranDau, NgayThiDau, Gio, SanThiDau, MaTrongTai,
TenTrongTai, MaDoiBong, TenDoiBong, TySo)

Ma
TranDau

Ngay
ThiDau

Gio San
ThiDau

Ma
TrongTai

Ten
TrongTai

Ma
DoiBong

Ten
DoiBong

Ty
So

1 3/5/17 17g Hoa Lư T1 Nguyễn Ân D1 Hà Nội 3-2

1 3/5/17 17g Hoa Lư T1 Nguyễn Ân D2 Tp.HCM 3-2

2 5/5/17 19g Mỹ Đình T2 Lê Hà D1 Hà Nội 1-1

2 5/5/17 19g Mỹ Đình T2 Lê Hà D3 SLNA 1-1

a) Xác định khóa cho quan hệ KETQUATRANDAU biết các phụ thuộc hàm sau:
F={MaTranDauNgayThiDau, Gio, SanThiDau, MaTrongTai, TenTrongTai,
TySo

MaTrongTaiTenTrongTai
MadoiBongTenDoiBong

MaTranDau, MaDoiBongNgayThiDau, Gio, SanThiDau, MaTrongTai,
TenTrongTai, TenDoiBong, TySo}

b) Xác định dạng chuẩn cao nhất của quan hệ trên.
F={ABCDEFHI, EF, GH, AGBCDEFHI}
TN={AG}

TG={E}

Xi XiUTN XiUTN+ Siêu khóa Khóa

 AG ABCDEFGHIFK=Q+ AG AG

E AEG Q+ AEG

Khóa là K = {AG} hay K={MaTranDau, MaDoiBong}

Xét phụ thuộc hàm ABCDEFHIJK có A khơng là siêu khóa nên Q khơng
đạt BC, vế phải chứa các thuộc tính khơng phải là thuộc tính khóa nên Q
không đạt chuẩn 3

A+ = Q chứa các thuộc tính khơng là thuộc tính khóa nên Q khơng đạt 2.
Vậy Q đạt chuẩn 1

</div>
(8)<div class='page_container' data-page=8>

2) Xác định dạng chuẩn cao nhất cho quan hệ R.

3) Bạn đưa ra giải pháp để sửa quan hệ trên (tách quan hệ) đạt chuẩn cao hơn.
Bài giảng

1) Xác định tất cả khóa của lược đồ quan hệ R(A, B, C, D, E) và tập phụ thuộc hàm F={DEA;
B C; E AD; ABD}

 TN={BE}
 TG={AD}

Xi XiTN (XiTN)+ Siêu khóa Khóa

 BE BCADE=Q

BE BE

A ABE Q+ ABE

D DBE Q+ DBE

AD ADBE Q+ ADBE

Xác định khóa chính BE

2) Dạng chuẩn cao nhất

Xét DEA có DE khơng là siêu khóa R khơng đạt BCNF

Xét DEA có DE khơng là siêu khóa, A khơng là thuộc tính khóa R khơng đạt 3NF
Xét khóa BE

B+ = BC có C khơng là thuộc tính khóa R khơng đạt chuẩn 2
Vậy chuẩn cao nhất là chuẩn 1

3) Bạn đưa ra giải pháp để sửa quan hệ trên (tách quan hệ) đạt chuẩn cao hơn.
Xét DEA có DE khơng là siêu khóa, A khơng là thuộc tính khóa

Tách thành

Q1 (D,E,A) , F=={DEA; E AD; }
Q2(B, C, D, E), F={ B C; ABD}

Bài 6: Cho quan hệ HoaDon(Mahd, Masp, Ngayban, MotaSp, Mancc, Tenncc, 
Soluong, Dongia) và tập phụ thuộc hàm sau:

Quan hệ HoaDon có dữ liệu như sau:

Mahd Masp Ngayban MotaSp Mancc Tenncc Soluon

g

Dongia

Hd01 Tao 5/5/2017 Táo Mỹ Vna VinaMak 5 70000

Hd01 Bơ 5/5/2017 Bơ Đà Lạt Cop CopMark 10 30000

Hd02 Tao 6/5/2017 Táo Mỹ Vna VinaMak 6 70000

</div>
(9)<div class='page_container' data-page=9>

Mahd, Masp  Ngayban, MotaSp,
ManccMancc, Tenncc,

Mahd, MaspMancc, Tenncc
Yêu cầu:

1) Xác định tất cả khóa của lược đồ quan hệ.
2) Quan hệ trên thuộc dạng chuẩn mấy?

3) Bạn đưa ra giải pháp để sửa quan hệ trên (tách quan hệ) đạt chuẩn cao hơn.
Giải

1) Xác định tất cả khóa của lược đồ quan hệ

Đặt A=Mahd, B=Masp, C=Ngayban, D=MotaSp, E=Mancc, F=Tenncc, G=Soluong,

H=Dongia

Tập phụ thuộc hàm tương ứng:

F={ABCDEFGH, AC, EF, BDEFH}
 TN={AB}

 TG={E}

Xi XiTN (XiTN)+ Siêu khóa Khóa

 AB ABCDEFG

AB AB

E ABE ABCDEFG

ABE

Xác định khóa chính AB (Mahd, Masp)
2) Dạng chuẩn cao nhất

Xét ABCDEFGH

AB+ = ABCDEFGH có AB là siêu khóa
Xét AC

A+ =AC, có A khơng là siêu khóa
Nên Hoadon khơng đạt chuẩn BCNF
C khơng là thuộc tính khóa

Nên Hoadon không đạt chuẩn 3NF và chuẩn 2
Vậy chuẩn cao nhất là chuẩn 1

3) Bạn đưa ra giải pháp để sửa quan hệ trên (tách quan hệ) đạt chuẩn cao hơn.
Xét DEA có DE khơng là siêu khóa, A khơng là thuộc tính khóa

Tách thành

</div>
(10)<div class='page_container' data-page=10></div>

on thi cao hoc « kimchidhcns blog

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về