Trang1

Luận văn tốt nghiệp Nguyễn Văn Giang
LỜI GIỚI THIỆU
Ngày nay, mọi ngành, mọi lĩnh vực trong đời sống, trong khoa học
kinh doanh cũng như trong mọi mặt vận động của xã hội dưới mọi quy mô
từ xí nghiệp nhà máy, công ty đến quốc gia, quốc tế đều đã áp dụng công
nghệ thông tin vào quản lý và nhiều lĩnh vực khác như: điều khiển các quá
trình sản xuất, điều khiển tự động, trợ giúp quyết định, thương mại điện tử ...
Môn cơ sở dữ liệu là một trong những môn quan trọng liên quan đến
các vấn đề thu thập, xử lý và cho những thông tin cần thiết từ dữ liệu. Mục
tiêu chính của môn này là đưa ra các phương pháp để tổ chức thông tin làm
sao cho tối ưu nhất các khâu trên của dữ liệu[3]. Để tiến hành các mục tiêu
trên, người ta đi xây dựng các mô hình dữ liệu, và trên cơ sở mô hình dữ liệu
này người ta đi xây dựng các hệ cơ sở dữ liệu. Từ các mô hình này, nhân
loại đã đạt được nhiều thành công rực rỡ trên lĩnh vực này mà sản phẩm của
nó được thương mại hoá trên khắp thế giới như: Foxbase, Foxpro, DBase,
Access, SQL for Windows,...
Lý thuyết cơ sở dữ liệu nguyên cứu các cơ chế, nguyên lý và phương
pháp tổ chức dữ liệu trên các vật mang tin để khai thác có hiệu quả dữ liệu
trong các hệ thống tin học ứng dụng cũng như trong các hệ lưu trữ và tra cứu
thông tin. Trong số các mô hình cho việc tổ chức và khai thác cơ sở dữ liệu
(CSDL), trên thực tế mô hình quan hệ [6] là được quan tâm hơn cả. Bởi vì
mô hình này được xây dựng trên cơ sở lý thuyết và các quan hệ có cơ sở
toán học chặt chẽ, xử dụng rộng rãi các công cụ đại số và logíc. Trong cơ sở
dữ liệu quan hệ, các quan hệ có hình ảnh trực quan như là các bảng biểu
thông thường mà ta hay gặp. Điều đó tạo nên những thuận lợi trong việc
thực hiện các thao tác trên các quan hệ, các ngôn ngữ thao tác trên cơ sở dữ
Trang2

Luận văn tốt nghiệp Nguyễn Văn Giang

Chương 2: Giới thiệu về phụ thuộc hàm và một số tính chất của chúng
Chương 3: Các dạng chuẩn hoá dữ liệu trong mô hình quan hệ và một
số thuật toán của chúng
Chương 4: Cài đặt một số chương trình thực hiện cho thuật toán đã
nêu trên.
Trong thời gian hoàn thành bản luận văn tốt nghiệp, em xin chân
thành cảm ơn khoa CNTT và các thầy cô giáo đã giúp đỡ và truyền đạt cho
em những kiến thức cơ bản trong những năm học vừa qua.
Đặc biệt em xin chân thành cảm ơn thầy Đoàn Văn Ban - Viện CNTT
đã tận tình giúp đỡ và chỉ dẫn cho em những kiến thức và phương pháp làm
việc để em hoàn thành bản luận văn tốt nghiệp.
Trang4

Luận văn tốt nghiệp Nguyễn Văn Giang
CHƯƠNG I : TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU
I.1. KHÁI NIỆM VỀ CƠ SỞ DỮ LIỆU
Để lý giải cho các khái niệm, trước hết chúng ta hãy xem xét hệ thống bán
xe máy của công ty HONDA Việt Nam bằng máy tính. Dữ liệu lưu trữ trong máy
tính bao gồm thông tin về hành khách, loại xe, phân khối và giá cả .... Mọi thông
tin về mối quan hệ này được biểu diễn trong máy thông qua việc đặt mua xe của
khách hàng.Vậy làm sao để biểu diễn dữ liệu đó và bảo đảm cho khách hàng mua
đúng chiếc xe mà mình đăng kí. Những dữ liệu nêu trên được lưu trữ trong máy
theo một quy định nào đó được gọi là cơ sở dữ liệu (CSDL). Phần chương trình để
xử lý, thay đổi số liệu này là các hệ quản trị cơ sở dữ liệu [6].
Tổng quát chúng ta có các định nghĩa sau :
1. Cơ sở dữ liệu: Là khối dữ liệu phản ánh thông tin được lưu trữ trên hệ thống
theo một cấu trúc nào đó gọi tắt là cơ sở dữ liệu ( CSDL ).
2. Hệ quản trị cơ sở dữ liệu: Là một hệ thống phần mềm quản lý cơ sở dữ liệu
và tập các thao tác xử lý dữ liệu.
Hệ quản trị cơ sở dữ liệu là rất quan trọng, như là một bộ diễn dịch với ngôn

Yếu tố quan trọng nhất của cấu trúc cơ sở dữ liệu là dạng cấu trúc dữ liệu
lưu trữ được mô tả. Có thể thấy rằng loại dữ liệu nền tảng của việc mô tả các mối
quan hệ là loại bản ghi. Bởi vì các ràng buộc giữa các loại bản ghi tạo ra bản chất
cấu trúc cơ sở dữ liệu. Vì thế dựa trên việc xác định các ràng buộc giữa các loại dữ
Trang6

Luận văn tốt nghiệp Nguyễn Văn Giang
liệu được cho như thế nào mà chúng ta phân loại các mô hình dữ liệu. Có nghĩa là
từ cách nhìn của người sử dụng việc mô tả các dữ liệu và các ràng buộc giữa các
dữ liệu được thực hiện như thế nào. Hiện nay đã có nhiều loại mô hìmh dữ liệu.
Bốn
loại mô hình dữ liệu đang được sử dụng rộng rãi là: Mô hình phân cấp, Mô hình
mạng, Mô hình quan hệ, Mô hình hướng đối tượng.
I.2.1. Mô hình phân cấp [6]
Mô hình dưc liệu là một cây, trong đó các nút biểu diễn các tập thực thể,
giữa các con và nút cha được liên hệ theo một mối quan hệ xác định ( Dựa trên cấu
trúc cây)
Ví dụ hình sau: Gốc Alà thực thể lớn, ta chia thực thể A làm 3 thực thể nhỏ
hơn là B,C,D. Trong đó thực thể B ta lại chia ra làm 3 thực thể nhỏ hơn là G,H,I,
tương tự C có hai thực thể nhỏ là K và L, và D có 3 thực thể nhỏ là M,N và P
I.2.2. Mô hình mạng [6]
Mô hình biểu diễn là một đồ thị có hướng ( Cấu trúc đồ thị )
B DC
G H I K L
M N P
A
A
B
D
C

mô hình khác nhau nhằm mô tả và thể hiện thế giới thực một cách chính xác và
phù hợp như mô hình quan hệ thực thể ( Entily Relationship Model), mô hình dữ
liệu hướng đối tượng ( Object Oriented Model ),...
Theo cách nhìn của người sử dụng thì một cơ sở dữ liệu quan hệ là một tập
các bảng biến đổi theo thời gian.
Với ưu điểm về tính cấu trúc đơn giản và khả năng hình thức hoá phong phú
cơ sở dữ liệu quan hệ dễ dàng mô phỏng các hệ thống thông tin tiết kiệm có tính
độc lập cao, dễ sửa đổi, bổ xung cũng như khai thác dữ liệu. Mặt khác, việc khai
thác và áp dụng kĩ thuật tổ chức và sử dụng bộ nhớ cho phép cài đặt các cơ sở dữ
liệu quan hệ đem lại hiệu quả cao và làm cho cơ sở dữ liệu khẳng định được ưu thế
của mình trên thị trường.
Trang9

Luận văn tốt nghiệp Nguyễn Văn Giang
Trang10

Luận văn tốt nghiệp Nguyễn Văn Giang
CHƯƠNG II : CÁC PHỤ THUỘC HÀM
Đặt vấn đề:
- Khái niệm thực thể: Là đối tượng có trong thực tế mà chúng ta cần khảo sát và
giải quyết nhiều vấn đề liên qua đến đối tượng này.
Ví dụ: Thực thể sinh viên, thực thể con người, thực thể hệ thống kế toán tài
vụ ,...
Thông thường người ta chia các thực thể lớn thành các thực thể đơn giản
hơn và đến khi một thực thể được mô tả bàng một tệp dữ liệu.

- Các thuộc tính: Là đặc trưng của một thực thể. Các thuộc tính dùng để phân biệt
thực thể đó với thực thể khác.
Ví dụ: Thực thể sinh viên có các thuộc tính sau :Mã_SV, Họ_tên, Giới_tính,
Nơi_sinh, Quê_quán ...

