Bộ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
NGUYỄN THỊ PHƯƠNG THÙY
KHÓA VÀ PHẢN KHÓA TRONG MÔ HÌNH DỮ LIỆU DẠNG KHÓI
• *
Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01
LUẬN VĂN THẠC SĨ MÁY TÍNH Người hướng dẫn khoa học: TS. Trịnh Đinh Vinh
HÀ NỘI, 2013
LỜI CẢM ƠN
Tôi xin bày tỏ lòng biểt ơn sâu sắc đến thầy giáo TS Trịnh Đình Vinh, người đã tận tình
hướng dẫn, giúp đỡ và động viên tôi trong suốt quá trình làm luận văn.
Xin cám ơn tẩt cả các thầy giáo, cô giáo trong Trường Đại học Sư phạm Hà Nội 2 đã tạo điều
kiện hết sức để tôi được học tập và hoàn thành khóa học được thuận lợi.
Xin chân thành cảm ơn các thầy giáo, cô giáo đã trực tiếp giảng dạy và mang đển cho tôi
niềm say mê nghiên cứu khoa học.
Tôi xin gửi lời biểt ơn chân thành tới đồng nghiệp, bạn bè, gia đình đã luôn tạo điều kiện,
ủng hộ về mọi mặt để tôi hoàn thành luận văn.
Hà Nội, tháng ỉ 2 năm 2013 Tác giả luận văn
Nguyễn Thị Phương Thùy
LỜI CAM ĐOAN
Tôi xin cam đoan rằng kết quả nghiên cửu trong luận văn này là trung thực và không
trùng lặp với các đề tài khác, Tôi cũng xin cam đoan rằng các thông tin trích dẫn trong luận văn
đã được chỉ rõ nguồn gốc.
Tác giả luận văn
Nguyễn Thị Phương Thùy
MỤC LỤC
1.6.1.
1.6.2. Bài toán thành viên và thuật toán tìm baođóng của tập thuộc tính
21
1.2.
1.3.
1.4. MỞ ĐẦU

tính chất về khóa và phản khóa trong mô hình khối.
1.12. Nghiên cứu mối quan hệ giữa khóa và phản khóa trong cơ sở dừ liệu dạng
1.13. khối.
4. Đối tưọng và phạm vi nghiên cửu:
1.14. *Đổì tượng nghiên cứu
1.15. Khóa và phản khóa trong mô hình dữ liệu dạng khối.
1.16. *Phạm vi nghiên cứu
1.17. Các tính chất của khóa trong mô hình dữ liệu dạng khối.
1.18. Các tính chất của phản khóa trong dữ liệu dạng khối.
4
5. Phưong pháp nghiên cứu:
1.19. Phương pháp tổng họp phân tích các vấn đề có liên quan đến đề
tài. Phương pháp lý luận.
1.20. Phương pháp chứng minh.
6. Giá thiết khoa học:
1.21. Phát biểu các tính chất và mối quan hệ giữa khóa và phản khóa trong mô
hình dữ liệu dạng khối.
7. Cấu trúc của luận văn:
1.22. Luận văn gồm: Lời mở đầu, ba chương nội dung, phần kết luận và tài liệu
tham khảo.
1.23. Chương 1: Trình bày các khái niệm cơ bản nhất về mô hình quan hệ. Trình bày
các phép toán đại số trên mô hình quan hệ, các vấn đề về phụ thuộc hàm, bao đóng, các
tính chất cùa khóa vả phản khóa trong mô hình cơ sở dữ liệu quan hệ. Phần cuối của
chương trình bày về các dạng chuẩn,
1.24. Chương 2: Giới thiệu tổng quan về mô hình khối: định nghĩa khối, lược đồ khối,
lát cắt, khóa, đại số quan hệ trên khối, phụ thuộc hàm, các dạng chuẩn trong khối.
1.25. Chương 3: Phát biểu và chứng minh một số tính chẩt của khóa và phản khóa
trong mô hình dữ liệu dạng khối.
1.26. CHƯƠNG 1: MÔ HÌNH cơ SỞ DỮ LIỆU QUAN HỆ
1.27. Mô hình dữ liệu quan hệ (Relational Data Model) gọi tắt là mô hình quan

1.41.
1.42.
7
1.2. Ai 1.3. a
2
1.4.
1.5. A
n
1.6. hi(A]) 1.7. hi(A
2
)
1.8.
1.9. hi(A
n
)
1.10. h
2
(A,) 1.11. h
2
(A
2
)
1.12.
1.13. hstAn)
1.14. 1.15. 1.16. 1.17.
1.18. h
m
(Ai) 1.19. h
m
(A2)

1.40. 3
1.41. CT00
4
1.42. Lưu Nam
1.43. Bản
hàng
1.44. 2
1.45. Bảng 1.2: Bảng cơ sở c 1.46. ữ liệu nhân viên
1.43. Bộ giá trị: (CT001, Nguyễn Anh, Giám đốc, 6) là một bộ. Neu một bộ t
= (di, d2, dm) £ г, г xác định trên tập thuộc tính и, X
Q
u. Khi đó, kí hiệu t.x là giá trị
của tập thuộc tính X trên bộ t. Neu X = {Ai, A2, Ak) thì
1.44. t.x = (d[, d
2
, d
k
) .
1.45. Định nghĩa 1.3
1.46. Tập tất cả các thuộc tính cần quản lý của một đối tượng cùng với moi
quan hệ giữa chúng được gọi là lược đồ quan hệ. Lược đồ quan bệ R với tập thuộc tính
и = {А], A
2
, A
n
} được viết là R(Ab A2, An) hoặc R(U).
1.47. Khi đó, một quan hệ r sẽ được xác định trên lược đồ R(U). Miền giá trị
cua quan hệ r là tập tất cả các bộ của quan hệ được xác định trong lược đồ quan hệ
R(U).
1.3. Khóa của quan hệ [5], [7]:

1
1.53. А 1.54. 2
4/01/92
1.55. H
N
1.56. T
OAN
1.57.
SV0
1.58. В
1.59. 3/
05/92
1.60. V
P
1.61. L
Y
1.62.
SV0
1.63. В
1.64. 3/
05/92
1.65. V
P
1.66. T
OAN
1.67.
Sinh
v
i
ê

1.84. Trương
Hoa
1.85. 4
1.86. CT005 1.87. Phong Lan 1.88. 4
1.61.
1.4.2. Phép giao
1.62. Cho hai quan hệ r và s khả giao. Giao của r và s ký hiệu là r n s là một
quan hệ gồm tập tất cả các bộ thuộc r và thuộc s. Ta có:
1.63. rn s = {t I t e r v à t es}
1.64. Ví dụ 1.5: trong ví dụ 1.3 đã có hai người nhập dừ liệu vào hai quan hệ
Bảng 1 và Bảng 2.
1.65.
1.4.3. Phép trừ
1.66. Cho hai quan hệ r và s khả hợp. Hiệu của r và s ký hiệu là r s là tập tất cả
các bộ thuộc r nhưng không thuộc s. Ta có:
1.67. r - s = {t I t 6 r và t Ể s}
1.68. Ví dụ 1.6: Trong ví dụ 1.3 Bảng 1 vàBảng 2 có cùng thuộc.Nói
theo lý
1.69. thuyết hai bảng này có cùng lược đồ. Phép trừ trên hai bảng được
1
1.89. Mã sô 1.90. Họ và tên 1.91. Bậc lương
1.92. CT003
1.93. Nguyên
Giang
1.94. 2
1.95. CT006 1.96. Hoàng Ban 1.97. 4
1.98. CT001
1.99. Trương
Hoa
1.100.4

chẳng hạn mã số 1 - mã số 2.
1.75.
1
1.112.Mã sô 1.113.Họ vả tên 1.114.Bậc lương
1.115.CT006
1.116.Nguyên
Giang
1.117.2
1.118.CT003 1.119.Hoàng Ban 1.120.4
1.121. Bảng 1.6: 1.122.
3
hép trừ hai quan hệ
Nhân viên
Bảng
1.123. Mã
sô
1.124. Đơ
n vị
1.125.Bậc lương
1.126. CT
001
1.127. Bán
hàng
1.128.4
1.129. CT
002
1.130. Kê
toán
1.131.6
1.132. CT

tên
1.144.Đ
ơn vị
1.145.Bậc
lương
1.146.
CT001
1.147.C
TOOl
1.148. Nguyên
Giang
1.149.B
án hàng
1.150.4
1.151.
CT001
1.152.C
T002
1.153. Trương
Hoa
1.154.B
án hàng
1.155.4
1.156.
CT002
1.157.C
TOOl
1.158. Nguyên
Giang
1.159.K

3
hép nhân hai quan hệ
1.81.
1.82.
1.4.6. Phép chọn
1.83. Phép chọn là phép toán lọc lấy ra một tập con các bộ của quan hệ đã cho
thoả mãn một điều kiện xác định. Điều kiện đó được gọi là điều kiện chọn hay biểu thức
chọn.
1.84. Biểu thức chọn F được định nghĩa là một tổ hợp logic của các toán hạng,
mồi toán hạng là một phép so sánh đơn giản giữa hai biến là hai thuộc tính hoặc giữa
một biến là một thuộc tính và một giá trị hằng. Biểu thức chọn F cho giá trị đúng hoặc
sai đối với mỗi bộ đã cho của quan hệ khi kiểm tra riêng bộ đó.
1
1.178.
Mã sô
1.179.Họ và tên 1.180.Đơn vị
1.181.Bậc
lương
1.182.
CT001
1.183.Nguyên Anh
1.184.Giám
đôc
1.185. 6
1.186.
CT002
1.187.Nguyên
Giang
1.188.Kê
Toán

1.209.
CT002
1.210.Kê
Toán
1.211. 4
1.212.
CT003
1.213.Bán
hàng
1.214. 3
1.215.
CTỌỌ4
1.216.Bán
hàng
1.217. 2
1.218.
CT005
1.219.Nhân
viên
1.220. 5
1.221. Bảng 1.8: Phép chiêu trong quan hệ
1.85. Các phép toán so sánh trong biểu thức F Ỷ,
s
1.86. Các phép toán logic trong biếu thức F: A (và), V
(hoặc), -I (phủ định). Cho r là một quan hệ và F là
một biếu thức logic trên các thuộc tính của r. Phép
chọn trên quan hệ r với biểu thức chọn F, kí hiệu là
ÔF (r), là tập tất cả các
1.87. bộ của r thoả mãn F. Ta có: ỗp (r) = {11 tEr F(t)}.
1