CHƯƠNG V: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU

Cơ sở dữ liệu (CSDL) là nơi lưu trữ lâu dài các dữ liệu của hệ thống ở bộ nhớ
ngoài. CSDL này phải được tổ chức tốt theo hai tiêu chí:
1. Hợp lý, nghĩa là phải đủ, không dư thừa.
2. Tiện lợi khi truy nhập, nghĩa là thao tác tìm kiếm, cập nhật, bổ sung và loại
bỏ các thông tin phải diễn ra một cách nhanh chóng, thu
ận tiện.
Nội dung của chương này là giới thiệu một số công cụ thường dùng trong quá
trình xây dựng CSDL.
I. PHỤ THUỘC HÀM

Khái niệm về phụ thuộc hàm (trong một quân hệ) là một khái niệm có tầm quan
trọng hết sức lớn đối với việc thiết kế các mô hình dữ liệu. Để biết được phụ thuộc
hàm là gì ta xét ví dụ sau:

Ví dụ: Þ Bấ
t hợp lý à đưa ra rang buộc nếu 2 bộ dữ liệu bằng nhau trên SOXE thì
bằng nhau trên LOAIXE và bằng nhau CHUSH
Þ Ràng buộc như vậy ta gọi là phụ thuộc hàm.
Như vậy: Phụ thuộc hàm là một loại ràng buộc dữ liệu nhằm đảm bảo các bộ dữ
liệu nếu bằng nhau trên tập thuộc tính này thì bằng nhau trên tập thuộc tính khác.

}
R⊆ΥΧΥ→
Χ
,/
SOXE LOAIXE
CHUSH 92N95501 DREAMII NAM
92N95502 WAVE@ HOA
92N95504 DREAMII MY
92N95501 @ NAM
XEMAY=
· Cho lược đồ quan R, F là một tập phụ thuộc hàm trên R. Một quan hệ tương
ứng với R chỉ được gọi là thể hiện của R nếu quan hệ đó thỏa F.
Định nghĩa:

Cho một quan hệ r định nghĩa trên lược đồ quan hệ R: X, Y Í R. Xét quan hệ
r, giả sử thỏa thuộc hàm X®Y và nếu không tồn tại một tập con thật sự X’ của
X sao cho r cũng thỏa phụ thuộc hàm X®Y thì ta nói Y phụ thu
ộc hàm đầy đủ
vào X trong r.
Người ta dùng ký hiệu FD (Functional Dependency) để chỉ phụ thuộc
hàm và FFD (Functinoal Dependency) để chỉ phụ thuộc hàm đầy đủ.
Định lý 2.1:

Cho một quan hệ r định nghĩa trên lược đồ quan hệ R. X,Y R, ta có:
-
X ® Y là phụ thuộc hàm trên r khi và chỉ khi X là khóa của quan hệ r(XY).
-


Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng
trên quan hệ r và f: X ® Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ
tiên đề Armstrong thì f đúng trên r.
b. Bổ đề 2:

A4: Tính hợp: Nếu X® Y và X ® Z thì X ®Y Z.
A5: Tính tự bắc cầu: Nếu X
→
Y và WY
→
Z thì XW
→
Z.
A6: Tính tách: Nếu X
→
Y và Z
→
Y thì X
→
Z.
c. Bao đóng của tập thuộc tính:Định nghĩ
a:

Cho lược đồ quan hệ R, tập thuộc tính hàm F trên R . X R, bao đóng của X
theo F là một tập các thuộc tính được định như sau:
X

F
= ABC

Thuật toán tìm bao đóng của tập thuộc tính trong lược đồ quan hệ:
- Cho tập phụ thuộc hàm F trên tập thuộc tính R và một tập con các thuộc tính
X, X
+
ta xuất phát từ thuộc tập X và bổ sung dần cho X các thuộc tính vế phải P
của các phụthuộc hàm T
→
P Î F thỏa điều kiện T X. Thuật toán sẽ dừng khi
không thể bổ sung thêm thuộc tính nào cho X.
Thuật toán :