02 Nguyễnviệt Cường Nam 12-5-1974 Vĩnh phúc
03 Phan Hoa Nữ 13-7-1978 Hà tĩnh
.
.
.
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
20 Hoàng quốc Khanh Nam 12-6-1976 Hà nội
Dễ thấy rằng thực thể sinh viên trên chính là tệp dữ liệu mô tả về thông tin
của các Sinh viên của một trường nào đó, với năm thuộc tính cụ thể gồm: Mã_sv,
Họ_tên, Giới_tính, Năm_sinh, Quê_quán. Trong tệp dữ liệu trên có 20 bản ghi.
II.1. PHỤ THUỘC HÀM
II.1.1. Khái niệm về phụ thuộc hàm
Trên cơ sở nghiên cứu tệp dữ liệu người ta định nghĩa chính xác tệp dữ liệu
như sau ( đôi khi người ta còn gọi là quan hệ ).
Cho trước R = { a1, a2,..., an } là tập hữu hạn và không rỗng, nó được gọi là
tập các thuộc tính. Mỗi thuộc tính ai ( i = 1,2,...,n ) là một miền giá trị D(a
i
) và
Trang12

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

, h
j
∈ r ta có ( a ∈A mà h
i
(a) = h
j
(a)) => ( b∈B ( h
i
(b) = h
j
(b))) ⇒
A→B
Có thể thấy rằng, B mà phụ thuộc hàm vào A nếu hai dòng bất kỳ mà các giá
trị của tập thuộc tính A bằng nhau từng cặp một thì kéo theo các giá trị trên tập
thuộc tính B cũng phải bằng nhau từng cặp một.
Ví dụ: Trong quan hệ Xe_máy có các thông tin về số xe, mác của xe, màu
của xe, giá xe, năm sản xuất.
Số xe Mác Màu Giá Năm sản xuất
100 Honda Đỏ 500 1996
300 Dream Mận 700 1998
500 Wave Xanh biển 1000 1999
Theo định nghĩa, trong quan hệ trên, nếu số xe xác định màu xe thì khi biết
số xe người ta biết ngay được màu của xe, giá trị về màu này là duy nhất.
Số xe → Màu
Số xe → Giá
Mác → Giá
Định nghĩa phụ thuộc hàm là rất quan trọng, nó nói lên mối quan hệ ngữ
nghĩa trong nội bộ một tệp dữ liệu. Mối quan hệ ngữ nghĩa này được thể hiện giữa
các tập cột. Ngoài phụ thuộc hàm ra, hiện nay người ta đã phát hiện ra trên ba
mươi loại phụ thuộc dữ liệu. Người ta cũng chỉ ra tương ứng mỗi phụ thuộc dữ liệu

1
(phản xạ): Nếu Y ⊆ X thì X→Y
A
2
(tăng trưởng):Nếu Z ⊆ R, X→Y thì XZ → YZ
A
3
(bắc cầu):Nếu X→Y, Y→Z thì X→Z
Xét ví dụ sau: AB → C, C → A
Cần chứng minh rằngBC → ABC. Thật vậy từ
1. C → A(giả thiết)
2. BC → AB (tăng trưởng)
3. AB → C (giả thiết)
Trang15

Luận văn tốt nghiệp Nguyễn Văn Giang
4. AB → ABC (tăng trưởng (3) thêm AB)
5. BC → ABC (bắc cầu từ (2) và (4)).
Chúng ta có các bổ đề sau:
Bổ đề 1:
Hệ tiên đề Amstrong là đúng. Có nghĩa là F là tập phụ thuộc hàm đúng trên
quan hệ r. Nếu X→Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề
Amstrong thì X→Y là đúng trên quan hệ r.
Chứng minh: Lần lượt kiểm tra tính đúng đắn của ba đề A
1
,A
2
,A
3
A

