1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Tài liệu học tập Cơ sở dữ liệu: Phần 2 - Trường ĐH Kinh tế kỹ thuật công nghiệp

Tài liệu học tập Cơ sở dữ liệu: Phần 2 - Trường ĐH Kinh tế kỹ thuật công nghiệp

Nội dung của tài liệu bao gồm 4 chương, trình bày cụ thể như sau: Cơ sở dữ liệu quan hệ; Ngôn ngữ truy vấn dữ liệu; Lý thuyết thiết kế cơ sở dữ liệu; Bảo mật và toàn vẹn dữ liệu. Mời các bạn cùng tham khảo nội dung tài liệu phần 2 dưới đây. 121 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU CHƯƠNG 3 LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU Mục tiêu: Chương này sẽ trình bày những khái niệm cơ bản nhất về lý thuyết cơ sở dữ liệu quan hệ do E.F Codd đề xuất, đó là các khái niệm về quan hệ, về khóa của lược đồ quan hệ. Nhữ

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 80

Ngày tạo 4/6/2023 9:40:44 PM +00:00

Loại tệp PDF

Kích thước 1.30 M

Tên tệp

Tải Tài liệu học tập Cơ sở dữ liệu: Phần 2 - Trường ĐH... (.pdf)

Xem mẫu

  1. 121 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU CHƯƠNG 3 LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU Mục tiêu: Chương này sẽ trình bày những khái niệm cơ bản nhất về lý thuyết cơ sở dữ liệu quan hệ do E.F Codd đề xuất, đó là các khái niệm về quan hệ, về khóa của lược đồ quan hệ. Những khái niệm này có vai trò quan trọng trong việc thiết kế và cài đặt các hệ cơ sở dữ liệu quan hệ và các hệ quản trị cơ sở dữ liệu. Nội dung của chương bao gồm các phần: Phụ thuộc hàm Bao đóng Phủ tối thiểu Khóa của lược đồ quan hệ Phép tách – kết nối Các dạng chuẩn của lược đồ quan hệ Các phương pháp chuẩn hóa lược đồ quan hệ 3.1. Phụ thuộc hàm 3.1.1 Định nghĩa phụ thuộc hàm Cho một quan hệ R xác định trên tập thuộc tính U, kí hiệu là R(U). X, Y là các tập con của U, ta nói rằng X xác định Y hay Y phụ thuộc hàm vào X, kí hiệu X  Y nếu trên quan hệ R ta có mọi bộ giá trị t1, t2 bất kỳ mà giá trị của tập thuộc tính X trên bộ t1 (kí hiệu t1[X]) bằng giá trị của tập thuộc tính X trên bộ t2 (kí hiệu là t2[X]) thì t1[Y]) = t2[Y]). Phụ thuộc hàm ký hiệu là FD. Cần chú ý rằng chỉ xét các phụ thuộc hàm thỏa mãn cho mọi quan hệ trên lược đồ tương ứng của nó. Không thể xem xét một phụ thuộc hàm thỏa mãn một quan hệ r đặc biệt ( ví dụ quan hệ rỗng) của lược đồ R rồi sau đó qui nạp rằng phụ thuộc hàm đó là thỏa trên R. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  2. 122 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU S (S# STATUS CITY) P (P# PNAME COLOR WEIGHT CITY) SP (S# P# QTY) Trong quan hệ S của hàng cung ứng, mỗi một trong số các thuộc tính SNAME, STATUS, CITY đều phụ thuộc hàm vào thuộc tính S#. Mỗi giá trị S# tồn tại vừa đúng một giá trị tương ứng đối với từng thuộc tính SNAME, STATUS, CITY. Khi đó có thể viết: S# → SNAME, S# → STATUS và S# → CITY. 3.1.2 Phụ thuộc hàm đầy đủ và không đầy đủ  Phụ thuộc hàm (FD) đầy đủ: Một FD X Y là một phụ thuộc hàm đầy đủ nếu loại bỏ bất kỳ thuộc tính A nào ra khỏi X thì FD không còn đúng nữa  Phụ thuộc hàm không đ  ầy đủ (FD bộ phận): Một FD X Y là phụ thuộc hàm bộ phận nếu có thể bỏ đi 1 thuộc tính A  X ra khỏi X mà FD vẫn còn đúng. 3.1.3 Hệ tiên đề Amstrong Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ R(U) và X→Y là một phụ thuộc hàm, X,Y⊆ U. Nói rằng X→Y được suy diễn logic từ F nếu mối quán hệ r trên R(U) đều thỏa các phụ thuộc hàm của F thì cũng thỏa X→Y. Chẳng hạn F= {A→B,B→C} thì A→C suy ra từ F. Gọi F+ là bao đóng (closure) của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. nếu F= F+ thì F là họ đầy đủ( full family) của các phụ thuộc hàm. Để có thể xác định khóa của một lược đồ quan hệ và các suy diễn logic giữa các phụ thuộc hàm cần thiết phải tính được F+ từ F. Do đó đòi hỏi phải có các hệ tiên đề. Tập các quy tắc của hệ tiên đề được Armstrong (1974) đưa ra, thường được gọi là hệ tiên đề Armstrong. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  3. 123 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Gọi R(U) là lược đồ quan hệ với U= {A1, ….., An} là tập các thuộc tính. X,Y, Z, W ⊆ U. Hệ tiên đề Armstrong bao gồm :  A1(phản xạ): nếu Y⊆X thì X→Y  A2(tăng trưởng):nếu Z⊆U và X→Y thì XZ→YZ trong đó ký hiệu XZ là tập hợp của 2 tập X và Z thay cho ký hiệu X∪Z.  A3(bắc cầu): nếu X→Y và Y→Z thì X→Z Ví dụ : AB→C, C→A Cần chứng minh rằng BC→ABC Thật vậy từ : 1. C→A ( giả thiết) 2. BC→AB ( luật tăng trưởng (1) thêm B) 3. AB→C ( giả thiết) 4. AB→ABC ( tăng trưởng (3) thêm AB) 5. BC→ABC ( bắc cầu từ (2) và (4)) Định lý : Hệ tiên đề Armstrong là đúng. Có nghĩa là F là tập các phụ thuộc hàm đúng trên quan hệ r. nếu X→Y là một phụ thuộc hàm được suy diễn từ F nhờ hệ tiên đề Armstrong thì X→Y là đúng trên quan hệ r. Chứng minh : Lần lượt kiểm tra tính đúng đắn của ba tiên đề A1, A2, A3 A1 : Tiên đề A1 rõ ràng là đúng vì không thể có hai bộ bằng nhau trên X mà lại không bằng nhau trên tập con của nó. A2 : Giả sử rằng quan hệ r thỏa mãn X→Y. Tồn tại hai bột, u ∈r sao cho t[XZ] = u[ZX] mà t[YZ] ≠ u[YZ]. Vì rằng t[Z] = u[Z] nên để có t[YZ] ≠ u[YZ] thì t[Y] ≠ u[Y]. Nhưng vì t[X] = u[X] nên t[Y] ≠ u[Y] là trái với giả thiết X→Y. Vì vậy A2 đúng. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  4. 124 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU A3 : Cho X→Y và Y→Z đúng trên quan hệ r. Giả sử tồn tại hai bộ t, u∈r sao cho t[Y] = u[Y]. Nhưng lại có t[Y] = u[Y] và t[Z] ≠ u[Z] là trái với giả thiết Y→Z. Do vậy t[Z] = u[Z]. Suy ra X→Z đúng trên quan hệ r. Từ hệ tiên đề Armstrong suy ra một số luật sau đây : Định lý : a. Luật hợp: nếu X→Y và X→Z thì X→YZ b. Luật tựa bắc cầu: nếu X→Y và WY→X thì XW→Z c. Luật tách: nếu X→Y và Z⊆Y thì X→Z Chứng minh: a. Từ X→Y dùng luật tăng trưởng thêm X có X→XY, dùng luật bắc cầu ta có điều phải chứng minh. b. Từ X→Y, dùng luật tăng trưởng, thêm W có WX→WY. Dùng luật bắc cầu cho WX→WY và Wy→Z suy ra WX→Z. c. Vì Z⊆Y nên Y→Z theo luật phản xạ. Dùng luật bắc cầu cho X→Y và Y→Z có X→Z. 3.1.4. Bao đóng 3.1.4.1 Bao đóng của tập các phụ thuộc hàm Định nghĩa: Cho quan hệ R xác định trên tập thuộc tính U, F là tập các phụ thuộc hàm. Tập hợp tất cả các phụ thuộc hàm được suy diễn logic từ tập F được gọi là bao đóng của F và kí hiệu là F+ Ví dụ: Cho quan hệ R, U ={ A, B, C, D, E, I } F= {AI, ACD, BC, DE} Ta có: 1. BC (gt) 2. AB  AC (tăng trưởng thêm A vào (1)) 3. AC D (gt) KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  5. 125 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU 4. AB  D (bắc cầu (2) và (3)) CM tương tự có: AC E, AB E Vậy: F+ ={AI, ACD, BC, DE, ABD, ACE, ABE} 3.1.4.2. Bao đóng của tập các thuộc tính Định nghĩa: Cho quan hệ R xác định trên tập các thuộc tính U, gọi F là tập các phụ thuộc hàm trên tập U, X  U, X+ là bao đóng của X trên tập F được định nghĩa như sau: X+ = { X  A / X  A  F+ } 3.1.4.3. Thuật toán tìm bao đóng  Input: U, F; X, Y, Z  U  Output: X+  Phương pháp: Tính liên tiếp tập các thuộc tính X0, X1, … theo quy tắc:  B1: X0 = X  Bi: Xi+1 = Xi  A Nếu tồn tại phụ thuộc hàm Y  Z thuộc F+ mà A  Z, Y  Xi Do X  U mà U hữu hạn nên i hữu hạn, khi đó X+ = Xi+1 Ví dụ: Cho quan hệ R xác định trên U, với U = { A, B, C, D, E, I}; F= {AI, ACD, BC, DE} Tìm (AC)+ Giải: 1. X0 = AC 2. X1= ACDI (vì A  I, AC  D) 3. X2= ACDIE (vì D  E) Vậy: (AC)+ = ACDEI KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  6. 126 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU 3.1.5. Phủ tối thiểu Phủ của tập các phụ thuộc hàm : Gọi F và G là các tập của các phụ thuộc hàm. Nói rằng F, G là tương đương nếu F+ = G+. Nếu F, G là tương đương đôi khi còn nói F phủ G (và G phủ F). Dễ dàng kiểm tra liệu F và G có tương đương với nhau hay không. Phương pháp kiểm tra: Lấy mỗi phụ thuộc hàm Y→Z thuộc F, kiểm tra xem liệu Y→Z có thuộc G+ không ? Dùng thuật toán 3.1 để tính Y+ và kiểm tra liệu Z⊆ Y+ hay không ? Nếu tồn tại một phụ thuộc hàm Y→Z thuộc F mà không phụ thuộc G+ thì chắc chắn F+ ≠ G+. Nếu mỗi phụ thuộc hàm thuộc F cũng thuộc G+ thì mỗi phụ thuộc hàm V→W thuộc F+ cũng thuộc G+. Để kiểm tra mỗi phụ thuộc G là thuộc F+ quá trình làm hoàn toàn tương tự. Do đó F và G là tương đương khi và chỉ khi mỗi phụ thuộc hàm thuộc F là thuộc G+ và mỗi phụ thuộc hàm thuộc G thuộc F+. Định lý : Mỗi tập các phụ thuộc hàm F đều được phủ bằng tập các phụ thuộc hàm G mà vế phải các phụ thuộc hàm đó bao gồm không quá một thuộc tính. Chứng minh : Gọi G là tập các phụ thuộc hàm X→A sao cho với X→Y thuộc F thì A∈Y. TừX→Y suy ra X→A. Do vậy G⊆ F+ Ngược lại, có F⊆ G+ vì nếu Y= A1…An thì X→Y được suy ra từ : X→A1, ….., X→An nhờ luật hợp. Để có thể phục vụ quá trình thiết kế lược đồ cơ sở dữ liêu, sau đây sẽ đưa ra một số khái niệm: Gọi tập các phụ thuộc hàm F là tối thiểu nếu: a. Mỗi vế phải của một phụ thuộc hàm thuộc F chỉ có một thuộc tính. b. Không tồn tại một phụ thuộc hàm X→A thuộc F mà F+ = (F- {X→A}) +. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  7. 127 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU c. Không tồn tại một phụ thuộc hàm X→A thuộc F và một tập hợp con Z của X mà F+= (F- {X→A}∪ {Z→A}) + Thực vậy, điều kiện b đảm bảo cho tập F không có một phụ thuộc hàm nào mà dư thừa, điều kiện C đảm bảo không có thuộc tính nao tham gia phía trái của phụ thuộc hàm là dư thừa. Vế phải của phụ thuộc hàm ở điều kiện a chỉ có một thuộc tính đảm bảo chắc chắn không có một thuộc tính nào trên vế phải là dư thừa. Định lý Mỗi tập phụ thuộc hàm F đều tương đương với một tập F’ tối thiểu. Chứng minh: Giả sử rằng không vế phải nào của các phụ thuộc hàm của F có nhiều hơn một thuộc tính. Để kiểm tra điều kiện b, xét (X→Y) ∈F. Nếu (F- {X→Y}) + =F+ thì loại bỏ X→Y khỏi F. Chú ý rằng các phụ thuộc hàm được sắp theo một thứ tự khác nhau thì sẽ cho ra kết quả khác nhau. Ví dụ: Cho tập F gồm: A→B, A→C, B→C, B→A, C→A Có thể loại bỏ F : B→A và A→C hoặc loại bỏ B→C nhưng không thể đồng thời loại bỏ cả ba phụ thuộc hàm. Như vậy điều kiện b được thỏa. Cần kiểm tra điều kiện c cho tập các phụ thuộc còn lại của F. Ở đây cũng cần lưu ý tới thứ tự các thuộc tính xuất hiện bên vế trái của các phụ thuộc hàm. Loại bỏ các thuộc tính vế trái của các phụ thuộc hàm sao cho tập các thuộc tính vẫn là tương đương. Quá trình tiếp tục cho đến khi không thể loại bỏ phụ thuộc hàm nào được nữa. Như vậy tập các phụ thuộc hàm còn lại của F sẽ tạo nên F’ và thỏa ba điều kiện của một tập tối thiểu. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  8. 128 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Tìm phủ tối thiểu  B1: Tách các thuộc tính ở vế phải của mỗi phụ thuộc hàm thành nguyên tử (Vế phải của mỗi phụ thuộc hàm chỉ có 1 thuộc tính)  B2: Loại bỏ phụ thuộc hàm dư thừa Giả sử: Xét phụ thuộc hàm XY  Tính X+ trên tập F’ (F’ đã loại bỏ FD XY ) Nếu X+ Y thì loại XY khỏi tập F  B3: Loại bỏ các thuộc tính dư thừa ở vế trái Giả sử: Xét phụ thuộc hàm XYZ (Loại X hoặc loai Y?) Xét XZ tính X+ (trên tập F) nếu Y X+  Loại Y Xét YZ tính Y+ (trên tập F) nếu X Y+  Loại X Vậy, tập các phụ thuộc hàm còn lại là phủ tối thiểu cần tìm. Ví dụ: Cho F = {X → Z, XY → WP, XY → ZWQ, XZ → R}. Xác định tập phủ tối thiểu từ tập F? Giải: B1. Tách các vế phải của các phụ thuộc hàm sao cho chỉ chứa duy nhất một thuộc tính: F = {X→Z, XY→W, XY →P, XY→Z, XY →W, XY → Q, XZ → R}. B2. Loại bỏ các phụ thuộc dư thừa: xét lần lượt từng phụ thuộc hàm + Xét X→Z. Tính X+ trên F-{X→Z} Có X+ =X ko chứa Z. + Xét XY →W (vì trong tập phụ thuộc hàm F có 2 phụ thuộc hàm này nên loại đi) KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  9. 129 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU  F={X→Z, XY→W, XY →P, XY→Z, XY → Q, XZ → R} + Xét XY→Z vì (XY)+=XYZWPQ (Tính (XY)+ trên F-{ XY→Z}) Ta thấy Z ⊂ (XY)+ vì vậy loại XY→Z  F: = {X→Z, XY →W, XY →P, XY → Q, XZ → R} B3. Loại bỏ các thuộc tính vế trái dư thừa: xét tất cả các phụ thuộc hàm mà VT có từ 2 thuộc tính trở lên: + Xét XY→W: X→W có X+=XZR không chứa Y nên Y ko dư thừa Y→W có Y+=Y không chứa X nên X ko dư thừa Tương tự xét: XZ → R Có X+=XZR chứa Z nên Z dư thừa. Ta có phủ tối thiểu: G: = {X→Z, XY →W, XY →P, XY → Q, X → R}. 3.1.6. Khóa  Thuật toán tìm tất cả các khóa  Tìm tập thuộc tính nguồn (TN): Chứa tất cả các thuộc tính xuất hiện ở vế trái (VT) và không xuất hiện ở vế phải (VP) của các phụ thuộc hàm và những thuộc tính không xuất hiện ở VT lẫn VP của các phụ thuộc hàm.  Tập thuộc tính trung gian (TG): Chứa tất cả những thuộc tính xuất hiện ở cả VT lẫn VP của các phụ thuộc hàm.  Thuật toán:  B1: Tạo tập TN và TG  B2: Nếu TG =  thì lược đồ quan hệ chỉ có một khóa K = TN  Kết thúc, KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  10. 130 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Ngược lại, chuyển sang B3  B3: Tìm tất cả các tập con Xi của tập trung gian TG  B4: Tìm tất cả các siêu khoá Si bằng cách với  Xi : Nếu (TN  Xi )+ = Tập thuộc tính của R Thì Si = TN  Xi  B5: Tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu Si, Sj  S, nếu Si  Sj thì Loại Sj ra khỏi tập siêu khoá S; Si còn lại chính là tập khóa cần tìm. Ví dụ: Cho lược đồ quan hệ R(C,S,Z) và tập phụ thuộc hàm như sau: F = {CS → Z, Z → C} Tìm tất cả các khóa của R? Ta có: TN={S}, TG={C,Z} Xi (Xi TN) (Xi TN)+ Siêu khóa Khóa  S S C CS CSZ CS CS Z SZ CSZ SZ SZ CZ CSZ CSZ CSZ 3.2. Phép tách - kết nối 3.2.1 Khái niệm Phép tách một lược đồ quan hệ R = {𝐴1 … … , 𝐴𝑛 } là việc thay thế lược đồ quan hệ R bằng các cặp lược đồ {𝑅1 ……,𝑅𝑘 } trong đó 𝑅𝑖 ⊆ R, i = l, …., k và R = 𝑅1 ∪ 𝑅2 ∪…..∪ 𝑅𝑘 . KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  11. 131 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Ở đây không đòi hỏi các lược đồ 𝑅𝑖 phải là phân biệt. Mục tiêu của phép tách chủ yếu là loại bỏ các dị thường dữ liệu. 3.2.2. Phép tách-kết nối tự nhiên Cho lược đồ quan hệ người cung cấp: S(SNAME, ADD, PRO, PRICE) và giả sử có các phụ thuộc hàm : SNAME → ADD SNAME → PRO, SNAME → PRICE Lược đồ S có thể thay thế bằng hai lược đồ khác là S1(SNAME, ADD) và S2 (SNAME, PRO, PRICE) Như vậy rõ ràng ở S1 mỗi nhà cung cấp chỉ cần một lần lưu địa chỉ tương ứng của họ chứ không phải lặp đi lặp lại như ở lược đồ S. Vấn đề đặt ra là liệu một cơ sở dữ liệu r thỏa mãn trên S, khi tách ra S1 và S2 có phù hợp không? Hai hình chiếu r[𝑆1 ] và r[𝑆2 ] có còn phù hợp k? Hai hình chiếu r[𝑆1 ] và có còn giữ được cùng thông tin với r? Nói cách khác, nếu kết nối 2 hình chiếu r[𝑆1 ] và r[𝑆2 ] thành 1 quan hệ mới, ví dụ s = r[𝑆1 ] * r[𝑆2 ] liệu r # s hay r=s? để nghiên cứu các điều kiện cho kết quả phép kết nối tự nhiên nêu trên là duy nhất và bằng quan hệ ban đầu, cần thiết phải nghiên cứu 3.2.3 Phép tách - kết nối không mất mát thông tin. 3.2.3 Phép tách - kết nối không mất mát thông tin. a. Kết nối không mất thông tin Nếu R là một lược đồ quan hệ được tách thành các lược đồ con 𝑅1 ,𝑅2 …𝑅𝑘 và D là tập các phụ thuộc dữ liệu, nói rằng phép tách là tách - kết nối không mất mát thông tin (lossless Join decomposition) đối với D nếu mối quan hệ r trên R thỏa D: r = Π𝑅1 (𝑟) ∗ Π𝑅2 (𝑟) ∗ … .∗ Π𝑅𝑘 (𝑟) tức là r được tạo nên từ phép nối tự nhiên của các hình chiếu của nó trên các 𝑅𝑖 , i= 1…,k. Sau đây xem xét một số tính chất của kết nối không mất mát thông tin. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  12. 132 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Tập các lược đồ 𝜌 = (R1, …., Rk) được thay thế cho lược đồ R. Gọi m𝜌 là ánh xạ xác định nhờ m𝜌(𝑟) = Π𝑅𝑖 (𝑟) có nghĩa là m𝜌(𝑟) là kết nói của phép chiếu của r trên các lược đồ con trong 𝜌. Điều kiện để kết nói không mất mát thông tin đối với D được biểu diễn như sau: Với mọi r thỏa D, r= m𝜌(𝑟) Định lý: Gọi R là lược đồ quan hệ 𝜌 = (R1, …., R2) là phép tách của R, r là quan hệ trên R và ri = Π𝑅𝑖 (𝑟) thì: a. r⊆ m𝜌(𝑟) b. Nếu s= m𝜌(𝑟) thì Π𝑅𝑖 (𝑟) = 𝑟𝑖 c. m𝜌(m𝜌(𝑟)) = m𝜌(𝑟) b. Kiểm tra phép kết nối không làm mất mát thông tin Liệu một phép tách có phép kết nối không mất mát thông tin hay không đối với tập các phụ thuộc hàm được kiểm tra qua thuật toán sau đây: Thuật toán: Kiểm tra kết nối không mất mát thông tin Input : Lược đồ quan hệ R, tập các phụ thuộc hàm F và phép tách. Output : Kết luận phép tách có phải là không mất mát thông tin ? Phương pháp : Thiết lập một bảng với n cột và k hàng, cột thứ j ứng với thuộc tính Aj, hàng thứ i ứng với lược đồ Ri. Tại hàng j và cột j điền ký hiêu aj nếu Aj ∈Ri, nếu không điền ký hiệu bij. Bây giờ xem xét đến các phụ thuộc hàm từ F áp dụng cho bảng vừa thiết lập được. Giả sử xem xét (X→Y) ∈F. Xét các hàng nếu có giá trị bằng nhau trên thuộc tính X thì làm bằng các giá trị của chúng trên Y. Chú ý khi làm bằng giá trị trên Y, nếu một trong hai giá trị là aj thì ưu tiên làm bằng ký hiệu là aj. Ngoài ra làm bằng chúng bằng một trong các ký hiệu bij. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  13. 133 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Tiếp tục áp dụng thuật toán cho các phụ thuộc hàm, kể cả các phụ thuộc hàm đã áp dụng cho tới khi không còn áp dụng được nữa. Xem xét lại bảng kết quả: Nếu xuất hiện một hàng gồm các ký hiệu a1…an thì phép kết nối không làm mất thông tin. Trường hợp ngược lại là kết nối mất mát thông tin (lossy join). Ví dụ: Cho R(U) , U = {A, B, C, D}. F = {A  C, B C, CD  B, CD} Phép tách  = {R1(AB), R2(BD), R3(ABC), R4(BCD)} Kiểm tra phép tách  có mất mát thông tin? Giải: Lập một bảng gồm: - 4 cột (A, B, C, D) - 4 hàng (R1, R2, R3, R4) KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  14. 134 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Áp dụng phụ thuộc hàm : A  C Áp dụng phụ thuộc hàm: B C KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  15. 135 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Áp dụng phụ thuộc hàm: CD Kết luận: Dòng (hàng) thứ 3 xuất hiện toàn giá trị a (a1,a2,a3,a4) nên phép tách không bị mất mát thông tin. Định lý Nếu 𝜌= (R1, R2) là một phép tách của R và F là tập hợp phụ thuộc hàm thì 𝜌 là phép tách không mất mát thông tin đối với F khi và chỉ khi : R1∩ R2 -→ R1- R2 hoặc R1∩ R2 -→ R2 – R1 Chú ý rằng các phụ thuộc hàm nêu trên không nhất thiết phải thuộc tập F ban đầu nhưng là đủ để thuộc F+. 3.3. Chuẩn hóa lược đồ quan hệ 3.3.1. Các dạng chuẩn 3.3.1.1. Dạng chuẩn thứ nhất (1NF – First Normal Form) Một lược đồ quan hệ R được gọi là ở dạng chuẩn một nếu và chỉ nếu toàn bộ các miền có mặt trong R đều chỉ chứa các giá trị nguyên tố. Từ định nghĩa này cho ta thấy rằng bất kỳ quan hệ chuẩn hóa nào cũng ở dạng 1NF và tất nhiên điều đó đúng. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  16. 136 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Ví dụ: SV (MSSV,Hoten, Ngsinh, ngoaingu) Quan hệ SV chưa ở dạng chuẩn 1 vì có thuộc tính ngoại ngữ là đa trị. 3.3.1.2. Dạng chuẩn thứ 2 (2NF) Lược đồ quan hệ R ở dạng chuẩn thứ hai nếu nó ở dạng 1NF và nếu mỗi thuộc tính không khóa của R là phụ thuộc hàm đầy đủ vào khóa chính. Ví dụ: Cho quan hệ R (A, B, C, D, E) F= {AB CD, CE}  Ở dạng chuẩn 2 3.3.1.3. Dạng chuẩn thứ 3 (3NF) Cho lược đồ quan hệ R(U), X là tập con các thuộc tính X⊆ U, A là một thuộc tính thuộc U. A được gọi là phụ thuộc bắc cầu vào X trên R nếu tồn tại một tập con Y của R sao cho X→Y, Y→A nhưng Y ↛ X (không xác định hàm) với A ∉ XY. Ví dụ 1: Cho lược đồ quan hệ R(SAIP) với các phụ thuộc hàm SI→P và S→A. R là không ở dạng 3NF, thậm chí không ở dạng 2NF. Giả sử X= SI, Y= S, A là thuộc tính không khóa vì chỉ có 1 khóa là SI. Vì X→Y và Y→A nhưng lại có Y→X tức là S→SI là không thỏa. Chú ý rằng trong trường hợp này X→Y và Y→A không chỉ thỏa trên R mà là những phụ thuộc đã cho. Điều đó là đủ để nói rằng X→Y, Y→A suy ra từ tập các phụ thuộc hàm. Như vậy A là phụ thuộc bắc cầu vào khóa chính SI. Ví dụ 2: Cho phụ lược đồ quan hệ R(CSZ) với các phụ thuộc hàm CS→Z, Z→C. Trong lược đồ này mọi thuộc tính đều là thuộc tính khóa. Do vậy R là ở dạng 3NF. Ví dụ 3: Cho R (A, B, C, D, E, F) F= {AB CD, ABE, E F} KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  17. 137 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU  Quan hệ R không ở dạng chuẩn 3 Vì thuộc tính F phụ thuộc bắc cầu vào khóa AB Định nghĩa : Lược đồ quan hệ R là ở dạng chuẩn thứ ba (3NF) nếu nó là 2NF và mỗi thuộc tính không khóa của R là không phụ thuộc hàm bắc cầu vào khóa chính. 3.3.1.4. Dạng chuẩn Boye- Codd (BCNF) Lược đồ quan hệ R với tập các phụ thuộc hàm được gọi là ở dạng chuẩn BCNF nếu X→A thỏa trên R, A∈X thì X là một khóa của R. Ví dụ 1: Trong ví dụ R(CSZ) nêu trên, rõ ràng R không ở BCNF mà là ở 3NF vì rằng Z→C nhưng không phải là khóa của R. Ví dụ 2: cho R (A1,A2,A3,A4,A5) Với các phụ thuộc hàm: A1,A2 → A3,A4,A5 A4 → A2  R vi phạm dạng chuẩn BCNF Vì có thuộc tính khóa (A2) phụ thuộc hàm vào thuộc tính không khóa (A4). Từ ví dụ này thấy rằng một lược đồ quan hệ có thể có 3NF nhưng không phải BCNF. Do đó mỗi lược đồ quan hệ ở BCNF là 3NF. Để khẳng định điều đó có định lý sau đây. Định lý : Nếu một lược đồ quan hệ R với tập phụ thuộc hàm F là ở BCNF thì nó là ở 3NF. Chứng minh: KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  18. 138 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Giả sử rằng lược đồ quan hệ R là ở dạng BCNF nhưng không ở dạng 3NF. Như vậy sẽ tồn tại một phụ thuộc hàm bắc cầu hoặc phụ thuộc hàm thành phần X→ Y→A trong đó X là khóa của R, A ∉X hoặc A ∉Y. Và Y→X ∉ F+. Do vậy Y không phải là một khóa của R. Nhưng A∉ Y, do đó Y→A là một phụ thuộc hàm cho nên vi phạm điều kiện BCNF (tức là Y phải là khóa). 3.3.2. Chuẩn hóa qua phép tách không làm mất mát thông tin a. Phép tách lược đồ quan hệ thành BCNF Định lý : a. Giả sử R là một lược đồ quan hệ với tập phụ thuộc hàm F. Gọi 𝛒 =(R1, ….., Rk) là một phép tách không mất mát thông tin của R đối với F. Gọi Fi là hình chiếu của F trên Ri, i=1…k, tức là tập của (X→Y) ∈ F + sao cho X⊆ Ri và Y⊆ Ri. Gọi 𝛅 =(S1,……,Sm) là phép tách không mất mát thông tin của Ri đối với Fi . Khi đó phép tách của R thành (R1,….., Ri-1, S1….. ,Sm, Ri+1….., Rk) đối với F là không mất mát thông tin. b. Giả sử R, F và 𝝆 như ở mục (a). Gọi t= (R1,….., Rk, Rk+1, ……, Rn) là một phép tách của R thành tập các lược đồ bao gồm cả 𝛒 thì t cũng là phép tách không làm mất mát thông tin đối với F. Thuật toán: Tách một lược đồ quan hệ thành BCNF Input : Lược đồ quan hệ R và tập phụ thuộc hàm F Output : Phép tách của R không làm mất mát thông tin sao cho mỗi lược đồ quan hệ trong phép tách đều ở dạng BCNF đối với phép chiếu của F trên lược đồ đó. Phương pháp: KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  19. 139 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Cấu trúc phép tạch 𝝆 trên R theo phương pháp lặp liên tiếp. Tại mỗi bước phép tách 𝝆 là đảm bảo không mất mát thông tin đối với F. Bước đầu: 𝝆 chỉ bao gồm R Các bước tiếp theo : Nếu S là một lược đồ thuôc 𝝆 , S chưa ở dạng BCNF, chọn X→A là phụ thuộc hàm thỏa trên S, trong đó X không chứa khóa của S, A∉ X. Rõ ràng cần phải có một số thuộc tính khác của S vừa không phải A, vừa không thuộc X hoặc nếu không thuộc X thì phải chứa một khóa của S. Thay thế S trong 𝝆 bởi S1và S2 với S1=XA, S2= S - A Theo định lý, phép tách S thành S1 và S2 là không mất mát thông tin đối với tập phụ thuộc hàm trên S vì rằng S1 ∩ S2 = X, X→S1 –S2 = A. Theo bổ đề phần (a) được thay S bằng S1 và S2 là không mất mát thông tin. Mỗi lược đồ đều có số thuộc tính ít hơn S. Quá trình tiếp tụ cho tới khi tất cả các lược đồ đều ở BCNF. Chú ý rằng tại mọi thời điểm 𝝆 luôn đảm bảo không mất mát thông tin, vì rằng 𝝆 ban đầu là R, mà bước thay đổi 𝝆 đều bảo toàn tính chất đó. Ví dụ: Cho lược đồ R(CTHRSG), trong đó C- giáo trình, T- Thầy giáo, H- giờ, R- Phòng học, S- Sinh viên, G- Lớp. Tập các phụ thuộc hàm: C→T : Mỗi giáo trình có một thầy dạy HR→C : Chỉ một môn học (giáo trình) ở một phòng tại một thời điểm HT→R : Tại mỗi thời điểm mỗi thầy chỉ có thể dạy ở một phòng CS→G : Mỗi sin viên chỉ ở một lớp theo học mỗi giáo trình HS→R : Mỗi sinh viên chỉ có thể ở một phòng tại mỗi thời điểm Giải : Khóa của R là HS Tách lược đồ R thành lược đồ BCNF: KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
  20. 140 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Xét CS→G cho R. Vi phạm điều kiện BCNF vì CS không chưa khóa. Do vậy, dùng thuật toán 3.3 để tách R thành R1(CSG) và R2(CTHRS). Bước tiếp theo cần tính F+ và chiếu xuống R1 và R2, sau đó kiểm tra các lược đồ đã ở BCNF hay chưa. Có thể biểu diễn quá trình tách qua sơ đồ sau : C→ T R (CTHRSG) HR→ C CS→G Khóa = HS TH→ R HS→R C→T R1 (CSG) R2 (CTHRS) TH→R HHS→C Khóa = CS Khóa = SH HS→R R→C CSG R21 (CT) R22 (CHRS) CH→R Khóa = C Khóa = HS HR→C C→T C→T R221 (CHR) R222 (CHS) Khóa = CH, HR KhóaCH→R, = SH HR→C CH→R, HR→C HS→C R→C b. Phép tách lược đồ quan hệ thành 3NF Tương tự như phép tách không mất mát thông tin một lược đồ quan hệ thành BCNF, ở đây sẽ đưa ra thuật toán tách thành 3NF. Thuật toán: Tách một lược đồ thành 3NF Input : Lược đồ quan hệ R, tập các phụ thuộc hàm F, để không làm mất tín tổng quát, ta giả sử rằng nó là phủ tối thiểu. Output : Phép tách không làm mất mát thông tin trên R bảo toàn các phụ thuộc hàm sao cho mỗi lược đồ con đều ở 3NF. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường