Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
MỞ ĐẦU
Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được tập trung
nghiên cứu của tin học nhằm giải quyết các vấn đề về quản lý, tìm kiếm và xử
lý thông tin trên các hệ thống thông tin lớn, đa dạng và phức tạp. Cùng với sự
phát triển mạnh mẽ của tin học và máy tính trong đời sống kinh tế, văn hoá, xã
hội,...việc nghiên cứu CSDL ngày một phát triển rộng rãi và hoàn thiện hơn.
Hiện nay có rất nhiều loại mô hình cho các hệ CSDL như:
Mô hình mạng (Network model)
Mô hình phân cấp (Hierachical model)
Mô hình quan hệ (Relational model)
Từ những năm 1970, mô hình dữ liệu quan hệ do E.F Codd đưa ra đã
tạo ra cơ sở toán học chặt chẽ với cấu trúc hoàn chỉnh làm nền tảng cho các
vấn đề nghiên cứu lý thuyết về CSDL. Với ưu điểm về tính cấu trúc và khả
năng hình thức phong phú, CSDL quan hệ dễ dàng mô phỏng các hệ thông tin
đa dạng trong thực tiễn tạo điều kiện lưu trữ thông tin tiết kiệm, có tính độc
lập và nhất quán cao, dễ sửa đổi, bổ sung cũng như khai thác dữ liệu, mô hình
quan hệ có sự phát triển mạnh mẽ về lý thuyết và ngày càng được sử dụng
rộng rãi trong việc thiết kế các CSDL lớn và phức tạp. Ngôn ngữ quản trị dữ
liệu cho mô hình quan hệ khá trong sáng và tự nhiên, do đó dễ học, dễ sử
dụng, điều này lý giải cho sự phát triển mạnh mẽ không ngừng của các hệ
quản trị CSDL trên máy tính IBM-PC như: Dbase, Foxbase, Foxpro, Access,
SQL Forwin, Oracle,...
Mô hình dữ liệu quan hệ đặt trọng tâm hàng đầu không phải tính hiệu
quả của máy tính, mà sự mô phỏng trực quan dữ liệu theo quan điểm người
dùng, cung cấp mô hình dữ liệu đơn giản, dễ hiểu, chặt chẽ và có khả năng tự
Hoàng Văn Thủy
1
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
động hoá thiết kế. Trong bản luận văn này em đã trình bầy một số kiến thức
cơ bản về cơ sở dữ liệu và áp dụng kiến thức này xây dựng chương trình:

1.7 Khoá của quan hệ, lược đồ quan hệ, họ f . . . . . . . . . . . . . . . . . . . . . . . .
13
1.8 Tập các phản khóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.9 Nửa dàn giao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.10 Hệ bằng nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.11 Thể hiện . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.12 Sơ đồ quan hệ tương đương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
1.13 Thuộc tính cơ bản, thuộc tính thứ cấp . . . . . . . . . . . . . . . . . . . . . . . . .
22
1.14 Một số thuật toán liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
CHƯƠNG II: DẠNG CHUẨN ĐỐI VỚI QUAN HỆ VÀ
SƠ ĐỒ QUAN HỆ . . . . . . . . . . . . . . . . . . . . 37
Hoàng Văn Thủy
3
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
2.1 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.2 Dạng chuẩn 2NF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40
2.3 Dạng chuẩn 3NF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43
2.4 Dạng chuẩn BCNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5 Các thuật toán liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

