BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THẾ ANH

T×m hiÓu c¸c phô thuéc bao hµm
trong m« h×nh quan hÖ vµ øng dông
vµo viÖc chuyÓn ®æi sang m« h×nh EER
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Huế, 2015


MỤC LỤC
Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục các thuật ngữ
Danh mục các chữ viết tắt
Danh mục các bảng
Danh mục các hình vẽ, đồ thị
MỞ ĐẦU .......................................................................................................... 1
Chương 1. CÁC RÀNG BUỘC DỮ LIỆU TRONG MÔ HÌNH
QUAN HỆ ................................................................................................ 3
1.1. Giới thiệu chung về vấn đề toàn vẹn ngữ nghĩa......................................... 3
1.2. Khái niệm ràng buộc toàn vẹn ................................................................... 3
1.2.1. Các yếu tố của ràng buộc toàn vẹn ......................................................... 4

3.3.4. Xác định mối quan hệ ........................................................................... 53
3.3.5. Các mối quan hệ được xác định bởi các quan hệ biểu diễn mối quan hệ59
3.3.6. Các mối quan hệ kết tập ........................................................................ 62
3.4. Gán các thuộc tính .................................................................................... 64
3.5. Ví dụ minh họa tiến trình trích xuất từ mô hình quan hệ
sang mô hình EER ................................................................................... 66
3.6. Kết luận .................................................................................................... 67
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ...................................................... 69
TÀI LIỆU THAM KHẢO ............................................................................... 70


DANH MỤC CÁC THUẬT NGỮ
Attribute

Thuộc tính

Composite Attribute

Thuộc tính phức hợp

Dangling Key Attribute

Thuộc tính khóa bộ phận

Derived Attribute

Thuộc tính dẫn xuất

Domain


Inclusion Dependencies

Phụ thuộc bao hàm

Multivalued Attribute

Thuộc tính đa trị

MultiValued Dependencies

Phụ thuộc đa trị

N-ary Relationship

Mối quan hệ đa nguyên bậc n

Non Key Attribute

Thuộc tính không khóa

Partial Key

Khoá bộ phận

Primary Key

Khoá chính

Primary Key Attribute



Strong Entity Type

Kiểu thực thể mạnh

Subclass

Lớp con

Superclass

Lớp cha

Weak Entity Relation

Quan hệ tập thực thể yếu

Weak Entity Type

Kiểu thực thể yếu


DANH MỤC CÁC CHỮ VIẾT TẮT
CSDL

Cơ sở dữ liệu

DBMS

Hệ quản trị cơ sở dữ liệu


Phụ thuộc đa trị

NKA

Thuộc tính không khóa

PKA

Thuộc tính khóa chính

RBTV

Ràng buộc toàn vẹn


DANH MỤC CÁC BẢNG

Số hiệu
bảng

Tên bảng

Trang

3.1

Biểu diễn quan hệ cấu trúc EER

39

2.1

Mối quan hệ nhị nguyên

17

2.2

Biểu diễn lớp cha và lớp con trong mô hình EER

19

2.3

Ký hiệu chuyên biệt hóa và các lớp con trong mô hình EER

20

2.4

Tổng quát hoá CAR, TRUCK và MOTOCYCLE thành
VEHICLE

21

2.5

Chuyên biệt hóa toàn phần

21


24

2.11

Sơ đồ lưới với sự đa kế thừa của CSDL trường đại học

25

2.12

Sự hợp nhất của hai hay nhiều lớp sử dụng ký hiệu category

26

2.13

Mô hình EER và CSDL của một trường đại học

27

3.1

Ví dụ mẫu mô hình quan hệ

41

3.2

Các bước trong kỹ thuật đảo ngược của cơ sở dữ liệu quan hệ

Một khóa ngoài xác định một quan hệ nhị nguyên

58

3.8

Một khóa ngoài xác định một quan hệ is-a

59

3.9

