Thiết kế là một bước khá quan trọng trong quá trình xây dựng một cơ sở dữ liệu. Trong hệ thống quản lý dữ liệu, các công việc chủ yếu được thực hiện không chỉ là thu thập dữ liệu, lưu trữ dữ liệu, và khôi phục các dữ liệu mà quan trọng hơn cả là chuyển đổi dữ liệu đó thành thông tin.
AMBIENT/
Chủ đề:
Nội dung Text: Báo cáo đồ án: Thiết kế cơ sở dữ liêu
- 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 07520556
MỤC LỤC
1. Bao đóng của tập X trên F
2. Khóa
3. Phủ tối tiểu
4. Xác định dạng chuần 2
5. Xác định dạng chuẩn 3
6. Xác định dạng chuẩn BC
- 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 07520556
//B 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 07520556
//B 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 đ ng v i G
thì thay VT->VP thành t pcon->VP và đ n b 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 đ ng v i G
thì thay VT->VP thành t pcon->VP và đ n b 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 đ ng v i G
thì thay VT->VP thành t pcon->VP và đ n b c4
}
//B c 4: K t thúc
- Báo cáo đ án TKCSDL 07520556
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
}
- 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:OLX-
bPqLb0cJ: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/CMSC661-
05/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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