CHƯƠNG III: CHUẨN HÓA DỮ LIỆU TRONG THỰC TẾ . . .
52
3.1 Dạng chuẩn thứ nhất (1NF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
3.2 Dạng chuẩn 2 (2NF ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
3.3 Dạng chuẩn 3 (3NF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .58
3.4 Dạng chuẩn Boyce Codd (BCNF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60

(CSDL) như: Dbase, Foxbase, Foxpro, Oracle, Mega,..
1.1 Quan hệ .
Định nghĩa 1.
Cho R={a
1
,a
2
,..,a
n
} là một tập hữu hạn không rỗng các tập thuộc tính.
Mỗi thuộc tính a
i
có một miền giá trị là D
ai
. Khi đó r là một tập các bộ
{h
1
,h
2
,..,h
m
} được gọi là một quan hệ trên R với h
j
(j =1, 2,..,m) là một hàm:
h
j
: R → ∪ Da
i
Hoàng Văn Thủy
5

)
h
2
(a
1
) h
2
(a
2
) ............... h
2
(a
n
)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
h
m
(a
1
) h
m
(a
2
) ............... h
m
(a
n
)
Nhận xét:
- Định nghĩa này là quan trọng, toàn bộ cơ sở dữ liệu dựa trên định

Thuộc tính Tên hàng là một xâu ký tự có độ dài không quá 30
Thuộc tính Mầu sắc là một xâu ký tự có độ dài không qúa 15
Trọng lượng là một số nguyên không quá 10
Tỉnh là một xâu ký tự không quá 20
Như vậy ta có tập thuộc tính
MẶTHÀNG = { Mã hàng, Tên hàng, Màu sắc, Trọng lượng, Tỉnh}
Ở đây D
Mã hàng
là tập các xâu ký tự độ dài không quá 5
D
Tên hàng
là tập các xâu ký tự độ dài không quá 30
D
Màu sắc
là tập các xâu ký tự độ dài không quá 15
D
Trọng lượng
là tập các xâu ký tự độ dài không quá 10
D
Tỉnh
là tập các xâu ký tự độ dài không quá 20
Hoàng Văn Thủy
7
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
Khi đó chúng ta có các quan hệ r = {h
1
, h
2
, h
3

,.., a
n
} là tập các thuộc tính, r = { h
1
, h
2
,.., h
m
} là một
quan hệ trên R, và A, B ⊆ R ( A, B là tập cột hay tập thuộc tính ). Khi đó ta
nói A xác định hàm cho B hay B phụ thuộc hàm vào A trong r

f
( ký pháp A → B ) nếu:

r
( ∀ h
i
, h
j
∈ r) (( ∀a ∈ A ) ( h
i
(a) = h
j
(a)) ⇒ ( ∀b ∈ B ) ( h
i
(b) = h
j
(b) ))


{ SBD } → { HOTEN, DIACHI, TINH, KHUVUC }
Khái niệm phụ thuộc hàm miêu tả một loại ràng buộc ( phụ thuộc dữ
liệu) xẩy ra tự nhiên nhất giữa các tập thuộc tính.
Phụ thuộc hàm trên tập các thuộc tính R là một dãy các ký tự có dạng
A → B, ở đây A, B ⊆ R. Ta nói phụ thuộc hàm A → B đúng trong
r nếu A B . Ta nói rằng r thoã mãn A → B.
Hoàng Văn Thủy
9
r
f
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
Dễ thấy F
r
là tập tất cả các phụ thuộc hàm đúng trong r.
1.3 Hệ tiên đề Armstrong.
Năm 1974, Armstrong đã chỉ ra được bốn đặc trưng cho một tập phụ
thuộc hàm của một file dữ liệu nào đó. Chúng được gọi là hệ tiên đề
Armstrong.
Định nghĩa 3. (Hệ tiên đề Armstrong)
Cho trước R = {a
1
, a
2
,.., a
n
} là một tập hữu hạn không rỗng các thuộc
tính.
ta gọi P(R) x P(R) = {(A, B) : A, B ⊆ R }
Khi đó : Y ⊆ P(R) x P(R) là họ f nếu
∀ A, B, C, D ⊆ R có

Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
r
1
= 1 1 r
2
= 1 1
2 3 2 3
1 2 1 2
Có thể thấy rằng r
1
và r
2
khác nhau nhưng F
r1
= F
r2
.
Như vậy là tương quan giữa các lớp quan hệ với các lớp họ phụ thuộc
hàm được thể hiện bằng hình vẽ sau: Lớp các quan hệ Lớp các phụ thuộc hàm
1.4 Hàm đóng.
Định nghĩa 5. (Hàm đóng)
Một hàm L : P(R) → P(R), ( P(R) là tập các tập con của R ) được gọi là
hàm đóng trên R nếu với mọi A, B ∈ P(R):
- A ⊆ L(A)
- Nếu A ⊆ B thì L(A) ⊆ L(B)
- L (L(A)) = L (A).
Định lý 6.

A
2
→ B
2
F = . . . . . .
. . . . . .
A
t
→ B
t
ở đây A
i
, B
i
⊆ R ( i = 1,...,t ) và A
i
→ B
i
là phụ thuộc hàm
Ví dụ: Cho sơ đồ quan hệ s = < R, F >, với R = {a
1
, a
2
, a
3
, a
4
}
{a
1

+
= { a: A →{a} ∈ F
+
}. A
+
được gọi là bao đóng của A trên s
Rõ ràng A → B ∈ F
+
nếu và chỉ nếu B ⊆ A
+
.
Định nghĩa 10. ( Bao đóng của một tập thuộc tính trên tập phụ thuộc
hàm của một quan hệ)
Giả sử r = { h
1
, h
2
,.., h
m
} là một quan hệ trên R = { a
1
, a
2
,..., a
m
}.
Ta đặt
A
+
r

2
∈ r đều tồn tại một thuộc tính a ∈ A sao cho h
1
(a) ≠
h
2
(a). Nói cách khác, không tồn tại hai bộ mà có giá trị bằng nhau trên mọi
tập thuộc tính của A. Điều kiện này có thể viết t
1
(A) ≠ t
2
(A). Do vậy, mỗi giá
trị của A xác định là duy nhất. Khi biết giá trị thuộc tính trong A sẽ biết được
các giá trị của thuộc tính khác.
Theo định nghĩa của Codd: Nếu có hai dòng bằng nhau trên các giá trị
của khoá A thì sẽ kéo theo bằng nhau trên tất cả các cột còn lại. Như vậy sẽ
Hoàng Văn Thủy
13
f
r
f
r
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
có hai cột bằng nhau, điều này không thể có được và nếu có thì đấy là dữ liệu
nhầm lẫn.
Chúng ta gọi A ( A ⊆ R) là một khoá tối tiểu của r ( tương ứng của s,
của Y) nếu:
+ A là một khoá của r (s,Y) tức A → R
+ Bất kỳ một tập con thực sự của A không là khoá của r (s, Y) hay
không tồn tại A' tập con thực sự A' ⊂ A mà A' → R.

là tập tất cả các khoá tối tiểu của r (s, Y).
Nếu ta có: K ={K
1
, K
2
,.., K
n
}
ở đây, K
i
(i = 1,.., t) là các tập con của R, nếu có tính chất sau:
+ K
i
không bao giờ nằm trong K
j
( K
i
⊆ K
j
) thì K được gọi là một hệ
Sperner.
Dễ thấy K
r
, K
s
, K
v
là hệ Sperner trên R.
1.8 Tập các phản khoá
Tập phản khóa đóng vai trò quan trọng trong quá trình nghiên cứu cấu

cũng là hệ Sperner trên R.
Hoàng Văn Thủy
15
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
- Ở đây ta luôn giả thiết rằng nếu một hệ Sperner đóng vai trò tập các khoá
tối tiểu (tập các phản khóa), thì hệ Sperner không rỗng ( Không chứa
R).
- Demertovics.J. đã chứng tỏ rằng nếu K là một hệ Sperner tuỳ ý, thì tồn tại
một sơ đồ quan hệ s sao cho K
s
= K và tồn tại quan hệ r để K
r
= K.
1.9 Nửa dàn giao
Định nghĩa13.
Cho I ⊆ P(R). Khi đó I được gọi là nửa dàn giao nếu
R ∈ I và A, B ∈ I ⇒ A ∩ B ∈ I.
Định nghĩa 14.
Giả sử I là một nửa giàn giao. Giả sử M ⊆ P(R). Ký hiệu
M
+
= { ∩M': M' ⊆ M}. Ta nói rằng M là hệ sinh của I nếu và chỉ nếu M
+
= I.
Chú ý: R ∈ M
+
nhưng không thuộc M vì nó là giao của một họ rỗng các tập
hợp.
- Ký hiệu N
I

(a) = h
j
(a)},
E
r
được gọi là hệ bằng nhau của r
Giả sử M
r
= { A∈P (R) : ∃ E
ij
= A, ∃ E
pq
:A ⊂ E
pq
}
Khi đó M
r
được gọi là hệ bằng nhau cực đại của r .
Hoàng Văn Thủy
16
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
Nhận xét:
Hệ bằng nhau và hệ bằng nhau cực đại đóng một vai trò quan trọng
trong các thuật toán thiết kế cũng như mối quan hệ giữa các lớp quan hệ và
lớp các phụ thuộc hàm trong quá trình nghiên cứu cấu trúc logic của lớp các
phụ thuộc hàm.
Ví dụ: Cho quan hệ r.
a
1
a

2
}
E
r
= E
14
= {a
2
,

a
3
, a
5
}
E
23
= {a
4
}
E
24
= {a
3
,

a
4
, a
5

2
,

a
3
, a
5
}
{a
3
,

a
4
, a
5
}
Vậy M
r
là hệ bằng nhau cực đại của r.
1.11. Thể hiện.
Định nghĩa 16.
Giả sử r là một quan hệ trên R và F là một họ f trên R. Ta nói r thể
hiện F nếu F
r
= F. Chúng ta có thể nói r là một quan hệ Armstrong của F
Định lý 17. (Điều kiện cần và đủ để một quan hệ là thể hiện của một họ
f cho trước)
Giả sử r = {h
1

R và A ⊆ R:
∩ E
ij
nếu tồn tại E
ij
∈ E
r
: A ⊆ E
ij
L
Fr
(A) =
R ngược lại
Trường hợp 1: Giả sử không tồn tại E
ij
∈ E
r
sao cho A ⊆ E
ij
, như vậy với
mọi h
i
, h
j
∈ r tồn tại a ∈ A : h
i
(a) ≠ h
j
(a). Do đó theo định nghĩa phụ thuộc
hàm ta có A → R.

∈ E
r
} và E = ∩E
ij

Eij
∈
V
Dễ thấy A ⊆ E.
+ Nếu V = E
r
thì mọi E
ij
đều

chứa A và E, do đó ∀a ∈ A, ∀i,j :
h
i
(a) = h
j
(a) ∀b ∈ E ∀i,j : h
i
(b) = h
j
(b). Vậy ta có thể nói A → E
hay (A, E) ∈ F
r
.
+ Nếu V ≠ E
r

.
Từ định nghĩa của L
Fr
: L
Fr
(A) ={a∈R: (A,{a})∈ F
r
} và (A, E) ∈ F
r
ta có
A ⊆ E ⊆ L
Fr
(A).
Vì r là một quan hệ trên R ta có E ⊂ R. Như vậy (E, L
Fr
(A))∈F
r
(1)
Ta sẽ chứng minh rằng E = L
Fr
(A).
Giả sử L
Fr
(A) chứa thuộc tính c, c∉E. Khi đó tồn tại E
ij
∈V mà c ∉ E
ij
do đó tồn tại cặp h
i
, h

Fr
) = E
r
+
Định nghĩa 19.
Cho trước quan hệ r và hệ Sperner K trên R. Chúng ta nói rằng r thể
hiện K nếu K
r
= K.
Định nghĩa 20.
Cho F là một họ f trên R, (A, B) là một phần tử của F.
Hoàng Văn Thủy
20
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
Ta nói (A, B) là một phụ thuộc có vế phải cực đại của F nếu với mọi B' (B
⊆ B') và (A, B') ∈ F kéo theo B = B'.
Ta ký hiệu M(F) là tập tất cả các phụ thuộc có vế phải cực đại của F
Định nghĩa 21.
Ta nói rằng B là vế phải cực đại của F nếu có A sao cho (A, B) ∈
M(F) và ta ký hiệu I(F) là tập tất cả các vế phải cực đại của F.
1.12 Sơ đồ quan hệ tương đương.
Định nghĩa 22.
Giả sử s = <R, F> và t = <R, G> là hai lược đồ quan hệ trên R. Ta
nói s là tương đương với t nếu F
+
= G
+
. Trong trường hợp này ta có thể nói
s là phủ định của t hoặc t là phủ định của s.
Nhận xét:

