Phương pháp xác định dạng chuẩn

Chỉ xét các phụ thuộc hàm vi phạm ( Vi phạm khi vế trái không phải là khóa )

Vế	Phải	Trái
Có tham gia vào khóa	Có	Không	Có
Vi phạm dạng chuẩn	BC	3	2

Xét vế phải trước nhé rồi tới vế trái

Ví dụ :Xét lược đồ quan hệ <R,F>,với R = MTGAHDL và F = { H → D, M → T, MA → G, MH → L}

Ta có khóa là HMA

Xét các phụ thuộc hàm vi phạm ( có vế trái không phải là khóa )

H -> D vi phạm dạng chuẩn 2 ( vì thuộc tính vế trái H có tham gia vào khóa )

M->T vi phạm dạng chuẩn 2

MA -> G vi phạm dạng chuẩn 2

MH -> L vi phạm dạng chuẩn 2

-> lược đồ quan hệ trên vi phạm dạng chuẩn 2 và đạt dạng chuẩn 1.

Các bạn tham khảo nhé

yep... chính xác..
P/s: có ví dụ về chiếu.. thì post lên nhé...!!!

mình có cách tìm dạng chuẩn phân tích từng bước theo thuật toán của thầy nè, cũng dễ hiểu:





Cho lược đồ < R, F >, với R
= ABCDE, F ={AB → CD, D → C , AC → EB, AE→ B }. Hãy


Xác định dạng chuẩn của < R, F >


. Xác định dạng chuẩn


Bước 1: Muốn xác định dạng chuẩn thì đầu tiên phải tìm khóa


-
Tìm các thuộc tính nằm hoàn toàn bên trái của fụ thuộc
hàm. Những thuộc tính này chắc chắn sẽ nằm trong khóa: A


-
Tìm các thuộc tính nằm ở bên trái và bên phải. Những
thuộc tính này có khả năng nằm trong khóa nếu thuộc tính hoàn toàn nằm bên trái
không bao đóng đc toàn bộ các thuộc tính: B,C,D,E


-
Tìm những thuộc tính nằm hoàn toàn bên phải. Ta sẽ loại
những thuộc tính này vì nó sẽ ko bao giờ tham gia vào khóa. Ở lược đồ này ko có


-
Trước tiên ta sẽ xét bao đóng của A. Nếu A có thể bao
đóng toàn bộ các thuộc tính khác thì A sẽ là khóa và ko cần xét thêm nữa


-
A+: ta thấy A ko
bao đóng đc các thuộc tính khác vì trong fụ thuộc hàm nó fải kết hợp với 1
thuộc tính khác mới suy ra thuộc tính khác đc à fải kết hợp A với các
thuộc tính B,C,D,E


-
AB+ : ABCDE
à
AB là 1 khóa. Khi đó ta ko cần
phải xét thêm ABC hay ABD … nữa. Nếu
AB ko là khóa thì fải tiếp tục
xét ABC, ABD v..v.. Vì khóa là tập thuộc tính nhỏ nhất có thể bao đóng toàn bộ
các thuộc tính khác


-
AC+ : ACEBD à
AC là 1 khóa (tương tự như trên )


-
AD+: ADCEB à
AD là 1 khóa (tương tự như trên )


-
AE+: AEBCD à
AE là 1 khóa (tương tự như trên)


à
tất cả các khóa của R là AB, AC,AD,AE


Bước 2: Xác định dạng chuẩn

	AB → CD	D → C	AC → EB	AE→ B
DC BC	Ok	Ko ok	Ok	ok
DC 3		ok
DC 2

à R đạt chuẩn 3


Lý giải: xét dạng chuẩn thì phải xét từ dc cao nhất xuống
nếu ko thỏa dc cao nhất thì mới xét tiếp dc thấp hơn.


Để thỏa dc bc thì vế trái phải là siêu khóa (ở đây là AB,
AC,AD,AE) như vậy có 3 fụ thuộc hàm đạt dc BC


Để thỏa dc 3 thì vế trái là siêu khóa (nghĩa là đạt dc BC
rùi) hoặc vế phải có thuộc tính nằm trong khóa. Ở đây ta thấy C là thuộc tính
nằm trong khóa à
Dà
C thỏa chuẩn 3


