Giáo Trình
Dữ liệu và các mô hình
cơ sở dữ liệu
1

MỤC LỤC
H C TRÈNH I Ọ 5
CÁC KHÁI NI M C B N V D LI U VÀ CÁC M HÈNH C S D LI UỆ Ơ Ả Ề Ữ Ệ Ễ Ơ Ở Ữ Ệ 5
Nguyễn Đỡnh Hõn 5
Phần này bao gồm cỏc nội dung sau đõy 5
1.1 C C KH I NI M C B N V D LI U V H QTCSDLÁ Á Ệ Ơ Ả Ề Ữ Ệ À Ệ 6
1.1.1 D li uữ ệ 6
1.1.2 File d li uữ ệ 6
1.1.3 C s d li uơ ở ữ ệ 6
1.1.4 nh ngh a h c s d li uĐị ĩ ệ ơ ở ữ ệ 7
1.1.5 S v t lý h c s d li uơ đồ ậ ệ ơ ở ữ ệ 8
1.1.6 H th ng c s d li u m c logicệ ố ơ ở ữ ệ ứ 8
1.1.7 M t s t nh ch t c tr ng c a c s d li uộ ố ớ ấ đặ ư ủ ơ ở ữ ệ 8
Nguyễn Đỡnh Hõn 8
1.2 C C MÁ Ễ HÈNH C S D LI UƠ Ở Ữ Ệ 8
1.2.1 C c kh i ni m c b n xõy d ng m t h th ng th ng tin.ỏ ỏ ệ ơ ả để ự ộ ệ ố ụ 8
1.2.2 C c m h nh d li uỏ ụ ỡ ữ ệ 9
1.3 KH I NI M TO N H C HO MÁ Ệ Á Ọ Á Ễ HÈNH QUAN HỆ 10
1.3.1 Thu c t nh (Attribute)ộ ớ 10
1.3.2 Quan h (Relation)ệ 11
1.3.3 Kh i ni m ph thu c hàm (Function dependency)ỏ ệ ụ ộ 12
1.3.4 Kho (Key)ỏ 12
1.3.5 L c quan h (Relation Schema)ượ đồ ệ 13
1.3.6 Ph p t ch lộ ỏ c quan hượ đồ ệ 14
1.3.7 Bao úng c a t p ph thu c hàmđ ủ ậ ụ ộ 16

2.1.10 C c v d v t m ki m b ng i s quan hỏ ớ ụ ề ỡ ế ằ đạ ố ệ 31
2.2 NGỄN NG CON D LI U DSL - ALPHAỮ Ữ Ệ 31
2.2.1 Bi u th c ALPHAể ứ 31
2.2.2 Ph p t m ki mộ ỡ ế 32
2.2.3 C c ph p c p nh t d li uỏ ộ ậ ậ ữ ệ 35
2.2.4 C c hàm th vi nỏ ư ệ 36
2.3 NGỄN NG CON D LI U SQLỮ Ữ Ệ 37
2.3.1 Gi i thi u ng n ng SQLớ ệ ụ ữ 37
2.3.2 Thao t c b ngỏ ả 38
2.3.3 Kh i SELECTố 41
M t s tr ng h p v n d ng l nh SELECTộ ố ườ ợ ậ ụ ệ 44
a. Kiểm tra từ điển dữ liệu 44
b. Kết hợp nhiều lệnh SELECT 44
2.3.4. C c m nh c p nh t d li uỏ ệ đề ậ ậ ữ ệ 45
2.3.5 C c m nh v an toàn d li uỏ ệ đề ề ữ ệ 45
3

H C TRÈNH IIIỌ 47
CHU N HOÁ D LI U VÀ ĐI U KHI N AN TOÀN D LI UẨ Ữ Ệ Ề Ể Ữ Ệ 47
Nguyễn Đỡnh Hõn 47
Phần này bao gồm cỏc nội dung sau đõy 47
3.1 CHU N HO QUAN HẨ Á Ệ 48
3.1.1 Gi i thi u chu n hoớ ệ ẩ ỏ 48
3.1.2 C c d ng chu n hoỏ ạ ẩ ỏ 48
BANHANG (I) 49
BANHANG (I.1) 50
MATHANG (I.2) 50
BANHANG (I.1.1) 50
HOADON (I.1.2) 50
NHANVIEN (I.1.1.1) 50

 Khỏi niệm toỏn học hoỏ mụ hỡnh quan hệ
 Cỏc phộp toỏn của ngụn ngữ thao tỏc dữ liệu
 Cỏch thức tổ chức dữ liệu vật lý
 Tổ chức cỏc tệp cơ sở dữ liệu
5

1.1 CÁC KHÁI NIỆM CƠ BẢN VỀ DỮ LIỆU VÀ HỆ QTCSDL
1.1.1 Dữ liệu
Chỳng ta đang sống trong kỷ nguyờn thụng tin. Xu hướng xó hội hoỏ tin học tiếp đến là toàn cầu
hoỏ là xu hướng tất yếu khụng thể đảo ngược. Trong bối cảnh đú việc nắm bắt được cỏc thụng tin
nhanh chúng và chuẩn xỏc là yếu tố tối cần thiết quyết định sự thắng lợi trong quản lý điều hành.
Việc tin học hoỏ xó hội đó dẫn tới nhu cầu quản lý điều hành cụng việc trờn mỏy tớnh điện tử, như
vậy thực chất của cụng tỏc quản lý chớnh là quản lý thụng tin. Mọi thụng tin được quản lý trờn
mỏy tớnh theo bất kỳ phương cỏch gỡ cũng đều phải được thể hiện bằng cỏc dữ liệu ghi trờn một
thiết bị lưu trữ nào đú. Dữ liệu cũng rất phong phỳ cú thể là dữ liệu ở dạng văn bản, õm thanh hay
hỡnh ảnh, … Trong thực tế người ta lưu dữ liệu dưới nhiều dạng khỏc nhau mục đớch chung là đạt
hiệu quả cao trong lưu trữ và khai thỏc.
Như vậy dữ liệu chớnh là thụng tin, chỉ xột ở gúc độ tin học theo nghĩa hẹp thỡ đú chớnh là phần
nội dung của cỏc file.
1.1.2 File dữ liệu
File là một khối thụng tin được lưu trữ trong mỏy tớnh, được đặc trưng bởi tờn gọi. File được xỏc
định duy nhất bởi tờn (bao gồm cả đường dẫn) hoặc số hiệu file. Cú rất nhiều cỏc loại file khỏc
nhau như file ảnh (.BMP, .GIF, .JPG, …), file hệ thống (.SYS), file thực hiện được (.COM, .EXE,
…), file dữ liệu (.DBF, .MDB, .DAT, .DOC, …). Tuy nhiờn ở đõy chỳng ta chỉ xem xột cỏc file dữ
liệu, những file này bao gồm nhiều bản ghi cú cựng cấu trỳc xỏc định (loại bản ghi), đồng thời mỗi
bản ghi được phõn chia thành cỏc trường dữ liệu.
Vớ dụ:
File dữ liệu HOSO.MDB dựng để lưu trữ hồ sơ của tất cả cỏc cỏn bộ cụng nhõn viờn chức của
Trường CĐSPKT I như sau:
Tờn file: HOSO.MDB

những người cú trỏch nhiệm mới cú thể truy cập đến toàn bộ hoặc một phần cơ sở dữ liệu.
• Hiệu suất ứng dụng: mặc dự chia sẻ cựng một nguồn chung, cỏc ứng dụng phải cú hiệu suất
trong cơ sở dữ liệu giống như trong sử dụng thụng tin truyền thống.
 Chỳ ý: Năm tiờu chuẩn nờu trờn là yờu cầu đối với một cơ sở dữ liệu được thiết kế hoàn
thiện, trong thực tiễn khụng phải bao giờ cũng thực hiện được đầy đủ, tuỳ từng trường hợp cụ thể
và do những yờu cầu khỏc nhau mà mỗi tiờu chuẩn trờn được tụn trọng hoặc bị vi phạm nhiều ớt
khỏc nhau.
1.1.4 Định nghĩa hệ cơ sở dữ liệu
Như ta đó biết cơ sở dữ liệu là một tập hợp dữ liệu cú liờn quan với nhau được lưu trữ trờn mỏy
tớnh, phần chương trỡnh cho phộp khai thỏc cơ sở dữ liệu này gọi là hệ quản trị cơ sở dữ liệu, núi
cỏch khỏc nú cho phộp mụ tả, lưu giữ, thao tỏc, xử lý cỏc tập hợp dữ liệu tạo nờn cơ sở dữ liệu,
đồng thời nú bảo đảm sự an toàn và bớ mật của cỏc dữ liệu trong mụi trường cú nhiều người sử
dụng.
 Chỳ ý: với mỗi hệ quản trị cơ sở dữ liệu cần thiết phải tồn tại một cơ sở dữ liệu nhưng điều
ngược lại khụng đỳng.
Cỏc hệ quản trị cơ sở dữ liệu cú nhiệm vụ hỗ trợ cho cỏc nhà phõn tớch thiết kế cơ sở dữ liệu cũng
như cho cỏc người khai thỏc cơ sở dữ liệu. Thụng thường một hệ quản trị cơ sở dữ liệu phải đạt
được 5 yờu cầu sau:
7

• Một hệ quản trị cơ sở dữ liệu phải cú ngụn ngữ khai bỏo dữ liệu. Ngụn ngữ khai bỏo dữ
liệu một phương tiện cho phộp khai bỏo cấu trỳc của dữ liệu, mụ tả cỏc mối liờn hệ của dữ
liệu cũng như những qui tắc quản lý ỏp đặt lờn trờn dữ liệu đú. Ngụn ngữ khai bỏo dữ liệu
được xõy dựng trờn một loại mụ hỡnh nào đú. Hiện nay phần lớn cỏc hệ QTCSDL được
xõy dựng dựa trờn mụ hỡnh dữ liệu quan hệ
• Một hệ quản trị cơ sở dữ liệu phải cú ngụn ngữ thao tỏc dữ liệu. Ngụn ngữ thao tỏc dữ
liệu cho phộp người sử dụng cú thể cập nhật dữ liệu (thờm, sửa , xoỏ) khai thỏc dữ liệu cho
nhiều mục đớch khỏc nhau
• Một hệ quản trị cơ sở dữ liệu phải cú ngụn ngữ con truy vấn dữ liệu
• Mỗi hệ quản trị cơ sở dữ liệu cũng cú thể được cài đặt một cơ chế riờng để giải quyết vấn đề

