Cơ sở dữ liệu-chương 4

Tài liệu tham khảo về bài giảng Cơ sở dữ liệu- CHƯƠNG 4THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ...
Nội dung trích xuất từ tài liệu:
Cơ sở dữ liệu-chương 4 CHƯƠNG 4 THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ“Làm thế nào để có một cơ sở dữ liệu tốt?” Hồ Cẩm Hà- ĐHSP HNQuá trình thiết kế CSDL Thế giới thực Tập hợp các yêu cầu và phân tích Các yêu cầu CSDL Thiết kế khái niệm Lược đồ logic (trong một mô hình dữ liệu bậc cao) Không phụ thuộc DBMS Ánh xạ mô hình dữ liệu DBMS cụ thể Lược đồ khái niệm (trong mô hình dữ liệu của một DBMS cụ thể ) Thiết kế vật lý Lược đHồtrong Hà- ĐHSP HN ồ Cẩm (đối với cùng một DBMS cụ thể đó)Cần loại bỏ dư thừa dữ liệu Khi dư thừa dữ liệu dẫn đến những khó khăn khi cập nhật dữ liệu Hồ Cẩm Hà- ĐHSP HNPhụ thuộc hàm.Dạng dư thừa dữ liệu thường gặp Có X→Y trên R(U): ∀r(R) ∀ t1, t2 ∈ r, t1[X] = t2[X] ⇒ t1[Y]=t2[Y]. Hồ Cẩm Hà- ĐHSP HNHệ qui tắc suy diễn AmstrongA1. Phản xạ (Reflexivity). Nếu Y ⊆ X thì X→YA2. Tăng trưởng (Augmentation). Nếu X→Y thì mọi Z⊆U, XZ→YZA3. Bắc cầu (Transitivity). Nếu X→Y và Y→Z thì X→Z Hồ Cẩm Hà- ĐHSP HNHệ tiên đề Armstrong là đúng và đủ Hồ Cẩm Hà- ĐHSP HN Các qui tắc suy diễn bổ sungQuy tắc hợp (the union rule)Nếu {X→Y, X→Z} đúng thì X→YZ đúngQuy tắc giả bắc cầu (the pseudotransitivity rule){X→Y, WY→Z} đúng thì WX→Z đúngQuy tắc tách (the decomposition rule)Nếu (X→Y) đúng và Z⊆Y thì X→Z đúng. Hồ Cẩm Hà- ĐHSP HNTập phụ thuộc hàm tối tiểuF và G là tương đương nếu F+=G+, ký hiệu F~G.Có thể kiểm tra được F và G, tập nào phủ tập nào và chúngcó tương đương hay không (tính X+)Định lí 7.9:Cho tập phụ thuộc hàm F luôn tìm được phủ tối tiểu của F Hồ Cẩm Hà- ĐHSP HN Tập phụ thuộc hàm tối tiểu Tập PTH F là tối tiểu nếu:1. Vế phải của mỗi phụ thuộc trong F gồm đúng một thuộc tính.2. Không thể bỏ đi một phụ thuộc nào trong F mà vẫn thu được một tập phụ thuộc tương đương với nó.3. Không thể bỏ đi bất kỳ một thuộc tính nào ở vế trái của một phụ thuộc nào trong F mà vẫn thu được một tập phụ thuộc tương đương với nó. Hồ Cẩm Hà- ĐHSP HN Tập phụ thuộc hàm tối tiểuCho F = {A→B, B→A, A→C, C→A, B→C}.Có thể tìm được hai tập phụ thuộc tối tiểu tương đương với FF1 = {A→B, B→C, C→A}F2 = {A→B, B→A, A→C, C→A} Hồ Cẩm Hà- ĐHSP HNPhép tách các lược đồ quan hệ Việc tách một lược đồ quan hệ trước hết là thay thế tập U các thuộc tính bằng những tập con U1, U2,…, Uk của nó sao cho U = U1 ∪ U2 ∪…∪ Uk. Chú ý rằng ở đây, ta không đòi hỏi U1, U2,…, Uk phải rời nhau. Hồ Cẩm Hà- ĐHSP HNPhép tách các lược đồ quan hệKhi đó, việc thay thế lược đồ R = 〈U, F〉 bằng các lược đồconR1 = 〈U1, F1〉,R2 = 〈U2, F2〉,…,Rk = 〈Uk, Fk〉được gọi là một phép tách lược đồ quan hệ đã cho 〈U, F〉.ký hiệu là ρ = (R1, R2,…, Rk).Đôi khi, kí hiệu ρ = (U1, U2,…, Uk). Hồ Cẩm Hà- ĐHSP HN Phép tách các lược đồ quan hệ Ta sử dụng một số ký hiệu sau:Dấu hoa thị (*) ký hiệu phép kết nối tự nhiên trên giao của hai tập thuộc tính.ρ = (R1, R2,…, Rk) hay ρ = (U1, U2,…, Uk) là phép tách lược đồ quan hệ trên U thành các lược đồ con tương ứng với các tập con thuộc tính U1, U2,…, Uk.ri = là hình chiếu của quan hệ r lên tập con thuộc tính Uimρ(r) = r1 * r2 *… * rk là kết quả của phép kết nối tự nhiên của các hình chiếu của r lên các tập con thuộc tính trong phép tách ρ. Hồ Cẩm Hà- ĐHSP HNPhép tách các lược đồ quan hệ Phép tách U thành {U1, U2,…, Uk} được gọi là kết nối không thất thoát (hay ngắn gọn là LJ) nếu với mỗi quan hệ r của lược đồ này, ta đều có r = r1 * r2 *… * rk = mρ(r) Phép tách bảo toàn các phụ thuộc của F Hồ Cẩm Hà- ĐHSP HN Tách kết nối không mất thông tin Kiểm tra được tính kết nối không thất thoát của một phép tách (thuật toán 3.2) A B C D EVí dụU = ABCDE, U1 = AD, U2 = AB, U3 = BE,U a b b a b1 1 12 13 4 15U4 = CDE, U5 = AE U a a b b b 2 1 2 23 24 25Tập các phụ thuộc hàm là: A→C, B→C, U b a b b a 3 31 2 33 34 5 U b b a a aC→D, DE→C, CE→A. 4 41 42 3 4 5 ...