Mô tả:
Báo cáo đ án TKCSDL
07520556
ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÁO CÁO Đ
ÁN
MÔN THIẾT KẾ CƠ SỞ DỮ LIỆU
GVHD:
PHAN NGUYỄN THỤY AN
SVTH:
HUỲNH MINH LỘC-07520556
KHOA HỆ THỐNG THÔNG TIN
TP. HCM, NGÀY 2 THÁNG 1 NĂM 2010
Báo cáo đ án TKCSDL
MỤC LỤC
1.
2.
3.
4.
5.
6.
Bao đóng của tập X trên F
Khóa
Phủ tối tiểu
Xác định dạng chuần 2
Xác định dạng chuẩn 3
Xác định dạng chuẩn BC
07520556
Báo cáo đ án TKCSDL
07520556
1. Tìm bao đóng c a X trên F (X+ là bao đóng c n tìm)
a. Đ nh nghĩa:
Closure(X, F) = {A| X->A thu c F+}
b. Thu t toán:
Closure(X, F)
{
//B
c 1:
X+=X
//B c 2: l p cho đ n khi t p bao đóng c n tìm X+ không thay đ i
gì khi duy t qua m i ph thu c hàm trong F
do
{
Old=X+
foreach( VT->VP in F)
{
if (X+ ch a VT) thì
X+ +=VP
}
}while(Old!=X+)
//B
c 3: Tr v t p bao đóng. K t thúc
return X+
}
Báo cáo đ án TKCSDL
07520556
2. Tìm khóa
a. Đ nh nghĩa:
- Siêu khóa là t p thu c tính X sao cho Closure(X,F) = U
- Khóa là siêu khóa nh nh t
//G c là thu c tính ch có bên v trái c a m i pth trong F
//Nhánh là thu c tính có c bên v trái và bên ph i c a m i pth trong F
//Lá là thu c tính ch có bên v ph i c a m i pth trong F
//Treo là thu c tính n m đ n đ c c a m i pth trong F
b. Thu t toán
FindKey()
{
//B c 1: Duy t qua m i ph thu c hàm trong F tìm Treo, G c,
Nhánh và Lá
foreach(VT->VP in F)
{
Tìm:
1. G c
2. Nhánh
3. Lá
4. Treo
}
Báo cáo đ án TKCSDL
//B
07520556
c 2: Tính bao đóng c a Treo h i G c đ i v i F
if Closure(Treo h i G c) = t p U
{
Khóa+= (Treo h i G c)
//Đ n b
c4
}
//B c 3: Tìm t t c t p con c a c a t p Nhánh, h i t p con
đó v i treo và g c tính bao đóng so sánh tìm khóa
//Duy t qua t t c các thu c tính t c a t p trung gian
if Closure(Treo h i G c h i t) = U
{
Key += (Treo h i G c h i t)
Lo i thu c tính t ra kh i N
}
//Duy t qua t t c các t p con c a t p trung gian có 2 ph n t
if Closure(Treo h i G c h i t pcon) = U
{
Key += (Treo h i G c h i t pcon)
}
Báo cáo đ án TKCSDL
07520556
//Duy t qua t t c các t p con c a t p trung gian có 3 ph n t
if Closure(Treo h i G c h i t pcon) = U
{
Key += (Treo h i G c h i t pcon)
}
........................................
..........................................
//Duy t qua t t c các t p con c a t p trung gian có TG.Count ph n t
if Closure(Treo h i G c h i t pcon) = U
{
Key += (Treo h i G c h i t pcon)
}
//B
c 4: K t thúc
}
3.
Tìm ph t i ti u G
a. Đ nh nghĩa: G là ptt c a F khi và ch khi
Báo cáo đ án TKCSDL
07520556
M i X->A in G, M i B in X (B là t p con th c s c a X)
- A ch có 1 thu c tính
- Không t n t i ( F- {X->A} ) t
ng đ
ng v i G
- Không t n t i ( F- {X->A} ) h i {B}->A t
ng đ
ng v i G
b. Thu t toán:
//B c 1: Bi n t t c các ph thu c hàm thành nh ng ph thu c hàm có 1
thu c tính v trái
foreach ( VT->VP in F)
{
foreach(t in VT.SubSet(1))
{
G+=VT->t
}
}
F=G
//B
c 2: Lo i b nh ng ph thu c hàm d th a
foreach (VT->VP in F)
{
Tính Closure(VT, G b VT->VP) có ch a VP
thì b VT->VP ra kh i G
}
Báo cáo đ án TKCSDL
//B
07520556
c 3: Bi n đ i các ph thu c hàm ch a đ y đ thành đ y đ
F=G
foreach (VT->VP in F)
{
//Duy t qua m i t p con th c s c a VT có 1 ph n t
if (G b VT->VP) h i (t pcon->VP) t
ng đ
thì thay VT->VP thành t pcon->VP và đ n b
ng v i G
c4
//Duy t qua m i t p con th c s c a VT có 2 ph n t
if (G b VT->VP) h i (t pcon->VP) t
ng đ
thì thay VT->VP thành t pcon->VP và đ n b
ng v i G
c4
....................................
....................................
//Duy t qua m i t p con th c s c a VT có VT.Count - 1 ph n t
if (G b VT->VP) h i (t pcon->VP) t
ng đ
thì thay VT->VP thành t pcon->VP và đ n b
}
//B
c 4: K t thúc
ng v i G
c4
Báo cáo đ án TKCSDL
3. Xác đ nh d ng chu n 2:
a. Đ nh nghĩa: R đ t 2NF khi và ch khi M i X->A in F
Ho c X không là t p con th c s c a khóa
Ho c A là thu c tính khóa
b. Thu t toán
foreach ( X->A in F)
{
if X là t p con th c s c a khóa và A là thu c tính khóa
R ko đ t d ng chu n 2
}
R đ t d ng chu n 2
4. Xác đ nh d ng chu n 3:
a. Đ nh nghĩa: R đ t 3NF khi và ch khi M i X->A in F
Ho c X siêu khóa
Ho c A là thu c tính khóa
b. Thu t toán
foreach ( X->A in F)
{
if X không ch a khóa và A không là thu c tính khóa
R ko đ t d ng chu n 3
}
07520556
Báo cáo đ án TKCSDL
07520556
R đ t d ng chu n 3
5. Xác đ nh d ng chu n BC:
a. Đ nh nghĩa: R đ t BCNF khi và ch khi M i X->A in F
Ho c X siêu khóa
b. Thu t toán
foreach ( X->A in F)
{
if X không ch a khóa
R ko đ t d ng chu n BC
}
R đ t d ng chu n BC
6. References:
1. http://google.com
2. http://74.125.153.132/search?q=cache:OLXbPqLb0cJ:www.uit.edu.vn/forum/index.php%3Fshowtopic%3D256
%26st%3D20+thuat+toan+tim+phu+toi+thieu&cd=4&hl=vi&ct=cl
nk&gl=vn
3. http://www.csee.umbc.edu/~pmundur/courses/CMSC66105/Minimal-cover-example.pdf
4. http://clem.mscd.edu/~tuckerp/CSI3310/C14.2.html
5. http://www.dcs.ed.ac.uk/home/opb/dbs/notes/03-4up.pdf
6. http://hauionline.com/showthread.php?t=8626
7. http://www.dis.uniroma1.it/~catarci/DBslides/Mod3L4/tsld024.ht
m
Báo cáo đ án TKCSDL
07520556
- Xem thêm -