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.
Cùng với sự phát triển của mô hình dữ liệu quan hệ, có nhiều vấn đề lý thuyết và
thực nghiệm nảy sinh và được giải quyết . Khi thiết kế CSDL quan hệ ta thường đứng
trước vấn đề lựa chọn giữa các lược đồ quan hệ: lược đồ nào tốt hơn? Tại sao? …
Có thể nói tổng quát một lược đồ quan hệ có cấu trúc tốt là lược đồ không chứa
đựng các vấn đề liệt kê sau đây:
a. Dư thừa dữ liệu
Là sự trùng lặp thông tin trong CSDL.
Ví dụ: Xét lược đồ quan hệ NHACC(Ten_NCC, Hang, DonGia, Diachi_NCC).
Nếu một nhà cung cấp cung cấp nhiều mặt hàng thì địa chỉ nhà cung cấp phải lặp lại
nhiều lần kéo theo dư thừa dữ liệu.
Ngoài việc gây lãng phí dung lượng lưu trữ, sự dư thừa dữ liệu có thể gây ra những hậu
quả nghiêm trọng đối với dữ liệu khi người dùng cập nhật dữ liệu làm cho dữ liệu không
tương thích, thiếu nhất quán.
Ví dụ: Xét lại lược đồ NHACC trên. Ta có thể sửa địa chỉ một nhà cung cấp tại một bộ
nào đó mà không sửa ở một bộ khác gây ra địa chỉ không nhất quán của cùng một nhà cung
cấp.
b. Dị thường do thêm dữ liệu
Không thể chèn bộ mới vào quan hệ nếu không có đầy đủ dữ liệu.
Ví dụ: Ta không thể ghi nhận địa chỉ một nhà cung cấp nếu nhà cung cấp đó không
cung cấp mặt hàng nào cả vì Ten_NCC, Hang tạo thành một khoá cho quan hệ.
c. Dị thường do xóa dữ liệu
3
Ngược lại với vấn đề c, khi ta xoá hết các mặt hàng do một hãng cung cấp, ta không thể
theo dõi được địa chỉ của hãng đó.
Trong ví dụ trên, vấn đề này sẽ không còn nữa khi ta thay quan hệ NHACC bằng hai
quan hệ:
NCC_ĐC(TÊN_NCC, ĐC_NCC)
NCC_HG(TÊN_NCC, TÊN_HG, GIA)
Cách giải quyết các vấn đề trên khi thiết kế lược đồ quan hệ là xây dựng lược đồ đạt các
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(A1,…,An) là một sơ đồ quan hệ với tập thuộc tính U={A1,…,An}. 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 = {A1,…,An} 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ạ:
Y X X Y
4
F2) Tính tăng trưởng:
X Y XZ YZ
F3) Tính bắc cầu:
X Y, Y Z X Z
b. Bao đóng:
Bao đóng (closure) của tập phụ thuộc hàm F (ký hiệu là F+) là tập hợp tất cả các
phụ thuộc hàm có thể suy ra từ F dựa vào các tiên đề Armstrong. Tức nó phải thoả hai tính
chất sau:
i) F+ F
ii) Khi áp dụng các hệ tiên đề Armstrong cho F+ ta không thu được phụ thuộc
hàm nào nằm ngoài F+.
Bao Đóng Của Tập Thuộc Tính : Cho tập phụ thuộc hàm F trên tập thuộc tính U và
X U. Bao đóng của tập thuộc tính X (đối với F), ký hiệu X+, là tập sau:
X+ = {A | X A F+}
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:
Tập phụ thuộc hàm tối thiểu là tập phụ thuộc hàm thoả mãn các điều kiện sau:
1) Vế phải của mỗi phụ thuộc hàm trong F chỉ có 1 thuộc tính.
2) Mọi phụ thuộc hàm X A F đều không dư thừa, tức là tập phụ thuộc hàm
có từ F bằng sự loại bỏ phụ thuộc hàm X A: F \ {X A} không tương
đương với F.
3) Với mỗi phụ thuộc hàm X A F, mọi thuộc tính B X đều không dư
thừa, tức là tập phụ thuộc hàm có từ F bằng việc thay phụ thuộc hàm X A
bởi phụ thuộc hàm (X \{B}) A : (F \ {X A}) {X \ {B}) A} không
tương đương với F.
Tập phụ thuộc hàm tương đương của F:
Tập phụ thuộc hàm G được gọi là tương đương với F nếu và chỉ nếu F+ = G+
Ký hiệu: F ≡ G
Phủ tối thiểu của F:
Là tập phụ thuộc hàm tối thiểu và tương đương với F
Ký hiệu : PTT(F)
f. Các dạng chuẩn:
Như đã nói ở trên, một lược đồ quan hệ có thể bị dư thừa dữ liệu, dị thường do thêm,
dị thường do xóa. Những vấn đề trên đã được giải quyết qua việc xây dựng các dạng
chuẩn.
Xét lược đồ quan hệ R(U, F), với U là tập thuộc tính, F là tập phụ thuộc hàm.