a. Thực thể
Thế giới nhận biết được chứa cỏc phần tử biểu diễn cỏc đối tượng mà người ta cú thể phõn biệt
chỳng với nhau, cỏc đối tượng này là khụng phõn chia được.
Định nghĩa 1. Thực thể là một hỡnh ảnh tượng trưng cho một đối tượng cụ thể hay một khỏi niệm
trừu tượng nhưng cú mặt trong thế giới thực.
b. Đặc trưng
Định nghĩa 2. Đặc trưng của thực thể là những yếu tố giỳp ta nhận biết thực thể, một thực thể bao
gồm nhiều đặc trưng để phõn biệt nú với cỏc thực thể khỏc.
c. Mối quan hệ giữa cỏc kiểu thực thể
Thế giới thực chịu những sự biến đổi được thể hiện bằng sự tạo ra, sự thay đổi, sự loại bỏ. Tất cả
cỏc thể hiện đú được gọi là sự kiện. Cỏc thực thể cú sự liờn kết với nhau trong khi tham gia vào cỏc
sự kiện của thế giới thực.
1.2.2 Cỏc mụ hỡnh dữ liệu
- Thế hệ đầu tiờn
Từ những năm 70 người ta đó thương mại hoỏ thế hệ đầu tiờn cỏc cơ sở dữ liệu. Thế hệ đầu tiờn
này dựa trờn mụ hỡnh dữ liệu phõn cấp hoặc mụ hỡnh dữ liệu mạng.
Mụ hỡnh dữ liệu phõn cấp đặc trưng bởi cấu trỳc dữ liệu được trỡnh bày dưới dạng phõn cấp cõy
nhiều mức, mỗi một mức bao gồm một hoặc nhiều nhúm dữ liệu và chỳng lại cú thể phõn ra thành
nhiều nhúm dữ liệu hoặc cỏc dữ liệu cơ bản (cỏc lỏ cõy).
Mụ hỡnh dữ liệu mạng đặc trưng bởi cấu trỳc dữ liệu tương ứng với một tổ hợp của nhiều phõn cấp
cõy khỏc nhau. Mỗi một đối tượng của thế giới thực được biểu diễn bởi một phõn cấp, cũn sự liờn
kết giữa cỏc đối tượng được thể hiện bằng cỏc múc nối giữa cỏc phõn cấp này.
- Thế hệ thứ hai
Thế hệ thứ hai của cỏc cơ sở dữ liệu được đặc trưng bởi mụ hỡnh dữ liệu quan hệ và mụ hỡnh dữ
liệu quan hệ thực thể.
Mụ hỡnh dữ liệu quan hệ đặc trưng bởi cấu trỳc dữ liệu được tạo nờn bởi một hệ thống cỏc quan hệ
(biểu diễn dạng bảng), trong đú quan hệ biểu diễn một đối tượng của tổ chức.
Mụ hỡnh dữ liệu quan hệ thực thể cú thể coi như là một loại mụ hỡnh quan hệ, nú tập trung trong
một mụ hỡnh cỏc ưu điểm của mụ hỡnh dữ liệu mạng và mụ hỡnh dữ liệu quan hệ. đúng gúp của
mụ hỡnh này là đưa ra một quan niệm thống nhất giữa cỏc dữ liệu thụng qua sự đi lại dễ dàng cho

tớnh khụng tớnh toỏn phải được cung cấp từ thế giới thực. Vớ dụ: thuộc tớnh điểm trung bỡnh mụn
(DTB) được tớnh toỏn từ điểm cỏc mụn, điểm cỏc mụn ta phải nhập vào. Do đú DTB là thuộc tớnh
tớnh toỏn, điểm cỏc mụn là thuộc tớnh khụng tớnh toỏn.
 Chỳ ý: Giỏ trị của một thuộc tớnh khụng phải lỳc nào cũng xỏc định được nờn người ta quy
ước: miền giỏ trị của cỏc thuộc tớnh đều cú thể chứa thờm một giỏ trị đặc biệt gọi là giỏ trị rỗng
(null). Giỏ trị rỗng này, tuỳ theo ngữ cảnh, cú thể đặc trưng cho một giỏ trị khụng thể xỏc định
được hoặc được đặc trưng cho một giỏ trị chưa thể xỏc định được ở thời điểm đang xột nhưng cú
thể được biết vào thời điểm khỏc.
iii) Cỏch mụ tả miền giỏ trị của một thuộc tớnh
- Nếu số cỏc phần tử của miền giỏ trị là ớt thỡ liệt kờ tất cả cỏc giỏ trị của cỏc phần tử.
Vớ dụ: {Giới tớnh, (nam, nữ)}, {Màu, (xanh, đỏ, tớm, vàng)}
- Nếu số cỏc phần tử của miền giỏ trị nhiều thỡ dựng cỏch mụ tả tập hợp.
10

Vớ dụ: {Tuổi học sinh, số nguyờn N: N
∈
[6, 18]}
- Nếu số cỏc phần tử của miền giỏ trị rất nhiều hoặc khụng biết trước được mà khụng cú tớnh chất
đặc trưng nào thỡ mụ tả tập hợp đú theo kiểu của dữ liệu.
Vớ dụ: {Họ tờn, chuỗi ký tự cú độ dài nhỏ hơn 50}
- Nếu kiểu dữ liệu của thuộc tớnh cú cấu trỳc thỡ miền giỏ trị của nú là tớch đề cỏc của cỏc miền
giỏ trị thành phần.
Vớ dụ:
Type Toa_do_man_hinh = Record
x: 0 24;
y: 0 79;
End;
{Toa_do_man_hinh, [0 24] x [0 79]}
Tuy nhiờn, cú những trường hợp miền giỏ trị của một thuộc tớnh chỉ là một tập con thực sự của
tớch đề cỏc của cỏc miền giỏ trị thành phần.