Đầu vào
: - LĐQH p = (R, F )
- Tập thuộc tính X R Đầu ra
: X
+
F
= {A /A R , F |= X
→
A }Phương pháp:


Ta có :
A
+
= AED

AF
+
= AFECDB.

d. Bổ đề

X
→
Y có thể suy dẫn từ F nhờ hệ Armstrong khi và chỉ khi Y X
+

Chứng minh
() Nếu F |= X
→
Y thì Y X
+

Đặt Y = A
1,
A
2,…
A
n

A

∈
⊆
∪
⊆
⇒
⊆
∀ ∈
⇒
∈
⇒
⊆
⇐
⊆
A
A
i
( i=1,…,n), A
i
Î

X
+

F |= X
→
A
i
(
i
= 1,…,n)

¹ R.Phương pháp:

:= R {K là khóa}
or mỗi A Î R do
F (K\A)
+

Ví dụ
: Cho quan hệ r trên lược đồ quan hệ R=(A,B,C,D) và tập phụ thuộc hàm
F:
F= {AB C, C A, B D}. Tìm khóa của lược đồ quan hệ R.

Ta có:

+ giả sử K là khóa, ta có: K= ABCD
+ Loại A trong K ta được K = BCD (1), nếu loại C trong K ta được K = ABD (2)
+ Loại D trong K ở (1) ta được K = BC là khóa
+ Loại D trong K (2) ta được K = AB là khóa.
+Vậy khóa của lược đồ quan hệ: K ={BC, AB}

Nhược điểm: +Bắt đầu tập khoía với số lượng thuộc tính lớn
+Xét tất cả
thuộc tínhtrong R(A X).

Nhận xét:

+Những thuộc tính nào xuất hiện duy nhất ở phía phải tập phụ thuộc hàm
a) Cải tiến:

T:= X
X
→
YF
P := Y
X
→
Y F
K:=(R\P) (T P)
For mỗi thuộc tínhA T Pdo
If (K\A)
+
=R then

K=K\A
Return k;
Như vậy trong cả 2 phương pháp trên ta có kết luận.
Bắt đầu với một siêu khóathid ta có thể tồn được khóa
+ Nếu (R\P)
+
=R thì được đồ quan hệ R chỉ có duy nhất một khkóa

+ Nếu T P= Æ thì trên lược đồ quan hệ Rchỉ có duy nhất 1 khóalà R
f
. Dùng đồ thị của tập phụ thuộc hàm để xác định khóa của một lược đồ
quan hệ

∈∩
∩
A
B
A
B
C
A
B
D
- Hàm phụ thuộc A ® BC Đồ thị của một tập phụ thuộc hàm:Cho một tập phụ thuộc hàm F,ta có thể biểu
diển thành một đồ thịvới qui tắc: Mỗi một thuộc tính là một đỉnh trong đồ thị.
Ví dụ
:
Cho một tập phụ thuộc hàm F={A ®B, AB ®C, B®D,CD®E} ta biểu diễn
thành đồ thị sau:
Trong đồ thị, ta định nghĩa :
Đỉnh gốc: là đỉnh mà ch
ỉ có điểm đi của mủi tên.
Ví dụ:
Đỉnh A của đồ thị trên


Định nghĩa 1

- Ta nói F suy ra G, ký hiệu F|= G, nếu và chỉ nếu G
+
Í F
+
.

- Ta nói F và G tương đương, ký hiệu F º G, nếu và chỉ nếu F|=G và G|=F, khi
đó ta nói G là một phủ của F và ngược lại.

Định nghĩa 2

Tập phụ thuộc hàm F gọi là tối thiểu nếu:
1. "f ÎF Þ X ® A (vế phải chỉ có 1 thuộc tính)
C
A
B
C
A
B
C
D
E
2. Không tồn tại f= X ® A Î F và Z Ì X thỏa F
+
= (F\{F} È {Z A})
+



X ® A
1
A
2
A
n
thay bởi X ® A
1
, X ® A
2
, X ® A
n
.
·

