Xác định khóa, Tìm phủ tối thiểu, Chuẩn hóa dữ liệu

 

Luyện Tập

Xác định khóa, Tìm phủ tối thiểu, Chuẩn hóa dữ liệu 3NF

ĐỀ SỐ 1:

Câu II:  

Cho lược đồ quan hệ Q(A,B,C,D,E,G,H) và tập phụ thuộc hàm:

F = { E → C; H → E; A→ D; A,E → H; D,G → B; D,G → C }

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.

HƯỚNG DẪN:

1. Tìm khóa?

TN = {AG }

TG = { DEH }

TN+F = { AG }+F = AGDBC ≠ Q+

Xi	TN U Xi	(TN U Xi)+	Siêu khóa	Khóa
ø	AG	AGDBC
D	AGD	AGDBC
E	AGE	AGEDBCH = Q+	AGE	AGE
H	AGH	AGHDEBC = Q+	AGH	AGH
DE	AGDE	AGDEBCH = Q+	AGDE
DH	AGDH	AGDHBCE = Q+	AGDH
EH	AGEH	AGEHDBC = Q+	AGEH
DEH	AGDEH	AGDEHBC = Q+	AGDEH

Vậy TK = { AGE, AGH }

2. 3NF?

Xét pth: E → C, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

3. Tìm phủ tối thiểu?