Một quan hệ biểu diễn mối quan hệ thông thường xác định
một quan hệ n-ary

61

3.10

Một quan hệ biểu diễn mối quan hệ chuyên biệt xác định một
quan hệ n-ary

62

3.11

Xác định một mối quan hệ tổng thể

64


thuộc tính được bao hàm trong tập hợp giá trị của thuộc tính khác.
Theo đó, luận văn gồm các phần như sau: phần mở đầu, ba chương nội dung,
phần kết luận và tài liệu tham khảo.
Nội dung Chương 1 là nhằm giới thiệu khái quát các ràng buộc dữ liệu trong mô
hình quan hệ.
Nội dung Chương 2 là nhằm giới thiệu khái quát mô hình ER và một mô hình
mở rộng của mô hình ER, đó là mô hình EER.


2

Dựa vào các nội dung trình bày trong Chương 1 và Chương 2, Chương 3 tập
trung trình bày phương pháp trích xuất một mô hình EER từ mô hình quan hệ có sử
dụng các ràng buộc phụ thuộc bao hàm.
Do thời gian còn hạn chế nên Luận văn không thể tránh khỏi những nhầm lẫn và
thiếu sót. Chúng tôi mong nhận được những ý kiến đóng góp của quý thầy cô, bạn bè và
những người quan tâm đến Luận văn này.


3

Chương 1
CÁC RÀNG BUỘC DỮ LIỆU TRONG MÔ HÌNH QUAN HỆ
1.1. Giới thiệu chung về vấn đề toàn vẹn ngữ nghĩa
Một số vấn đề khó khăn cho một hệ cơ sở dữ liệu là bảo đảm tính nhất quán
CSDL. Một trạng thái CSDL được gọi là nhất quán nếu CSDL thỏa một tập các ràng
buộc, được gọi là ràng buộc toàn vẹn ngữ nghĩa [3]. Duy trì CSDL nhất quán đòi hỏi
phải sử dụng đến nhiều cơ chế khác nhau như điều khiển hoạt động đồng thời, độ tin
cậy, bảo vệ và kiểm soát tính toàn vẹn ngữ nghĩa. Kiểm soát toàn vẹn ngữ nghĩa bảo
đảm được tính nhất quán của CSDL bằng cách phế bỏ các chương trình cập nhật dẫn

kế - đó là một việc làm rất quan trọng. Ràng buộc toàn vẹn được xem như là một
công cụ để diễn đạt ngữ nghĩa của CSDL. Một CSDL được thiết kế cồng kềnh nhưng
nó thể hiện được đầy đủ ngữ nghĩa của thực tế vẫn có giá trị cao hơn rất nhiều so
với một cách thiết kế gọn nhẹ nhưng nghèo nàn về ngữ nghĩa vì thiếu các ràng buộc
toàn vẹn của CSDL.
Công việc kiểm tra ràng buộc toàn vẹn thường được tiến hành vào thời điểm
cập nhật dữ liệu (thêm, sửa, xoá). Những ràng buộc toàn vẹn phát sinh phải cần được
ghi nhận và xử lý một cách tường minh (thường là bởi một hàm chuẩn hoặc một
đoạn chương trình).
Ràng buộc toàn vẹn và kiểm tra sự vi phạm ràng buộc toàn vẹn là hai trong
số những vấn đề quan trọng trong quá trình phân tích thiết kế cơ sở dữ liệu, nếu
không quan tâm đúng mức đến những vấn đề trên, thì có thể dẫn đến những hậu quả
nghiêm trọng về tính an toàn và toàn vẹn dữ liệu, đặc biệt là đối với những cơ sở dữ
liệu lớn.
1.2.1. Các yếu tố của ràng buộc toàn vẹn
Mỗi ràng buộc toàn vẹn có bốn yếu tố: điều kiện, bối cảnh, bảng tầm ảnh hưởng
và hành động phải cần thực hiện khi phát hiện có ràng buộc toàn vẹn bị vi phạm:
- Điều kiện:
Điều kiện của ràng buộc toàn vẹn là sự mô tả, và biểu diễn hình thức nội
dung của nó. Điều kiện của một ràng buộc toàn vẹn R có thể được biểu diễn bằng
ngôn ngữ tự nhiên, ngôn ngữ đại số quan hệ, ngôn ngữ mã giả, ngôn ngữ truy vấn
SQL,… ngoài ra điều kiện của ràng buộc toàn vẹn cũng có thể được biểu diễn bằng
phụ thuộc hàm.
Ví dụ 1.1. Sau đây là một số ràng buộc toàn vẹn trên lược đồ CSDL quản lý
sinh viên.
Mỗi lớp học phải có một mã số duy nhất để phân biệt với các lớp học khác
trong trường.