, h
2
, …, h
m
} với mỗi h
j
(j = 1, 2, …, m) là một hàm:
h
j
: R 

Ra
a
i
i
D
∈
sao cho h
j
(a
i
)
∈

i
a
D
. Núi cỏch khỏc, một quan hệ r trờn R là tập hợp con của tớch
đề cỏc của n miền giỏ trị
i

1
(a
2
) … h
1
(a
n
)
h
2
h
2
(a
2
) h
2
(a
2
) … h
2
(a
n
)
… … … … …
h
m
h
m
(a
1

trong r (ký phỏp A
>
r
f
B) nếu và chỉ nếu:
(
∀
h
i
, h
j

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

B.
 Chỳ ý: Ta cú thể viết (A, B) hoặc A
→
B thay cho A
>
r
f
B nếu khụng sợ nhầm lẫn về mặt
ký phỏp.
1.3.4 Khoỏ (Key)
Định nghĩa Giả sử r là một quan hệ trờn R và K
⊆
R. Khi đú K là một khoỏ của r nếu K
→
R.
Gọi K là một khoỏ tối thiểu của r nếu:
- K là một khoỏ của r
- Bất kỳ một tập con thực sự của K khụng là khoỏ của r.
Cỏc thuộc tớnh tham gia vào một khoỏ được gọi là thuộc tớnh khoỏ, cỏc thuộc tớnh khụng tham gia
vào một khoỏ gọi là thuộc tớnh khụng khoỏ.
12

Từ định nghĩa của quan hệ và định nghĩa của khoỏ dễ thấy rằng một quan hệ luụn luụn cú ớt nhất
một khoỏ (tầm thường nhất là lấy R làm khoỏ), cú thể cú nhiều khoỏ và cú thể cú nhiều khoỏ tối
thiểu.
Từ định nghĩa của khoỏ và định nghĩa phụ thuộc hàm trờn quan hệ ta cú thể chứng minh rằng khoỏ
được dựng làm cơ sở để phõn biệt hai bộ tuỳ ý trong một quan hệ. Núi cỏch khỏc, khoỏ của một
quan hệ r trờn R là tập con K
⊆
R thoả món cỏc tớnh chất: Với bất kỳ hai bộ h

K = { SCMT, Họ và tờn, Ngày sinh}
Dễ thấy {SBD} và {SCMT} là cỏc khoỏ tối thiểu.
Trong trường hợp quan hệ cú nhiều khoỏ tối thiểu, khi cài đặt trờn một HQT CSDL người sử dụng
chọn một trong số cỏc khoỏ tối thiểu để làm cơ sở nhận diện một bộ trong quan hệ, khoỏ được chọn
này được gọi là khoỏ chớnh (primary key). Khoỏ chớnh chỉ thật sự cú ý nghĩa trong quỏ trỡnh khai
thỏc CSDL, cũn về phương diện lý thuyết, khoỏ chớnh khụng cú vai trũ gỡ khỏc cỏc khoỏ tối thiểu
cũn lại.
Trong một số HQT CSDL như Access, Oracle, DB2, … cú cài đặt cơ chế tự động kiểm tra tớnh duy
nhất trờn khoỏ chớnh. Vớ dụ, nếu thờm một bộ mới h
n
cú giỏ trị khoỏ chớnh trựng với giỏ trị khoỏ
chớnh của một bộ h
i
đó cú thỡ hệ thống sẽ thụng bỏo lỗi và yờu cầu nhập lại một giỏ trị khỏc.
Để cho thuận tiện trong cỏc phộp xử lý, người ta thường quy ước:
1. Trong một bộ của một quan hệ cỏc thuộc tớnh khoỏ khụng chứa cỏc giỏ trị rỗng.
2. Khụng được phộp sửa đổi giỏ trị của thuộc tớnh khoỏ. Nếu muốn sửa đổi giỏ trị của thuộc tớnh
khúa của một bộ h, người sử dụng phải xoỏ bộ h và sau đú thờm mới một bộ h’ với giỏ trị của
thuộc tớnh khoỏ đó được sửa đổi.
1.3.5 Lược đồ quan hệ (Relation Schema)
Định nghĩa: Một lược đồ quan hệ s (hay một sơ đồ quan hệ) là một cặp <R, F> trong đú R là một
tập hữu hạn và khụng rỗng cỏc thuộc tớnh, F là tập cỏc phụ thuộc hàm trờn R.
 Chỳ ý:
13

1. Cần phõn biệt khỏi niệm quan hệ và lược đồ quan hệ, một quan hệ thuộc vào khụng
gian cơ sở dữ liệu, một lược đồ quan hệ thuộc vào sơ đồ thiết kế.
2. Thứ tự cỏc thuộc tớnh trong R, thứ tự cỏc bộ trong r, thứ tự cỏc phụ thuộc hàm trong F
là khụng quan trọng.
3. Trong một quan hệ khụng được cú 2 bộ bất kỳ tựng nhau.

k
i
i
R
1=
, ở đõy khụng đũi hỏi cỏc R
i
phải phõn biệt với nhau. Mục đớch của
phộp phõn ró này là nhằm loai bỏ cỏc dữ liệu dư thừa (redundancy) và loại bỏ cỏc dị thường: khụng
nhất quỏn (inconsistency), dị thường khi thờm bộ (insertion anormalous), dị thường khi xoỏ bộ
(Deletion anormalous) của quan hệ khi thực hiện cỏc phộp cập nhật (sửa, thờm, xoỏ). Vớ dụ xột
quan hệ HANG {Tờn hóng (TH), Địa chỉ (DC), Mặt hàng (MH), Đơn giỏ(DG)} ta sẽ thấy:
a. Dư thừa dữ liệu: khi cú tờn hóng, thỡ lại cú địa chỉ của hóng đú trong quan hệ.
b. Khụng nhất quỏn, là hệ quả của a); giả sử trong quan hệ cú nhiều bộ ghi tờn hóng và
địa chỉ thỡ khi địa chỉ của hóng thay đổi, nếu ta chỉ sửa địa chỉ này trờn một số bộ thỡ
cỏc bộ khỏc vẫn giữ giỏ trị cũ.
c. Dị thường khi thờm bộ: một hóng chưa cung cấp mặt hàng nào thỡ chưa thể thờm bộ
ứng với hóng đú được (khụng đưa được mặt hàng, đơn giỏ vào).
d. Dị thường khi xoỏ bộ: là vấn đề ngược lại của c); nếu bỏ tất cả cỏc mặt hàng trong quan
hệ thỡ tờn hóng và địa chỉ của hóng cũng bị xoỏ theo (nhất là trong trường hợp nhiều
hóng cựng cung cấp một mặt hàng).
Do vậy, vấn đề đặt ra là: cú thể phõn ró quan hệ trờn thành một tập cỏc quan hệ con nhằm trỏnh tất
cả cỏc điều đó núi ở trờn, nhưng khụng bị mất mỏt thụng tin. Ta định nghĩa phộp phõn ró khụng
mất thụng tin như sau:
Định nghĩa 2: Giả sử lược đồ quan hệ s = <R, F> được phõn ró thành cỏc lược đồ quan hệ s
1
, s
2
, …,
s

