Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
MỤC LỤC

MỤC LỤC 1
LỜI MỞ ĐẤU 3
NỘI DUNG 6
I.KHÁI NIỆM VỀ HỆ CƠ SỞ DỮ LIỆU QUAN HỆ 6
1. CSDL (DataBase): 6
2. CSDL quan hệ (Relationship DataBase): 6
3. Hệ quản trị CSDL (DataBase Management System - DBMS) 6
4. Mô hình dữ liệu quan hệ 8
Các phép toán trên quan hệ: 11
5. Khoá của quan hệ 11
II.THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ 14
1. Các vấn đề gặp phải khi tổ chức dữ liệu 14
2. Phụ thuộc hàm 15
4. Bao đóng của tập phụ thuộc hàm 19
5. Bao đóng của tập thuộc tính 21
6. Thuật toán tìm bao đóng của tập thuộc tính 22
7. Khóa của lược đồ quan hệ và các thuộc tính tham gia vào khóa 24
7.1. Thuật toán tìm một khoá của một lược đồ quan hệ 24
7.2. Thuật toán tìm tất cả các khoá của một lược đồ quan hệ 26
7.3. Thuật toán cải tiến 26
8. Phủ tối tiểu 28
8.1 Tập phụ thuộc hàm tương đương 28
8.2 Thuật toán tìm phủ tối tiểu 29
9. Phép tách lược đồ quan hệ 30
9.1. Kết nối không mất mát thông tin 31
9.2 Kiểm tra phép kết nối không mất mát thông tin 31
III.CÁC DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ 33
1. Dạng chuẩn thứ nhất (1NF – First Normal Form) 34

scripting gần gũi, đơn giản, linh hoạt,… cộng với phần mềm lưu trữ dữ
liệu quan hệ như Oracle, MySQL, MS SQL Server, PostGreSQL,…
khiến RDBMS (Hệ Quản Trị CSDL quan hệ) gần như độc tôn trong các
mô hình lưu trữ dữ liệu. Nhưng theo đà phát triển vượt bậc của Công
nghệ thông tin và do nhu cầu của người dùng, đã dẫn đến những yêu
cầu về thế hệ lưu trữ phải ngày càng hiệu quả hơn và thế là một thế hệ
databse mới ra đời.
Thế hệ lưu trữ dữ liệu kế tiếp đòi hỏi gì?
Sự gia tăng đột biến về lượng đặt ra một thách thức lớn cho các
mô hình lưu trữ, dẫn đến bài toán về yêu cầu phân tán. Trên thực tế,
RDBMS (Hệ Quản Trị CSDL quan hệ) đã tính toán và triển khai tương
đối thành công ở một mức độ nào đó nhưng vẫn kèm theo những hạn
chế nhất định về mặt tốc độ, và hay bị bottle neck (nghẽn cổ chai), …
Thế hệ database mới là gì?
Thế hệ database kế tiếp là một thế hệ cơ sở dữ liệu non -
relational (không ràng buộc), distributed (phân tán), open source (mã
nguồn mở), horizontal scalable (khả năng mở rộng theo chiều ngang)
để có thể lưu trữ, xử lý từ một lượng rất nhỏ cho tới hàng petabytes dữ
HVTH: Nguyễn Thị Kim Phượng Trang 3
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
liệu trong hệ thống và đặc biệt có độ chịu tải, chịu lỗi cao cùng với
những đòi hỏi về tài nguyên phần cứng thấp.
Tuy còn những hạn chế nhất định như vậy, nhưng tại sao
việc chọn mô hình dữ liệu quan hệ làm hệ thống hình thức cho
các hệ CSDL phân tán cũng như các hệ CSDL khác thì có nhiều lý
do:
- Trong sách “NGUYÊN LÝ CÁC HỆ CƠ SỞ DỮ LIỆU VÀ CƠ SỞ
TRI THỨC” – tác giả Jeffrey Ullman - biên dịch Trần Đức
Quang – hiệu đính Hồ Thuần đã nhận xét: “Cơ sở toán học của
mô hình quan hệ làm cho nó trở thành một ứng cử viên sáng giá

làm việc rất nghiêm túc cùng với cách giảng giải rõ ràng, dễ hiểu,
thông qua các ví dụ ứng dụng trong thực tế cuộc sống, thầy đã tận tâm
truyền đạt những kiến thức nền tảng cơ bản cho chúng em về môn học
“CƠ SỞ DỮ LIỆU NÂNG CAO” – chính điều này thật sự giúp em
hiểu rõ hơn vấn đề, mở rộng tầm nhìn, thấy được sự cần thiết của môn
học đang ảnh hường và chi phối đến nhiều lĩnh vực trong thời đại.

HVTH: Nguyễn Thị Kim Phượng Trang 5
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
NỘI DUNG

I. KHÁI NIỆM VỀ HỆ CƠ SỞ DỮ LIỆU QUAN HỆ
1. CSDL (DataBase):
CSDL là tập hợp của các dữ liệu có cấu trúc liên quan với nhau
về mặt logic, liên quan đến các vấn đề trong thực tế mà chúng ta đang
cố gắng mô hình hóa chúng, CSDL là hệ thống tích hợp các tập tin
được sử dụng nhằm giảm thiểu sự dư thừa dữ liệu.
2. CSDL quan hệ (Relationship DataBase):
Là loại CSDL được tổ chức dười dạng bảng (table). Về hình
thức, một quan hệ relation r được định nghĩa trên n tập (D
1
, D
2
,…D
n
không nhất thiết phải tách biệt) là một tập các n bộ (hoặc đơn giản là
các bộ <d
1
,d
2

Dựa vào sự phân cấp, các hệ cơ sở dữ liệu (hệ CSDL) đầu tiên
được xây dựng theo các mô hình phân cấp và mô hình mạng, đã xuất
hiện vào những năm 1960, được xem là thế hệ thứ nhất của các hệ
quản trị cơ sở dữ liệu (hệ QTCSDL). Tiếp theo là thế hệ thứ hai, các hệ
QTCSDL quan hệ, được xây dựng theo mô hình dữ liệu quan hệ do
E.F. Codd đề xuất vào năm 1970.
Các hệ QTCSDL có mục tiêu tổ chức dữ liệu, truy cập và cập nhật
những khối lượng lớn dữ liệu một cách thuận lợi, an toàn và hiệu quả.
Tuy nhiên, với sự phát triển nhanh chóng của công nghệ truyền
thông và sự phát triển vượt bậc không ngừng của mạng Internet, cùng
với xu thế toàn cầu hoá trong mọi lĩnh vực, đặc biệt là về thương mại,
đã làm nảy sinh nhiều ứng dụng mới, phải quản lý những đối tượng có
cấu trúc phức tạp (văn bản, âm thanh, hình ảnh) và động (các chương
trình, các mô phỏng). Các CSDL thuộc thế hệ một và hai không thể giải
quyết được các bài toán trong môi trường phân tán (không tập trung),
đòi hỏi phải xử lý song song các dữ liệu và hệ thống không thuần nhất.
Thế hệ thứ ba của hệ quản trị CSDL ra đời vào những năm 80 trong đó
có CSDL phân tán đã đáp ứng những nhu cầu đặt ra trong thời đại này.
Một hệ quản trị CSDL thực hiện các chức năng sau:
+ Tạo cấu trúc dữ liệu tương ứng với mô hình dữ liệu được chọn.
+ Đảm bảo tính độc lập dữ liệu.
+ Cập nhật dữ liệu.
+ Phát sinh các báo cáo từ các dữ liệu trong CSDL.
HVTH: Nguyễn Thị Kim Phượng Trang 7
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
+ Đảm bảo tính an toàn và toàn vẹn dữ liệu trong CSDL.
+ Cung cấp các tiện ích sao lưu phục hồi dữ liệu.
+ Cung cấp các thủ tục điều khiển tương tranh.
Một hệ quản trị thông thường có các thành phần chính sau:
+ Ngôn ngữ định nghĩa dữ liệu (Data Definition Language).

Sự thể hiện của lược đồ quan hệ ở một thời điểm nào đó được
gọi là quan hệ, rõ ràng là trên một lược đồ quan hệ có thể xác định
nhiều quan hệ. Quan hệ là tập con của tích Đề Các của một hoặc nhiều
miền. Vậy, mỗi quan hệ có thể là vô hạn, ở đây luôn giả thiết rằng quan
hệ là một tập hữu hạn.
Có thể định nghĩa quan hệ một cách hình thức như sau:
Định nghĩa: Gọi U = {A
1
, A
2
, …, A
n
} là tập hữu hạn các thuộc
tính, mỗi thuộc tính A
i
với i = 1,…, n có miền giá trị tương ứng là
Dom(A
i
). Quan hệ r trên tập thuộc tính U = {A
1
,…, A
n
}, ký hiệu là r(U)
hoặc r(A
1
, , A
n
), là tập con của tích Đề Các của các miền giá trị.
r(U)
⊆

a
2
2
a
2
n
a
3
1
a
3
2
a
3
n

a
m
1
a
m
2
a
m
n
Trong đó: A
1
, A
2
, A

Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
- Khi nói đến lược đồ quan hệ trong đó chỉ tập trung vào khía
cạnh mô tả cấu trúc của một quan hệ mà không quan tâm đến ràng
buộc thì ta sẽ dùng ký hiệu
R(A
1
, A
2
, …, A
n
).
- Mỗi quan hệ là một thể hiện của lược đồ quan hệ, ký hiệu r(R)
là quan hệ r của lược đồ R.
- Với một bộ t thuộc quan hệ r của lược đồ R và X ⊆ U, ta ký hiệu
t[X] là bộ t chỉ chứa các giá trị của các thuộc tính trong X, và t[A
i
] để chỉ
giá trị của bộ t tương ứng với thuộc tính A
i
.
Các phép toán trên quan hệ:
- Các phép toán tập hợp (Set operation): Phép hợp (Union operation),
Phép Giao (Intersection), Phép Trừ (Minus, Difference), Tích
Descartes (Cartesian Product, Product)
- Các phép toán quan hệ: Phép Chiếu (Projection), Phép Chọn
(Selection), Phép Kết, Phép Kết Tự Nhiên (Join, Natural join), Phép
chia (Division)
5. Khoá của quan hệ
Định nghĩa: Cho quan hệ r xác định trên tập thuộc tính U, K là
một tập thuộc tính K ⊆ U. Gọi K là khoá của quan hệ r nếu với ∀ bộ t

d
1
t
2
= a
2
b
2
c
2
d
2
t
3
= a
3
b
3
c
2
d
2
t
4
= a
1
b
2
c
2

của quan hệ là rất khó khăn. Lưu ý rằng, nếu K là khóa của quan hệ r
thì với mọi tập K
’
sao cho K ⊆ K
’
, K
’
cũng là khóa của r.
Định nghĩa khóa tối tiểu: Tập K ⊆ U được gọi là khóa tối tiểu
của quan hệ r xác định trên tập thuộc tính U nếu thỏa mãn:
+ K là một khóa của r,
+ Bất kỳ tập con thực sự K
’
nào của K đều không là khóa.
Một quan hệ có thể có nhiều khóa tối tiểu, thông thường người ta
chọn một khóa tối tiểu làm khóa chính, các khóa tối tiểu còn lại gọi là
khóa dự bị (hay khóa dự tuyển). Việc chọn một khóa tối tiểu làm khóa
chính là tùy ý, nhưng thông thường nên chọn khóa tối tiểu có một thuộc
tính hoặc có ít thuộc tính nhất.
HVTH: Nguyễn Thị Kim Phượng Trang 12
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
Khóa chính được dùng để nhận diện một bộ trong quan hệ, khi
muốn tìm kiếm một bộ t nào đó, ta chỉ cần biết thành phần khóa chính
của t là đủ. Do đó, giá trị của các thuộc tính trên tập khóa chính của tất
cả các bộ phải khác NULL. Đây là ràng buộc toàn vẹn thực thể của
CSDL. Thực tế, khi sửa đổi giá trị thuộc tính trong khóa chính của 1 bộ t
chính là hủy bộ t đó và đưa vào bộ t
’
khác.
Thuộc tính khóa là thuộc tính có tham gia vào một khóa nào đó

sau:
MASV HOTEN MONHOC DIEMTHI
TT5001 Nguyễn Duy An Cấu trúc dữ liệu 7
TT5001 Nguyễn Duy An Cơ sở dữ liệu 8
TT5014 Lê Hoàng Minh Kỹ thuật lập trình 5
TT5001 Nguyễn Duy An Kỹ thuật lập trình 6
Quan hệ trên ghi kết quả điểm thi các môn của các sinh viên.
Chúng ta nhận thấy một số vấn đề nảy sinh như sau:
1. Dư thừa dữ liệu: Với mỗi môn thi họ tên của sinh viên lại
được lặp lại.
2. Không nhất quán (dị thường xuất hiện khi sửa dữ liệu): Do
hậu quả dư thừa, chúng ta có thể sửa đổi họ tên của một sinh viên
trong một bộ nào đó nhưng vẫn để lại họ tên cũ trong những bộ khác.
Vì vậy có thể không có họ tên duy nhất đối với mỗi sinh viên như mong
muốn.
3. Dị thường khi thêm bộ: Chúng ta không thể biết họ tên của
một sinh viên nếu hiện tại sinh viên đó không dự thi môn nào.
HVTH: Nguyễn Thị Kim Phượng Trang 14
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
4. Dị thường khi xoá bộ: Ngược lại với vấn để thứ 3, chúng ta
có thể xoá tất cả các môn thị của một sinh viên, vô ý làm mất dấu vết
để tìm ra họ tên của sinh viên này
Những vấn đề nêu trên sẽ được giải quyết nếu chúng ta phân rã
lược đồ quan hệ Diemthi thành hai lược đồ quan hệ:
Sinhvien(MASV, HOTEN)
Ketqua(MASV, MONHOC, DIEMTHI)
Lúc này, lược đồ quan hệ Sinhvien cho biết họ tên của mỗi sinh
viên chỉ xuất hiện đúng một lần, do vậy không có dư thừa. Ngoài ra
chúng ta có thể nhập họ tên của một sinh viên dù hiện tại sinh viên đó
chưa có kết quả thi môn nào. Tuy nhiên, để tìm danh sách họ tên của

Y (đọc là X
xác định hàm Y hoặc Y phụ thuộc hàm vào X). (Nghĩa là, không thể tồn
tại hai bộ r giống nhau ở các thuộc tính trong tập X mà lại khác nhau ở
một hay nhiều thuộc tính nào đó trong tập Y).
Ký hiệu phụ thuộc hàm là f, tập phụ thuộc hàm là F. Như vậy:
f: X
→
Y
F = {f: X
→
Y | X, Y ⊆ U, và Y phụ thuộc hàm vào X}
- Nếu Y không phụ thuộc hàm vào X ta có thể viết X! →Y
HVTH: Nguyễn Thị Kim Phượng Trang 15
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
- Lưu ý: Chỉ xét những các phụ thuộc hàm thoả mãn cho mọi
quan hệ trên lược đồ tương ứng của nó. Không thể xem xét một phụ
thuộc hàm thoả mãn một quan hệ r đặc biệt (ví dụ quan hệ rỗng) của
lược đồ R rồi sau đó quy nạp rằng phụ thuộc đó thoả mãn trên R.
Ví dụ 1: Cho quan hệ
S(S#, SNAME, STATUS, CITY)
SP(S#, P#, QTY)
P(P#, PNAME, CORLOR, WEIGHT, CITY)
Trong quan hệ của hãng cung ứng, mỗi một trong số các thuộc
tính SNAME, STATUS, CITY đều phụ thuộc hàm vào thuộc tính S#. Mỗi
giá trị S# tồn tại vừa đúng một giá trị tương ứng đối với từng thuộc tính
SNAME, STATUS và CITY khi đó có thể viết: S#
→
SNAME, S#
→
STATUS và S#

Ví dụ: Cho lược đồ quan hệ R(U, F):
U = {A,B,C,D,E}, F = {A→BC, B →D, AD → E}
* Nhận xét:
- Lược đồ quan hệ dùng để mô tả cấu trúc của quan hệ, tại mỗi
thời điểm lược đồ quan hệ có thể hiện là một quan hệ cụ thể.
- Có thể ký hiệu lược đồ quan hệ xác định trên tập thuộc tính U =
{A
1
, …, A
n
} như sau: R(U) hay R(A
1
, …, A
n
).
HVTH: Nguyễn Thị Kim Phượng Trang 17
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
- Thể hiện của quan hệ R của lược đồ quan hệ R(U, F) là tập tất
cả các bộ thỏa mãn tập tất cả các phụ thuộc hàm trong F.
Hệ tiên đề Armstrong cho phụ thuộc hàm
Gọi R(U, F) 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:
− Tiên đề phản xạ: Nếu Y

− Luật tựa bắc cầu (bắc cầu giả): Nếu X
→
Y và YW
→
Z thì
XW
→
Z
− Luật tách: Nếu X
→
Y và Z
⊆
Y thì X
→
Z
3. Phụ thuộc đa trị
Mối quan hệ giữa dữ liệu với nhau được thể hiện qua phụ thuộc
hàm, nhưng phụ thuộc hàm không phải là duy nhất. Khái niệm phụ
thuộc hàm trong trường hợp tổng quát không đủ để vét hết các loại phụ
thuộc tồn tại trong quan hệ. Trong thực tế còn có nhiều loại phụ thuộc
dữ liệu nữa. Chẳng hạn, mỗi cặp vợ chồng (tên cha, mẹ) không phải
xác định duy nhất tên một đứa con mà là một hoặc một số con; hoặc
HVTH: Nguyễn Thị Kim Phượng Trang 18
Bài Thu Hoạch “CHUYÊN ĐÈ CSDLNC”  GVHD: PGS - TS Đỗ Phúc
một người có thể xác định sở hữu trên một chiếc xe máy… Mối quan hệ
đó trong CSDL gọi là phụ thuộc đa trị.
Giả sử cho R là một lược đồ quan hệ, X và Y là hai tập con của
R. Ta nói rằng, X là xác định đa trị Y, ký hiệu: X
→
→

→
Z-Y
Các luật phối hợp giữa FD và MVD
A4. Nếu X
→
Y thì X
→
→
Y
A5. Nếu X
→
→
Y, Z
⊆
Y và W là tập con phân biệt với Y (tức là
W
∩
Y =
φ
) và W
→
Z thì X
→
Z.
4. Bao đóng của tập phụ thuộc hàm
- Suy diễn: Cho lược đồ quan hệ R(U, F), F – là tập phụ thuộc
hàm, X, Y ⊆ U, X → Y là một phụ thuộc hàm. Ta nói phụ thuộc hàm X
→ Y được suy diễn logic ra từ F nếu mọi quan hệ r trên lược đồ R thỏa
mãn các phụ thuộc hàm trong F thì cũng thỏa mãn phụ thuộc hàm X →
Y.

→
CE; D
→
H; GH
→
C; AC
→
D; BC
→
AC;
BC
→
D; DA
→
AH; DG
→
C; BC
→
AD,… }
- Phụ thuộc hàm có vế trái dư thừa
F là tập các phụ thuộc hàm trên lược đồ quan hệ Q, Z là tập thuộc
tính, Z→Y∈F.
Phụ thuộc hàm Z → Y có vế trái dư thừa (phụ thuộc không đầy
đủ) nếu có một A∈Z sao cho: F ≡ F-{Z → Y}∪{(Z-A) → Y}
Ngược lại Z → Y là phụ thuộc hàm có vế trái không dư thừa hay
Y phụ thuộc hàm đầy đủ vào Z hay phụ thuộc hàm đầy đủ.
Ta nói F là tập phụ thuộc hàm có vế trái không dư thừa nếu F
không chứa phụ thuộc hàm có vế trái dư thừa.
Thuật toán loại khỏi F các phụ thuộc hàm có vế trái dư thừa.
Bước 1: Lần lượt thực hiện bước 2 cho các phụ thuộc hàm X→Y của F

U được suy ra từ X dựa vào các phụ thuộc hàm trong F
và hệ tiên đề Armstrong, nghĩa là:
X
+
= {A: A
∈
U và X
→
A
∈
F
+
}. Ta có X ⊆ X
+
.
Ví dụ: Cho lược đồ quan hệ R(ABCDEGH) và tập phụ thuộc hàm
F:
F = {B
→
A; DA
→
CE; D
→
H; GH
→
C; AC
→
D}. Hãy tính B
+
; H

+ Tính phản xạ: X ⊆ X
+
+ Tính đơn điệu: Nếu X ⊆ Y thì X
+
⊆ Y
+
+ Tính lũy đẳng: X
++
= X
+
+ (XY)
+
= X
+
Y
+

+ (X
+
Y)
+
= (XY
+
)
+
= (X
+
Y
+
)

Áp dụng thuật toán ta có:
- B
0
: X
0
= {A}
- B
1
: X
1
= {AB} (vì có A
→
B, {A} ⊆ X
0
)
- B
2
: X
2
= {ABC} (vì có B
→
C, {B} ⊆ X
1
)
- B
3
: X
3
= X
2

= {BD}, sau đó chọn phụ thuôc hàm có vế trái chứa B, D
hoặc BD.
- B
1
: X
1
= {BDEG} (vì có D
→
EG, {D} ⊆ X
0
), lại tiếp tục tìm phụ
thuộc hàm có vế trái chứa trong X
1
.
- B
2
: X
2
= {BCDEG} (vì có BE
→
C, {BE} ⊆ X
1
)
- B
3
: X
3
= {ABCDEG} (vì có CE
→
AG, {CE} ⊆ X

→
DE, {AB} ⊆ X
0
)
- B
2
: X
2
= {ABDEH} (vì có E
→
H, {E} ⊆ X
1
)
- B
3
: X
3
= X
2

Vậy (AB)
+
= {ABDEH}.
7. Khóa của lược đồ quan hệ và các thuộc tính tham gia vào khóa.
- Siêu khóa (superkey) của một lược đồ quan hệ R = {A1, A2, , An}
là tập thuộc tính S ⊆ R thỏa tính chất không có hai bộ t1 và t2 trong một
trạng thái hợp lệ r của R mà t1[S] = t2[S]
- Khóa (key) K là siêu khóa với tính chất bổ sung là khi xóa thuộc tính
nào khỏi K sẽ khiến K không còn là siêu khóa.
- Nếu lược đồ quan hệ có nhiều hơn một khóa, mỗi khóa sẽ được gọi là

- K = ABC
- Loại thuộc tính A, do (K-A)
+
= (BC)
+
= ABC nên K =BC
- Thuộc tính B không loại được, do (K-B)
+
= (AC)
+

= AB
- Loại thuộc tính C, do (K-C)
+

=(AB)
+
= ABC nên K = B
Vậy một khoá của R là B
Nhận xét:
- Những thuộc tính nào xuất hiện duy nhất ở phía phải của tập
phụ thuộc hàm F thì tham gia vào khoá.
- Những thuộc tính xuất hiện duy nhất ở phía trái thì chắc chắn
tham gia vào khoá.
- Những thuộc tính không xuất hiện trong các phụ thuộc hàm
chắc chắn phải tham gia vào khoá.
- Những thuộc tính vừa có mặt ở vế trái, vừa có mặt ở vế phải có
khả năng tham gia vào khoá hoặc không.
HVTH: Nguyễn Thị Kim Phượng Trang 25