Bước 1:  F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = {  E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = {  E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

Bước 3:

F’ = {  E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

* Xét E → C: E+ - { E → C } = E, C ∉ E+ ⇔ E → C ∉ F+ ⇒ Không thể bỏ pht này.

* Các pth H → E; A→ D; A,E → H; D,G → B đều không bỏ được vì các thuộc tính E, D, H, B chỉ xuất hiện 1 lần bên vế phải.

* D,G → C: DG+ - { D,G → C } = DGB, C ∉ DG+ ⇔ D,G → C ∉ F+  ⇒ Không thể bỏ pht này.

Vậy F’ = { E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

Là phủ tối thiếu của F.

4. Phân rã?

Vậy TK = { AGE, AGH }

Bước 1, Bước 2: Không làm

Bước 3: Q1( EC ) với F1 = { E → C }

Q2( HE ) với F2 = { H → E }

Q3( AD ) với F3 = { A→ D }

Q4( AEH ) với F4 = { A,E → H }

Q5( DGB ) với F5 = { D,G → B }

Q6( DGC ) với F6 = { D,G → C }

Bước 4: Vì không có LĐQH con nào chứa 1 khóa của Q nên bổ sung 1 khóa của Q vào phân rã: Q7( AGE ), F7 = {ø}

===============================================

ĐỀ SỐ 2

Câu II

Cho lược đồ quan hệ  Q(ABCDEG) và tập phụ thuộc hàm  

F= {B → C; DEG → B; A → D; A → E; A → G}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về  dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.

HƯỚNG DẪN

1. Tìm khóa?

TN = { A }

TG = { BDEG }

TN+F = { A }+F = ADEGBC = Q+

Vậy Q chỉ có 1 khóa duy nhất là A

2. 3NF?

Xét pth: B → C, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

3. Tìm phủ tối thiểu?

Bước 1:  F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = {  B → C;

DEG → B;

A → D;

A → E;

A → G }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = {  B → C;

DEG → B;

A → D;

A → E;

A → G }

Bước 3:

F’ = {  B → C;

DEG → B;

A → D;

A → E;

A → G }

* Các pth B → C; DEG → B; A → D; A → E; A → G đều không bỏ được vì các thuộc tính C, B, D, E, G chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { B → C;

DEG → B;

A → D;

A → E;

A → G }

Là phủ tối thiếu của F.

4. Phân rã?

TK = {A}

Bước 1, Bước 2: Không làm

Bước 3: Q1( BC ) với F1 = { B → C }

Q2( DEGB ) với F2 = { DEG → B }

Q3( AD ) với F3 = { A→ D }

Q4( AE ) với F4 = { A → E }

Q5( AG ) với F5 = { A → G }

Bước 4: Vì có Q3, Q4, Q5 chứa khóa của Q nên không bổ sung.

===============================================

ĐỀ SỐ 3

Câu II :

Cho lược đồ quan hệ Q(ABCDEG) và tập các phụ thuộc hàm

F = {AB→ C, AC→D, D→EG, G→B, A→D, CG→A}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về  dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.

HƯỚNG DẪN

1. Tìm khóa?

TN = {ø}

TG = { ABCDG }

Xi	TN U Xi	(TN U Xi)+	Siêu khóa	Khóa
ø	ø	ø
A	A	ADEGBC = Q+	A	A
B	B	B
C	C	C
D	D	DEGB
G	G	GB
AB	AB	ADEGBC = Q+	AB
AC	AC	ADEGBC = Q+	AC
AD	AD	ADEGBC = Q+	AD
AG	AG	ADEGBC = Q+	AG
BC	BC	BC
BD	BD	BDEG
BG	BG	BG
CD	CD	CDEGBA = Q+	CD	CD
CG	CG	CGABDE = Q+	CG	CG
DG	DG	DGBE
ABC	ABC	ADEGBC = Q+	ABC
ABD	ABD	ADEGBC = Q+	ABD
ABG	ABG	ADEGBC = Q+	ABG
ACD	ACD	ADEGBC = Q+	ACD
ACG	ACG	ADEGBC = Q+	ACG
ADG	ADG	ADEGBC = Q+	ADG
BCD	BCD	CDEGBA = Q+	BCD
BCG	BCG	CGABDE = Q+	BCG
BDG	BDG	BDGE
CDG	CDG	CDEGBA = Q+	CDG
ABCD	ABCD	CDEGBA = Q+	ABCD
ABCG	ABCG	CDEGBA = Q+	ABCG
ABDG	ABDG	CDEGBA = Q+	ABDG
ACDG	ACDG	CDEGBA = Q+	ACDG
BCDG	BCDG	CDEGBA = Q+	BCDG
ABCDG	ABCDG	CDEGBA = Q+	ABCDG

Vậy TK = { A, CD, CG }

2. 3NF?

Xét pth: G→B, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

3. Tìm phủ tối thiểu?

Bước 1:  F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = {  AB→ C,

AC→D,

D→E,

D→G,

G→B,

A→D,

CG→A }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = {  AB→ C,

AC→D,

D→E,

D→G,

G→B,

A→D,

CG→A }

• AB→C: có B dư thừa vì A→D→G→B  A→B ( B ẩn trong A)

• A C→D: có C dư thừa vì A→D

Bước 3:

F’ = {  A→ C,

A→D,

D→E,

D→G,

G→B,

A→D,

CG→A }

• A→D: bỏ pth này vì trùng lắp

• Các pth A→ C; D→E; D→G; G→B; A→D; CG→A đều không bỏ được vì các thuộc tính C, E, G, B, D, A chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { A→ C,

D→E,

D→G,

G→B,

A→D,

CG→A }

Là phủ tối thiếu của F.

4. Phân rã?

Dựa vào phủ tối thiểu F’

TK = { A, CD, CG }

Bước 1, Bước 2: Không làm

Bước 3: Q1( AC ) với F1 = { A → C }

Q2( DE ) với F2 = { D→E }

Q3( DG ) với F3 = { D→G }

Q4( GB ) với F4 = { G→B }

Q5( AD ) với F5 = { A→D }

Q6( CGA ) với F6 = { CG→A }

Bước 4: Vì có Q1 chứa khóa của Q nên không bổ sung.

===============================================

ĐỀ SỐ 4

Câu II :

Cho quan hệQ(GHIKLM) và tập các phụ thuộc hàm

F = {GH→ L, I→M, L→K, HM→G, GK→I, H→L}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về  dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.

HƯỚNG DẪN

1. Tìm khóa?

TN = { H }

TG = {GIKLM }

TN+F = { H }+F = HLK ≠ Q+

Xi	TN U Xi	(TN U Xi)+	Siêu khóa	Khóa
ø	H	HLK
G	HG	HGLKIM = Q+	HG	HG
I	HI	HILMGK = Q+	HI	HI
K	HK	HKL
L	HL	HLK
M	HM	HMLKGI = Q+	HM	HM
GI	HGI	HGLKIM = Q+	HGI
GK	HGK	HGLKIM = Q+	HGK
GL	HGL	HGLKIM = Q+	HGL
GM	HGM	HGLKIM = Q+	HGM
IK	HIK	HGLKIM = Q+	HIK
IL	HIL	HGLKIM = Q+	HIL
IM	HIM	HGLKIM = Q+	HIM
KL	HKL	HKL
KM	HKM	HGLKIM = Q+	HKM
LM	HLM	HGLKIM = Q+	HLM
GIK	HGIK	HGLKIM = Q+	HGIK
GIL	HGIL	HGLKIM = Q+	HGIL
GIM	HGIM	HGLKIM = Q+	HGIM
GKL	HGKL	HGLKIM = Q+	HGKL
GKM	HGKM	HGLKIM = Q+	HGKM
GLM	HGLM	HGLKIM = Q+	HGLM
IKL	HIKL	HGLKIM = Q+	HIKL
IKM	HIKM	HGLKIM = Q+	HIKM
ILM	HILM	HGLKIM = Q+	HILM
KLM	HKLM	HGLKIM = Q+	HKLM
GIKL	HGIKL	HGLKIM = Q+	HGIKL
GIKM	HGIKM	HGLKIM = Q+	HGIKM
GILM	HGILM	HGLKIM = Q+	HGILM
GKLM	HGKLM	HGLKIM = Q+	HGKLM
IKLM	HIKLM	HGLKIM = Q+	HIKLM
GIKLM	HGIKLM	HGLKIM = Q+	HGIKLM

Vậy TK = { HG, HI, HM }

G

I

K

L

M

Cách 2: Tìm chu trình của Tập TG

Ta thấy G, I và M tạo thành 1 chu trình, vì vậy mỗi điểm trên chu trình này kết hợp với TN tạo thành khóa của Q.

Vậy TK = { HG, HI, HM }

2. 3NF?

Xét pth: L→K, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

3. Tìm phủ tối thiểu?

Bước 1:  F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = {  GH→ L,

I→M,

L→K,

HM→G,

GK→I,

H→L }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = {  GH→ L,

I→M,

L→K,

HM→G,

GK→I,

H→L }

• GH→L: có G dư thừa vì có H→L

Bước 3:

F’ = {  H→ L,

I→M,

L→K,

HM→G,

GK→I,

H→L }

• H→ L: bỏ pth này vì trùng lắp

• Các pth I→M; L→K; HM→G; GK→I; H→L đều không bỏ được vì các thuộc tính M, K, G, I, L chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { I→M,

L→K,

HM→G,

GK→I,

H→L }

Là phủ tối thiếu của F.

4. Phân rã?

Dựa vào phủ tối thiểu F’

TK = { HG, HI, HM }

Bước 1, Bước 2: Không làm

Bước 3: Q1( IM ) với F1 = { I→M }

Q2( LK ) với F2 = { L→K }

Q3( HMG ) với F3 = { HM→G }

Q4( GKI ) với F4 = { GK→I }

Q5( HL ) với F5 = { H→L }

Bước 4: Vì có Q3 chứa khóa của Q nên không bổ sung.

===============================================

ĐỀ SỐ 5

Câu II :

Cho lược đồ quan hệ Q và tập phụ thuộc hàm F được cho như sau:

Q(A,B,C,D,E,G,H,K,L,M,N),  F={ C → D,E; G → H,K; A,G → L; M → A,N; A → B,C}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về  dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.

HƯỚNG DẪN

1. Tìm khóa?

TN = { GM }

TG = { AC }

TN+F = {GM }+F = GMANBCDEHKL = Q+

Vậy Q có 1 khóa duy nhất là GM

2. 3NF?

Xét pth: C → D,E, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

3. Phủ tối thiểu?

Bước 1:  F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = {  C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = {  C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Bước 3:

F’ = {  C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Các pth C → D; C → E; G → H; G → K; A,G → L; M → A; M → N; A → B; A → C đều không bỏ được vì các thuộc tính D, E, H, K, L, A, N, B, C chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Là phủ tối thiếu của F.

4. Phân rã?

Dựa vào phủ tối thiểu F’

TK = { GM }

Bước 1, Bước 2: Không làm

Bước 3: Q1( CD ) với F1 = { C → D }

Q2( CE ) với F2 = { C → E }

Q3( GH ) với F3 = { G → H }

Q4( GK ) với F4 = { G → K }

Q5( AGL ) với F5 = { A,G → L }

Q6( MA ) với F6 = { M → A }

Q7( MN ) với F7 = { M → N }

Q8( AB ) với F8 = { A → B }

Q9( AC ) với F9 = { A → C }

Bước 4: Vì không có LĐQH con nào chứa 1 khóa của Q nên bổ sung 1 khóa của Q vào phân rã: Q10( GM ), F10 = {ø}

.

===============================================

ĐỀ SỐ 6

BÀI 2:  

Cho lược đồ quan hệ CCS và tập phụ thuộc hàm F được cho như sau như sau: CCS(MAHV,HOTEN,NGAYSINH,MALOP,TENLOP,NGAYKG,MAMH,TENMH,SOTIET, DIEMTHI, SOBL, SOTIEN)

F={ MAHV → HOTEN, NGAYSINH, MALOP,

MALOP → NGAYKG, TENLOP,

MAMH → TENMH,SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,SOTIEN}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về  dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.

HƯỚNG DẪN

1. Tìm khóa?

TN = { MAMH, SOBL }

TG = { MAHV, MALOP }

TN+F = { MAMH, SOBL }+F = { MAMH, SOBL, TENMH, SOTIET, MAHV, SO TIEN, DIEMTHI, HOTEN, NGAYSINH, MALOP, NGAYKG, TENLOP } = CSS+

Vậy CSS có 1 khóa duy nhất là { MAMH, SOBL }

2. 3NF?

Xét pth: MAHV → HOTEN, NGAYSINH, MALOP, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

3. Tìm phủ tối thiểu?

Bước 1:  F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = {  MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = {  MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Bước 3:

F’ = {  MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Các pth MAHV → HOTEN, MAHV → NGAYSINH, MAHV → MALOP, MALOP → NGAYKG, MALOP → TENLOP, MAMH → TENMH, MAMH → SOTIET, MAHV,MAMH → DIEMTHI, SOBL → MAHV, SOBL → SOTIEN đều không bỏ được vì các thuộc tính HOTEN, NGAYSINH, MALOP, NGAYKG, TENLOP, TENMH, SOTIET, DIEMTHI, MAHV, SOTIEN chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Là phủ tối thiếu của F.

4. Phân rã?

Dựa vào phủ tối thiểu F’

TK = { MAMH, SOBL }

Bước 1, Bước 2: Không làm

Bước 3: Q1(MAHV, HOTEN ) với F1 = { MAHV → HOTEN }

Q2(MAHV, NGAYSINH ) với F2 = { MAHV → NGAYSINH }

Q3(MAHV, MALOP ) với F3 = { MAHV → MALOP }

Q4(MALOP, NGAYKG ) với F4 = { MALOP → NGAYKG }

Q5(MALOP, TENLOP ) với F5 = { MALOP → TENLOP }

Q6(MAMH, TENMH ) với F6 = { MAMH → TENMH }

Q7(MAMH, SOTIET ) với F7 = { MAMH → SOTIET }

Q8(MAHV,MAMH, DIEMTHI ) với F8 = { MAHV,MAMH → DIEMTHI }

Q9(SOBL, MAHV ) với F9 = { SOBL → MAHV }

Q10(SOBL, SOTIEN ) với F10 = { SOBL → SOTIEN }

     Bước 4: Vì không có LĐQH con nào chứa 1 khóa của CSS nên bổ sung 1 khóa của CSS vào phân rã: Q11( MAMH, SOBL ), F11 = {ø}

===============================================

ĐỀ SỐ 8

CÂU II :  

Cho lược đồ quan hệ HoaDon và tập các phụ thuộc hàm F như sau: HoaDon(SOHD, KHACH, NGAYLAP, MATHANG, DONGIA, SOLUONG) F={SOHD →KHACH, NGAYLAP,

SOHD,MATHANG →DONGIA,SOLUONG}

1.  Tìm khóa cho Hoadon

2.  Hãy cho biết lược đồ quan hệ HoaDon có đạt dạng chuẩn nào ? Tại sao?

3.  Nếu lược đồ chưa đạt dạng chuẩn 3 hãy phân rã thành các lược đồ con đạt dạng chuẩn 3, xác định khóa chính cho các lược đồ con này.)

HƯỚNG DẪN

1. Tìm khóa?

TN = { SOHD, MATHANG }

TG = { ø }

Vậy HoaDon có 1 khóa duy nhất là { SOHD, MATHANG }

2. Tìm dạng chuẩn?

• 2NF:

Tập thuộc tính không khóa: N = {KHACH, NGAYLAP, DONGIA, SOLUONG}

• Xét pht SOHD, MATHANG →KHACH Є F:

có MATHANG dư thừa vì có SOHD→KHACH

 SOHD, MATHANG →KHACH  là phụ thuộc hàm không đầy đủ.

Vậy HoaDon không đạt 2NF.

Dạng chuẩn của LĐQH HoaDon là 1NF

3. Phân rã?

F={ SOHD →KHACH,

SOHD → NGAYLAP,

SOHD,MATHANG →DONGIA,

SOHD,MATHANG → SOLUONG}  

Phân rã thành các lược đồ con đạt dạng chuẩn 3:

Bước 1, Bước 2: Không làm

Bước 3:

Q1(SOHD, KHACH) với F1 = { SOHD →KHACH },  có K1 = {SOHD}

Q2(SOHD, NGAYLAP) với F2 = { SOHD → NGAYLAP }, có K2 = {SOHD}

Q3(SOHD,MATHANG, DONGIA) với F3 = {SOHD,MATHANG →DONGIA}, có K3 = {SOHD, MATHANG}

Q4(SOHD,MATHANG, SOLUONG) với F4 = {SOHD,MATHANG →  SOLUONG}, có K4 = {SOHD, MATHANG}

Bước 4: Vì có Q3 chứa khóa của Q nên không bổ sung.