A
2
= {a, b, c, d} = R do {a, b, d} → {c}
Ta tìm được {a, b}
+
={a, b, c, d}.
Vậy {c} ∈ {a, b}
+
đối với G, tức là {a, b} →{c}∈ G
+
Xét từng phụ thuộc hàm trong G. Hai phụ thuộc hàm sau đã nằm trong F.
Xét phụ thuộc hàm {a, b, d} → {c, d}∈ G. Kiểm tra xem phụ thuộc hàm
này có thuộc F
+
hay không.
Tính {a, b, d}
+
đối với G:
A
0
= {a, b, d}
A
1
= {a, b, c, d} = R do {a, b}→{c}
Ta tìm được {a, b, d}
+
={a, b, c, d}.
Vậy c, d ∈ {a, b, d}
+
đối với F, tức là {a, b, d}→{c, d}∈ F

2
,.., h
m
} là một quan hệ trên R = { a
1
, a
2
,.., a
n
} và K
r
là tập tất cả các khóa tối tiểu của r. Ta nói a là một thuộc tính cơ bản của r
nếu tồn tại một khoá tối tiểu K (K ∈ K
r
) để a là một phần tử của K.
Nếu a không là thuộc tính cơ bản, a sẽ được gọi là thuộc tính thứ cấp.
Nhận xét:
Thuộc tính cơ bản và thuộc tính thứ cấp đóng một vai trò quan trọng
trong việc chuẩn hóa các sơ đồ quan hệ và các quan hệ.
Đinh lý 26.
Cho trước một sơ đồ quan hệ s = < R, F > và một thuộc tính a. Bài
toán xem a có phải là thuộc tính cơ bản hay không là bài toán NP - đầy
đủ.
1.14 Một số thuật toán liên quan
Thuật toán 1. (Tìm tập các thuộc tính cơ bản của một quan hệ trên R)
Input: r = { h
1
, h
2
, ..., h

ta xây dựng tập M
Hoàng Văn Thủy
23
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
M = { B ∈ P(R): Tồn tại E
ij
∈ E
r
: E
ij
= B }
Bước 3: Từ M xây dựng tập M
r
M
r
= { B ∈ P(R) : ∀B' ∈ M : B ⊄ B' }
Bước 4: Xây dựng tập V = R\ ∩ M
r
Nhận xét:
Ta thấy m( m-1) ≥ E
r
M ≥ M
r
)
Do vậy M
r
được tính bằng thuật toán thời gian đa thức. Suy ra V tính được
bằng thời gian đa thức theo số hàng và số cột của r
Ví dụ: Xét quan hệ ( A B C D )
1 0 1 1

