1

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA HỆ THỐNG THÔNG TIN

ĐẶC TẢ THUẬT TOÁN MÔN THIẾT KẾ CƠ SỞ DỮ LIỆU Sinh viên thực hiện :
 Trần Hưng Nghiệp – 07520245
 Nguyễn Thành Phương – 07520285
 Nguyễn Ngọc Linh – 07520194

GIÁO VIÊN HƯỚNG DẪN: Phan Nguyễn Thụy An

Thành phố Hồ Chí Minh, tháng 1 năm 20

2

CHƯƠNG 1: TỔNG QUAN
1. Đặt vấn đề:
Cơ sở dữ liệu quan hệ được xây dựng theo lý thuyết do E.F.Codd giới thiệu năm
1970. Mô hình quan hệ có nhiều ưu điểm hơn hẳn các mô hình trước nó và từ năm
1980 đã trở thành mô hình được dùng rộng rãi để phát triển hệ quản trị CSDL.

dạng chuẩn.
2. Cơ sở kiến thức:
a. Phụ thuộc hàm:
Phụ thuộc hàm (functional dependancy) là một công cụ dùng để biểu diễn một cách hình
thức các ràng buộc toàn vẹn. Phương pháp biểu diễn này có rất nhiều ưu điểm, và đây là một
công cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ sở dữ liệu. Phụ thuộc hàm có ứng
dụng trong việc giải quyết các bài toán như: tìm khoá, tìm phủ tối thiểu, xác định dạng
chuẩn…
Định Nghĩa Phụ Thuộc Hàm:
Cho R(A
1
,…,A
n
) là một sơ đồ quan hệ với tập thuộc tính U={A
1
,…,A
n
}. X và Y là tập
con của U. Xét một quan hệ cụ thể r nao đó. Ta nói X  Y (đọc là: X xác định hàm Y hoặc Y
phụ thuộc hàm vào X) nếu với mỗi cặp bộ u, v của r thỏa:
u[X] = v[X]  u[Y] = v[Y]
Để chứng minh và suy ra các phụ thuộc hàm khác từ các phụ thuộc hàm đã có ta dùng hệ
tiên đề Armstrong:
Gọi R(U) là lược đồ quan hệ với U = {A
1
,…,A
n
} là tập các thuộc tính. X, Y, Z,
W  U. Hệ tiên đề Armstrong bao gồm:
F1) Tính phản xạ:

}
c. Bài toán thành viên:
Qua phần trên ta nhận thấy X
+
được định nghĩa thông qua F
+
. Vấn đề nảy sinh khi
nghiên cứu lý thuyết CSDL là: Cho trước tập các phụ thuộc hàm F và một phụ thuộc
hàm f, bài toán kiểm tra có hay không f ∈ F
+
gọi là bài toán thành viên.
d. Siêu khóa, khóa:
Cho quan hệ R(U, F), với U là tập thuộc tính, F là tập phụ thuộc hàm. Cho K ⊆ U.
Định nghĩa Siêu Khoá Của Quan Hệ :
K là một siêu khoá của R nếu thoả điều kiện sau:
K xác định hàm mọi thuộc tính trong U. Tức là K
+
= U.
Định nghĩa Khoá Của Quan Hệ :
5

K là một khoá của R nếu thỏa:
K là siêu khóa và không có siêu khóa nào nhỏ hơn K. Tức là K
+
= U và
H⊂K ⇒ H
+
≠ U.
Một lược đồ quan hệ có thể có nhiều siêu khoá, nhiều khoá.
e. Phủ tối thiểu:

iii) Dạng chuẩn 3: R được xem là đạt dạng chuẩn 3 nếu nó đạt dạng chuẩn 2 và
mọi thuộc tính không khóa đều không phụ thuộc bắc cầu vào khóa.
Một cách định nghĩa khác : R được xem là đạt dạng chuẩn 3 nếu mọi phụ
thuộc hàm không hiển nhiên trong F đều có vế trái chứa khóa hay vế phải nằm
trong khóa
iv) Dạng chuẩn B – C : R được xem là đạt dạng chuẩn B – C nếu mọi phụ thuộc
hàm không hiển nhiên trong F đều có vế trái chứa khóa.
3. Yêu cầu cho đề tài:
 Đề tài phải trình bày rõ ràng các thuật toán sau và các thuật toán bổ trợ:
o Thuật toán tìm Bao đóng
o Thuật toán kiểm tra Phụ thuộc hàm thành viên
o Thuật toán tìm Khóa
o Thuật toán tìm Phủ tối thiểu
o Thuật toán xác định Dạng chuẩn
 Cài đặt thử nghiệm các thuật toán trên trong phần mềm có giao diện đồ họa, nhập liệu
trực tiếp hay từ file dữ liệu nhập.

7

for each (pth P->Q) in F
If P  TapMoi Then
TapMoi = TapMoi  Q
End If
Next (pth P->Q)
End While
Return TapMoi
}

c. Độ phức tạp, nhận xét, cải tiến:
Thuật toán trên có độ phức tạp tính toán O(n
2
) với n là số thuộc tính của lược
đồ quan hệ R.
Thuật toán có thể cải tiến bằng cách: Sau khi thêm Q vào TapMoi, ta loại bỏ
pth P->Q ra khỏi F. Vì ta đã thêm Q rồi nên không cần xét thêm nữa.
Ta có thể xây dựng thuật toán với độ phức tạp tuyến tính, sử dụng LIST.
2. Thuật toán kiểm tra phụ thuộc hàm thành viên:
Cho lược đồ quan hệ R(U, F), tập thuộc tính U, tập phụ thuộc hàm F. Cho phụ thuộc
hàm f: X->Y. Kiểm tra xem f có thuộc F
+
không?
a. Ý tưởng:
- X->Y  F
+
 X
+
F
 Y
b. Mô hình hóa:

khóa của R?
a. Ý tưởng: (Tìm khóa Vét cạn)
- Tìm tất cả các siêu khóa :
o Liệt kê tất cả các tập con của U
o Tìm bao đóng của các tập con đó
o Nếu Bao đóng = U thì tập con đó là siêu khóa.
- So sánh các siêu khóa, loại bỏ cái lớn hơn đi được các khóa.
b. Mô hình hóa:
 Input: Tập thuộc tính U, Tập phụ thuộc hàm F.
 Output: Tập các khóa K.