Đến đây ta ko cần xét. VÀ để lấy dc của R thì nó sẽ là dc
thấp nhất trogn tất cả dc mà fụ thuộc hàm đạt đc


Giải thích thêm: để thỏa dc 2 thì vế trái là siêu khóa( như
trên) hoặc vế trái ko nằm trong khóa. Tất nhiên là nó ko thỏa dc 3 rùi mới xét
đến dc 2.

-----------------------hết-------------------------------

Mới lụm được 1 bí kíp về cách tìm phủ tối tiểu, các bác xem tham khảo nha:

thuật toán vẫn là 3 bước thôi
bc1: Tách hết các về phải còn 1 thuộc tính
mẹo: dùng luật tách a->bc thành a->b và a->c
bc2: Loại các phụ thuộc hàm dư thừa
mẹo: quan sát các phụ thuộc hàm bắc cầu a->b,b->c,a->c thì bỏ a->c
quan sát vế phải, nếu có 2 phụ thuộc hàm(pth) cùng ra 1 kết quả thì có khả năng là dư thừa< nếu mỗi pth có 1 kq thì còn thừa j nữa>. Khi đó, ta kiểm tra bằng cách tìm bao đóng của vế trái của từng pth, nếu trong bao đóng xuất hiện vế trái của pth kia, thì pth này là dư thừa
bc3: loại bỏ thuộc tính dư thừa bên vế phải
lại mẹo: lại phải quan sát tiếp, 1 thuộc tính xuất hiện ở vế phải, lại xuất hiện tiếp ở vế trái(có từ 2 tht trở lên), thì có khả năng là dư thừa tht này
Mình chưa tìm đc mẹo để chứng minh, bạn đành tìm thêm trong bài tập nhé:-b

-----------------------

Bí kíp lịm trên net, không phải của mình, hehe

Nheo đã viết:Mới lụm được 1 bí kíp về cách tìm phủ tối tiểu, các bác xem tham khảo nha:

thuật toán vẫn là 3 bước thôi
bc1: Tách hết các về phải còn 1 thuộc tính
mẹo: dùng luật tách a->bc thành a->b và a->c
bc2: Loại các phụ thuộc hàm dư thừa<khoai tây nhất>
mẹo: quan sát các phụ thuộc hàm bắc cầu a->b,b->c,a->c thì bỏ a->c
quan sát vế phải, nếu có 2 phụ thuộc hàm(pth) cùng ra 1 kết quả thì có khả năng là dư thừa< nếu mỗi pth có 1 kq thì còn thừa j nữa>. Khi đó, ta kiểm tra bằng cách tìm bao đóng của vế trái của từng pth, nếu trong bao đóng xuất hiện vế trái của pth kia, thì pth này là dư thừa
bc3: loại bỏ thuộc tính dư thừa bên vế phải
lại mẹo: lại phải quan sát tiếp, 1 thuộc tính xuất hiện ở vế phải, lại xuất hiện tiếp ở vế trái(có từ 2 tht trở lên), thì có khả năng là dư thừa tht này
Mình chưa tìm đc mẹo để chứng minh, bạn đành tìm thêm trong bài tập nhé:-b

-----------------------

Bí kíp lịm trên net, không phải của mình, hehe

..~~~>> bước 2 và 3 cóa vấn đề rùi,,... Nheo ơi... nó làm seo ý... hì hì... nếu cóa phát biểu sai thì đừng trách e....
Theo Ly thì như thế này:
- Bc1: phân rã VPhai: tức tách hết các vế phải còn 1 thuộc tính
vd: ta có a->bc, tách thành a->b và a->c
- Bc2: rút gọn Vtrai = cách loại bỏ thuộc tính dư thừa bên vế trái
vd: ta có ab->c, ta tính a+, b+ . Nếu a+ =ac -> PTH này thành a->c (b dư thừa.. nên bỏ b)
- Bc3: rút gọn PTH = cách loại bỏ PTH dư
vd: phần này khó gthich we'... nói chung nhìn bên Vphai thấy nó có nhiều đg đi thì ta xét.. có bỏ đc đường nào hem..??