…


∏
Rk
r)(
trờn R thoả F.
Thuật toỏn: kiểm tra phộp phõn ró khụng mất thụng tin
Vào: s = <F, R>, phộp phõn ró
ρ
=(s
1
, s
2
, …, s
k
), s
i
= <R
i
, F
i
>
Ra: kết luận phộp phõn ró
ρ
cú phải là khụng mất thụng tin khụng?
14

Thuật toỏn:
- Thiết lập một bảng với n cột và k hàng; hàng i ứng với sơ đồ quan hệ R

1
, A
2
, …, A
n
thỡ phộp
phõn ró khụng mất thụng tin, ngược lại là phộp phõn ró mất thụng tin.
Vớ dụ:
Cho s = <R, F> với R = {a, b, c, d, e, g}, F = {a → b, cd → a, bc → d, ae → g, ce → d},
ρ
= (s
1
, s
2
,
…, s
k
) với: R
1
= {a, b}, R
2
= {a, c, d}, R
3
= {b, c, d}, R
4
= {a, e, g}, R
5
= {c, d, e}. Kiểm tra xem phộp
phõn ró mất thụng tin?
- Lập bảng:

b
16
s
2
A
1
b
22
A
3
A
4
b
25
b
26
s
2
A
1
A
2
A
3
A
4
b
25
b
26

A
1
b
42
b
43
b
44
A
5
A
6
s
4
A
1
A
2
b
43
b
44
A
5
A
6
s
5
b
51

1
A
1
A
2
b
13
b
14
b
15
b
16
s
1
A
1
A
2
b
13
b
14
b
15
b
16
s
2
A

2
A
3
A
4
b
35
b
36
s
3
A
1
A
2
A
3
A
4
b
35
b
36
s
4
A
1
A
2
b

4
A
5
b
56
s
5
A
1
b
52
A
3
A
4
A
5
A
6
- Xột phụ thuộc hàm ce → d bảng khụng đổi (quay lại xột a → b ta cú bảng sau):
5 a b c d e g
Bảng
kết quả
6 a b c d e g
15

s
1
A
1

A
3
A
4
b
25
b
26
s
2
A
1
A
2
A
3
A
4
b
25
b
26
s
3
A
1
A
2
A
3

A
5
A
6
s
4
A
1
A
2
b
43
b
44
A
5
A
6
s
5
A
1
A
2
A
3
A
4
A
5

B là một phụ thuộc hàm. Ta núi rằng
A
→
B được suy diễn logic từ F nếu quan hệ r trờn R đều thoả món cỏc phụ thuộc hàm của F thỡ
cũng thoả món phụ thuộc hàm A
→
B.
Gọi tập tất cả cỏc phụ thuộc hàm được suy diễn logic từ F là bao đúng (closure) của F, ký phỏp là
F
+
. Nếu F = F
+
thỡ F được gọi là họ đầy đủ (full family) cỏc phụ thuộc hàm.
1.3.8 Hệ tiờn đề cho phụ thuộc hàm
Để cú thể xỏc định được khoỏ của một quan hệ và cỏc suy diễn lụgic giữa cỏc phụ thuộc hàm cần
thiết phải tớnh được F
+
từ F, điều này đũi hỏi phải cú cỏc quy tắc, muốn vậy phải xõy dựng hệ tiờn
đề cho phụ thuộc hàm.
Cho R là một tập hữu hạn và khụng rỗng cỏc thuộc tớnh, ký phỏp P(R) là tập cỏc tập con của R, giả
sử A, B, C
∈
P(R).
- Tiờn đề 1 (Phản xạ): B
⊆
A thỡ A
→
B
- Tiờn đề 2 (Tăng trưởng): A
→

∪
B
∪
C.
Chứng minh:
1. C
→
A (giả thiết)
2. C
∪
B
→
A
∪
B hay B
∪
C
→
A
∪
B (tăng trưởng của 1. thờm B)
3. A
∪
B
→
C (giả thiết)
4. A
∪
B
∪

Một số tớnh chất của phụ thuộc hàm:
1) Tớnh chất hợp: nếu A
→
B và A
→
C thỡ A
→
B
∪
C
2) Tớnh chất tựa bắc cầu: nếu A
→
B và B
∪
D
→
C thỡ A
∪
D
→
C
3) Tớnh chất tỏch: nếu A
→
B và C
⊆
B thỡ A
→
C
1.3.9 Cỏc dạng phụ thuộc hàm
i) Phụ thuộc hàm đầy đủ (fully functional dependence)