cầu cho WX →WY và WY →Z suy ra WX →Z .
c. Vì Z ⊆ Y nên X →Z ( theo luật phản xạ )
Dùng luật bắc cầu cho X →Y và Y →Z có X →Z.
Một hệ quả quan trọng của luật tách và luật hợp là nếu X →Y suy ra X→A
i
với mọi A
i
∈ Y.
Để dễ dàng chứng minh cho tính đầy đủ của hệ tiên đề Amstrong, ở đây đưa
thêm khái niệm bao đóng của tập các thuộc tính của tập các phụ thuộc hàm. Gọi F
là tập các phụ thuộc hàm trên tập thuộc tính R, X ⊆ R. X
+
là bao đóng của X đối
với F được định nghĩa như sau:
X
+
= {A \ X →A ∈F
+
}
Nói cụ thể X
+
là tập tất cả các thuộc tính A mà phụ thuộc hàm X→A có thể
được suy diễn logíc từ F nhờ hệ tiên đề Amstrong.
Bổ đề 3:
X →Y suy diễn từ hệ tiên đề Amstrong khi và chỉ khi Y ⊆ X
+
Chứng minh:
Giả sử Y = A
1
,A

Tính đúng đắn của hệ tiên đề đã được chứng minh qua bổ đề 1.ở đây chỉ cần
chứng minh tính đầy đủ tức là nếu X→Y không thoả trên r thì X→Y không thể suy
diễn từ F.
Gọi F là tập các phụ thuộc hàm trên tập thuộc tính R. Giả sử rằng X→Y là
không thể suy dẫn được từ hệ tiên đề. Xét quan hệ r gồm hai tập sau:
11...1 11...1
11...1 00...0
Các thuộc tính thuộc X
+
Các thuộc tính còn lại
Trước hết cần chỉ ra rằng tất cả các phụ thuộc hàm thuộc F đều thoả r. Thật
vậy, giả sử (V→W) ∈F nhưng không thoả trên r. Do đó V ⊆ X
+
,
hoặc hai bộ của r
sẽ không bằng nhau ít nhất trên một thuộc tính của V. Như vậy W không thể là tập
con của X
+
hoặc V → W thoả trên r .
Gọi A ∈ W nhưng A không thuộc X
+
. Vì XV ∈ X
+
, X→V suy ra từ bổ đề 3 .
( X→V ∈ F ) do vậy, nhờ luật bắc cầu suy ra X→A, nhưng do A không thuộc X
+
như giả thiết, do vậy là mâu thuẫn. Từ đó kết luận rằng mỗi (V→W) ∈ F đề thoả
trên r .
Bây giờ cần chứng minh rằng X→Y không thoả trên r. Giả sử rằng X→Y là
thoả trên r. Như trên có X ⊆ X

X→A
1
,. . . , X→A
n
nhờ luật hợp .
Để có thể phục vụ quá trình thiết kế lược đồ cơ sở dữ liệu, sau đây sẽ đưa ra
một số khái niệm.
Gọi các tập phụ thuộc hàm F là tối thiểu nếu :
a/ Mỗi vế phải của một phụ thuộc hàm F chỉ có một thuộc tính .
b/ Không tồn tại một phụ thuộc hàm X→A thuộc F mà
F
+
= (F - { X→A})
+
Trang19

Luận văn tốt nghiệp Nguyễn Văn Giang
c/ Không tồn tại một phụ thuộc hàm X→A thuộc F và một tập con Z của X
mà : F
+
= (F - { X→A} ∪ { Z→A } )
+
.
Thực vậy điều kiện b/ bảo đảm cho tập F không có phụ thuộc hàm nào là dư
thừa và diều kiện c/ đảm bảo không có một thuộc tính nào tham gia phía trái của
phụ thuộc hàm là dư thừa. Vế phải của phụ thuộc hàm ở điều kiện a/ chỉ có một
thuộc tính bảo đảm chắc chắn không có một thuộc tính nào trên vế phải là dư thừa .
II.1.5. Định nghĩa sơ đồ quan hệ
Cho trước R = { a1, a2,..., an }
A,B ∈ R, đặt A→ B là một phụ thuộc hàm.

A→R
Không tồn tại A
’
sao cho A
’
⊂ A(A
’
tập con thực sự của A)
mà A
’
→ R
Khoá cho sơ đồ quan hệ: Cho trước s = <R,F> là sơ đồ quan hệ .Trong đó F =
<A1→B1,...,At→Bt>.
Khi đó :
A ⊆ R được gọi là khoá của s nếu A→R∈F
+
.
A là khoá tối tiểu của s nếu :
- A→R∈F
+
- Không tồn tại A
’
sao cho A
’
⊂ A sao cho A
’
→R∈F
+
Khoá đây chính là hình ảnh của cột mã số hay cột số thứ tự trong Tệp dữ
liệu nào đó .