Nheo đã viết:Mới lụm được 1 bí kíp về cách tìm phủ tối tiểu, các bác xem tham khảo nha:

thuật toán vẫn là 3 bước thôi
bc1: Tách hết các về phải còn 1 thuộc tính
mẹo: dùng luật tách a->bc thành a->b và a->c
bc2: Loại các phụ thuộc hàm dư thừa
mẹo: quan sát các phụ thuộc hàm bắc cầu a->b,b->c,a->c thì bỏ a->c
quan sát vế phải, nếu có 2 phụ thuộc hàm(pth) cùng ra 1 kết quả thì có khả năng là dư thừa< nếu mỗi pth có 1 kq thì còn thừa j nữa>. Khi đó, ta kiểm tra bằng cách tìm bao đóng của vế trái của từng pth, nếu trong bao đóng xuất hiện vế trái của pth kia,=> chính xác (theo Mr. thầy) thì trong bao đóng có xuất hiện vế phải thì => thì pth này là dư thừa
bc3: loại bỏ thuộc tính dư thừa bên vế phải
lại mẹo: lại phải quan sát tiếp, 1 thuộc tính xuất hiện ở vế phải, lại xuất hiện tiếp ở vế trái(có từ 2 tht trở lên), thì có khả năng là dư thừa tht này
Mình chưa tìm đc mẹo để chứng minh, bạn đành tìm thêm trong bài tập nhé:-b

-----------------------

Bí kíp lịm trên net, không phải của mình, hehe

Thuật toán này không chính xác nha, nó sẽ làm cho bài toán giải bị dài dòng hơn bình thường đó. phần ghi chữ đỏ phía trên đó...

nguyenduc đã viết:

Nheo đã viết:Mới lụm được 1 bí kíp về cách tìm phủ tối tiểu, các bác xem tham khảo nha:

thuật toán vẫn là 3 bước thôi
-----------------------

Bí kíp lịm trên net, không phải của mình, hehe

Thuật toán này không chính xác nha, nó sẽ làm cho bài toán giải bị dài dòng hơn bình thường đó. phần ghi chữ đỏ phía trên đó...

..~~~>> đã sửa lại rùi đóa...

Tình hình là các buổi cuối mình không đi học .

Mình muốn hỏi BTPT BTTT và chuẩn hóa phương pháp các bước như thế nào . Mình bí lù . Xin các cao thủ lớp giúp đỡ . Mình nghĩ nhiều người cũng giống mình . Vì thấy Topic CSDL ko có sôi nổi như các topic trước .

Mạn phép .

Saturn đã viết:Tình hình là các buổi cuối mình không đi học .

Mình muốn hỏi BTPT BTTT và chuẩn hóa phương pháp các bước như thế nào . Mình bí lù . Xin các cao thủ lớp giúp đỡ . Mình nghĩ nhiều người cũng giống mình . Vì thấy Topic CSDL ko có sôi nổi như các topic trước .

Mạn phép .

1) Về BTTT: tức là bạn thả DLieu vào (cái này hẻm biết ghi bước ra seo... thui bạn ráng coi cái ví dụ 6.3, trang 158 nhé)
2) Về BTPT: tức xét các PTH trên các lược đồ con...cái này cũng hẻm biết ghi các bước ra seo... nếu bạn cóa thể tham gia học nhóm thì mình cóa thể chỉ.. chứ bảo viết trình tự thì hơi khó...
3) Về Chuẩn hóa: cóa 2 phương pháp
a) Tiếp cận phân rã: (trang.61)
- tìm tập khóa.
- rã theo vi phạm.
b) tiếp cận tổng hợp (tr. 163)
- tìm phủ tối tiểu
- ghi lại các lược đồ con (đây là cách gthich of mình cho dễ hiểu, còn trong sách ghi là: Phát sinh) - tức là từ các PTH of phủ tối tiểu.. bạn ghi ra các lược đồ con
- nhóm: các lược đồ có khóa tương đương nhau thì nhóm lại.. (nếu cần)
- bổ sung: các thuộc tính thiếu (nếu cần).
P/s: để hiễu rõ.. khuyên bạn tham gia đi câu cá đi.. cóa gì théc méc.. thì hỏi Pà Kon hen...