Luận văn Lược đồ cơ sở dữ liệu chuẩn hóa

trong luận văn là trung thực và chưa từng công bố trong bất kỳ công trình nào khác. Mọi thông tin trích dẫn trong luận văn đều đã được chỉ rõ nguồn gốc. Thái Nguyên, tháng 9 năm 2020 Tác giả Nguyễn Thị Mai Lan ii LỜI CẢM ƠN Tác giả xin được bày tỏ lòng biết ơn Ban Giám hiệu, giảng viên Trường Đại học Công nghệ thông tin – truyền thông – Đại học Thái Nguyên đã tận tình giảng dạy và tạo mọi điều kiện thuận lợi cho tác giả trong suốt quá trình học tập, nghiên cứu và thực hiện luận văn. Với tình cảm chân thành, tác giả xin được bày tỏ lòng biết ơn, cảm ơn sâu sắc tới PGS. TSKH Nguyễn Xuân Huy đã tận tình hướng dẫn, giúp đỡ để luận văn hoàn thành. Cuối cùng, tác giả xin được gửi lời cảm ơn tới bạn bè, gia đình và đồng nghiệp đã luôn động viên, giúp đỡ tác giả hoàn thành khóa học. Thái Nguyên, tháng 9 năm 2020 Tác giả Nguyễn Thị Mai Lan iii MỤC LỤC LỜI CAM ĐOAN ........................................................................................ i LỜI CẢM ƠN ............................................................................................ ii MỤC LỤC ................................................................................................. iii CÁC KÍ HIỆU ............................................................................................ v DANH MỤC CÁC BẢNG ........................................................................ vi MỞ ĐẦU ..................................................................................................... 1 1. Đặt vấn đề ................................................................................................ 1 2. Đối tượng và phạm vi nghiên cứu ........................................................... 4 3. Hướng nghiên cứu ................................................................................... 4 4. Phương pháp nghiên cứu ......................................................................... 4 5. Ý nghĩa khoa học và thực tiễn ................................................................. 5 6. Cấu trúc của luận văn .............................................................................. 5 Chương 1. CÁC KIẾN THỨC CƠ BẢN ................................................. 6 1.1.Quan hệ, bộ, thuộc tính .......................................................................... 6 1.2. Phụ thuộc hàm .................................................................................... 12 1.3. Bao đóng của tập thuộc tính ............................................................... 14 1.4. Phủ ...................................................................................................... 17 1.5. Khóa của lược đồ quan hệ .................................................................. 18 1.6. Các dạng chuẩn 1NF, 2NF, 3NF và BCNF ........................................ 19 1.7. Bảo toàn 3NF bảo toàn phụ thuộc hàm .............................................. 19 Chương 2. CÁC THUẬT TOÁN VỀ CHUẨN HÓA DỮ LIỆU QUAN HỆ .............................................................................................................. 20 2.1. Các thuật toán đại số quan hệ ............................................................. 20 2.1.1. Phép chọn......................................................................................... 20 2.1.2. Phép chiếu ........................................................................................ 20 2.1.3. Kết nối tự nhiên ............................................................................... 21 2.1.4. Phép hợp .......................................................................................... 22 iv 2.1.5. Phép giao ......................................................................................... 22 2.1.6. Phép trừ ............................................................................................ 23 2.1.7. Phép chia .......................................................................................... 24 2.2. Các thuật toán quản lý phụ thuộc hàm ................................................ 25 2.2.1. Thuật toán tìm phủ thu gọn tự nhiên của tập PTH F ....................... 25 2.2.2. Thuật toán tìm phủ không dư của tập PTH F ................................... 26 2.2.3. Thuật toán tìm phủ thu gọn trái của tập PTH F ............................... 26 2.2.4. Thuật toán tìm phủ thu gọn phải của tập PTH F .............................. 27 2.2.5. Thuật toán tìm phủ thu gọn của tập PTH F ...................................... 28 2.3. Các thuật toán tìm bao đóng ............................................................... 29 2.4. Các thuật toán khóa ............................................................................. 30 Chương 3. CÀI ĐẶT VÀ ỨNG DỤNG .................................................. 30 3.1. Tiếp cận hướng đối tượng cho thiết kế ............................................... 30 3.2. Thiết kế lớp tập hợp Set ...................................................................... 30 3.2.1. Các thuộc tính của lớp Set ............................................................... 30 3.2.2. Các phương thức của lớp Set ........................................................... 30 3.2.3. Các phép toán tập hợp ..................................................................... 33 3.3. Thiết kế lớp lược đồ quan hệ RSC ..................................................... 40 3.3.1. Các thuộc tính của lớp lược đồ quan hệ RSC .................................. 40 3.3.2. Các phương thức của lớp lược đồ quan hệ RSC ............................. 40 KẾT LUẬN ............................................................................................... 65 TÀI LIỆU THAM KHẢO ....................................................................... 66 v CÁC KÍ HIỆU KÍ HIỆU Ý NGHĨA a  S Phần tử a thuộc tập S a  S Phần tử a không thuộc tập S X  Y Tập X là tập con thực sự của tập Y X  Y Tập X là tập con của tập Y X  Y Giao của hai tập X và Y X  Y Hiệu của tập X và Y X  Y Hợp của hai tập X và Y  Lượng tử tồn tại  Lượng tử với mọi PTH Phụ thuộc hàm K Khóa LĐ Lược đồ vi DANH MỤC CÁC BẢNG Bảng 1. Quan hệ Bán hàng với 3 khách hàng đầu tiên ................................ 2 Bảng 2. Quan hệ Bán hàng với 4 khách hàng ............................................. 3 Bảng 3. Quan hệ Bán hàng với 4 khách hàng ............................................. 3 Bảng 1.1. Quản lý sinh viên ....................................................................... 8 Bảng 1.2. Bảng quy ước kích thước ............................................................ 8 1 MỞ ĐẦU 1. Lý do lựa chọn đề tài 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]. 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(XY)  (u,vR): (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 (XY). 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]:  X, Y, Z  U: 2 F1. Tính phản xạ: Nếu X  Y thì X  Y  F + F2. Tính gia tăng: Nếu XY  F + thì XZYZ  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 dạng chuẩn cho các lược đồ quan hệ. Một dạng biểu diễn của lược đồ quan hệ được gọi là dạng chuẩn nếu nó cho phép người quản trị và người khai thác cơ sở dữ liệu đảm bảo được tính nhất quán và toàn vẹn dữ liệu trong quá trình cập nhật và khai thác cơ sở dữ liệu [4],[5]. Quá trình chuẩn hoá (do Codd đề nghị 1972) lấy một lược đồ quan hệ và thực hiện một loạt các kiểm tra để xác nhận nó có thoả mãn một dạng chuẩn nào đó hay không. Quá trình này được thực hiện theo phương pháp trên xuống bằng việc đánh giá mỗi quan hệ với tiêu chuẩn của các dạng chuẩn và tách các quan hệ nếu cần. Lúc đầu, Codd đề nghị ba dạng chuẩn gọi là dạng chuẩn 1, dạng chuẩn 2 và dạng chuẩn 3. Tất cả các dạng chuẩn này dựa trên các phụ thuộc hàm giữa các thuộc tính của một quan hệ. Chuẩn hoá dữ liệu có thể được xem như một quá trính phân tích các lược đồ quan hệ cho trước dựa trên các phụ thuộc hàm và các khoá chính của chúng để đạt đến các tính chất mong muốn: (1) Cực tiểu sự dư thừa và (2) Cực tiểu các phép cập nhật bất thường. Thí dụ, cho quan hệ bán hàng như sau: Đơn giá Thành tiền Tên Số Bộ Mã hàng (nghìn (nghìn hàng lượng đồng) đồng) 1 H1 Bút 10 2 20 2 H2 Vở 4 10 40 3 H3 Cặp 70 1 70 3 Bảng 1. Quan hệ Bán hàng với 3 khách hàng đầu tiên Ta biết, quan hệ Bán hàng các thỏa phụ thuộc hàm sau đây: Mã hàng  Đơn giá Mã hàng  Tên hàng Mã hàng  Đơn giá, Tên hàng Đơn giá, Số lượng  Thành tiền Nếu khách hàng thứ tư mua vở nhưng bàn tính tiền nạp nhầm dữ liệu thì quan hệ Bán hàng có thể có dạng sau: Đơn giá Thành tiền Tên Số Bộ Mã hàng (nghìn (nghìn hàng lượng đồng) đồng) 1 H1 Bút 10 2 20 2 H2 Vở 4 10 40 3 H3 Cặp 70 1 70 4 H2 Vở 4 10 45 Bảng 2. Quan hệ Bán hàng với 4 khách hàng Như vậy, quan hệ Bán hàng tại Bảng 2 chứa dữ liệu không chuẩn. Sự cố này do bộ 4 gây ra. Tuy nhiên, có trường hợp sinh ra dữ liệu không chuẩn nhưng ta không thể biết nguyên nhân tại bộ nào. Giả sử khách hàng thứ tư cũng mua vở với dữ liệu được nạp như trong Bảng 3. Đơn giá Thành tiền Tên Số Bộ Mã hàng (nghìn (nghìn hàng lượng đồng) đồng) 1 H1 Bút 10 2 20 2 H2 Vở 4 10 40 4 3 H3 Cặp 70 1 70 4 H2 Vở 5 10 50 Bảng 3. Quan hệ Bán hàng với 4 khách hàng Lúc này ta chỉ có thể nói, quan hệ Bán hàng chứa dữ liệu mâu thuẫn tại bộ 2 và bộ 4, nhưng ta không biết bộ nào sinh ra mâu thuẫn. Trong trường hợp này ta nói quan hệ Bán hàng không chuẩn. Luận văn được tập trung nghiên cưú các dạng chuẩn của lược đồ cơ sở dữ liệu quan hệ. Vậy trong khuôn khổ khóa luận thạc sĩ, học viên chọn đề tài: Lược đồ cơ sở dữ liệu chuẩn hóa 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.  Các thuật toán cơ bản xử lý các đối tượng trong lược đồ quan hệ.  Các thuật toán chuẩn hóa lược đồ quan hệ. 3. Hướng nghiên cứu  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, các dạng chuẩn, các thuật toán tính bao đóng, khóa, chuẩn hó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, khóa, các dạng chuẩn 2NF và 3NF.  Thử nghiệm các lược đồ quan hệ. 5 4. Phương pháp nghiên cứu Trong luận văn học viên dự kiến sử dụng các phương pháp nghiên cứu chính sau:  Phương pháp 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.  Phương pháp lập trình hướng đối tượng.  Phương pháp đối sánh.  Phương pháp trao đổi khoa học, lấy ý kiến chuyên gia. 5. Ý nghĩa khoa học và thực tiễn  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 dạng chuẩ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, khóa của các lược đồ quan hệ và các thuật toán chuẩn hóa 3NF. Hệ thống có thể được sử dụng để khảo sát và kiểm định các dạng chuẩn và các quy trình chuẩn hóa lược đồ quan hệ. 6. Cấu trúc của luận văn Luận văn có cấu trúc gồm: Phần mở đầu Phần nội dung Chương 1. Các kiến thức cơ sở. Chương 2. Các thuật toán về chuẩn hóa dữ liệu quan hệ Chương 3. Cài đặt và ứng dụng. 6 CHƯƠNG 1 - CÁC KIẾN THỨC CƠ BẢN Trong chương 1 này, tôi sẽ giới thiệu một số cơ sở lý thuyết về cơ sở dữ liệu gồm: 1.1 Quan hệ, bộ, thuộc tính Định nghĩa 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 AiU, i = 1,2,...,n có một tập chứa ít nhất hai phần tử dom(Ai) được gọi là miền trị của thuộc tính Ai. Gọi D là hợp của 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 là R(U), là một tập các á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(U) 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 U. Một quan hệ rỗng, ký hiệu , là 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ó hai bộ trùng lặp. 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ữ LATIN HOA đầu bảng chữ A, B, C,... Tập thuộc tính được ký hiệu bằng các chữ LATIN 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 7 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, t1 ... 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 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 nhau trên miền rỗng các thuộc tính, t. = v..  Hàm Attr(R) cho tập thuộc tính của quan hệ R.  Hàm Card(R) cho lực lượng (số bộ) 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) Ký hiệu REL(U) là tập toàn thể các quan hệ trên tập thuộc tính U, REL_p(U) là tập toàn thể các quan hệ có không qúa p bộ trên tập thuộc tính U, p  1. 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 Attr(R) = Attr(S). Với mỗi bộ t trong quan hệ R(U) và mỗi bộ v trong quan hệ S(V) ta ký hiệu tv là phép dán hai bộ t và v. tv cho ta bộ r trên tập thuộc tính UV thoả điều kiện: r.U = t và r.V = v. Với mỗi bộ t trong quan hệ R(U) và với mỗi quan hệ S(V) ta ký hiệu tS là phép dán bộ t với quan hệ S. tS cho ta quan hệ P(UV) = { tv | vS } Thí dụ 8 Trong một trường học, chúng ta quản lý sinh viên theo biểu gồm các thuộc tính sau: Giới Năm Quê STT Mã SV Họ tên SV Lớp Khoa tính sinh quán Nguyễn Thái Toán 1 DTS001 Nam 2001 A1 Duy Nam Bình học Bùi Minh Vật 2 DTS002 Nữ 2001 Phú Thọ A2 Hiền lí Trần Ngọc Thái Toán 3 DTS003 Nữ 2000 A1 Hà Nguyên học Hoàng Hóa 130 DTS130 Mạnh Nam 2001 Hà Nội A3 học Trung Bảng 1.1. Quản lý sinh viên Ta quy ước kích thước của các thuộc tính như sau: Tên thuộc tính Kiểu Kích thước STT Kí tự 3 MASV Kí tự 8 HOTEN Kí tự 30 GIOITINH Kí tự 4 NAMSINH Số 4 QUE Kí tự 15 LOP Kí tự 3 KHOA Kí tự 15 Bảng 1.2. Bảng quy ước kích thước 9 Như vậy ta có tập thuộc tính SINHVIEN={STT,MASV,HOTEN,GIOITINH,NAMSINH,QUE,LOP,KHOA} Ta có ứng với cột Mã SV có DTS01, DTS02DTS130 là thuộc tính của bảng Với bản ghi thứ 2(dòng thứ 2) chúng ta có một bộ gồm STT(2), Mã SV(DTS02), Họ tên SV(Bùi Minh Hiền), Giới tính(Nữ), Năm sinh(2001), Quê quán(Phú Thọ), lớp(A2), Khoa(Vật lí). 1.2 Phụ thuộc hàm Định nghĩa Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là biểu thức dạng f: X→Y ; X,Y⊆ U 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 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. X là vế trái và Y là vế phải của PTH f. Ta cũng dùng hai toán tử LS(f) và RS(f) để xác định vế trái và vế phải của PTH f, cụ thể là nếu f: X→ Y thì LS(f) = X, RS(f) = Y. Cho quan hệ R(U) và một PTH f: X→Y trên U. Ta nói quan hệ R thoả PTH f 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(X→Y) (∀ u,v ∈ R): (u.X = v.X) (u.Y = v.Y) Ta dùng ký hiệu X ↛Y với ý nghĩa tập thuộc tính Y không phụ thuộc hàm vào tập thuộc tính X[7,8]. 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) 10 Nếu quan hệ R thỏa PTH f ta cũng nói PTH f đúng trong quan hệ R. Thí dụ: Cho quan hệ R(A, B, C, D, E) như sau P (A B C D E) a 1 x d y a 1 x d x b 2 y 2 x b 2 y 2 y Và các PTH f1: AA, f2: AB, f3: ACC, f4: AD, f5: DA, f6: AE. Khi đó các PTH f1 - f5 đúng trong R, mặt khác, R không thỏa PTH f6. Cho trước tập PTH F trên 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, SAT_p(U), p  1 là tập toàn thể các quan hệ Có không quá p bộ trên U và thoả tập PTH F , cụ thể là SAT(F) = { R | RREL(U), R(F) } SAT_p(F) = { R | RREL_p(U), R(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 . Hệ tiên đề Armstrong Bao đóng của tập PTH Định nghĩ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 XY  F + thì XZYZ  F + F3. Tính bắc cầu: Nếu XY  F + và YZ  F + thì XZ  F + Chú ý : 11 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 đúng trong mọi quan hệ. Ngoài ra, các quan hệ trên tập thuộc tính U có không quá một bộ thỏa mọi PTH trên U. Một số tính chất của PTH Cho tập thuộc tính U và các tập phụ thuộc hàm F, G trên U, tập một số quan hệ  trên U, các quan hệ R và S trên U. Dễ dàng chứng minh các tính chất sau đây: 1. Nếu F  G thì SAT(F)  SAT(G) 2. SAT(FG) = SAT(F)  SAT(G) 3. FD(RS)  FD(R)  FD(S) 4. R  S  FD(R)  FD(S) 5. F  FD(SAT(F)) 6.   SAT(FD()) 7. SAT(FD(SAT(F))) = SAT(F) 8. FD(SAT(FD())) = FD() Thí dụ Chứng tỏ FD(RS)  FD(R )  FD(S). Ta chọn U = AB; quan hệ R(U) chứa một bộ duy nhất u = (a,x); quan hệ S(U) chứa một bộ duy nhất v = (a,y), x y. R và S thỏa mọi PTH trên U. Quan hệ P = R S chứa 2 bộ u và v. P không thỏa PTH AB. Một số tính chất mở rộng của PTH Sử dụng ba tiên đề Armstrong ta dễ dàng chứng minh các tính chất F4 - F11 sau đây. Một số tính chất được chia nhỏ nhằm mục đích mô tả các hệ tiên đề khác cho PTH trong các mục tiếp theo.  X, Y, Z, V  U,  A  U: F4. Tính tựa bắc cầu: XY, YZV  XZV F5. Tính phản xạ chặt: X X 12 F6. Mở rộng vế trái và thu hẹp vế phải: XY  XZY\V F7. Cộng tính đầy đủ: XY, ZV  XZYV F8. Mở rộng vế trái: XY  XZY F9. Cộng tính ở vế phải: XY, XZ  XYZ F10. Bộ phận ở vế phải: XYZ  XY F11.Tính tích luỹ: XYZ, ZAV  XYZA 1.3 Bao đóng của tập thuộc tính Định nghĩa 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+} Thuật toán tìm bao đóng của một 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. Để xác định bao đóng X+ của tập thuộc tính X ta xây dựng dãy bao nhau X(0)  X(1)   X(i) như sau  Xuất phát: Đặt X(0)=X,  Với i > 0, ta đặt 푋(푖+1) = 푋푖 ⋃ 푅 퐿→푅∈퐹 퐿푋푖  Nếu X(i+1) = X(i) thì dừng thuật toán và cho kết quả X + = X(i). Algorithm Closure Format: thuộc tính X của U Output: - Y = X+ = {A U | XA F+} Method Y:=X; repeat 13 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. Thuật toán trên có độ phức tạp O(mn2 ). 1.4 Phủ Định nghĩa 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 có nghĩa F và G không tương đương. 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+ 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 PTH F. + Phủ không dư Định nghĩa: 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 (i) G là một phủ của F, và (ii) G có dạng không dư theo nghĩa sau: gG: G \{g} ≢ G Thuật toán tìm phủ không dư của tập PTH Algorithm Nonredundant Format: Nonredundant(F) Input: - Tập PTH F Output: - Một phủ không dư G của F 14 (i) G  F  (ii) g  G: G\{g} ≢ G Method G:=F; for each FD g in F do If IsMember(g,G\{g})then G:=G\{g}; endif; endfor; return G; end Nonredundant. + Phủ thu gọn trái Định nghĩ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 (i) G là một phủ của F, và (ii) (LRG,AL): G\{LR}{L\AR} ≢ G Thuật toán tìm phủ thu gọn trái của tập PTH Để ý rằng AL ta có L\A L, nên g: LRG,AL): G\{g}{L\AR}╞ LR, do đó ta chỉ cần kiểm tra G ╞ L\AR ? Algorithm Left_Reduced Format: Left_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn trái G của F (i) G  F (ii) g:LRG,AL: G\{g}{L\AR}≢G Method G:=F; for each FD g:L  R in F do X:=L; for each attribute A in X do if IsMember(L\AR,G)then delete A from L in G; endif; endfor; 15 endfor; return G; end Left_Reduced. + Phủ thu gọn phải Định nghĩ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 phải của F nếu (i) G là một phủ của F, và (ii) (LRG, AR): G\{LR}{LR\A} ≢ G Thuật toán tìm phủ thu gọn phải của tập PTH Algorithm Right_Reduced Format: Right_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn của F Method G:=F; for each FD g:L  R in F do H:=G\{LR}; X:=R; for each attribute A in X do if A in Closure(L,H{LR\A})then delete A from R in G; endif; endfor; endfor; return G; end Right_Reduced. + Phủ thu gọn Định nghĩ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 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. Thuật toán tìm phủ thu gọn của tập PTH Algorithm Reduced 16 Format: Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn của F Method return Right_Reduced(Left_Reduced(F)); end Reduced + Phủ tối thiểu Định nghĩa: 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 thiểu của F nếu (i) G là một phủ thu gọn của F (ii) Vế phải của mọi PTH trong G chỉ chứa một thuộc tính. Thuật toán tìm phủ tối thiểu của tập PTH Algorithm MinCover Format: MinCover(F) Input: - Tập PTH F Output: - Một phủ tối thiểu G của F Method // Tách mỗi PTH LR trong F thành các PTH có // vế phải chỉ chứa một thuộc tính LA, A  R G:=; for each FD LR in F do for each attribute A in R\L do if LA not_in G then add LA to G; endif; endfor; endfor; G:=Nonredundant(Left_Reduced(G)); return G; end MinCover. Thí dụ 17 Cho lược đồ quan hệ R = , Trong đó : U = {ABC} F = {A→B, B→A, C→B} Hãy tìm một khoá tối thiểu K của lược đồ R Đặt T = {ABC}; P = {AB} ; K = U\P = {C} Tính thử K + Ta có K+ = {CBA} = U Vì K+ = U, nên khóa tối thiểu tìm được là: K = {C} là một khoá của R. 1.5 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Đ p nếu (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. Thí dụ: Tìm khóa biết: U = ABCDEGF = {B -> C, AC -> D, D -> G, AG -> E} Đặt: T = { BACDG}- P = {CDGE}- K = U\P Ta được: K = {AB}, T ∩ P = {CDG} Tính K+ ta có: K+ = {BEACDG} U 18 Vậy khóa tìm được là: K = {AB} Chú ý: Trong một số tàì liệu thuật ngữ khoá được dùng theo nghĩa siêu khoá và thuật ngữ khoá tối tiểu được dùng theo nghĩa khoá. 1.6 Các dạng chuẩn 1NF, 2NF, 3NF và BCNF 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. 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á,  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 XA, 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 XY đề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 1.7 Bảo toàn 3NF bảo toàn phụ thuộc hàm 19 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ả RREL(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 thiểu của F: G = {K1A1, K2A2,..., KmAm} 2. Ghép các PTH có cùng vế trái trong G để thu được phủ G = {K1X1, K2X2,..., KsXs}. 3. /* Xét phép tách  = (K1X1,...,KsXs). Nếu  chứa một siêu khóa nào đó của p 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 20 CHƯƠNG 2 - CÁC THUẬT TOÁN VỀ CHUẨN HÓA DỮ LIỆU QUAN HỆ Trong chương này tôi sẽ trình bày các thuật toán của đại số quan hệ, thuật toán quản lý phụ thuộc hàm, các thuật toán tìm bao đóng và các thuật toán tìm khóa gồm các thuật toán sau: 2.1. Các thuật toán của đại số quan hệ Các thuật toán của đại số quan hệ gồm: 2.1.1 Phép chọn Algorithm Selection Function: Thực hiện phép Chọn Format: P = R(e) Input: - Quan hệ R(U) - Biểu thức chọn e trên U. Output: - Quan hệ P(U) = R(e) = {tR | Sat(t,e)} Method // Tạo lập quan hệ P tương thích với R Create(P,Attr(R)); for each tuple t in R with Sat(t,e) do add t to P ; endfor; return P; end Selection. Độ phức tạp tính toán: Thuật toán duyệt r bộ, phép kiểm tra Sat(t, e) kiểm tra trên n thuộc tính, tổng cộng cần O(n.r) phép kiểm tra. [1,2] 2.1.2 Phép chiếu Algorithm Projection Function: Thực hiện phép Chiếu Format: P = R[X] Input: - Quan hệ R(U) - Tập con thuộc tính X của U. 21 Output: - Quan hệ R[X]={t.X | tR} Method Create(P,X); for each tuple t in R with t.X not_in P do add t.X to P ; endfor; return P; end Projection. Độ phức tạp tính toán: Giả sử mỗi lần thuật toán chỉ nạp được 1 bộ vào quan hệ kết quả P. Để kiểm tra bộ t.X có trong P ta cần tối đa r phép so sánh theo n thuộc tính. Vậy độ phức tạp tính toán là O(n.r2). [1,2] 2.1.3 Kết nối tự nhiên Algorithm Join Function: Thực hiện phép Kết nối tự nhiên hai quan hệ. Format: P = RS Input: - Quan hệ R(U) - Quan hệ S(V) Output: - Quan hệ RS={uv | uR,vS,u.M = v.M, M = U  v} Method X = Attr(R)  Attr(S); M = Attr(R)  Attr(S); Create(P,X); for each tuple u in R do for each tuple v in S with (u.M = v.M) do add uv to P ; endfor; endfor; return P; end Join. 22 Độ phức tạp tính toán: Giả sử hai quan hệ R và S có k thuộc tính chung, khi đó độ phức tạp tính toán sẽ là O(r.s.k) thao tác trên bộ. [1,2] 2.1.4 Phép hợp