quan hệ có là cơ bản hay không với thời gian đa thức theo số hàng và số
cột của r.
Hoàng Văn Thủy
24
Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu
Một vấn đề thường xuyên xảy ra là đối với một sơ đồ quan hệ cho
trước (s = <R, F>), và một phụ thuộc hàm A → B, chúng ta muốn biết
A →B có là phần tử của F
+
hay không. Để trả lời câu hỏi này chúng ta cần
tính bao đóng F
+
của tập các phụ thuộc hàm F.
Tuy nhiên tính F
+
trong trường hợp tổng quát là rất khó khăn và tốn
kếm thời gian vì các tập phụ thuộc hàm thuộc F
+
là rất lớn cho dù F có thể
là nhỏ. Chẳng hạn, F = {A → B
1
, A → B
2
,.... A → B
n
}, khi đó F
+
bao gồm
cả những phụ thuộc hàm A → Y với Y ⊆ {B
1

là bao đóng của A đối với F.
Phương pháp: Lần lượt tính các tập thuộc tính A
o
, A
1
như sau:
1). A
0
= A
2). A
i
= A
i-1
∪ {a} nếu ∃ (C → D) ∈ F, {a} ∈ D và C ⊆ A
i-1
3). Rõ ràng A = A
0
⊆ A
1
⊆ ... ⊆ A
i
⊆ R và R hữu hạn nên tồn tại i sao cho
A
i
= A
i+1
Khi ấy thuật toán dừng và A
i
chính là A
+