ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN THỊ LINH
CÁC THUẬT TOÁN XỬ LÝ
PHỤ THUỘC HÀM NỚI LỎNG
Chuyên ngành: Khoa học Máy tính
Mã số: 8 48 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TSKH NGUYỄN XUÂN HUY
1
Thái Nguyên năm 2020
LỜI CAM ĐOAN
Tên tôi là: Nguyễn Thị Linh Sinh ngày: 18/08/1989 Học viên lớp Cao học CK17A - Trường Đại học Công nghệ Thông tin và
Truyền thông - Thái Nguyên.
Tôi xin cam đoan toàn bộ nội dung liên quan tới đề tài được trình bày trong luận văn là do bản thân tôi tìm hiểu và nghiên cứu, dưới sự hướng dẫn khoa học của Thầy giáo PGS. TSKH. Nguyễn Xuân Huy.
Tác giả luận văn
Các nội dung trong luận văn đúng như nội dung trong đề cương và yêu cầu của thầy giáo hướng dẫn. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Nếu sai tôi hoàn toàn chịu trách nhiệm trước hội đồng khoa học và trước pháp luật.
2
Nguyễn Thị Linh
LỜI CẢM ƠN
Lời đầu tiên, em xin bày tỏ lòng cảm ơn và kính trọng sâu sắc đối với Thầy PGS.TS Nguyễn Xuân Huy, người đã tận tình hướng dẫn em trong suốt quá trình làm luận văn này. Thầy giúp em hiểu và tiếp cận những vấn đề khoa học rất lý thú, hướng em vào nghiên cứu các lĩnh vực rất thiết thực và bổ ích. Em đã học hỏi được rất nhiều ở Thầy cũng như phong cách làm việc, phương pháp tiếp cận tri thức. Em luôn được Thầy chỉ bảo tận tình trong suốt quá trình làm luận văn.
Em cũng xin thể hiện sự kính trọng và biết ơn đến Quý Thầy Cô trong Trường ĐH CNTT&TT, trang bị cho chúng em đầy đủ về cơ sở vật chất cũng như tri thức để em hoàn thành khóa học.
Cuối cùng em xin cảm ơn các bạn học viên trong lớp Cao học, những người luôn bên cạnh và cung cấp những thông tin quý báu trong suốt quá trình học tập, nghiên cứu để hoàn thành luận văn này.
Thái Nguyên, ngày 26 tháng 8 năm 2020
Học viên
3
Nguyễn Thị Linh
MỤC LỤC
LỜI CAM ĐOAN ..................................................................................................... 2
LỜI CẢM ƠN ........................................................................................................... 3
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ......................................... 8
DANH MỤC CÁC BẢNG ........................................................................................ 9
DANH MỤC CÁC HÌNH ...................................................................................... 10
LỜI NÓI ĐẦU ......................................................................................................... 11
CHƯƠNG 1 CÁC KIẾN THỨC CƠ SỞ .............................................................. 16
1.1. Giới thiệu chung ................................................................................... 16
1.2. Định nghĩa về quan hệ, bộ, thuộc tính.................................................. 16
1.3. Bao đóng của tập thuộc tính .................................................................. 17
1.4. Các kí hiệu và một số quy ước .............................................................. 18
1.5.1. Định nghĩa lược đồ quan hệ .......................................................... 19
1.5.2. Khóa của lược đồ quan hệ ............................................................. 19
1.5. Lược đồ quan hệ và khóa của lược đồ quan hệ ................................... 19
1.6.1. Phép chọn (phép lọc, Selection) .................................................... 21
1.6.2. Phép chiếu (Projection) ................................................................. 21
1.6.3. Phép kết nối tự nhiên (Natural Join) ............................................. 21
1.6.4. Phép cộng (hợp, Union) ................................................................ 22
1.6.5. Phép trừ (hiệu, Substraction/Minus) ............................................. 22
1.6.6. Phép giao (Intersection) ................................................................ 22
1.6.7. Phép chia (Division) ...................................................................... 22
1.6.8. Thứ tự thực hiện các phép toán quan hệ ....................................... 22
1.6.9. Một số hàm tiện ích ....................................................................... 23
4
1.6. Các phép toán quan hệ .......................................................................... 21
1.6.10. Một số ví dụ ................................................................................ 23
1.7.1. Các tính chất của phụ thuộc hàm .................................................. 27
1.7.2. Suy dẫn theo tiên đề (suy dẫn logic) ............................................. 27
1.7.3. Phủ................................................................................................. 28
1.7. Phụ thuộc hàm ........................................................................................ 25
1.8. Chuẩn hóa ............................................................................................... 30
CHƯƠNG 2 CÁC THUẬT TOÁN QUẢN LÝ LƯỢC ĐỒ QUAN HỆ ............ 32
2.1.1. Thuật toán tìm hợp của hai tập hợp .............................................. 32
2.1.2. Thuật toán tìm giao của hai tập hợp .............................................. 33
2.1.3. Thuật toán tìm hiệu của hai tập hợp .............................................. 34
2.1. Thuật toán tập hợp ................................................................................. 32
2.3. Thuật toán tìm phủ không dư ............................................................... 36
2.4. Thuật toán tìm phủ tối tiểu ................................................................... 36
2.5. Thuật toán kiểm tra tính tổn thất của phép tách bằng kỹ thuật
bảng ................................................................................................................. 37
CHƯƠNG 3 CHƯƠNG TRÌNH THỬ NGHIỆM ............................................... 41
3.1.1. Cấu tử Set ...................................................................................... 42
3.1.2. Hàm Reset ..................................................................................... 42
3.1.3. Hàm Card ...................................................................................... 43
3.1.4. Hàm Empty ................................................................................... 43
3.1.5. Hàm IsIn ........................................................................................ 43
3.1.6. Toán tử gán tập hợp ...................................................................... 43
3.1.7. Toán tử lấy hợp của hai tập hợp .................................................... 43
3.1.8. Toán tử lấy giao của hai tập hợp ................................................... 44
5
3.1. Lớp tập hợp Set ...................................................................................... 41
3.1.9. Toán tử lấy hiệu của hai tập hợp ................................................... 44
3.1.10. Toán tử in ra tập hợp ................................................................... 44
3.1.11. Toán tử so sánh ........................................................................... 44
3.2.1. Cấu tử khởi tạo phụ thuộc hàm ..................................................... 46
3.2.2. Hàm đặt vào phụ thuộc hàm ......................................................... 46
3.2.3. Hàm lấy vế trái của phụ thuộc hàm .............................................. 46
3.2.4. Hàm lấy vế phải của phụ thuộc hàm ............................................. 46
3.2.5. Hàm thêm vào vế trái của phụ thuộc hàm ..................................... 47
3.2.6. Hàm thêm vào vế phải của phụ thuộc hàm ................................... 47
3.2.7. Toán tử gán phụ thuộc hàm ........................................................... 47
3.2.8. Toán tử in ra phụ thuộc hàm ......................................................... 47
3.2. Lớp phụ thuộc hàm FD .......................................................................... 45
3.3.1. Cấu tử khởi tạo lược đồ quan hệ ................................................... 48
3.3.2. Hủy tử của lược đồ quan hệ .......................................................... 49
3.3.3. Hàm gán giá trị rỗng cho lược đồ quan hệ .................................... 49
3.3.4. Hàm gán giá trị cho lược đồ quan hệ ............................................ 49
3.3.5. Hàm trả về khóa của lược đồ quan hệ ........................................... 50
3.3.6. Hàm mở rộng để đưa thêm phụ thuộc hàm ................................... 50
3.3.7. Toán tử gán lược đồ quan hệ ......................................................... 50
3.3.8. Hàm chèn thêm một lược đồ quan hệ ........................................... 50
3.3.9. Hàm chuẩn hóa tự nhiên ............................................................... 51
3.3.10. Hàm tìm bao đóng ....................................................................... 51
3.3.11. Hàm tìm khóa .............................................................................. 52
3.3.12. Hàm kiểm tra siêu khóa .............................................................. 52
6
3.3. Lớp lược đồ quan hệ RSC .................................................................... 47
3.3.13. Hàm kiểm tra khóa ...................................................................... 53
3.3.14. Hàm kiểm tra chuẩn BCNF ......................................................... 53
3.3.15. Hàm kiểm tra dẫn xuất ................................................................ 53
3.3.16. Hàm tìm phủ không dư ............................................................... 54
3.3.17. Toán tử in ra lược đồ quan hệ ..................................................... 54
3.4. Minh họa chương trình .......................................................................... 54
KẾT LUẬN ............................................................................................................. 63
TÀI LIỆU THAM KHẢO ...................................................................................... 63
7
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Kí hiệu, chữ viết tắt Ý nghĩa
CSDL Cơ sở dữ liệu
ĐTB Điểm trung bình
GV Giáo viên
HB Học bổng
HS Học sinh
LĐQH Lược đồ quan hệ
LĐQH Lược đồ quan hệ
8
|X| Lực lượng của tập X
DANH MỤC CÁC BẢNG
Bảng 3.1. Một số hàm và toán tử lớp tập hợp ................................................. 42
Bảng 3.2. Một số hàm và toán tử lớp phụ thuộc hàm ..................................... 46
9
Bảng 3.3. Một số hàm và toán tử lớp lược đồ quan hệ ................................... 48
DANH MỤC CÁC HÌNH
Hình 3.1. Thử nghiệp với lớp Set ............................................................................ 56 Hình 3.2. Thử nghiệm với lớp FD ........................................................................... 57 Hình 3.3. Thử nghiệm với lớp RSC ......................................................................... 58 Hình 3.4. Thử nghiệm lớp RSC với cơ sở dữ liệu học sinh .................................... 60 Hình 3.5. Thử nghiệm lớp RSC với cơ sở dữ liệu thời khóa biểu ........................... 61 Hình 3.6. Thử nghiệm lớp RSC với cơ sở dữ liệu thiết bị ....................................... 62
10
LỜI NÓI ĐẦU
1. Đặt vấn đề
Năm 1970 Codd đề xuất khái niệm phụ thuôc hàm như một cơ chế quản
lý ngữ nghĩa dữ liệu trong cơ sở dữ liệu quan hệ [8], [9], [10].
Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là công thức dạng
f: X Y; X, Y U
trong đó ta gọi X là vế trái và Y là vế phải của PTH f.
Cho quan hệ R(U) và một PTH f: X Y trên U. Ta nói quan hệ R thoả
PTH f, hoặc PTH f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R giống nhau trên X thì chúng cũng giống nhau trên Y,
R(XY) (u, vR): (u.X = v.X) (u.Y = v.Y)
Nếu f: X Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ
thuộc hàm vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc
tính Y.
Nếu Y không phụ thuộc hàm vào X thì ta viết X ! Y hoặc (XY).
Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH
F, và viết R(F), nếu R thoả mọi PTH trong F: R(F) ( f F): R(f)
Cho trước tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các quan hệ
trên U thoả tập PTH F.
Cho tập các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng
trong mọi quan hệ của .
Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F + là tập
nhỏ nhất các PTH trên U chứa F và thoả các tính chất F1 - F3 của hệ tiên đề
Armstrong Ao sau đây [1], [2], [3]:
11
X, Y, Z U: F1. Tính phản xạ: Nếu X Y thì X Y F + F2. Tính gia tăng: Nếu XY F + thì XZYZ F + F3. Tính bắc cầu: Nếu X Y F + và Y Z F + thì X Z F +
Sau đó hàng loạt công trình nghiên cứu đề xuất các loại phụ thuộc dữ liệu
khác được xuất hiện trong lý thuyết cơ sở dữ liệu [4],[5],[10].
Các phụ thuộc dữ liệu đảm bảo cho dữ liệu trong các cơ sở dữ liệu phản
ánh sát với thế giới thực, phi mâu thuẫn có tính nhất quán và trợ giúp tối ưu hóa
trong tìm kiếm dữ liệu [6], [7].
Trong số các biến thể của phụ thuộc hàm thì các phụ thuộc nới lỏng
(Relaxed Functional Dependencies) được nghiên cứu và ứng dụng với tần xuất
cao vì các lý do sau đây. Thứ nhất, các điều kiện bổ sung cho phụ thuộc hàm
để tạo ra các phụ thuộc nới lỏng thường khá gần với các yêu cầu trong đời
thường. Thứ hai, các phụ thuộc nới lỏng có thể được dùng làm cơ sở để đặc tả
các loại phụ thuộc khác [6], [7].
Cho tập thuộc tính U. Một phụ thuộc hàm nới lỏng trên U là công thức
dạng
f: (γ)X (δ)Y; X, Y U
trong đó ta gọi X là vế trái và Y là vế phải của phụ thuộc hàm nới lỏng f.
Cho quan hệ R(U) và một phụ thuộc hàm nới lỏng f: (γ)X (δ)Y trên U.
Ta nói quan hệ R thoả phụ thuộc hàm nới lỏng f, hoặc phụ thuộc hàm nới lỏng
f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R thỏa điều kiện γ
và giống nhau trên X thì chúng cũng giống nhau trên miền Y thỏa điều kiện δ,
R(XY) (γ)X, (δ)Y, (u,vR): (u.X = v.X) (u.Y = v.Y)
Nếu f: (γ)X (δ)Y là một phụ thuộc hàm nới lỏng trên U thì ta nói tập
thuộc tính Y phụ thuộc (hàm) nới lỏng vào tập thuộc tính X, hoặc tập thuộc tính
X xác định hàm nới lỏng tập thuộc tính Y.
Dưới đây xin trích dẫn một số thí dụ về các phụ thuộc hàm nới lỏng.
Trong bảng tuần hoàn các nguyên tố hóa học Mendelev, hai chất có cùng
số electron tại lớp ngoài cùng thì có cùng ái lực, tức là chúng có cùng xu thế
12
nhận thêm cho đủ số electron từ nguyên tố khác.
Phụ thuộc hàm nới lỏng f: (E = s)E (true)A
Ý nghĩa của phụ thuộc hàm nới lỏng trong trường hợp này là: Chỉ xét trên các bộ thỏa điều kiện số điện tử tại lớp ngoài cùng bằng s, E
= s, thì hai nguyên tố có cùng lượng E sẽ có cùng ái lực.
Một dạng khác của phụ thuộc hàm nới lỏng là phân loại học sinh. Hai học
sinh có thể có điểm khác nhau nhưng vẫn được xếp vào cùng loại.
g: (a ĐTB b)ĐTB (true)Loại
Phụ thuộc hàm nới lỏng g cho biết hai học sinh có điểm trung bình (ĐTB)
13
trong cùng một đoạn [a; b] thì có cùng loại đánh giá.
Trong công trình của nhóm nghiên cứu Loredana Caruccio, Vincenzo
Deufemia, và Giuseppe Polese [7] đã phân loại hầu hết các phụ thuộc hàm nới
lỏng từ năm 1970 đến 2016.
Trong khuôn khổ khóa luận thạc sĩ này, học viên chọn đề tài: “Các thuật
toán xử lý phụ thuộc hàm nới lỏng”.
2. Đối tượng và phạm vi nghiên cứu
Luận văn tập trung khảo sát các đối tượng liên quan đến các lược đồ cơ
sở dữ liệu quan hệ sau đây:
- Lý thuyết phụ thuộc hàm và phụ thuộc hàm nới lỏng. - Các thuật toán cơ bản xử lý các đối tượng trong phụ thuộc hàm nới
lỏng.
3. Hướng nghiên cứu của đề tài
- Nghiên cứu lý thuyết liên quan đến đề tài: Cơ sở dữ liệu quan hệ, phụ thuộc hàm, phụ thuộc hàm nới lỏng, các thuật toán tính bao đóng, khóa.
- Cài đặt các lớp đối tượng quản lý tập hợp, thuộc tính, phụ thuộc hàm,
phụ thuộc hàm nới lỏng, khóa.
- Thử nghiệm các lược đồ quan hệ trang bị phụ thuộc hàm nới lỏng.
4. Cấu trúc của luận văn và những nội dung nghiên cứu chính
Cấu trúc của luận văn gồm:
- Phần mở đầu. - Chương 1, 2 và 3. - Phần kết luận và đề nghị. - Tài liệu tham khảo.
Nội dung chính của luận văn:
14
- Chương 1 giới thiệu các kiến thức cơ bản về CSDL, các định nghĩa về quan hệ, thuộc tính, bộ. Phụ thuộc hàm cũng như thuật toán tính bao đóng của các tập thuộc tính, tìm khóa của LĐQH, các chuẩn 1NF, 2NF, 3NF, BCNF, chuẩn hóa 3NF và bảo toàn thuốc tính PTH, PTH nới lỏng.
- Chương 2 trình bày một số thuật toán về: quản lý tập hợp, quản lý tập thuộc tính, quản lý tập phụ thuộc hàm nới lỏng, tính bao đóng, khóa.
- Chương 3 là cài đặt chương trình mô phỏng “Thuật toán xử lý phụ
thuộc hàm nới lỏng” và ứng dụng.
5. Phương pháp nghiên cứu
Trong luận văn học viên sử dụng các phương pháp nghiên cứu chính sau: - Nghiên cứu lý thuyết: Tổng hợp tài liệu, hệ thống lại các kiến thức,
tìm hiểu các khái niệm, thuật toán sử dụng trong đề tài.
- Lập trình thử nghiệm. - Lấy ý kiến chuyên gia.
6. Ý nghĩa khoa học của đề tài
Việc nghiên cứu đề tài có thể đóng góp thêm một vài chức năng quản lý
ngữ nghĩa dữ liệu thông qua các phụ thuộc hàm nới lỏng. Loại phụ thuộc hàm
này cho phép xử lý dữ liệu mịn hơn và linh hoạt hơn.
Luận văn thiết kế và cài đặt một hệ thống với các chức năng nhập xuất,
lưu trữ, tính bao đóng và khóa của các lược đồ quan hệ có trang bị các phụ
thuộc hàm nới lỏng. Hệ thống có thể được sử dụng để khảo sát và kiểm định
15
một số tính chất của các lược đồ quan hệ với phụ thuộc hàm nới lỏng.
CHƯƠNG 1 CÁC KIẾN THỨC CƠ SỞ
Chương này trình bày một số khái niệm cơ bản về tập hợp, về phụ thuộc
hàm và về lược đồ quan hệ. Nội dung chương sẽ là cơ sở để nghiên cứu những
vấn đề trong các chương sau.
1.1. Giới thiệu chung
Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được tập trung nghiên
cứu và phát triển của công nghệ thông tin. Trong quản lý các cơ sở dữ liệu
(CSDL), phụ thuộc dữ liệu được hiểu là những mệnh đề mô tả các ràng buộc
mà dữ liệu phải đáp ứng trong thực tế. Nhờ có những mô tả phụ thuộc này mà
hệ quản trị cơ sở dữ liệu có thể quản lý tốt được chất lượng dữ liệu. Lý thuyết
về các phụ thuộc dữ liệu đóng vai trò quan trọng trong việc mô tả thế giới
thực, phản ánh ngữ nghĩa dữ liệu trong cơ sở dữ liệu. Phụ thuộc dữ liệu được
Codd, tác giả của mô hình dữ liệu quan hệ đặt nền móng từ những năm 70 với
khái niệm phụ thuộc hàm. Một cách giải thích rất trực quan cho bài toán quản
lý được tổ chức theo hàng và cột, trong đó cột được biểu thị thuộc tính thông
tin cần quản lý của một đối tượng, thuộc tính này được gọi là tiêu đề của cột
và các giá trị trong cột đó có cùng một kiểu. Tập hợp tất cả các giá trị thuộc
tính trên một hàng (gọi là bộ) là dữ liệu về đối tượng đang quản lý.
Cho tập hữu hạn U = {A1, A2,...,An} khác rỗng (n> = 1). Các phần tử của U
được gọi là thuộc tính. Ứng với mỗi thuộc tính AiU (i = 1,2,....,n) có một tập
chứa ít nhất 2 phần tử dom(Ai) được gọi là miền giá trị của Ai. Gọi D là tập hợp
1.2. Định nghĩa về quan hệ, bộ, thuộc tính
16
các dom(Ai) (i = 1,2,....,n). Một quan hệ R với các thuộc tính U, kí hiệu R(U) là
một ánh xạ t: U D sao cho với mỗi Ai U ta có t(Ai) dom(Ai). Mỗi ánh xạ
được gọi là một bộ của quan hệ R.
Mỗi quan hệ R có hình ảnh là một bảng, mỗi cột ứng với một thuộc tính,
mỗi dòng là một bộ.
Ta kí hiệu t(U) là một bộ trên tập thuộc tính.
Một quan hệ rỗng là một quan hệ không chứa bộ nào. Vì mỗi quan hệ là
một tập các bộ, nên trong quan hệ không có 2 bộ trùng lặp.
1.3. Bao đóng của tập thuộc tính
Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong
U. Bao đóng của tập thuộc tính X, ký hiệu X+ là tập thuộc tính
X+ = {A U | X A F+}
Suy dẫn theo quan hệ
Cho tập PTH F trên tập thuộc tính U và f là một PTH trên U. Ta nói PTH
f được suy dẫn theo quan hệ từ tập PTH F và viết F ├ f, nếu mọi quan hệ R(U)
thoả F thì R cũng thoả f: F ├ f SAT(F) SAT(f).
Cho tập thuộc tính U và tập PTH F trên U, ta định nghĩa F* là tập toàn bộ
các PTH f được suy dẫn theo quan hệ từ tập PTH F
F* = {f: X Y | X, Y U, F ├ f}
Ta viết F !├ f hoặc F ├ f để biểu thị tập PTH F không dẫn theo quan
hệ ra được PTH f .
Định lý (Tính đủ và chặt của hệ tiên đề Armstrong)
F+ = F*
Nói cách khác, suy dẫn theo quan hệ và suy dẫn theo tiên đề là một, tức là F ╞
17
f F ├ f.
Quy ước giản lược: Ta thường viết X Y thay vì viết X Y F+ hoặc F ╞ X
Y.
1.4. Các kí hiệu và một số quy ước
Theo truyền thống của lý thuyết cơ sở dữ liệu chúng ta chấp nhận các
quy định sau đây:
Các thuộc tính được kí hiệu bằng các chữ LATINH HOA đầu bảng chữ A,
B, C, D...
Tập thuộc tính được kí hiệu bằng các chữ LATINH HOA cuối bảng chữ
X, Y, Z,...
Các phần tử trong một tập thường được liệt kê như một xâu kí tự, không
có các ký hiệu biểu diễn tập, chẳng hạn ta viết X = ABC thay vì viết X = {A, B,
C}. XY biểu diễn hợp của hai tập X và Y, X Y. Phép trừ hai tập X và Y được
kí hiệu là X\Y, hoặc X-Y.
Một phân hoạch của tập M (thành các tập con rời nhau và có hợp là M),
X1, X2,..., Xm được kí hiệu là M = X1| X2,|...|Xm với ý nghĩa M = X1 X2 ...
Xm và Xi Xj = Ø , 1 ≤ i, j ≤ m, i j.
Các bộ được biểu diễn bằng các chữ Latin thường có thể kèm chỉ số, thí
dụ t, u, v, i1...
Với mỗi bộ t trong quan hệ R(U) và mỗi tập con các thuộc tính X U ta
kí hiệu t[X] hoặc t.X là hạn chế của bộ (ánh xạ) t trên tập thuộc tính X. Ta chấp
nhận quy ước tự nhiên là miền giá trị của mọi thuộc tính chứa ít nhất hai phần
tử.
Trong trường hợp một miền trị của thuộc tính chỉ chứa một giá trị duy
nhất thì ta có thể loại bỏ cột tương ứng của thuộc tính đó trong quan hệ.
Ta chấp nhận quy ước sau đây: Mọi cặp bộ t và v trong mọi quan hệ giống
18
nhau trên miền rỗng các thuộc tính
t.Ø = v.Ø
Hàm Artr(R) cho tập thuộc tính của quan hệ R
Hàm Card(R) cho lực lượng (số bội) của quan hệ R
Trong trường hợp tập thuộc tính U đã cho trước ta có thể viết đơn giản R
thay cho R(U).
Hai quan hệ R và S được gọi là tương thích nếu chúng có cùng một tập
thuộc tính, tức là nếu Artr(U) = Artr(S).
Với mỗi bộ u trong quan hệ R(U) và mỗi bộ v trong quan hệ S(V) ta ký
hiệu uv là phép dán bộ. uv cho ta bộ t trên tập thuộc tính UV thoả điều kiện
t.U = u và t.V = v.
Với mỗi bộ u trong quan hệ R(U) và với mỗi quan hệ S(V) ta ký hiệu uS
là phép dán bộ u với quan hệ S. uS cho ta quan hệ
P(UV) = {uv | v S}
Để thể hiện các phép toán quan hệ ta sẽ dùng các ký pháp tựa như ký pháp
của hệ ISBL (Information System Base Language).
1.5. Lược đồ quan hệ và khóa của lược đồ quan hệ
1.5.1. Định nghĩa lược đồ quan hệ
Lược đồ quan hệ (LĐQH) là một cặp p = (U, F), trong đó U là tập hữu
hạn các thuộc tính, F là tập các phụ thuộc hàm trên U.
Quy ước: Trong trường hợp không chỉ rõ tập PTH F, ta xem LĐQH chỉ là
một tập hữu hạn các thuộc tính U.
1.5.2. Khóa của lược đồ quan hệ
Cho LĐQH p = (U,F). Tập thuộc tính K U được gọi là khoá của LĐQH
p nếu
19
(i) K+ = U
(ii) A K: (K {A})+ U
Hai điều kiện trên tương đương với
(i') K U
(ii') A K: (K {A}) ! U
Nếu K thoả điều kiện (i) thì K được gọi là một siêu khoá.
Thuộc tính A U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở) nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Cho LĐQH (U,F), ta kí hiệu UK là tập các thuộc tính khóa và UO là tập các thuộc tính không khóa.
Ví dụ: Cho U = {A,B,C,D,E} và F = {ABC, ACB, BCDE}, hãy
tìm một khóa của lược đồ quan hệ r xác định trên U và F.
Bước 1: K = U tức là K = ABCDE
Bước 2: Tính bao đóng của (K\A)+ nghĩa là tính (BCDE)+ = BCDE ta thấy
kết quả tính bao đóng không bằng U+ nên K = ABCDE
Bước 3: Tính bao đóng của (K\B)+ nghĩa là tính (ACDE)+ = ABCDE ta
thấy kết quả tính bao đóng bằng U+ nên loại B ra tập K ban đầu K = ACDE.
Bước 4: Tính bao đóng của (K\C)+ nghĩa là tính (ADE)+ = ADE ta thấy kết quả tính bao đóng không bằng U+ nên không bỏ C ra tập K ta có K = ACDE.
Bước 5: Tính bao đóng của (K\D)+ nghĩa là tính (ACE)+ = ACEBD ta thấy
kết quả tính bao đóng bằng U+ nên bỏ D ra tập K ta có K = ACE.
Bước 6: Tính bao đóng của (K\E)+ nghĩa là tính (AC)+ = ACBDE ta thấy
kết quả tính bao đóng bằng U+ nên bỏ E ra tập K ta có K = AC.
20
Kết quả: Khóa là K = AC.
1.6. Các phép toán quan hệ
1.6.1. Phép chọn (phép lọc, Selection)
Cho quan hệ R(U) và biểu thức điều kiện (còn gọi là biểu thức lọc hay
biểu thức chọn) e. Phép chọn trên quan hệ R theo điều kiện e, ký hiệu R(e) cho
ta quan hệ:
P(U) = R(e) = {t R | Sat(t, e)}
trong đó hàm logic Sat(t, e) kiểm tra bộ t thoả điều kiện e được xác định như
sau:
1. Thay mọi xuất hiện của mỗi thuộc tính A trong biểu thức chọn e bằng
trị tương ứng của A trong bộ t, t.A, ta thu được một mệnh đề logic b.
2. Tính trị của b. Nếu là đúng (True) thì bộ t thoả điều kiện e; ngược lại,
nếu trị của b là sai (False) thì bộ t không thoả điều kiện e.
Trong các biểu thức chọn ta sử dụng ký hiệu cho các phép toán logic như
sau:
Tích: & hoặc hoặc AND
Tổng: | hoặc hoặc OR
Phủ định: ! hoặc hoặc NOT
Kéo theo: hoặc IMPLY
1.6.2. Phép chiếu (Projection)
Phép chiếu quan hệ R(U) trên tập con thuộc tính X U, ký hiệu R[X], cho
ta quan hệ P(X) = R[X] = {t.X | t R} R[X] được tính theo 2 bước như sau:
1. Xoá các cột không thuộc X của bảng R,
1. Xoá bớt các dòng giống nhau trong bảng kết quả: chỉ giữ lại một dòng
trong số các dòng giống nhau.
1.6.3. Phép kết nối tự nhiên (Natural Join)
Phép kết nối (tự nhiên) hai quan hệ R(U) và S(V), ký hiệu RS, cho ta quan
hệ chứa các bộ được dán từ các bộ u của quan hệ R với mỗi bộ v của quan hệ S
21
sao cho các trị trên miền thuộc tính chung (nếu có) của hai bộ này giống nhau:
P(UV) = R S = {u v | u R, v S, u.M = v.M, M = U V}
Nếu M = U V = , RS sẽ cho ta tích Descartes trong đó mỗi bộ của
quan hệ R sẽ được ghép với mọi bộ của quan hệ S.
1.6.4. Phép cộng (hợp, Union)
Phép cộng (hợp theo lý thuyết tập hợp hoặc kết nối dọc) hai quan hệ tương
thích R(U) và S(U), ký hiệu R+S, cho ta quan hệ chứa các bộ của mỗi quan hệ
thành phần: P(U) = R+S = {t | t R t S}.
1.6.5. Phép trừ (hiệu, Substraction/Minus)
Phép trừ (theo lý thuyết tập hợp hoặc lấy phần riêng) hai quan hệ tương
thích R(U) và S(U), ký hiệu RS, cho ta quan hệ chứa các bộ của quan hệ R
không có trong quan hệ S: P(U) = RS = {t | t R, t S}.
1.6.6. Phép giao (Intersection)
Phép giao (theo lý thuyết tập hợp hoặc lấy phần chung) hai quan hệ tương
thích R(U) và S(U), ký hiệu R&S, cho ta quan hệ chứa các bộ xuất hiện đồng
thời trong cả hai quan hệ thành phần: P(U) = R&S = {t | t R, t S}.
Các phép toán cộng, trừ và giao được gọi là các phép toán tập hợp trên các
quan hệ (tương thích).
1.6.7. Phép chia (Division)
Phép chia quan hệ R(U) cho quan hệ S(V), ký hiệu R : S, cho ta quan hệ
P(M) = R : S = {t.M | tR, (t.M)S R, M = U V}.
1.6.8. Thứ tự thực hiện các phép toán quan hệ
Trong một biểu thức quan hệ các phép toán một ngôi có đô ưu tiên cao
hơn (do đó được thực hiện sớm hơn) các phép toán hai ngôi. Tiếp đến là nhóm
các phép toán kết nối, giao và chia, cuối cùng là nhóm các phép toán cộng và
trừ. Thứ tự ưu tiên từ cao đến thấp của các phép toán quan hệ được liệt kê như
22
sau:
() , [ ]
, & , :
+ ,
Dãy các phép toán cùng thứ tự ưu tiên được thực hiện lần lượt từ trái qua
phải. Nếu biểu thức quan hệ có chứa các cặp ngoặc () thì các biểu thức con
trong các cặp ngoặc được thực hiện trước.
1.6.9. Một số hàm tiện ích
1. Sum(R,A): Cho tổng các giá trị số trong thuộc tính (cột) A của quan hệ
R, Sum(R,A) = {t.A | t R}
2. Avg(R,A): Cho trung bình cộng các giá trị trong thuộc tính số A của
quan hệ R, Avg(R,A) = Sum(R,A) / Card(R) nếu Card(R) 0
3. Max(R ,A): Cho giá trị lớn nhất trong thuộc tính A của quan hệ R. 4. Min(R,A): Cho giá trị nhỏ nhất trong thuộc tính A của quan hệ R.
1.6.10. Một số ví dụ
a. Ví dụ về biểu thức quan hệ
Ta có biểu thức quan hệ P = SR(A > Avg(S,A))[A, B] sẽ được thực hiện
theo trật tự sau đây:
1. Tính hàm c = Avg(S,A) cho c là giá trị trung bình của cột A trong
quan hệ S.
2. Thực hiện phép chọn P1 = R(A > c) 3. Thực hiện phép chiếu P2 = P1 [A, B]
4. Thực hiện phép kết nối P = SP2
b. Ví dụ về cơ sở dữ liệu sinh viên thực tập
SV(SV#, HT, NS, QUE, HL)
DT(DT#, TDT, CN, KP) SD(SV#, DT#, NTT, KM, KQ)
Quan hệ SV(SV#, HT, NS, QUE, HL) chứa thông tin về các sinh viên
23
trong một lớp của một trường đại học, SV - tên quan hệ sinh viên
Các thuộc tính:
SV# - Mã sinh viên
HT - Họ và tên sinh viên
NS - Năm sinh của sinh viên
QUE - Quê (tỉnh)
HL - Học lực thể hiện qua điểm trung bình
Quan hệ DT(DT#, TDT, CN, KP) chứa thông tin về các đề tài nhà
trường quản lý,
DT - Tên quan hệ đề tài Các thuộc tính:
DT# - Mã số đề tài TDT - Tên đề tài CN – Họ và tên chủ nhiệm đề tài KP – Kinh phí cấp cho đề tài (triệu đồng)
Quan hệ SD(SV#, DT#, NTT, KM, KQ) chứa thông tin về tình hình
thực tập của các sinh viên theo các đề tài,
SD - Tên quan hệ sinh viên - đề tài Các thuộc tính:
SV# - Mã số sinh viên DT# - Mã số đề tài mà sinh viên đó tham gia NTT - Nơi thực tập để triển khai đề tài (tỉnh) KM – Khoảng cách từ nơi thực tập đến trường KQ – Kết quả thực tập theo đề tài đã chọn
Giả thiết là một sinh viên có thể tham gia nhiều đề tài, mỗi đề tài sinh
viên đó thực tập tại một điạ điểm.
Với mỗi câu hỏi, yêu cầu trả lời bằng một biểu thức của đại số quan hệ.
Tuổi được tính đến năm current_year (năm hiện hành). Ví dụ, ta có câu hỏi như sau:
Cho danh sách họ tên và mã các sinh viên trẻ (dưới 18 tuổi tính đến năm
24
current_year), học và thực tập đều đạt loại khá/giỏi (điểm không dưới 8.5)
Trả lời:
SD(KQ > = 8.5)[SV#]SV(current_yearNS < 18 & HL > = 8.5)[SV#,
HT].
1.7. Phụ thuộc hàm
Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là công thức dạng
f: X Y; X, Y U
trong đó ta gọi X là vế trái và Y là vế phải của PTH f.
Cho quan hệ R(U) và một PTH f: X Y trên U. Ta nói quan hệ R thoả
PTH f, hoặc PTH f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R
giống nhau trên X thì chúng cũng giống nhau trên Y,
R(XY) (u,vR): (u.X = v.X) (u.Y = v.Y)
Nếu f: X Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ
thuộc (hàm) vào tập X, hoặc tập thuộc tính X xác định hàm tập thuộc
tính Y.
Nếu Y không phụ thuộc hàm vào X thì ta viết X ! Y hoặc (XY).
Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH
F, và viết R(F), nếu R thoả mọi PTH trong F: R(F) ( f F): R(f)
Cho trước tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các quan hệ
trên U thoả tập PTH F.
Cho tập các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng
trong mọi quan hệ của .
Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F+ là tập
nhỏ nhất các PTH trên U chứa F và thoả các tính chất F1 - F3 của hệ tiên đề
Armstrong Ao sau đây:
X, Y, Z U:
F1. Tính phản xạ: Nếu X Y thì X Y F+
F2. Tính gia tăng: Nếu XY F+ thì XZYZ F+
25
F3. Tính bắc cầu: Nếu X Y F+ và Y Z F+ thì X Z F+
Chú ý: Các PTH có vế trái chứa vế phải như mô tả trong (F1) được gọi là
tầm thường. Các PTH tầm thường thoả trong mọi quan hệ.
Cho tập thuộc tính U. Một phụ thuộc hàm nới lỏng trên U là công thức
dạng
f: (γ)X (δ)Y; X, Y U
trong đó ta gọi X là vế trái và Y là vế phải của phụ thuộc hàm nới lỏng f.
Cho quan hệ R(U) và một phụ thuộc hàm nới lỏng f: (γ)X (δ)Y trên U.
Ta nói quan hệ R thoả phụ thuộc hàm nới lỏng f, hoặc phụ thuộc hàm nới lỏng
f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R thỏa điều kiện γ
và giống nhau trên X thì chúng cũng giống nhau trên miền Y thỏa điều kiện δ,
R(XY) (γ)X, (δ)Y, (u,vR): (u.X = v.X) (u.Y = v.Y)
Nếu f: (γ)X (δ)Y là một phụ thuộc hàm nới lỏng trên U thì ta nói tập
thuộc tính Y phụ thuộc (hàm) nới lỏng vào tập thuộc tính X, hoặc tập thuộc tính
X xác định hàm nới lỏng tập thuộc tính Y.
Một ví dụ về phụ thuộc hàm nới lỏng là phân loại học sinh. Hai học sinh
có thể có điểm khác nhau nhưng vẫn được xếp vào cùng loại.
f: (a ĐTB b)ĐTB (true)Loại
Phụ thuộc hàm nới lỏng f cho biết hai học sinh có điểm trung bình (ĐTB)
trong cùng một đoạn [a; b] thì có cùng loại đánh giá.
Một ví dụ khác là tính học bổng cho sinh viên. Hai sinh viên có thể có
ĐTB khác nhau nhưng vẫn cùng nhận được mức học bổng (HB) như nhau.
g: (a ĐTB b)ĐTB (true)HB
Phụ thuộc hàm nới lỏng g cho biết hai sinh viên có ĐTB trong cùng một
đoạn [a; b] thì có cùng mức học bổng.
Trong công trình của nhóm nghiên cứu Loredana Caruccio, Vincenzo
Deufemia, và Giuseppe Polese [7] đã phân loại hầu hết các phụ thuộc hàm nới
26
lỏng từ năm 1970 đến 2016. Trong công trình này, nhóm tác giả phân tích chi
tiết các tính chất và ứng dụng của PTH nới lỏng. Một phân chia chi tiết thành
19 loại PTH nới lỏng khác nhau cũng được liệt kê trong tài liệu này.
1.7.1. Các tính chất của phụ thuộc hàm
Cho tập thuộc tính U. Với mọi tập con các thuộc tính X, Y, Z và V trong U
và với mọi thuộc tính A trong U ta có:
F1. Tính phản xạ: Nếu Y X thì X Y
F2. Tính gia tăng: Nếu X Y thì XZ YZ
F3. Tính bắc cầu: Nếu X Y và Y Z thì X Z
F4. Tính tựa bắc cầu: Nếu XY, YZV thì XZV
F5. Tính phản xạ chặt: X X
F6. Mở rộng vế trái và thu hẹp vế phải: Nếu XY thì XZ Y \ V
F7. Cộng tính đầy đủ: Nếu XY và ZV thì XZYV
F8. Mở rộng vế trái: Nếu XY thì XZY
F9. Cộng tính ở vế phải: Nếu XY và XZ thì XYZ
F10. Bộ phận ở vế phải: Nếu XYZ thì XY
F11.Tính tích luỹ: Nếu XYZ, ZAV thì XYZA
1.7.2. Suy dẫn theo tiên đề (suy dẫn logic)
Ta nói PTH f được suy dẫn theo tiên đề (hoặc suy dẫn logic) từ tập PTH
F và ký hiệu là F ╞ f, nếu f F +: F ╞ f f F+.
Nói cách khác f được suy dẫn theo tiên đề từ tập PTH F nếu xuất phát từ
F, áp dụng các luật F1, F2 và F3 của hệ tiên đề Armstrong sau hữu hạn lần ta sẽ
thu được PTH f.
Ta viết F !╞ f hoặc F ╞ f để biểu thị tập PTH F không dẫn logic ra
27
được PTH f.
1.7.3. Phủ
Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn
ra được G, ký hiệu F ╞ G, nếu ( g G): (F ╞ g).
Ta nói F tương đương với G, ký hiệu F G, nếu F ╞ G và G ╞ F.
Nếu F G ta nói G là một phủ của F.
Ký hiệu
F !╞ G: F không suy dẫn ra được G.
F ! G: F và G không tương đương.
+ trong trường hợp cần chỉ rõ bao đóng của tập thuộc tính X lấy theo tập
Cho tập PTH F trên tập thuộc tính U và X là tập con của U, ta dùng ký
hiệu XF
PTH F.
Phủ thu gọn tự nhiên
Cho hai tập PTH F và G trên cùng một tập thuộc tính U. G là phủ thu gọn
tự nhiên của F nếu
1) G là một phủ của F, và
2) G có dạng thu gọn tự nhiên theo nghĩa sau:
a) Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau)
b) Các vế trái của mọi PTH trong G khác nhau đôi một.
Phủ không dư
Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ không
dư của F nếu
1) G là một phủ của F, và
2) G có dạng không dư theo nghĩa sau: ( g G): G - {g} ! G
Phủ thu gọn
a) Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn
trái của F nếu
28
1) G là một phủ của F, và
2) Không thể bỏ bất kỳ thuộc tính nào khỏi vế trái của bất kỳ PTH nào
trong G mà vẫn giữ được tính tương đương
(XYG, AX): G -{XY} {(X-{A})Y} ! G
b) G được gọi là phủ thu gọn phải của F nếu
1) G là một phủ của F, và
2) Không thể bỏ bất kỳ thuộc tính nào khỏi vế phải của bất kỳ PTH nào
trong G mà vẫn giữ được tính tương đương
(XYG, AY): G -{XY} {(XY-{A})} ! G
c) G được gọi là phủ thu gọn của F nếu G đồng thời là phủ thu gọn trái và thu
gọn phải của F.
Phủ tối tiểu
Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ tối tiểu
của F nếu
1) G là một phủ thu gọn của F,
2) Vế phải của mọi PTH trong G chỉ chứa một thuộc tính.
1.7.4. Bài toán thành viên
Cho tập thuộc tính U, một tập các PTH F trên U và một PTH X Y trên
U. Hỏi rằng X Y F+ hay không?
Định lý: X Y F+ khi và chỉ khi Y X+.
Ví dụ: Cho lược đồ quan hệ R = (U, F) với U = {A,B,C,D,E,G,H} và F =
{AB→C, D→EG, ACD→B, C→A, BE→C, CE→AG, BC→D, CG→BD, G→
H} tính (BE)+
Lời giải:
đặt X0 = BE
1) X1 = BEC (áp dụng BE→C)
2) X2 = BECAG (áp dụng CE→AG)
29
3) X3 = BECAGD (áp dụng BC→D)
4) X4 = BECAGDH (áp dụng G→H)
Vậy (BE)+ = ABCDEGH.
1.8. Chuẩn hóa
1.8.1. Phép tách
Cho lược đồ quan hệ p = (U,F). Một phép tách trên tập thuộc tính U là
𝑘 một họ các tập con của U, = (X1, X2,...,Xk) thỏa tính chất ⋃ 𝑖 = 1
= 𝑈 𝑋𝑖
Phép tách = (X1, X2,...,Xk) trên tập thuộc tính U được gọi là không tổn thất
(hoặc không mất thông tin) đối với tập PTH F nếu
R(U) SAT(F): R[X1 ] R[X2] ... R[Xk] = R
Ngược lại, nếu không tồn tại đẳng thức thì ta gọi là phép tách tổn thất.
1.8.2. Các dạng chuẩn
LĐQH p = (U,F) được gọi là LĐ
a) Dạng chuẩn 1 (1NF) Nếu mọi thuộc tính trong U đều không phải là thuộc
tính phức hợp. Chính xác ra là: LĐ p được gọi là LĐ dạng chuẩn 1 nếu chỉ sử
dụng các phép toán quan hệ thì không thể truy nhập đến một thành phần của
một thuộc tính có hơn một thành phần.
Thí dụ, câu hỏi "Hiển thị những địa điểm thực tập có chứa chữ Quảng trong tên
tỉnh" không thể trả lời được chỉ bằng các phép toán quan hệ mà phải sử dụng
thêm các thao tác lập trình như tìm kiếm và cắt xâu kí tự.
b) Dạng chuẩn 2 (2NF): nếu p là LĐ 1NF và mọi thuộc tính không khoá đều
phụ thuộc đầy đủ vào mọi khoá,
A UO , K Key(p) : K+ A
c) Dạng chuẩn 3 (3NF): nếu p là LĐ 1NF và mọi thuộc tính không khoá đều
phụ thuộc trực tiếp vào mọi khoá,
30
A UO , K Key(p) : K* A
d) Dạng chuẩn 3 (3NF): nếu p là LĐ 1NF và mọi PTH không tầm thường
XA, A là thuộc tính không khóa đều cho ta X là một siêu khoá,
(X A, A UO – X) X+ = U
e) Dạng chuẩn Boyce-Codd (BCNF): nếu p là LĐ 1NF và mọi thuộc tính
đều phụ thuộc trực tiếp vào mọi khoá,
A U , K Key(p) : K* A
f) Dạng chuẩn Boyce-Codd (BCNF): nếu p là LĐ 1NF và mọi PTH không tầm
thường XY đều cho ta X là một siêu khóa.
(X Y, Y – X ) X+ = U
Sơ đồ tương quan giữa các dạng chuẩn: BCNF 3NF 2NF
Ví dụ: Chuẩn hoá 3NF CSDL Thực tập:
SV(SV#, HT, NS, QUE, HL)
DT(DT#, TDT, CN, KP)
SD(SV#, DT#, NTT, KM, KQ)
với các tập PTH sau:
FSV = {{SV#} {HT, NS, QUE, HL}}
FDT = {{DT#} {TDT, CN, KP}}
FSD = {{SV#, DT#} {NTT, KQ} , {NTT} {KM}}
Lời giải:
Hai quan hệ SV và DT chỉ có 1 khoá đơn (1 thuộc tính) tương ứng là SV# và DT# và hai tập PTH tương ứng chỉ chứa 1 PTH nên hai quan hệ này ở BCNF(?).
31
Quan hệ SD có 1 khoá là K = SV#DT#. SD không ở 3NF vì có phụ thuộc bắc cầu của thuộc tính không khoá KM vào khoá K. Ta chuẩn hoá SD như sau:
1. Tách
SV#, DT# NTT
SV#, DT# KQ
NTT KM
2. Tìm phủ tối tiểu
G = {SV#, DT# NTT; SV#, DT# KQ; NTT KM}
3. Gộp: ta thu lại được F. Thành phần thứ nhất chứa khóa {SV#, DT#}.
4. Kết quả: = ({SV#, DT#, NTT, KQ}, {NTT, KM}). Ta thu được hai
quan hệ
SD(SV#,DT#,NTT,KQ) với khoá K = SV#,DT# và
NK(NTT,KM) với khoá NTT.
CHƯƠNG 2 CÁC THUẬT TOÁN QUẢN LÝ LƯỢC ĐỒ QUAN HỆ
Chương này trình bày một số thuật toán cơ bản quản lý lược đồ quan hệ
cũng như một số thuật toán cơ sở về tập hợp và phụ thuộc hàm để xây dựng
các lớp hỗ trợ cho lược đồ quan hệ.
2.1. Thuật toán tập hợp
2.1.1. Thuật toán tìm hợp của hai tập hợp
Algorithm Union
Function: Thực hiện phép Hợp hai tập hợp
32
Thuật toán:
Format: P = R+S Input: - Tập hợp R - Tập hợp S
Output: - Tập hợp R+S = {t | tR tS} Method
P := R; for each v in S
if (v not_in R) then
add v to P;
endif;
endfor; return P;
end Union.
Độ phức tạp tính toán: Phép kiểm tra v thuộc R đòi hỏi |R| lần duyệt và so sánh
trên các phần tử. Vậy độ phức tạp tính toán sẽ là O(|S||R|).
2.1.2. Thuật toán tìm giao của hai tập hợp
Algorithm Intersection
Function: Thực hiện phép Giao hai tập hợp Format: P = R*S Input: - Tập hợp R - Tập hợp S
Output: - Tập hợp R*S = {t | tR tS} Method
P = ; for each u in R
if (u in S) then add u to P;
endif;
endfor; return P;
end Intersection.
33
Thuật toán:
Độ phức tạp tính toán: Phép kiểm tra v thuộc S đòi hỏi |S| lần duyệt và so sánh
trên các phần tử. Vậy độ phức tạp tính toán sẽ là O(|S||R|).
2.1.3. Thuật toán tìm hiệu của hai tập hợp
Algorithm Subtraction
Function: Thực hiện lấy Hiệu hai tập hợp Format: P = R-S Input: - Tập hợp R - Tập hợp S
Output: - Tập hợp R-S = {t | tR tS} Method
P = ; for each u in R
if (u not_in S) then add u to P;
endif; endfor; return P;
end Subtraction.
Thuật toán:
Độ phức tạp tính toán: Phép kiểm tra v thuộc S đòi hỏi |S| lần duyệt và so sánh
trên các phần tử. Vậy độ phức tạp tính toán sẽ là O(|S||R|).
2.2. Thuật toán tìm bao đóng của một tập thuộc tính
Ý tưởng thuật toán: Cho tập PTH F trên tập thuộc tính U và một tập con các
thuộc tính X trong U. Để xác định bao đóng của tập thuộc tính X, X + ta xuất
phát từ tập X và bổ sung dần cho X các thuộc tính thuộc vế phải R của các PTH
L R F thỏa điều kiện L X. Thuật toán sẽ dừng khi không thể bổ sung
thêm thuộc tính nào cho X.
Algorithm Closure Function: Tính bao đóng của tập thuộc tính.
34
Thuật toán:
Format: Y = Closure(U,F,X) Input: - LĐQH p = (U,F) - Tập thuộc tính X U Output: - Y = X+ = {A U | XA F+} Method Y : = X; repeat Z : = Y; for each FD L R in F do if L Y then Y : = Y R; endif; endfor; until Y = Z; return Y; end Closure.
Độ phức tạp tính toán: Giả sử mỗi lần lặp trong repeat ta chỉ thêm được 1
thuộc tính. Khi đó repeat sẽ được lặp tối đa n lần. Mỗi lần lặp ta phải duyệt
toàn bộ m phụ thuộc hàm để thực hiện các thao tác trên các tập chứa tối đa n
thuộc tính. Vậy độ phức tạp tính toán sẽ là O(n2m).
Ví dụ:
Cho lược đồ quan hệ R = (U, F) với U = {A,B,C,D,E,G,H} và F = {AB→C,
D→EG, ACD→B, C→A, BE→C, CE→AG, BC→D, CG→BD, G→ H}
Tính (D)+, (BE)+
Giải:
a) Tính (D)+
X0 = D
1 - X1 = DEG (áp dụng D→EG)
2 - X2 = DEGH (áp dụng G→H) (= Constant)
Vậy (D)+ = DEGH
35
b) Tính (BE) +
X0 = BE
1 - X1 = BEC (áp dụng BE→C)
2 - X2 = BECAG (áp dụng CE→AG)
3 - X3 = BECAGD (áp dụng BC→D)
4 - X4 = BECAGDH (áp dụng G→H) (= Constant)
Vậy (BE)+ = ABCDEGH.
2.3. Thuật toán tìm phủ không dư
Algorithm Nonredundant
Format: Nonredundant(F) Input: - Tập PTH F Output: - Một phủ không dư G của F
(i) G F (ii) g G: G-{g} ! G
Method
U := Attr(F); // Tập thuộc tính của F G := F; for each FD g: L R in F do
if R Closure(U,G-{g},L) then
G := G – {g};
endif;
endfor; return G; end Nonredundant.
Thuật toán tìm phủ không dư của PTH F.
Chú thích: Hàm Closure(U,F,X) cho ra bao đóng của tập thuộc tính X
U trong LĐQH (U, F).
2.4. Thuật toán tìm phủ tối tiểu
Algorithm MinCover
36
Thuật toán tìm phủ tối tiểu G của tập PTH F.
Function: Tính phủ tối tiểu của tập PTH Format: MinCover(F) Input: - Tập PTH F Output: - Một phủ tối tiểu G của F Method // Tách mỗi PTH LR trong F thành các PTH LA, A R
G :=; for each FD L R in F do
for each attribute A in R do if LA not_in G then add LA to G;
endif;
endfor;
endfor; G := Reduced(G);
return G; end MinCover.
2.5. Thuật toán kiểm tra tính tổn thất của phép tách bằng kỹ thuật bảng
Algorithm Lossless_Join_Testing
Function: Kiểm tra tính tổn thất của phép tách bằng kỹ thuật bảng Input: - LĐQH p = (U,F) - Phép tách = (X1, X2,...,Xk) Output: - True, nếu là một phép tách không tổn thất.
- False, nếu ngược lại.
Method: 1. Khởi trị: Lập bảng T với các cột là các thuộc tính trong U và k dòng, mỗi dòng ứng với một thành phần của Xi trong : Dòng i chứa các ký hiệu phân biệt (KHPB) aj ứng với các thuộc tính Aj trong Xi và các ký hiệu không phân biệt (KHKPB) bij ứng với các thuộc tính Aj trong UXi . Chú ý rằng mọi KHPB trong cột j của T là giống nhau và bằng aj còn mọi KHKPB trong bảng T lúc đầu là khác nhau.
2. Sửa bảng: Lặp đến khi bảng T không còn thay đổi: Vận dụng các F-luật để biến đổi bảng như sau:
37
Thuật toán:
Với mỗi PTH L R trong F, nếu trong bảng T có chứa hai dòng u và v giống nhau trên L thì sửa các ký hiệu của chúng cho giống nhau trên mọi cột AR trong bảng T như sau:
a. nếu u.A = v.A: không sửa, b. nếu duy nhất một trong hai ký hiệu u.A hoặc v.A là KHPB a, kí hiệu còn lại là KHKPB b thì sửa mọi xuất hiện của kí hiệu b trong cột A của bảng thành KHPB a, c. nếu cả hai ký hiệu u.A và v.A đều là KHKPB bi và bj, i < j thì sửa mọi xuất hiện trong bảng của ký hiệu có chỉ số thứ nhất lớn hơn là bj thành ký hiệu có chỉ số nhỏ hơn là bi.
3. Kết luận: Gọi bảng kết quả là T*. Nếu T* chứa một dòng toàn KHPB thì return True; nếu không return False.
end Lossless_Join_Testing.
Ví dụ: Dùng kỹ thuật bảng để kiểm tra tính tổn thất của các phép tách sau:
a) p = (U,F), U = ABCD, F = {A B, AC D} = (AB, ACD).
b) p = (U,F), U = ABCDE,
F = {AC, BC, CD, DEC, CEA}
= (AD, AB, BE, CDE)
Giải:
a) p = (U, F), U = ABCD, F = {A B, AC D} = (AB, ACD).
T T*
A B C D
AB a1 a2 b13 b14
a1 ACD b22 / a2 a3 a4
Vì T* chứa dòng thứ hai gồm toàn ký hiệu phân biệt nên phép tách đã cho
38
là không tổn thất.
b) p = (U,F), U = ABCDE,
F = {A C, B C, C D, DE C, CE A}
= (AD, AB, BE, CDE).
T T*
A B C D E
AD a1 b12 b13/ a3 a4 b15
AB a1 a2 b23/b13 /a3 b24 / a4 b25
BE b31 a2 b33 /b13/a3 b34 / a4 a5
a5 CDE b41 / b31 b42 a3 a4
Vì T* không chứa một dòng toàn ký hiệu phân biệt nên phép tách đã cho
là tổn thất.
2.5. Thuật toán chuẩn hóa 3NF không tổn thất và bảo toàn phụ thuộc hàm
Algorithm 3NF
Function: Chuẩn hóa 3NF không tổn thất và bảo toàn PTH.
Input: LĐQH p = (U,F) Output: - Các LĐQH 3NF (U1,K1),(U2,K2),...,(Us,Ks) thoả RREL(U):
R[U1]R[U2]...R[Us] = R
- K1, K2,..., Ks - khoá của các lược đồ tương ứng F {F+[Ui] | i = 1,2,...,s}
Method 1. Tìm một phủ tối tiểu của F: G = {K1A1, K2A2,..., KmAm} 2. Ghép các PTH có cùng vế trái trong G để thu được phủ G = {K1X1, K2X2,..., KsXs}. 3. Xét phép tách = (K1X1,...,KsXs). Nếu chứa một siêu khóa nào đó của p
39
Thuật toán:
thì return {(K1X1,K1),...,(KsXs,Ks)} nếu không return {(K1X1,K1),...,(KsXs,Ks),(K,K)} với K là một khóa của p. construct = (K1X1,K2X2,...,KsXs); for each component V = KiXi in do if V+ = U then // V = KiXi là siêu khóa return {(K1X1,K1),...,(KsXs,Ks)}; endif; endfor; K = Key(U,F); return {(K1X1,K1),...,(KsXs,Ks),(K,K)}; End 3NF.
Ví dụ: Chuẩn hoá 3NF CSDL Thực tập:
SV(SV#, HT, NS, QUE, HL)
DT(DT#, TDT, CN, KP)
SD(SV#, DT#, NTT, KM, KQ)
với các tập PTH sau:
FSV = {{SV#} {HT, NS, QUE, HL}}
FDT = {{DT#} {TDT, CN, KP}}
FSD = {{SV#, DT#} {NTT, KQ} , {NTT} {KM}}
Giải:
Hai quan hệ SV và DT chỉ có 1 khoá đơn (1 thuộc tính) tương ứng là SV#
và DT# và hai tập PTH tương ứng chỉ chứa 1 PTH nên hai quan hệ này ở
BCNF(?).
Quan hệ SD có 1 khoá là K = SV#DT#. SD không ở 3NF vì có phụ thuộc
40
bắc cầu của thuộc tính không khoá KM vào khoá K. Ta chuẩn hoá SD như sau:
1. Tách
SV#, DT# NTT
SV#, DT# KQ
NTT KM
2. Tìm phủ tối tiểu
G = {SV#, DT# NTT; SV#, DT# KQ; NTT KM}
3. Gộp: ta thu lại được F. Thành phần thứ nhất chứa khóa {SV#, DT#}.
4. Kết quả: = ({SV#, DT#, NTT, KQ}, {NTT, KM}). Ta thu được hai
quan hệ SD(SV#,DT#,NTT,KQ) với khoá K = SV#,DT# và NK(NTT,KM) với
khoá NTT.
CHƯƠNG 3 CHƯƠNG TRÌNH THỬ NGHIỆM
Nội dung chính của chương này là minh họa cài đặt các thuật toán được
trình bày trong Chương 2. Nhóm các lớp được xây dựng có tính cấu trúc lần
lượt là lớp tập hợp Set, lớp phụ thuộc hàm FD và lớp lược đồ quan hệ RSC.
Theo thứ tự liệt kê này, thì lớp trước sẽ là cơ sở để xây dựng lớp sau.
3.1. Lớp tập hợp Set
Các hàm và toán tử của lớp Set.
STT Ký hiệu
Ý nghĩa
1.
Set
Cấu tử để khởi tạo tập hợp
2. Reset
Hàm gán giá trị rỗng cho tập hợp.
41
3. Card
Hàm trả về lực lượng của tập hợp
4. Empty
Hàm kiểm tra tập hợp có phải tập rỗng hay không
5.
IsIn
Hàm kiểm tra một phần tử có thuộc tập hợp hay không
6.
=
Toán tử gán tập hợp
7.
+
Toán tử lấy hợp của 2 tập hợp
8.
*
Toán tử lấy giao của 2 tập hợp
9.
-
Toán tử lấy hiệu của 2 tập hợp
10. <<
Toán tử in ra tập hợp
11. >, <, !=, ==, <=, >= Một số toán tử so sánh
1Bảng 3.1. Một số hàm và toán tử lớp tập hợp
Khai báo thuộc tính lớp Set
protected:
BS Data; // dữ liệu chứa 0..25 bit kiểu bitset
Ví dụ: x = ABC, y = BDF thì kế quả của phép toán hợp z = x + y = ABCDF,
giao z = x * y = B và hiệu z = x - y = AC.
3.1.1. Cấu tử Set
Set Constructor: Set(const string s)
if (IsAlpha(s[i]))
Data.reset(); for (int i = 0; i < s.length(); ++i) Data.set(Code(s[i]));
Trong đó, Data được khai báo là kiểu dữ liệu bitset có kích thước 26 bit:
Data[0..25] với ý nghĩa sử dụng là Data[i] = 1 là có phần tử thứ i và Data[i] =
0 là không có phần tử thứ i.
3.1.2. Hàm Reset
Reset method: void Reset()
Data.reset();
42
Trong đó, reset() là hàm của kiểu dữ liệu chuẩn bitset thực hiện chuyển
toàn bộ các bit thành bit 0.
3.1.3. Hàm Card
Empty method: int Card()
return Data.count();
Trong đó, count() là hàm của kiểu dữ liệu chuẩn bitset trả về số lượng bit 1.
3.1.4. Hàm Empty
Empty method: bool Empty()
return Data.none();
Trong đó, none() là hàm của kiểu dữ liệu chuẩn bitset để kiểm tra một bitset có toàn bit 0 hay không, trả về true nếu có và trả về false nếu ngược lại.
3.1.5. Hàm IsIn
IsIn method: bool IsIn(char e)
if (IsAlpha(e)) return Data[Code(e)]; return 0;
Hàm này sử dụng với 02 khai báo tiền xử lý
#define Code(c) (c)-'A'
#define IsAlpha(c) ((c) >= 'A' && (c) <= 'Z')
3.1.6. Toán tử gán tập hợp
singed operator: void operator =(const string s)
Data.reset();
for (int i = 0; i < s.length(); ++i)
if (IsAlpha(s[i]))
Data.set(Code(s[i]));
3.1.7. Toán tử lấy hợp của hai tập hợp
Union operator: Set operator +(const Set &y)
43
Set z(*this); z.Data |= y.Data; return z;
3.1.8. Toán tử lấy giao của hai tập hợp
Intersection operator: Set operator *(const Set &y)
Set z(*this); z.Data &= y.Data; return z;
z.Data[i] = 1;
3.1.9. Toán tử lấy hiệu của hai tập hợp
Minus operator: Set operator -(const Set &y) Set z; for (int i = 0; i < __SETSIZE; ++i) if (Data[i] && (!y.Data[i])) return z;
Trong đó, __SETSIZE là hằng kiểu int có giá trị là 26.
}
os << "{}"; return os;
os << ToAlpha(i);
3.1.10. Toán tử in ra tập hợp
Minus operator: ostream & operator <<(ostream & os, const Set & s) if (s.Empty()) { for (int i = 0; i < __SETSIZE; ++i) { if (s.Data[i]) } return os;
Phần này trình bày các toán tử so sánh bằng nhau (==), khác nhau (!=), nhỏ
hơn hoặc bằng (<=), lớn hơn hoặc bằng (>=), nhỏ hơn (<) và lớn hơn (>).
44
3.1.11. Toán tử so sánh
Equal operator: bool operator ==(const Set & y)
return Data == y.Data;
inEqual operator: bool operator !=(const Set & y)
return Data != y.Data;
lessThanOrEqual operator: bool operator <=(const Set & x,
const Set & y)
for (int i = 0; i < __SETSIZE; ++i)
if (x.Data[i] && (!y.Data[i]))
return false;
return true;
greaterThanOrEqual operator: bool operator >=(const Set & x,
const Set & y)
return y <= x;
lessThan operator: bool operator <(const Set & x, const Set
& y)
return((x <= y) && (x != y));
greaterThan operator: bool operator >(const Set & x, const
Set & y)
return y < x;
3.2. Lớp phụ thuộc hàm FD
Khai báo thuộc tính lớp FD
protected:
Set LS; // vế trái
Set RS; // vế phải
Các hàm và toán tử chính của lớp FD:
STT Ký hiệu Ý nghĩa
1.
FD
Cấu tử khởi tạo phụ thuộc hàm
45
2.
Put
Hàm đặt vào phụ thuộc hàm
3. GetLS Hàm lấy vế trái của phụ thuộc hàm
4. GetRS Hàm lấy vế phải của phụ thuộc hàm
5. AddLS Hàm thêm vào vế trái của phụ thuộc hàm
6. AddRS Hàm thêm vào vế phải của phụ thuộc hàm
7.
=
Toán tử gán phụ thuộc hàm
8.
<<
Toán tử in ra phụ thuộc hàm
2Bảng 3.2. Một số hàm và toán tử lớp phụ thuộc hàm
3.2.1. Cấu tử khởi tạo phụ thuộc hàm
FD constructor: FD(string ls, string rs) LS = ls; RS = rs; RS -= LS;// hai vế không giao nhau
3.2.2. Hàm đặt vào phụ thuộc hàm
Put method: void Put(const Set & ls, const Set & rs) LS = ls; RS = rs; RS -= LS;
3.2.3. Hàm lấy vế trái của phụ thuộc hàm
GetLS method: Set GetLS() return LS;
3.2.4. Hàm lấy vế phải của phụ thuộc hàm
GetRS method: Set GetRS() return RS;
46
3.2.5. Hàm thêm vào vế trái của phụ thuộc hàm
AddLS method: AddLS(const Set & ls) LS += ls;
3.2.6. Hàm thêm vào vế phải của phụ thuộc hàm
AddRS method: AddRS(const Set & rs) RS += rs;
3.2.7. Toán tử gán phụ thuộc hàm
Signed operator: operator =(const FD & g) LS = g.LS; RS = g.RS;
3.2.8. Toán tử in ra phụ thuộc hàm
Print operator: ostream & operator <<(ostream & os, const FD & f) os << f.GetLS() << " -> " << f.GetRS(); return os;
3.3. Lớp lược đồ quan hệ RSC
Khai báo lớp RSC:
protected:
Set Attr; // Tập thuộc tính Set
int FDNum; // Số lượng phụ thuộc hàm
FD * F; // Các phụ thuộc hàm
int Cap; // Capacity
Set Key; //Khóa
Các hàm và toán tử chính của lớp RSC:
STT Ký hiệu
Ý nghĩa
47
1. RSC
Cấu tử khởi tạo lược đồ quan hệ
2.
~RSC()
Hủy tử của lược đồ quan hệ
3. Reset
Hàm gán giá trị rỗng cho lược đồ quan hệ
4. Copy
Hàm gán giá trị cho lược đồ quan hệ
5. GetKey
Hàm trả về khóa của lược đồ quan hệ
6.
Extend
Hàm mở rộng để đưa thêm phụ thuộc hàm
7.
=
Toán tử gán lược đồ quan hệ
8.
Ins
Hàm chèn thêm một lược đồ quan hệ
9. Norm
Hàm chuẩn hóa tự nhiên
10. Closure
Hàm tìm bao đóng
11. FindKey
Hàm tìm khóa
12.
IsSuperkey
Hàm kiểm tra siêu khóa
13.
IsKey
Hàm kiểm tra khóa
14.
IsBCNF
Hàm kiểm tra chuẩn BCNF
15. Derive
Hàm kiểm tra dẫn xuất
16. NonRedundant Hàm tìm phủ không dư
17. <<
Toán tử in ra LĐQH
3Bảng 3.3. Một số hàm và toán tử lớp lược đồ quan hệ
3.3.1. Cấu tử khởi tạo lược đồ quan hệ
RSC constructor: RSC(const RSC &r) Reset(); Copy(r);
48
3.3.2. Hủy tử của lược đồ quan hệ
~RSC destructor: ~RSC()
if (F != NULL) {
delete [] F;
F = NULL;
}
3.3.3. Hàm gán giá trị rỗng cho lược đồ quan hệ
Reset method: Reset()
FDNum = 0;
Cap = 0;
F = NULL;
Attr.Reset();
Key.Reset();
3.3.4. Hàm gán giá trị cho lược đồ quan hệ
Copy method: void Copy(const RSC & r)
Attr = r.Attr; // Tap thuoc tinh
FDNum = r.FDNum; // so PTH
Cap = r.Cap; // Capacity
Key = r.Key;
delete [] F;
if (r.F == NULL)
F = NULL;
else {
F = new FD[Cap];
for(int i = 0; i < FDNum; ++i)
F[i] = r.F[i];
}
49
3.3.5. Hàm trả về khóa của lược đồ quan hệ
GetKey method: Set GetKey()
return Key;
3.3.6. Hàm mở rộng để đưa thêm phụ thuộc hàm
Extend method: void Extend()
int newCap = Cap + __UNIT;
FD *g = new FD[newCap];
for(int i = 0; i < FDNum; ++i)
g[i] = F[i];
Cap = newCap;
delete [] F;
F = g;
3.3.7. Toán tử gán lược đồ quan hệ
Signed operator: operator =(const RSC & r)
Copy(r);
3.3.8. Hàm chèn thêm một lược đồ quan hệ
Ins method: void Ins(const Set & ls, const Set & rs)
if (F == NULL)
{
Cap = __UNIT;
F = new FD[Cap];
F[0].Put(ls,rs);
FDNum = 1;
Attr = F[0].GetLR();
return;
}
50
if (FDNum == Cap) Extend();
F[FDNum].Put(ls,rs);
++FDNum;
Attr += (ls + rs);
3.3.9. Hàm chuẩn hóa tự nhiên
Norm method: void Norm()
int j = -1;
int k;
for (int i = 0; i < FDNum; ++i) {
if (F[i].GetRS().Empty()) continue;
++j;
F[j] = F[i];
for (int k = 0; k < j; ++k) {
if (F[k].GetLS() == F[i].GetLS()) {
F[k].AddRS(F[i].GetRS());
--j;
break;
} // if
} // for k
}
// for i
FDNum = j+1;
Attr.Reset();
for (int i = 0; i < FDNum; ++i)
Attr += F[i].GetLR();
}
3.3.10. Hàm tìm bao đóng
Closure method: Set Closure(const Set & x, int k = -1)
bitset<1000> mark; //danh dau cac FD da dung
Set y = x;
int used = 0;
51
while(true) {
used = 0;
for (int i = 0; i < FDNum; ++i) {
if (i == k) continue;
if (mark[i] == 0) {
if (F[i].GetLS() <= y) {
y += F[i].GetRS();
mark[i] = 1;
++used;
}
}
} // for
if (used == 0) break;
}
return y;
3.3.11. Hàm tìm khóa
FindKey method: Set FindKey()
Set k = Attr;
for (char c = 'A'; c <= 'Z'; ++c) {
if (k.Has(c)) {
k.Del(c);
if (!(Closure(k).Has(c)))
k.Ins(c);
}
} // for
return k;
3.3.12. Hàm kiểm tra siêu khóa
IsSuperkey method: bool IsSuperkey(const Set &x)
if (!(x <= Attr)) return false;
52
if (Key <= x) return true;
return Attr <= Closure(x);
3.3.13. Hàm kiểm tra khóa
IsKey method: bool IsKey(const Set &x)
if (!IsSuperkey(x))
return false;
// Kiem tra du thua
Set k = x;
for (char c ='A'; c <= 'Z'; ++c) {
if (k.IsIn(c)) {
k.Del(c);
if (Closure(k).IsIn(c))
return false;
k.Ins(c);
}
} // for
return true;
3.3.14. Hàm kiểm tra chuẩn BCNF
IsBCNF method: bool IsBCNF()
for (int i = 0; i < FDNum; ++i)
if (!IsSuperkey(F[i].GetLS()))
return false;
return true;
3.3.15. Hàm kiểm tra dẫn xuất
Derive method: bool Derive(const FD & g, int k = -1)
return (Closure(g.GetLS(),k) >= g.GetRS());
53
3.3.16. Hàm tìm phủ không dư
NonRedundant method: void NonRedundant()
for(int i = FDNum-1; i >= 0; --i) {
if (Derive(F[i],i)) {
if (FDNum-1 > i)
F[i] = F[FDNum-1];
--FDNum;
}
}
3.3.17. Toán tử in ra lược đồ quan hệ
Print operator: ostream & operator <<(ostream & os, const
RSC & s)
os << "\n Attribute Set: ";
os << s.Attr;
os << "\n Functional Dependencies: ";
for (int i = 0; i < s.FDNum; ++i)
os << "\n " << i << ". " << s.F[i];
return os;
3.4. Minh họa chương trình
Trong trường hợp tổng quát, giả sử ta có tập 05 phụ thuộc hàm:
1. A BC
2. ABD
3. BDE
4. DE A
54
5. B C
Khi đó:
void TestSet() {
Set x, y, z;
x = "ABCD";
y = "BD";
cout << "\n x = " << x;
cout << "\n y = " << y;
cout << "\n x > = y ? " << (x > = y);
cout << endl;
for (int i = 0; i < 26; ++i) {
cout << x[i];
}
cout << endl;
for (int i = 0; i < 26; ++i) {
if (y[i] ! = (char)0) cout << y[i];
}
cout << endl;
}
}
- Khi thực hiện dãy lệnh sau:
55
Ta thu ta thu được kết quả:
1Hình 3.1. Thử nghiệp với lớp Set
void TestFD() {
FD f("AB", "BFK"), g;
f.Print("\n f: ");
g = f;
cout << "\n g: " << g;
FD k("A", "C");
k.Print("\n k: ");
k.AddRS("DEF");
k.Print("\n Righ added k wit DEF: ");
k.AddLS("B");
k.Print("\n Left added k wit B: ");
}
- Khi thực hiện dãy lệnh sau:
56
Ta thu ta thu được kết quả:
2Hình 3.2. Thử nghiệm với lớp FD
void TestRSC() {
RSC r;
r.Read("rsc.txt"); //Đọc dữ liệu từ tệp rsc.txt
r.Show("\n r: ");
cout << "\n Key : " << r.GetKey();
cout << "\n BD? " << r.Closure("BD");
cout << "\n C? " << r.Closure("C");
cout << "\n A is a key? " << r.IsKey("A");
}
57
- Khi thực hiện dãy lệnh sau:
Ta thu ta thu được kết quả:
3Hình 3.3. Thử nghiệm với lớp RSC
Ta xét cơ sở dữ liệu Học sinh đơn giản sau: HS(HS#, HT, NS, QUE, DTB),
DTB(DTB#, XL, HB).
HS - tên quan hệ học sinh Các thuộc tính:
HS# - Mã học sinh
HT - Họ và tên học sinh
NS - Năm sinh của học sinh
QUE - Quê
DTB - Điểm trung bình
58
DTB - tên quan hệ điểm trung bình Các thuộc tính:
DTB# - Mã điểm trung bình (mã hóa dải điểm trung bình của học sinh)
XL - Xếp loại học sinh
HB - Học bổng dựa trên điểm trung bình
Nếu mã hóa các thuộc tính trong cơ sở dữ liệu theo thứ tự liệt kê ở trên
bởi các chữ cái A, B,…, G thì ta có 03 phụ thuộc hàm sau:
1. A -> BCDE
2. E -> FG
3. F -> G
Trong đó, hai phụ thuộc hàm cuối là phụ thuộc hàm nới lỏng.
void TestRSC() {
RSC r;
r.Read("sc2.txt");
r.Show("\n r: ");
cout << "\n Key : " << r.GetKey();
cout << "\n AE? " << r.Closure("AE");
cout << "\n BD is a key? " << r.IsKey("BD");
}
- Khi thực hiện dãy lệnh sau:
Ta thu được kết quả như trong Hình 3.4. Trong thử nghiệm này, nếu không
59
áp dụng khái niệm phụ thuộc hàm nới lỏng, thì kết quả sẽ không còn đúng nữa.
4Hình 3.4. Thử nghiệm lớp RSC với cơ sở dữ liệu học sinh
Ta xét cơ sở dữ liệu Thời khóa biểu giản lược như sau: GV(A#, B, C, D,
E), Mon(E#, G, H), Lop(#F, I, J, K).
Các thuộc tính: A: Mã giáo viên, B: Tên giáo viên, C: Ngày sinh, D: Tổ
chuyên môn, E: Mã môn học, G: Tên môn học, H: Số tiết, F: Mã lớp, I: Tên
lớp, J: Năm học, K: Khóa học, L: Giờ học.
Giả thiết: Mỗi giáo viên chỉ dạy 1 môn và tại 1 thời điểm, mỗi giáo viên
chỉ dạy cho 1 lớp.
Ta có 04 phụ thuộc hàm sau:
1. A -> BCDE
2. E -> GH
3. F -> IJK
4. AL -> F
void TestRSC() {
RSC r;
r.Read("sc5.txt");
60
- Khi thực hiện dãy lệnh sau:
r.Show("\n r: ");
cout << "\n Key : " << r.GetKey();
cout << "\n AE? " << r.Closure("AE");
cout << "\n BD is a key? " << r.IsKey("BD");
}
Ta thu được kết quả như trong Hình 3.5.
5Hình 3.5. Thử nghiệm lớp RSC với cơ sở dữ liệu thời khóa biểu
Ta xét cơ sở dữ liệu Thiết bị đơn giản sau: TB(A#, B, C, D, E, F, G),
PHONG(F#, H, I), MON(#G, J, K, L).
Các thuộc tính: A: Mã thiết bị, B: Tên thiết bị, C: Giá, D: Thời gian sản
xuất, E: Thời gian mua, F: Mã phòng (lắp đặt thiết bị), G: Mã môn học (sử dụng
thiết bị), H: Tên phòng, I: Tổ chuyên môn (quản lý phòng), J: Tên môn học, K:
Số tiết kỳ I, L: Số tiết kỳ II.
Ta có 03 phụ thuộc hàm sau:
1. A -> BCDEFG
61
2. F -> HI
3. G -> JKL
void TestRSC() {
RSC r;
r.Read("sc6.txt");
r.Show("\n r: ");
cout << "\n Key : " << r.GetKey();
cout << "\n AG? " << r.Closure("AG");
cout << "\n A is a key? " << r.IsKey("A");
cout << "\n BD is a key? " << r.IsKey("BD");
cout << "\n FG is a key? " << r.IsKey("FG");
}
- Khi thực hiện dãy lệnh sau:
Ta thu được kết quả như trong Hình 3.6.
6Hình 3.6. Thử nghiệm lớp RSC với cơ sở dữ liệu thiết bị
Như vậy, chương trình đã thử nghiệm chạy được trên bộ dữ liệu cụ thể và
62
đưa ra kết quả đúng như một số thuật toán đã trình bày trong Chương 2.
KẾT LUẬN
Luận văn đã đạt được kết quả:
- Nghiên cứu lý thuyết liên quan đến Cơ sở dữ liệu quan hệ, phụ thuộc
hàm, phụ thuộc hàm nới lỏng, các thuật toán tính bao đóng, khóa.
- Cài đặt được các lớp đối tượng quản lý tập hợp, thuộc tính, phụ thuộc
hàm, phụ thuộc hàm nới lỏng, khóa.
- Thử nghiệm cài đặt lớp đối tượng quản lý lược đồ quan hệ.
Hướng phát triển:
- Bổ sung thuật toán tìm tập phụ thuộc hàm từ CSDL cho trước.
- Hoàn chỉnh các hàm và toán tử cho các lớp đối tượng đã cài đặt. Ví dụ
như bổ sung thêm các toán tử thu gọn cho lớp tập hợp Set như +=, -=, *=.
- Cài tiến giao diện cho chương trình ứng dụng.
TÀI LIỆU THAM KHẢO
[1]. Nguyễn Xuân Huy (2003), Bài tập Cơ sở dữ liệu, NXB Thống Kê.
63
Tiếng Việt
[2]. Nguyễn Xuân Huy (2006), Các phụ thuộc logic trong cơ sở dữ liệu, Viện
[3]. Vũ Đức Thái (2016), Thiết kế cơ sở dữ liệu, NXB Đại học Thái Nguyên.
[4]. Vũ Đức Thi (1997), Cơ sở dữ liệu: Kiến thức và thực hành, NXB Thống
Khoa học và Công nghệ Việt Nam.
[5]. Lê Tiến Vương (2000), Nhập môn cơ sở dữ liệu quan hệ, NXB Thống Kê.
Kê.
[6]. Jaume Baixeries, Mehdi Kaytoue, Amedeo Napoli
Tiếng Anh
[7]. Loredana Caruccio, Vincenzo Deufemia, and Giuseppe Polese (2016), Relaxed Functional Dependencies - A Survey of Approaches, IEEE Trans. on Knowledge and Data Engineering, Vol. 28, No. 1, pp 147-165.
[8]. Maier D. (1983), The Theory of Relational Database, Computer Science
(2014), Characterization of Database Dependencies with FCA and Pattern Structures, Procc. Third International Conference, Analysis of Images, Social Networks and Texts (AIST 2014), Yekaterinburg, Russia. Springer, 436, pp.3 - 14, 2014.
[9]. Ullman, J. (1982), Principles of Data-base and Knowledge-base Systems, Second Edition, Computer Science Press, Potomac. (Có bản dịch tiếng Việt của Trần Đức Quang).
[10]. Garcia-Molina H., Ullman J., Widom J. (2002), Database System: The
Press, Rockville.
64
Complete Book, Prentice Hall.