Cho 1 tập phụ thuộc hàm F, phụ thuộc hàm X ® A Î F là thừa nếu:
+ Một tập phụ thuộc hàm được gọi là không dư thừa nếu không có bất cứ một
phụ thuộc hàm nào là thừa.
+ Cho một tập hợp thuộc hàm F, X "A Î F. X ® A là thừa A Î X
+
F\{A ®A}
Phương pháp để loại các thuộc tính dư thừa trong F:

For mỗi X ® A Î F do
IF A Î X
+

thừa.
(3) Không tồn tại bất cứ 1 phụ thuộc hàm nào thừa.
Cho một tập phụ thuộc hàm F nếu G là tập phụ thuộc hàm tương đương với F.
Mà G là cực tiểu thì ta nói G là phủ cực tiểu của F.
·Phương pháp để tìm phủ cực tiiểu của R.

Bước 1: Làm cho F thỏa mãn điều kiện (1)
Bước 2: Làm cho F thỏa mãn điều kiện (2)
Bước 3: Làm cho F thỏa mãn điều kiện (3)
II. TÁCH MỘT QUAN HỆ
Như ta đã biết mô hình quan hệ do cold đề xuất năm 1970, có những ưu điểm
vượt trội so với các mô hình dữ liệu trước đó:
-

Đơn giản
:
các dữ liệu được biểu diễn dưới dang duy nhất, là các bảng giá trị,
khá tự nhiên và dễ hiểu đối vớimọi người sử dụng.
-

Chặt chẽ
:
Các khái niệm được hình thức hóa cao ,cho phép sử dụng các
công cụ
Toán học,các thuật toán.
- Trựu tượng hóa cao: mô hình chỉ ở mức quan niệm, nghĩa là độc lập với các
mức vật lý, với sự cài đặt, với thiết bị. Nhờ đó mà làm tăng thêm tính độc lập

i
R,i=1…n.
R
1
R
2R
3
R
n
và R
i
R
J
với i j.
Ví dụ
: Với lược đồ quan hệ :r
(M_HANG,MAKH,TENKH,DCKH,SOLUONG,DONGIA)tacó phụ thuộchàm :
r1(M_HANG,MAKH,SOLUONG,DONGIA),r2(MAKH,TENKH,DCKH)
Việc phân rã một lược đồ phụ thuộc hàm xác định trên lược đồ ấy .
a. Phép tắc bảo toàn thông tin

Định nghĩa 1:

Cho một lược đồ quan hệ Rvà tập phụ thuộc hàm F trênR .Phép tách của lược
đồ quan hệ R là việc thay bởi một tập các lược đồ R1, R2, , Rk sao cho R1 È È
Rk = R
⊆


Vào
: R, F, r =(R1,R2,….Rk);R=A1,A2,….,An

Ra
: Kết luận r có bảo tyòan thông tin (theo F).
Phương Pháp

Bước 1:
Xây dựng bảng có k dòng và cột
- Mỗi một dòng tương ứng với một lượt đồ tách.
- Mỗ
i một cột tương ứng với 1 thuộc tính của R.

Tiến hành khởi tạo giá trị các ô: Ô tại vị trí (dòng i,cột j)=
Bước 2:
Biến đổi bảng (lặp )
Xét lần lượt từng phụ thuộc hàm X

∈
bjj nếu Aj Î Ri
và ngược lại ta nói phép tách không bảo toàn thông tin .
Ví dụ: Cho lược đồ quan hệ R(A,B,C,D,E,F,G) thỏa mãn phụ thuộc hàm:
F={A ®BC, AD ® EF, D ® G}
1) Kiểm tra phép tách r ={ABC, AEF, ADG} có bảo toàn thông tin không ?
Ta có:

Xét A ® BC
(2,2) = a
2(3,2) = a
2

(2,3) = a
3

(3,3) = a
3