B là cần thiết vỡ nếu C
⊆
B
⊆
A thỡ theo tiờn đề phản xạ luụn cú A
→
B
→
C, cũn điều kiện B khụng xỏc định hàm cho A để loại bỏ nhiều khoỏ khỏi quan hệ ở dạng chuẩn 3.
1.4 CÁC PHẫP TOÁN CỦA NGễN NGỮ THAO TÁC DỮ LIỆU
Cỏc phộp tớnh cơ bản mà nhờ đú một cơ sở dữ liệu được thay đổi là chốn (insert), loại bỏ (delete),
và thay đổi (change). Trong mụ hỡnh cơ sở dữ liệu quan hệ được nờu trờn, cỏc phộp tớnh này được
ỏp dụng cho từng bộ của cỏc quan hệ lưu trữ trong mỏy.
1.4.1 Phộp chốn (Insert)
Phộp chốn thờm một bộ vào quan hệ r trờn R = {a
1
, a
2
, …, a
n
} cú dạng r= r
∪
t.

Cỳ phỏp: INSERT (r; a
1
= d
1
, a
2

1
, d
2
, …, d
n
)
Mục đớch của phộp chốn là thờm một bộ phận vào một quan hệ nhất định. Kết quả của phộp tớnh
này cú thể gõy ra một số sai sút bởi những lý do sau:
1. Bộ mới được thờm vào là khụng phự hợp với lược đồ quan hệ cho trước.
2. Một số giỏ trị của một số thuộc tớnh nằm ngoài miền giỏ trị của thuộc tớnh đú.
3. Giỏ trị khoỏ của bộ mới cú thể là giỏ trị đó cú trong quan hệ đang lưu trữ.
1.4.2 Phộp loại bỏ (Del)
Phộp loại bỏ (Del) là phộp xoỏ một bộ ra khỏi một quan hệ cho trước. Giống như phộp chốn, phộp
loại bỏ cú dạng: r = r – t