TimKhoaVetCan(U,F)
{
Dim CacTapCon, CacSieuKhoa

CacTapCon = TimCacTapCon(U)
for each TapCon in CacTapCon
{
if TimBaoDong(TapCon, F) = U then
10

CacSieuKhoa = CacSieuKhoa  {TapCon}
end if
}
'loại bỏ các siêu khóa không nhỏ hơn
for each SieuKhoa1 in CacSieuKhoa
for each SieuKhoa2 in CacSieuKhoa
{
if SieuKhoa2  SieuKhoa1 then
CacSieuKhoa = CacSieuKhoa \ SieuKhoa1

 Input: Tập thuộc tính U, Tập phụ thuộc hàm F.
 Output: Tập các khóa K.

TimKhoaDoThi(U, F)
{
for each (pth P->Q) in F
{
VT = VT  P
VP = VP  Q
}
Goc = VT \ VP 'chi nam o ve trai
TrungGian = VT \ (VT \ VP) 'Nam o ca hai ve
CoLap = U \ VT \ VP

SK = Goc  CoLap
If TimBaoDong(SK, F) = U Then
Return SK 'là khóa duy nhất
Else
Dim CacTapcon, CacSieuKhoa
CacTapcon = TimCacTapCon(TrungGian)
For Each TapCon In CacTapcon
{
SKK = SK  TapCon
If TimBaoDong(SKK, F) = U Then
CacSieuKhoa = CacSieuKhoa  {SKK}
End If
}
'loại bỏ các siêu khóa không nhỏ hơn
for each SieuKhoa1 in CacSieuKhoa
for each SieuKhoa2 in CacSieuKhoa

e. Mô hình hóa:
 Input: tập phụ thuộc hàm F
 Output: Phủ tối thiểu của F: PTT(F)

TimPTT(F)
{
F = TachPTH(F)
F = LoaiPTHDuThua(F)
F = ThayThePTHKhongDayDu(F)
Return F
}
'
TachPTH(F)
{
for each (pth P->Q) in F
{
CacPhanTu = TimTungPhanTu(Q)
F = F \ (P->Q)
For Each PhanTu in CacPhanTu
F = F  (P->PhanTu)
}
} ThayThePTHKhongDayDu(F)
{
for each (pth P->Q) in F
{

13

}
}
}

'
LoaiPTHDuThua(F)
{
for each (pth f = P->Q) in F
{
P
+
(F\f)
= TimBaoDong(P, (F \ f))
if P
+
(F\f)
 Q then
F = F \ f
}
}
'

f. Độ phức tạp, nhận xét, cải tiến:
Thuật toán trên chỉ cho ta 1 PTT(F), các phủ tối thiểu khác có được khi ta thay đổi
thứ tự của các tập con khi thay thế các phụ thuộc hàm không đầy đủ.
5. Thuật toán xác định Dạng Chuẩn:
Cho lược đồ quan hệ R(U, F), tập thuộc tính U, tập phụ thuộc hàm F. Xác định dạng
chuẩn?
a. Ý tưởng:
- Tìm tất cả các khóa

}
'
DCBC(TapKhoa, F’)
{
for each (fth P->Q) in F’
{
if (Q  P) then
Re = false
for each K in TapKhoa
{
if (P  K) then
Re = true
Break;
end if
}
If Re = false then
Return false
End If
end if
}
15

return true
}
'
DC3(TapKhoa, F’)
{
for each (fth P->Q) in F’
{
if (Q  P) then

if (P  K) AND (P <> K) then
return false
end if
return true
} '
DC2_Old(TapKhoa, F, U)
{
TTKK = U
16

for each K in TapKhoa
TTKK = TTKK \ K

for each KK in TTKK
for each K in TapKhoa
{
TapCon = TimTapCon(K)
TapCon = TapCon \ K
for each TC in TapCon
if (TC
+
F
 KK) then
return false
end if
}
return true

* ( last(AB) = vị trí của B trong U, last(AB)=1 , last(AC) =2)
Debug mẫu
a. A B C D
b. AB AC AD BC BD CD
c. ABC ABD ACD BCD
d. ABCD
CHƯƠNG 3: CÀI ĐẶT CÁC THUẬT TOÁN
I. Cấu trúc dữ liệu
List được dùng làm cấu trúc lưu trữ chính vì đây là cấu trúc động, sử dụng tối ưu cho
bộ nhớ, và có các hàm cần thiết hỗ trợ như : Add, Addrange, index, RemoveAt …
Tập thuộc tính U: Dim str_U As List(Of String)
18

Mục đích: Mỗi thuộc tính là 1 string riêng biệt, có thể có khoảng trắng ở giữa.
Phụ thuộc hàm : Class F
Class F
Public Left As New List(Of String) 'Vế trái
của PTH, gồm 1 danh sách các string
Public Right As New List(Of String) 'Vế phải
của PTH, gồm 1 danh sách các string

Tập phụ thuộc hàm : Dim lst_F As List(Of F)
Tập con (Tập hợp gồm nhiều tập thuộc tính):
Dim lst_Tap_Con As List(Of List(Of String))
Tập khóa (Tập hợp gồm nhiều tập khóa)
Dim lst_Khoa As List(Of List(Of String))


flag = False
End If
If flag = False Then
Exit For
End If
Next

If flag Then
For dem2 = 0 To F(dem).Right.Count - 1
If str_kq.Contains(F(dem).Right(dem2))
= False Then
str_kq.Add(F(dem).Right(dem2))
End If
Next
End If
Next
Loop Until str_old.Count = str_kq.Count
Return str_kq
End Function
b. Tìm khóa
Private Function Tim_Khoa(ByVal lst_U As List(Of String),
ByVal lst_F As List(Of F)) As List(Of List(Of String))
Dim lst_Goc As New List(Of String) 'Các thuộc tính gốc
(1)
Dim lst_TG As New List(Of String) ' Các thuộc tính
trung gian (3)
Dim lst_R As New List(Of String) ' Các thuộc tính cô
lập ( rời) (4)
Dim lst_key As New List(Of String) ' Kết quả
Dim lst_kq As New List(Of List(Of String))

If lst_kq.Count > 0 Then
lst_kq.RemoveAt(0)
End If

Dim lst_Tap_Con As New List(Of List(Of String))
lst_Tap_Con = Tim_tap_Con_New(lst_TG)
Dim test As Integer
For i = 0 To lst_Tap_Con.Count - 1
test = 1
Dim lst_key_tmp As New List(Of String)
lst_key_tmp.AddRange(lst_key)
lst_key_tmp.AddRange(lst_Tap_Con(i)) 'Add
lần lượt các tập con vào khóa
If XPlusF(lst_key_tmp, lst_F).Count =
lst_U.Count Then

If lst_kq.Count = 0 Then
lst_kq.Add(lst_key_tmp)
Else 'Không add các siêu khóa
For j As Integer = 0 To lst_kq.Count -
1
If list_in(lst_kq(j), lst_key_tmp)
Then
test = 0
End If
Next

If test = 1 Then
lst_kq.Add(lst_key_tmp)
End If

'Kiểm tra và loại bỏ thuộc tính không đầy đủ
For i = 0 To lst_F.Count - 1
j = 0
While j < lst_F(i).Left.Count
lst_tmp.Clear()
lst_tmp.AddRange(lst_F(i).Left)
lst_tmp.RemoveAt(j)
If XPlusF(lst_tmp,
lst_F).Contains(lst_F(i).Right(0)) Then
lst_F(i).Left.RemoveAt(j)
j = -1
End If
j += 1
End While
Next

'Kiểm tra và loại bỏ phụ thuộc hàm dư thừa
i = 0
While i < lst_F.Count
lst_F_tmp.Clear()
lst_F_tmp.AddRange(lst_F)
lst_F_tmp.RemoveAt(i)
If XPlusF(lst_F(i).Left, lst_F_tmp).Count =
XPlusF(lst_F(i).Left, lst_F).Count Then
22

lst_F.RemoveAt(i)
i = -1
End If
i += 1

Return True
End Function

Private Function KT_Dang_Chuan_3(ByVal lst_F As List(Of
F), ByVal lst_U As List(Of String)) As Integer

Dim lst_Khoa As New List(Of List(Of String))
lst_Khoa = Tim_Khoa(lst_U, lst_F)
Dim bool_test As Integer
lst_F = Tim_Phu_TT(lst_F)

For i As Integer = 0 To lst_F.Count - 1
bool_test = 0 ' Vế trái là siêu khóa
23

For j As Integer = 0 To lst_Khoa.Count - 1
If list_in(lst_Khoa(j), lst_F(i).Left) Then
bool_test = 1
Exit For
End If
Next
If bool_test = 0 Then
For j As Integer = 0 To lst_Khoa.Count - 1 'Vế
phải nằm trong khóa, vế phải chỉ chứa 1 tt
If lst_Khoa(j).Contains(lst_F(i).Right(0))
Then
bool_test = 1
Exit For
End If
Next

If bool_test = 0 Then
Exit For
End If
Next
If bool_test = 0 Then
24

Return 0
Else
Return 1
End If
End Function

systems” (Volume 1&2). Computer Science Press.