Ta được bảng sau:
Xét AD ® EF (không thay đổi)
D ® F(không thay đổi)
A ® BC (không thay đổi)
AD ® EF (không thay đổi)
D ® G (không thay đổi)
2) Kiểm tra phép tách r ={ABCE, ADEF,DG} có bảo toàn thông tin không?
Ta có:


AEF
a
1
b
22
b
23
b
24
a
5
a
6
b
27

ADG
a
1
b
32
b
33
a
4
b
35
b
36

5
a
6
b
27

ADG
a
1
a
2
a
3
a
4
b
35
b
36
a
7

A B C D E F G
ABCE
a
1
a
2
a
3

b
33
a
4
b
35
b
36
a
7

Vậy phép tách bảo toàn thông tin.
Định lý:
Cho <R,F>phép tách ρ(R1,R2)của R là bảo toàn thông tin khi và ch
ỉ

khi
F|= (R1 Ç R2)
→
R1\R2.
Ví dụ:

R(A,B,C,D,E)
F= {A
→
B, AC
→
DE
r= (AB, ACDE) AB Ç ACDE ® AB\ ACDE


là hai tập con khác nhau của R, Y là phụ thuộc hàm đầy đủ vào X nếu Y là phụ
thuộc hàm vào X như
ng không phụ thuộc hàm vào bất kỳ tập hợp con thực sự nào
của X.
A B C D E F G
ABCE
a
1
a
2
a
3
b
14
a
5
b
16
b
17

ADEF
a
1
a
2
a
3
a
4

Ví dụ: Kiểu record ® không nguyên tố.
+ Cho lược đồ quan h
ệ R(B,O,I, S, Q,D) và tập phụ thuộc hàm:
F={S ® D, I ® B, IS ®Q, B ® O}
·

Dạng chuẩn 1 được xem như là một qui ước trên lược đồ quan hệ và tức
nhiên ta thừa nhận lược đồ luôn có dạng chuẩn 1.
d. Dạng chuẩn 2 (Second Normal Form 3 NF)

Lược đồ quan hệ R được gọi là 2 NF nếu X ® A trên R(A X) thì
+ Hoặc là A là thuộc tính khóa.
+ Hoặc X không là phải là tập con thật sự của khóa.
Ví dụ: Cho lược đồ quan hệ R(A,B, C, D) thỏa mãn phụ thuộc hàm:
F={A ® BCD, C ® D}
e. Dạng chuẩn 3 (Third Normal Form 3NF)

Lược đồ quan hệ R
được gọi là 3NF nếu X ® A trên R (A X) thì
+ Hoặc A là thuộc tính khóa
+ Hoặc X là siêu khóa
Ví dụ: Cho lược đồ quan hệ A(A,B,C,D) thỏa mãn phụ thuộc hàm
F={AB ® CD, D ® A}
f. Dạng chuẩn BCNF (BOYCE- CODD)

Lược đồ quan hệ R được gọi là BCNF nếu X ® A trên R (A X) thì
+ X là siêu khóa
Ví dụ: Cho lược đồ quan hệ R(A, B,C, D) thỏa mãn phụ thuộc hàm
F={ AB ® C, BC ®A}
g. Dạng chuẩn một lược đồ cơ sở dữ liệu:


Bước2:
-Nếu trong R có thuộc tính không xuất hiện trong PTH thì đưa các
thuộc tinh này thành 1 lược đồ trong , loại các thuộc tính này khỏi R
Bước3:
Nếu tồn tại một phụ thuộc liên quan đến tất cả các thuộc tính thì:
, kết thúc

Ngược lại qua bước 4;

Bước 4:
Với mỗi các phụ thuộc hàm X ® A, X ®A2, , X ®Ak thì tạo thành 1
lược đồ XA1A2 Ak.

Bước 5:
Nếu tồn tại R
i
, R
j
Î r mà R
i
Î R
j
thì loại R
i
khỏi r

Ví dụ:
R(A, B,C, D,E,F,G), F={AB ® C, AB ® D, C ®B, CD ® E}
- F: đã là phủ cực tiểu

R∪=
ρ
ρ