5

Xoá (X)

+

r2
r3

-(*)

…
rn
Bảng này chứa toàn các ký hiệu +, – hoặc -(*).
Chẳng hạn + tại (dòng r1, cột thêm) thì có nghĩa là khi thêm một bộ vào quan hệ
r1 thì ràng buộc toàn vẹn bị vi phạm.


6

Dấu - Tại ô (dòng r2, cột sửa) thì có nghĩa là khi sửa một bộ trên quan hệ r2
thì ràng buộc toàn vẹn không bị vi phạm.
Quy ước:
- Không được sửa thuộc tính khoá.
- Nếu không bị vi phạm do không được phép sửa đổi thì ký hiệu là - (*).
- Hành động cần phải có khi phát hiện có ràng buộc toàn vẹn bị vi phạm:
Khi một ràng buộc toàn vẹn bị vi phạm, cần có những hành động thích hợp.
Thông thường có 2 giải pháp:
Thứ nhất: Đưa ra thông báo và yêu cầu sửa chữa dữ liệu của các thuộc tính
cho phù hợp với quy tắc đảm bảo tính nhất quán dữ liệu. Thông báo phải đầy đủ và
phải thân thiện với người sử dụng. Giải pháp này là phù hợp cho việc xử lý thời gian
thực.

buộc toàn vẹn miền giá trị, ràng buộc toàn vẹn liên thuộc tính, ràng buộc toàn vẹn
liên bộ.
Thứ hai: Ràng buộc toàn vẹn có phạm vi là nhiều quan hệ bao gồm: ràng buộc
toàn vẹn phụ thuộc tồn tại, ràng buộc toàn vẹn liên bộ - liên quan hệ, ràng buộc toàn
vẹn liên thuộc tính - liên quan hệ.
Để minh hoạ, chúng ta xét ví dụ sau đây:
Ví dụ 1.2. Cho một CSDL C dùng để quản lý việc đặt hàng và giao hàng của
một công ty. Lược đồ CSDL C gồm các lược đồ quan hệ sau:
Q1: Khach (MAKH, TENKH, DIACHIKH, DIENTHOAI)
Mô tả:
Mỗi khách hàng có một mã khách hàng (MAKH) duy nhất, mỗi MAKH
xác định tên khách hàng (TENKH), địa chỉ (DIACHIKH), số điện thoại
(DIENTHOAI).
Q2: Hang (MAHANG, TENHANG, QUYCACH, DVTINH)
Mô tả:
Mỗi mặt hàng có một mã hàng (MAHANG) duy nhất, mỗi MAHANG xác
định tên hàng (TENHANG), quy cách hàng (QUYCACH), đơn vị tính (DVTINH).
Q3: Dathang (SODH, MAHANG, SLDAT, NGAYDH, MAKH)
Mô tả:
Mỗi mã số đặt hàng (SODH) xác định một ngày đặt hàng (NGAYDH) và mã
khách hàng tương ứng (MAKH). Biết mã số đặt hàng và mã mặt hàng thì biết được
số lượng đặt hàng (SLDAT). Mỗi khách hàng trong một ngày có thể có nhiều lần đặt
hàng.
Q4: Hoadon (SOHD, NGAYLAP, SODH, TRIGIAHD, NGAYXUAT)
Mô tả:
Mỗi hoá đơn tổng hợp có một mã số duy nhất là SOHD, mỗi hoá đơn bán hàng