Cỳ phỏp: DEL (r; a
1
= d
1
, a
2
= d
2
, …, a
n
= d
n
)
hoặc: DEL (r; d
1

1.4.3 Phộp thay đổi (Change)
Ta cú thể dựng hai phộp tớnh trờn để xử lý toàn bộ cỏc thao tỏc trờn CSDL quan hệ, tuy nhiờn đụi
khi người ta chỉ cần thay đổi giỏ trị của một hay một số cỏc thuộc tớnh nhất định, khi đú sử dụng
phộp tớnh thay đổi (CH) là rất cần thiết, nhằm giảm thiểu cỏc thao tỏc cũng như sự nhầm lẫn cú thể
cú. Phộp thay đổi như sau: Gọi tập {c
1
, c
2
, …, c
p
}
⊆
{a
1
, a
2
, …, a
n
} là tập cỏc thuộc tớnh của bộ cần
thay đổi giỏ trị, phộp thay đổi cú dạng:

Cỳ phỏp: CH (r; a
1
= d
1
, a
2
= d
2
, …, a

, …, b
m
= d
m
;
c
1
= e
1
, c
2
= e
2
, …, c
n
= e
p
).
Vớ dụ: Cụng ty Fujitsu đó hết hạn thuờ địa chỉ F8 fortuna LH, họ chuyển toàn bộ tổ chức hiện
cú vào HCM city, khi đú ta cú phộp thay đổi sau.
CH (HANG; TH = Fujitsu, DC = F8 fortuna LH, MH = PC, DG = 1200$; DC = Q1 HCM city).
1.5 CÁCH THỨC TỔ CHỨC DỮ LIỆU VẬT Lí
18

1.5.1 Giới thiệu cỏch thức tổ chức dữ liệu
Dữ liệu vật lý là kết quả thể hiện của việc đưa thụng tin vào quản lý trờn mỏy tớnh. Ở mức này cơ
sở dữ liệu vật lý được tổ chức dưới dạng cỏc tệp (file) dữ liệu, bao gồm cỏc bản ghi cú cựng cấu
trỳc xỏc định (loại bản ghi), đồng thời mỗi bản ghi được phõn chia thành cỏc trường dữ liệu ( field
names), mỗi trường chiếm một số xỏc định cỏc bytes và cú kiểu dữ liệu cố định. Cỏc phộp tớnh đặc
trưng trờn cỏc tệp dữ liệu là:


Tư tưởng cơ bản của tổ chức tệp băm là phõn chia tập cỏc bản ghi của tệp dữ liệu thành cỏc cụm
(Buckets). Mỗi cụm bao gồm một hoặc nhiều khối (block). Mỗi khối chứa một số lượng cố định cỏc
bản ghi.
Mỗi cụm ứng với một địa chỉ băm. Địa chỉ băm được đỏnh số từ 0 đến k-1. ở đầu mỗi khối đều
chứa con trỏ trỏ tới khối tiếp theo trong cụm, khối cuối cựng trong cụm chứa con trỏ rỗng. Cú một
bảng chỉ dẫn cụm (bucket directory) chứa k con trỏ, mỗi con trỏ ứng với một cụm, đú là địa chỉ của
khối đầu tiờn trong cụm.
Hỡnh 1.2
Tổ chức tệp
băm
0
 
Nul
l
1

b
1
b
2
Nul
l

b
3

k-1
  
Nul

Để xoỏ một bản ghi với khoỏ x, sử dụng thủ tục tỡm bản ghi. Nếu bản ghi thuộc một khối nào đú cú
nhiều bản ghi khỏc, khi đú bản ghi cú khoỏ x được loại bỏ, nếu bản ghi đú là duy nhất trong khối,
khi đú sẽ đồng thời với việc giải phúng khối khỏi cụm chứa khối.
- Sửa một bản ghi
Giả sử cần sửa một hoặc một số trường của một bản ghi cú khoỏ x. Nếu trường cần sửa cú tham gia
trong khoỏ x, việc sửa chữa sẽ là loại bỏ bản ghi này và thờm vào một bản ghi mới cho tệp (vỡ khi
sửa khoỏ thỡ rất cú thể bản ghi sẽ thuộc vào cụm khỏc). Thủ tục thờm, xoỏ giống như trờn. Nếu
trường cần sửa khụng thuộc khoỏ tiến hành sửa cỏc giỏ trị cỏc trường, nếu bản ghi khụng tồn tại,
xem như cú lỗi.
1.6.2 Tệp chỉ số
Một kiểu tổ chức tệp dữ liệu truy nhập khúa rất thường dựng trong CSDL là tệp chỉ số. Để dễ trỡnh
bày, ta giả thiết rằng tệp dữ liệu chớnh luụn luụn là tệp đó được sắp xếp theo khoỏ (vớ dụ theo thứ
tự tăng dần). Khoỏ luụn luụn được quan niệm rằng, bao gồm một hoặc nhiều trường cú thứ tự và cú
độ dài cố định. Giỏ trị của khoỏ cú thể là số, cú thể là một xõu kớ tự. Nếu là một xõu ký tự, việc sắp
xếp là theo A, B, C, … hay thứ tự từ điển. Chẳng hạn x
i
, y
j
là cỏc xõu ký tự, hai xõu x
1
…x
k
< y
1
…y
m
khi và chỉ khi:
1. k < m và x
1
…x

, d
1
), …

k
2
(k
1
, d
1
)

(k
2
, d
2
), …
 
(k
2
, d
2
)
 
 
 
 
(k
n
, d

1
, d
1
)
bằng với x, xem như bản ghi khụng tồn tại.
Phương phỏp tỡm kiếm nhị phõn
Phương phỏp tỡm kiếm tuần tự núi chung là chậm, thường cú thể sử dụng cỏc phương phỏp khỏc
như phương phỏp nhị phõn (chia đụi), vỡ tệp chỉ số bao giờ cũng được sắp xếp. Giả sử tệp chỉ số
được lưu trữ trờn n khối (b
1
, b
2
, …, b
n
). Để tỡm một bản ghi cú khoỏ x, trước hết chọn khối b
n/2
, so
sỏnh giỏ trị k thuộc khối b
n/2
và x, nếu k > x thỡ bộ cần tỡm nằm ở một trong cỏc khối b
1
, b
2
, …, b
n/2
,
ngược lại trong cỏc khối từ b
n/2+1
, …, b
n

i+1
, bản ghi khoỏ x sẽ là bản ghi đầu tiờn của khối mới này.
- Xoỏ một bản ghi
Quỏ trỡnh giống như thờm bản ghi, lưu ý nếu khi xoỏ một bản ghi tạo nờn một khối rỗng, khi đú cú
thể loại bỏ cả khối đú.
- Sửa một bản ghi
Sử dụng thủ tục tỡm một bản ghi để xỏc định bản ghi cần sửa.
- Nếu cỏc trường cần sửa khụng phải là trường khoỏ, việc sửa đổi giỏ trị của bản ghi tiến
hành bỡnh thường, giỏ trị của bản ghi sau khi sửa được ghi lại vị trớ cũ.
- Nếu cỏc giỏ trị cỏc trường cần sửa tham gia khoỏ, quỏ trỡnh sửa sẽ là xoỏ và sau đú thờm
mới một bản ghi.
 Chỳ ý: Tệp chỉ số cú thể được cấu trỳc một cỏch đơn giản hơn rất nhiều. Tệp này chỉ gồm hai