,h
2
,...,h
m
} là tệp dữ liệu trên tập thuộc tính R = {a
1
,a
2
,...,a
n
}, A∈
R.
A
+
r
= {a : a ∈ R và Ar→{a}}
A
+
r
được gọi là bao đóng của A trong r.
Nếu A là một tập bất kỳ ( tập cột bất kỳ ) thì A
+
là tập hợp tất cả những cột
mà phụ thuộc hàm vào A trong sơ đồ quan hệ S, chúng ta có A
+
r
là tập hợp tất cả
các cột mà phụ thuộc hàm vào {a} trong tệp dữ liệu r. Dễ thấy rằng theo hệ tiên đề
của Amstrong thì.
A ⊆ A

với thời gian tính là
đa thức sẽ được trình bầy ở chương sau..
II.2. CÁC PHÉP TOÁN TRÊN CƠ SỞ DỮ LIỆU QUAN HỆ
II.2.1. Phép chèn (Insert)
Phép chèn là phép thêm một bộ vào quan hệ r{A1,A2,...,An} có dạng: r =
r∪t.
Cú pháp:
Insert{r;A1=d1,A2=d2,...,An=dn}.
Trong đó A
i
với i= 1,2,...,n là tên các thuộc tính và Di ∈ Dom(A
i
) là các giá
trị thuộc miền trị tương ứng của thuộc tính A
i
.
Ví dụ: Thêm một bộ t4 = ( Vũ văn Tần ,1960,Trương ĐHĐĐ,422 ) vào
quan hệ Nhân_viên trên:
Insert(Nhân_viên ; Họ tên = Vũ vă Tần, Năm _sinh = 1960, Công tác= ĐH
ĐĐ, Lương=425).
Nếu xem như các trường là cố định, khi đó có thể biểu diễn phép chèn dưới
dạng không tường minh như sau :
Insert (r ;d1,d2,...,dn).
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 với những lý do sau
đây :
Trang23

Luận văn tốt nghiệp Nguyễn Văn Giang
1. Bộ mới thêm vào là không phù hợp với lược đồ quan hệ cho trước;

sai sót của phép thay đổi cũng sẽ xảy ra tương tự như phép chèn và phép loại bỏ.
II.3. CÁC PHÉP TÍNH XỬ LÝ BẢNG
Yêu cầu bài toán:
Trong phần này chúng ta sẽ khảo sát một số phép toán sử lý bảng ( Tệp dữ
liệu ). Chúng tạo nên ngôn ngữ xử lý dữ liệu. Ngôn ngữ xử lý dữ liệu là một ngôn
ngữ quan trọng trong hệ quản trị cơ sở dữ liệu ngững hệ quản trị Cơ sở dữ liệu này
là những công cụ sắc bén cho chúng ta trong quá trình xử lý, đặc biệt là xử lý
thông tin trong các hệ thông tin quản lý như: SQL for Windows, Orcale, IBM
DB2, Foxpro, Access,...
Ngôn ngữ xử lý dữ liệu đều dựa trên mô hình dữ liệu quan hệ. Trong đó hạt
nhân chủ yếu là tệp dữ liệu (bảng). Chúng ta sẽ khảo sát những phép toán xử lý tệp
dữ liệu cơ bản nhất của cái nằm trong ngôn ngữ xử lý dữ liệu này. Các phép toán
này được đề xuất bởi người sáng lập ra mô hình dữ liệu quan hệ.
Các phép toán xử lý tệp dữ liệu sau đây được chắt lọc từ ngôn ngữ xử lý dữ
liệu (Ngôn ngữ đại số quan hệ).
Đại số quan hệ như là cơ sở của ngôn ngữ bậc cao để thao tác trên quan hệ.
Người khai thác cơ sở dữ liệu phải nêu ra những câu hỏi diễn tả yêu cầu tìm kiếm
thông tin, kết xuất thông tin. Đại số quan hệ cung cấp các phép toán để đáp ứng
nhu cầu trên.
Gọi r là một quan hệ trên tập thuộc tính R = {A1,...,An}
ở đây luôn giả thiết rằng quan hệ r là tập hữu hạn các bộ. Đối với các phép
hợp, giao và trừ, hai quan hệ tham gia phải là khả hợp.
Trang25

Luận văn tốt nghiệp Nguyễn Văn Giang
Cho trước hai quan hệ

Từ hai quan hệ trên ta có các phép tính sau:
II.3.1. Phép hợp
Giả sử r và t là hai tệp dữ liệu cùng có n cột , trong ví dụ trên thì r và t có 3