8



Sửa

Xóa

Khach

+

-

-

+ Ràng buộc toàn vẹn về tính duy nhất
Ví dụ 1.4. Mỗi phòng ban phải có một tên gọi duy nhất
Ngoài ra nhiều khi ta còn gặp những ràng buộc toàn vẹn khác chẳng hạn như
ràng buộc toàn vẹn sau trong quan hệ sau đây:


9

KETQUA(MASV, MAMH, LANTHI, DIEM)
Mỗi sinh viên chỉ được đăng thi mỗi môn thi tối đa là 3 lần
b. Ràng buộc toàn vẹn về miền giá trị
Ràng buộc toàn vẹn có liên quan đến miền giá trị của các thuộc tính trong một
quan hệ. Ràng buộc này thường gặp. Thông thường các hệ quản trị CSDL đã tự động
kiểm tra (một số) ràng buộc loại này.
Ví dụ 1.5. Với r là một quan hệ của Hoadon ta có ràng buộc toàn vẹn sau:
R 3:  t  r
t.TRIGIAHD > 0

Xóa

Hoadon

+

+

-

1.2.2.2. Ràng buộc toàn vẹn có bối cảnh gồm nhiều quan hệ
a. Ràng buộc toàn vẹn về khoá ngoài
Ràng buộc toàn vẹn về khoá ngoài là một trường hợp đặc biệt của ràng buộc
bao hàm. Cũng giống như ràng buộc toàn vẹn về khoá nội, loại ràng buộc toàn vẹn
này rất phổ biến trong các CSDL.
Ví dụ 1.7.
R2.dathang[MAKH]  khach[MAKH]

R2

Thêm

Sửa

Xóa

Dathang

+



Dathang

+

-

-

Hoadon

+

+

-

c. Ràng buộc toàn vẹn liên bộ liên quan hệ
Ràng buộc loại này là mối liên hệ giữa các bộ trong một lược đồ cơ sở dữ
liệu. Chẳng hạn như tổng số tiền phải trả trong mỗi hoá đơn (chitiethd) phải bằng
TRỊ GIÁ HOÁ ĐƠN của hoá đơn đó trong quan hệ Hoadon. Hoặc số lượng học
viên trong một lớp phải bằng SOHOCVIEN của lớp đó.
Ngoài ra còn có một số loại RBTV khác như: ràng buộc toàn vẹn về thuộc
tính tổng hợp, ràng buộc toàn vẹn do tồn tại chu trình, ràng buộc toàn vẹn về giá trị
thuộc tính theo thời gian.
1.3. Các ràng buộc cấu trúc
Các ràng buộc cấu trúc diễn tả những đặc tính ngữ nghĩa cơ bản vốn có trong
mô hình. Thí dụ về những ràng buộc như thế nào là ràng buộc khóa duy nhất trong mô
hình quan hệ. Vì vậy chúng có vai trò rất quan trọng trong quá trình thiết kế CSDL.
Chúng tôi có thể diễn tả mối liên kết giữa các đối tượng, chẳng hạn như các phụ thuộc