trường: khoỏ k, con trỏ d. Mỗi bản ghi của tệp chỉ số tương ứng với một bản ghi của tệp chớnh, cũn
22

con trỏ d là địa chỉ của bản ghi trong tệp chớnh. Trong trường hợp này tệp dữ liệu chớnh khụng
nhất thiết phải được sắp xếp.
1.6.3 B - Cõy (Balanced tree)
Một kiểu tổ chức dữ liệu thường được sử dụng trong cơ sở dữ liệu là tổ chức cõy cõn bằng (B-cõy).
B-cõy được tổ chức theo cấp m, cú cỏc tớnh chất sau đõy:
- Gốc của cõy hoặc là một nỳt lỏ hoặc ớt nhất cú hai con,
- Mỗi nỳt (trừ nỳt gốc và nỳt lỏ) cú từ [m/2] đến m con,
- Mỗi đường đi từ gốc đến bất kỳ lỏ nào đều cú độ dài như nhau.
Hỡnh 3 biểu diễn một cõy phõn cấp 5. Mỗi khối ứng với lỏ chứa tối đa 5 bản ghi. Khối ứng với nỳt
chứa được 5 con trỏ và 4 khoỏ. Cỏc nỳt trong B-cõy thực chất là khối tệp chỉ số. Cỏc khối chỉ số
được phõn theo từng mức, mức càng cao độ chi tiết càng lớn.
Cấu trỳc mỗi nỳt trong B-cõy cú dạng:
(p
0
, k

.
Cỏc nỳt lỏ chỉ chứa khoỏ của cỏc bản ghi trong tệp chớnh.
Hỡnh 1.4
Tổ chức
B-cõy

2
 
Null
Nul
l

10

12

Null
     
2 4 6 10 …….
Xột cỏc phộp toỏn trờn B-cõy như sau:
- Tỡm kiếm một bản ghi
Giả sử cần tỡm một bản ghi nào đú cú giỏ trị khoỏ là x, trước hết cần xỏc định đường đi từ nỳt gốc
tới nỳt lỏ cú thể chứa bản ghi này. Muốn vậy liờn tiếp duyệt cỏc nỳt (cỏc nỳt cú dạng (p
0
, k
1
, p
1
, k
2

k
n
thỡ tỡm theo nỳt trỏ từ p
n
.
23

Cuối cựng sẽ tới một nỳt lỏ. trong nỳt lỏ tỡm tuần tự bằng cỏch so sỏnh khoỏ x với cỏc giỏ trị khoỏ
trong nỳt lỏ, từ đú sẽ nhận được bản ghi cần tỡm nếu bản ghi đú tồn tại, cũng cú thể khụng tồn tại
bản ghi trong tệp.
- Thờm một bản ghi
Giả sử cần thờm một bản ghi cú khoỏ là x vào tệp B-cõy, trước hết cần xỏc định vị trớ nỳt lỏ sẽ
chứa bản ghi đú. Thủ tục xỏc định nỳt lỏ như thủ tục tỡm kiếm một bản ghi.
Giả sử nỳt lỏ tỡm được là L. Nếu nỳt lỏ L cũn chỗ trống, việc thờm bản ghi mới đỳng vào thứ tự của
khoỏ.
Nếu nỳt L hết chỗ trống, tạo một nỳt lỏ mới L’. Chuyển nửa dữ liệu cuối của L sang L’ rồi bổ sung
bản ghi cú khoỏ x vào vị trớ tương ứng trong L hoặc L’.
Giả sử nỳt L-1 là nỳt ngay trờn nỳt L, khi đú phải thờm cặp (p’, k’) vào L-1, trong đú p’ là con trỏ
trỏ tới lỏ L’ và k’ là khoỏ bộ nhất chứa trong L’. Nếu L-1 đó đủ m con trỏ rồi, việc bổ sung (p’, k’)
vào L-1 dẫn tới việc nỳt l-1 phải tỏch làm 2 như làm với nỳt L. Quỏ trỡnh này cú thể truyền ứng
đến tận nỳt gốc của cõy dọc theo đường đi đó chọn.
- Xoỏ một bản ghi
Giả sử cần loại bỏ bản ghi cú khoỏ x vào B-cõy, trước hết cần xỏc định vị trớ nỳt lỏ sẽ chứa bản ghi
đú. Thủ tục xỏc định nỳt lỏ như thủ tục tỡm kiếm một bản ghi.
Nếu bản ghi cần xoỏ là bản ghi đầu tiờn của nỳt L thỡ phải tỡm tới nỳt p ngay trờn nỳt L để chỉnh
lại giỏ trị khoỏ đầu tiờn của L cú trước đú.
Nếu L lại là nỳt con đầu tiờn của p thỡ khoỏ đầu tiờn của L khụng đặt được ở p, khi đú khụng cần
thiết chỉnh sửa nữa. Tuy nhiờn cú thể khoỏ đầu tiờn đú của p lại xuất hiện ở một nỳt trờn đú. Do
vậy việc tỡm và chỉnh lý khoỏ này vẫn phải tiếp tục ngược lờn cho tới tận gốc như đường đi đó
vạch ra khi dựng thủ tục tỡm kiếm.