Bài tập chuẩn hóa lược đồ quan hệ

Nội dung Text: Bài tập về chuẩn hóa

1. NHẬP MÔN CƠ SỞ DỮ LIỆU QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm 5. BµI TËP VÒ chuẨN HOÁ MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC Phân biệt các dạng chuẩn của quan hệ.  Xác định một lược đồ ở dạng chuẩn nào.  Vận dụng giải các bài tập về chuẩn hóa quan hệ [Đ ưa các l ược đ ồ  quan hệ [quan hệ] từ dạng chuẩn thấp lên dạng chuẩn cao hơn]. Kiểm tra được một phép tách lược đồ aqua nhệ c ó mất thông tin  không. A/ NHẮC LẠI LÝ THUYẾT I. CÁC ĐỊNH NGHĨA, TÍNH CHẤT 1. Dạng chuẩn 1 [1NF - first normal form] Một lược đồ quan hệ α= [U, F] được gọi là ở dạng chuẩn một [1NF] nếu và ch ỉ nếu t ất c ả miền giá trị của các thuộc tính của R đều nguyên t ố [không thể phân chia đ ược]. Chú ý: Tính không thể phân chia được chỉ có tính chất tương đối. Định nghĩa này cho thấy ngay rằng bất kỳ quan hệ chuẩn hóa nào cũng ở 1NF. 2. Dạng chuẩn 2 [ 2NF- Second normal form] Trước khi nghiên cứu dạng chuẩn thứ 2 , ta xét Ví d ụ sau đây: Xét CSDL gồm 2 lược đồ quan hệ THI[MONTHI,GIAOVIEN] và SINHVIEN[MONTHI, MSSV, TEN, TUOI, DCHI, DIEM] phản ánh thông tin về k ết q ủa thi c ủa một đơn vị nào đó. Trong quan hệ THI thì MONTHI là khóa và trong quan hệ SINHVIEN thì MOMTHI và MSSV là khóa. ở quan hệ thứ hai dễ nhận thấy rằng MONTHI, MSSV,DIEM xác định kết qu thi c ủa sinh viên còn MSSV,TEN, TUOI, DCHI xác định đối tượng dự thi Xét các hiện hành của 2 lược đồ quan hệ THI và SINHVIEN nh ư sau: THI MONTHI GIAOVIEN ́ Thầy Công Toan Lý Thầy Hứa ́ Thầy Giao Hoa SINHVIEN MONTHI MSSV TEN TUOI DCHI DIEM ́ Toan 11 Lan 20 HN 8.0 ́ Toan 12 Hue 21 HY 7.5 ́ Hoa 11 Lan 20 HN 7.0 ́ Hoa 12 Hue 21 HY 6.0 Lý 11 Lan 20 HN 5.0 Lý 13 An 22 BN 4.0 Trang 1
2. NHẬP MÔN CƠ SỞ DỮ LIỆU QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm 3. Dạng chuẩn 3 [ 3NF- Second normal form] Định nghĩa: Cho lược đồ quan hệ α =[U, F], lược đồ α được gọi là ở dạng chuẩn 3, kí hiệu là 3NF, nếu như lược đồ ở dạng chuẩn 1NF và các thuộc tính không khoá c ủa α là không phụ thuộc hàm bắc cầu vào khoá chính. 4. Dạng chuẩn Boyce Codd [ BCNF- Boyce Codd normal form] Định nghĩa: Cho lược đồ quan hệ α =[U, F], lược đồ α được gọi là ở dạng chuẩn Boyce Codd, kí hiệu là BCNF, nếu như lược đồ ở dạng chuẩn 1NF và nếu XY ∈F+ [ Y ⊄ X ] thì X phải là siêu khoá của lược đồ. 5. Tách lược đồ quan hệ Định nghĩa: Phép tách lược đồ quan hệ α = [U, F] là phép thay thế nó bằng m ột t ập các lược đồ con αi = [Ui, Fi], i=1,..,k với điều kiện Ui ≠ φ ∀ i=1,..., k , ∪ Ui= U, Fi= F/Ui, Fi là hình chiếu của F lên tập thuộc tính Ui Phép tách đó được ký hiệu là σ ={U1, U2,.., Uk} Kí hiệu α = [U, F], σ ={U1, U2,.., Uk} là một phép tách khi đó R là m ột quan hệ trên U, kí hi ệu mδ[R]=R[U1] * R[U2] * ... * R[Uk] Định nghĩa: phép tách kết nối không mất thông tin Cho lược đồ quan hệ α = [U, F] và phép tách δ ={U1, U2,.., Uk} đối với lược đồ đó. phép tách δ được gọi là phép tách kết nối không mất thông tin nếu m ọi quan hệ R trên U thì ta có mδ[R]= R, ngược lại nếu mδ[R] ≠ R thì ta nói phép tách δ là phép tách mất thông tin. 6. Thuật toán kiểm tra phép tách kết nối có mất thông tin hay không? Dữ liệu vao: ̀ - Tập thuộc tính U - Tập phụ thuộc ham F ̀ - Phep tach δ ={U1, U2,.., Uk} ́ ́ Ra: Xac đinh liệu phep tach δ có mất thông tin hay không? ́ ̣ ́ ́ Phương phap: ́ Giả sử U={A1, A2,.., An}, ta xây dựng một bảng g ồm k dòng n c ột [ n=| U | , k=| δ |], cột thứ i của bảng ứng với thuộc tính Ai, hàng thứ j của b ảng ứng v ới l ược đ ồ con αi = [Ui, Fi], tại hàng i và cột j ta điền kí hiệu aj [ ta g ọi kí hi ệu aj là tín hi ệu chính] n ếu thu ộc tính aj ∈ Ui, nếu không ta điền bịj [ ta gọi bij là tín hiệu phụ]. Bây giờ ta biến đổi bảng như sau: Với mỗi phụ thuộc hàm X Y ∈ F, nếu trong bng có hai hàng giống nhau trên t ập thuộc tính X thi ta cần làm chúng giống nhau trên t ập thuộc tính Y theo quy t ắc sau: Nếu một trong hai giá trị là tín hiệu phụ thì ta s ửa l ại tính h ịêu ph ụ thành tín hi ệu - chính tức là sửa bij thành aj Nếu cả hai là tín hịêu phụ thì ta sửa lại hai tín hi ệu đó b ằng m ột trong các kí hi ệu - bij , tức là sửa lại chỉ số cho giống nhau. Tiếp tục áp dụng các phụ thuộc hàm trong bảng [ k ể c các ph ụ thuộc hàm đã đ ược s ử dụng] cho tới khi không còn áp dụng được nữa. Quan sát trong bảng cuối cùng: nếu xuất hiện ít nhất m ột hàng g ồm toàn tín hi ệu chính [ hàng gồm toàn kí hiệu a] thì phép tách k ết nối là không m ất thông tin, tr ường h ợp ngược lại là kết nối mất thông tin. 7. Phương pháp chuẩn hóa dữ liệu Trang 2
3. NHẬP MÔN CƠ SỞ DỮ LIỆU QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm 7.1. Thuật toán tách lược đồ thành 3NF Input: Lược đồ quan hệ α =[U, F] Output: Các lược đồ ở dạng 3NF [U1, K1] , [ U2, K2] ,…., [Un, Kn] thỏa mãn: a]  Quan hệ R trên U thì R[U1]*R[U2]* … * R[Un]=R b] K1, K2, …, Kn là các khoá của lược đồ con tưng ứng Phương pháp: 1. Tìm một khóa K của lược đồ α 2. Tìm một phủ G tối thiểu của F G={K1A1, K2A2, …, KpAp} 3. Ghép các phụ thuộc hàm có cùng vế trái trong G để thu đ ược ph ủ G={K1X1, K2X2, …, KnXn} 4. Phép tách δ ={K1X1, K2X2, …, KnXn} nếu khoá K không có mặt trong thành phần nào của δ thì thêm thành phần K vào δ. 5. Return δ 7.2. Tách không mất thông tin thành các lược đồ ở dạng BCNF Cho lược đồ α = [U, F], và phép tách δ ={U1, U2,.., Uk}, phép tách một lược đồ thành một tập các lược đồ ở dạng BCNF là phép tách thỏa mãn: Phép tách δ là phép tách kết nối không mất thông tin - Tất cả các lược đồ con αi = [Ui, Fi] đều ở dạng BCNF - Phương pháp : Xuất phát từ một phụ thuộc hàm X A nào đó của F, phụ thuộc hàm X A này vi phạm điều kiện BCNF, ta xây dựng phép tách δ ={U1, U2}, tương ứng với lược đồ α1 và α2 sao cho: Phép tách đó là phép tách kết nối không mất thông tin - Phụ thuộc hàm X A là phụ thuộc hàm của lược đồ α1 và nó thỏa mãn điều kiện - cua BCNF trong lược đồ này Nếu như các lược đồ α1 và α2 vẫn chưa ở dạng BCNF thì tiếp t ục quá trình đó, thì - các điều vi phạm BCNF đều bị loại bỏ, cuối cùng ta thu đ ược m ột t ập các l ược đ ồ con đ ều ở dạng BCNF và quá trình tách luôn luôn đm bo phép tách kết nối không m ất thông tin. Cơ sở của thuật toán trên là do gi thiết l ược đồ α = [U, F] chưa ở dạng BCNF do đó t ồn tại phụ thuộc hàm X A, A X, X không phải là siêu khoá U1=XA, U2 =U \ A Nhận xét X=U1 ∩ U2, U1 \ U2 =A, đã có X A do đó U1 ∩ U2  U1 \ U2 theo định lý ở phần trên thì phép tách δ ={U1 , U2} là phép tách có kết nối không mất thông tin. Vì U 1 =XA và phụ thuộc hàm X A là duy nhất trên lược đồ α1 = [U1, F1] nên X là siêu khoá. Nếu α1 , α2 chưa ở dạng BCNF thì ta áp dụng quá trình tách t ương t ự. Cuối cùng ta thu được một tập các lược đồ ở dạng BCNF và quá trình tách là không m ất thông tin. Ví dụ: Cho lược đồ α = [U, F] với U=CRHTSG [ C : Course, T : Teacher, H Hour, R : Room, S : Student, G : Group] Trang 3
4. NHẬP MÔN CƠ SỞ DỮ LIỆU QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm F ={CT , HR  C, CH  R, CS G, HS R} Nhận xét - Lược đồ này có duy nhất một khoá là HS - Lược đồ này chưa ở dạng BCNF - Ta thấy trong lược đồ α = [U, F] có phụ thuộc hàm CS  G vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U1 =CGS, U2 =CTHRS - Ta thấy trong lược đồ α2 = [U2, F2] có phụ thuộc hàm C T vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U3 =CT, U4 =CHRS - Ta thấy trong lược đồ α4 = [U4, F4] có phụ thuộc hàm CH  R vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U5 =CHR, U6 =CHS α = [U, F] U1 =CSG U2 =CTHRS F1={CSG} F2={CT, HRC, CHR, HSR} K=CS K=HS U3 =CT U4 =CHSR F3={CT} F4={ HRC, CHR, HSR} K=C K=HS U5 =CHR U6 =CHS F5={ HRC, HRC} F6={ HSC} K=HR, K=HC K=HS Như vậy phép tách cuối cùng là δ={ CSG, CT , CHR , CHS } III. MỘT SỐ LƯU Ý Tầm quan trọng của việc chuẩn hóa dữ liệu.  Phân biệt các dạng chuẩn, phương pháp tách quan hệ ở dạng chuẩn th ấp lên d ạng  chuẩn cao hơn.  Thuật toán kiểm tra phép tách có mất thông tin không? B/ BÀI TẬP MẪU Bài số 1: Kiểm tra phép tách có mất thông tin hay không? Cho lược đồ quan hệ α= [U, F] với U={A1, A2, A3, A4, A5} F={ A1  A2 A3 , A2 A4 A5 , A2 A3} δ={ A1 A2 A4, A2 A3, A1 A4 A5} Hỏi rằng phép tách δ trên có kết nối không mất thông tin không? Hướng dẫn: Trang 4
5. NHẬP MÔN CƠ SỞ DỮ LIỆU QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm Áp dụng thuật toán kiểm tra phép tách có mất thông tin không, ta ti ến hành t ừng b ước. Giải: Xây dựng bảng gồm 3 dòng 5 cột - Điền các tín hiệu vào bảng A1 A2 A3 A4 A5 U1 a2 b13 a4 b15 a1 U2 b12 a2 a3 b25 b24 U3 a1 b32 b33 a4 a5 - Biến đổi bảng trên dựa vào tập phụ thuộc hàm F A1  A2 A3 ta biến đổi bảng + Sử dụng phụ thuộc hàm A1 A2 A3 A4 A5 U1 a1 a2 a4 b15 b13 U2 b12 a2 a3 b24 b25 U3 a1 a4 a5 a2 b13 + Sử dụng phụ thuộc hàm A2 A4 A5 A1 A2 A3 A4 A5 U1 a1 a2 b13 a4 a5 U2 b12 a2 a3 b24 b25 U3 a1 a2 b13 b4 a5 + Sử dụng phụ thuộc hàm A2 A3 A1 A2 A3 A4 A5 U1 a1 a2 a4 a5 a3 U2 B12 a2 a3 b24 b25 U3 a1 a2 a4 a5 a3 δ là phép Trong bảng này có hàng cuối cùng gồm toàn các tín hiệu chính, do v ậy phép tách tách kết nối không mất thông tin. C/ BÀI TẬP TỰ GIẢI Bài tập 1: Dùng kỹ thuật bảng kiểm tra phép tách sau có mất thông tin không Trang 5
6. NHẬP MÔN CƠ SỞ DỮ LIỆU QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm α=[U, F] với U=ABCD, F={A→B, AC→D}, δ={AB, ACD} a] b] α=[U, F] với U=ABCDE, F={A→C, B→C, C→D, DE→C, CE→A}, δ={AD, AB, BE, CDE} c] Xác định và giải thích dạng chuẩn cao nhất của l ược đồ quan hệ α=[U, F] với U=ABCD, F={A→C, D→B, C→ABD} Bài tập 2: Cho lược đồ quan hệ α=[U, F] với U=ABCDEGH F={CD→H, E→B, D→G, BH→E, CH→DG, C→A } Hỏi rằng phép tách δ=[ABCDE, BCH, CDEGH] có kết nối mất thông tin không. Bài tập 3: Cho lược đồ quan hệ α=[U, F] với U=ABCD, F={D→B, C→A, B→ACD } Xác định dạng chuẩn cao nhất của lược đồ quan hệ trên Bài tập 4: Cho lược đồ quan hệ α =[U, F] với U=ABCD, F={CD→B, A→C, B→ACD } Xác định dạng chuẩn cao nhất của lược đồ quan hệ trên Bài tập 5: Cho α=[u, F] với U=ABCDE và F={A→C, B→C, A→D, DE→C, CE→A} kiểm tra tính kết nối không mất thông tin đối với phép tách δ={AD, AB, BE, CDE, AE } Bài tập 6: Cho α=[u, F] với U=ABCDEF và F={AB→C, C→B, ABD→E, F→A} kiểm tra tính kết nối không mất thông tin đối với phép tách δ={BC, AC, ABDE, ABDF } Bài tập 7: Cho α=[u, F] với U=ABCDEG F={D→G, C→A, CD→E, A→B} kiểm tra tính kết nối không mất thông tin đối với phép tách δ={DG, AC, SCE, AB } Bài tập 8: Cho α=[u, F] với U=ABCDE và F={A→C, B→C, C→D, DE→C, CE→A} Trang 6
7. NHẬP MÔN CƠ SỞ DỮ LIỆU QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm kiểm tra tính kết nối không mất thông tin đối với phép tách δ={AC, CD, BE, BC, AE} Bài tập 9: Cho [=[U, F] với U=XYZW và tập F={Y→W, W→Y, XY→Z} Dạng chuẩn cao nhất của lược đồ là gì? Bài tập 10: Cho [=[U, F] với U=ABCDEG và tập phụ thuộc hàm F={ AB→C, AC→E, EG→D, AB→G } δ={DEG, ABDEG } Phép tách trên có mất thông tin không? Hãy chứng minh mọi quan hệ chỉ có 2 thuộc tính đề ở dạng chuẩn BCNF? Bài tập 11: Xét quan hệ R[ABCDE] và tập phụ thuộc hàm F={ AB→CE, E→AB, C→D } Hãy tìm dạng chuẩn cao nhất của lược đồ? Bài tập 12: Xét quan hệ R[ABCDEG] và tập phụ thuộc hàm F={ A→B, C→DG , AC→E, D→G } - Hãy tìm khoá của lược đồ - Hãy tìm dạng chuẩn cao nhất của lược đồ Bài tập 13: Xét quan hệ R[ABCD] và tập phụ thuộc hàm F={ AB→D, AC→BD, B→C } Hãy tìm dạng chuẩn cao nhất của lược đồ Bài tập 14: Cho α=[u, F] với U=ABCDEF F={AB→C, C→B, ABD→E, F→A} Lược đồ có ở dạng BCNF không Trang 7