Tập tất cả các phụ thuộc hàm trên một sơ đồ quan hệ kí hiệu là FD (Functional
Dependencies) [1]. Cần chú ý rằng, chúng ta chỉ xét các phụ thuộc hàm thỏa mãn cho
mọi quan hệ trên sơ đồ tương ứng của nó. Chúng ta không thể xem xét một phụ thuộc
hàm thỏa một quan hệ r đặc biệt (ví dụ quan hệ rỗng) của sơ đồ R rồi sau đó qui nạp
rằng phụ thuộc đó thỏa trên R.
1.4.2. Phụ thuộc bao hàm
Một lược đồ quan hệ là một đối tượng R(U), trong đó R là tên của lược đồ quan
hệ và U là một dãy hữu hạn <A1, ....., Am> của thuộc tính. Để đơn giản, chúng ta đôi
khi viết A1, ....., Am cho <A1, ....., Am>. Để tránh các tham chiếu không rõ ràng, chúng
tôi cũng viết R. A để chỉ một thuộc tính A trong một lược đồ quan hệ R. A bộ t trên U
= <A1, ....., Am> là một chuỗi <a1, ....., am> đó, ai là một yếu tố từ các miền của Ai. Một
mối quan hệ (trên R(U), hoặc đơn giản hơn R) là một bộ dữ liệu trên U. Nếu t = là một bộ qua U = <A1, ....., Am>, và X = <Ai1, ....., Aik> trong đó i1, ....., ik là
các thành viên riêng biệt của {1, ....., m}, khi đó t[X] là <Ai1, ....., Aik>. Nếu r là một
quan hệ trên R, khi đó r[X] = {t[X]|  r}. Một lược đồ cơ sở dữ liệu D = {R1(U1), .....,
Rn(Un)} (hoặc đơn giản là {R1, ....., Rn}) là một tập hợp các lược đồ quan hệ [3]. Một
cơ sở dữ liệu trên D là một ánh xạ liên kết mà mỗi lược đồ quan hệ Ri(Ui) với một mối
quan hệ ri trên Ri. Trong phần còn lại của bài viết này, chúng tôi sẽ áp dụng các ký
hiệu sau đây: nếu R là một lược đồ quan hệ, thì biểu thị một quan hệ r trên R; Tương


12

tự, đại diện cho một cơ sở dữ liệu d trong lược đồ cơ sở dữ liệu D. Người ta biểu diễn
thuộc tính đơn lẻ bằng bảng chữ cái từ phía trước của bảng chữ cái (A, B,…) và tập
thuộc tính với các chữ cái từ phía sau (X, Y,…).
Định nghĩa 1.2. Giả sử Ri(A1, .....,Am) và Rj(B1, ....., Bp) là hai lược đồ quan hệ
(không nhất thiết khác nhau) trong một lược đồ cơ sở dữ liệu D ={R1, ..., Rn}. Nếu X
là một chuỗi các k thành viên riêng biệt của A1, ....., Am, và nếu Y là một chuỗi các k
thành viên riêng biệt của B1, ....., Bp, khi đó chúng ta nói rằng phụ thuộc bao hàm


này, một môn học có thể được dạy bởi một số giảng viên và không phụ thuộc vào dạy
cho đối tượng nào. Mối quan hệ ràng buộc này giữa các tập thuộc tính và một sơ đồ
quan hệ gọi là phụ thuộc đa trị. Bây giờ, chúng ta hãy xem định nghĩa hình thức của
phụ thuộc đa trị.
Định nghĩa 1.3. Cho R(U) là một sơ đồ quan hệ với U  { A1 , A2 ,..., An } là tập các
thuộc tính. X và Y là tập con của U. Chúng ta nói rằng X xác định đa trị Y hay Y phụ
thuộc đa trị vào X và kí hiệu  Y nếu với mọi quan hệ r xác định trên R(U) và với
hai bộ t1 và t 2 bất kỳ mà t1[ X ]  t2[ X ] thì tồn tại bộ t 3 sao cho:
t3[ X ]  t1[ X ], t3[ X ]  t1[Y ] và t3[ Z ]  t2 [ Z ] với Z  U \ XY .

Do tính đối xứng của t1 và t 2 dễ dàng thấy rằng trong r còn tồn tại bộ t 4 sao
cho: t4 [ X ]  t2 [ X ], t4 [Y ]  t2 [Y ] và t4[Z ]  t1[Z ] với Z  U \ XY .
Tập tất cả các phụ thuộc đa trị trên một lược đồ quan hệ kí hiệu là MVD
(MultiValued Dependencies) [1]. Có thể thấy phụ thuộc hàm là một trường hợp đặc
biệt của phụ thuộc đa trị, bởi vậy, cũng như các phụ thuộc hàm, chúng ta cũng có một
hệ tiên đề đúng đắn và đầy đủ đối với các phụ thuộc hàm và phụ thuộc đa trị.
1.5. Kết luận
Các ràng buộc toàn vẹn đảm bảo rằng các thay đổi thực hiện đối với cơ sở dữ
liệu bởi những người sử dụng hợp pháp không dẫn đến mất tính toàn vẹn dữ liệu.
Trong chương này, chúng tôi đã xem xét một số ràng buộc điển hình, bao gồm các
ràng buộc miền, các ràng buộc về khóa và một số dạng ràng buộc khác.
Các ràng buộc miền đặc tả một tập các giá trị có thể được kết hợp với một thuộc
tính. Các ràng buộc như vậy cũng có thể cấm sử dụng các giá trị null đối với các thuộc
tính đặc biệt.
Các ràng buộc toàn vẹn tham chiếu đảm bảo rằng một giá trị xuất hiện trong
một quan hệ đối với một tập các thuộc tính nhất định trong một quan hệ khác.
Các phụ thuộc hàm là một sự tổng quát hóa của các phụ thuộc khóa. Chúng yêu
cầu rằng giá trị đối với một tập các thuộc tính nhất định xác định duy nhất giá trị đối
với một tập các thuộc tính khác.

Chương này sẽ giới thiệu khái quát về mô hình ER, mô hình ER mở rộng, mô
hình quan hệ và chuyển đổi mô hình EER sang mô hình quan hệ.
2.2. Mô hình thực thể - mối quan hệ (ER)
Mô hình ER thường được biểu diễn dưới dạng lược đồ, được gọi là lược đồ
thực thể - mối quan hệ (gọi tắt là lược đồ ER). Trong thực tế đã có nhiều hệ thống
thông tin được thiết kế xuất phát từ mô hình ER. Ngoài việc đóng vai trò là mô hình
khái niệm, mô hình này còn được xem là một trong những mô hình dữ liệu ngữ nghĩa.
Thông qua mô hình ER, người ta có thể xác định được các tập thực thể của một hệ
thống thông tin, đồng thời ngữ nghĩa của mô hình còn được thể hiện bởi các mối quan
hệ giữa các tập thực thể.
2.2.1. Thực thể
Thực thể là các đối tượng mà chúng ta cần quản lý. Thực thể thường chỉ là một
người, nơi chốn, biến cố hay một khái niệm. Mỗi thực thể có thể có một hoặc nhiều
thuộc tính. Các thuộc tính không được trùng tên.
Kiểu thực thể (entity type): Là tập thực thể có cùng một tính chất chung. Kiểu
thực thể có tên và nên đặt danh từ số ít, dùng chữ in hoa. Trong mô hình ER ta sử dụng
hình chữ nhật để biểu diễn kiểu thực thể.
Thể hiện kiểu thực thể: Là đối tượng cụ thể của một tập thực thể.


16

Ví dụ:
- STUDENT là một kiểu thực thể.
- Sinh viên Nguyễn Văn A là một thể hiện của kiểu thực thể STUDENT
Kiểu thực thể mạnh (strong entity type): Là kiểu thực thể tồn tại độc lập với
các kiểu thực thể khác.
Kiểu thực thể yếu (weak entity type): Là kiểu thực thể mà sự tồn tại của nó
phụ thuộc vào kiểu thực thể khác.
Kiểu thực thể mà kiểu thực thể yếu phụ thuộc vào gọi là kiểu thực thể chủ. Mối