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

Chia sẻ: Doan Minh Tien | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

283
lượt xem 80
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo về bài giảng Cơ sở dữ liệu- CHƯƠNG 4 THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 HN
Quá 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 HN
Phụ 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 HN
Hệ qui tắc suy diễn Amstrong A1. Phản xạ (Reflexivity). Nếu Y ⊆ X thì X→Y A2. Tăng trưởng (Augmentation). Nếu X→Y thì mọi Z⊆U, XZ→YZ A3. Bắc cầu (Transitivity). Nếu X→Y và Y→Z thì X→Z Hồ Cẩm Hà- ĐHSP HN
Hệ tiên đề Armstrong là đúng và đủ Hồ Cẩm Hà- ĐHSP HN
Các qui tắc suy diễn bổ sung Quy tắc hợp (the union rule) Nếu {X→Y, X→Z} đúng thì X→YZ đúng Quy tắc giả bắc cầu (the pseudotransitivity rule) {X→Y, WY→Z} đúng thì WX→Z đúng Quy tắc tách (the decomposition rule) Nếu (X→Y) đúng và Z⊆Y thì X→Z đúng. Hồ Cẩm Hà- ĐHSP HN
Tập phụ thuộc hàm tối tiểu F 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úng có 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ểu Cho 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 F F1 = {A→B, B→C, C→A} F2 = {A→B, B→A, A→C, C→A} Hồ Cẩm Hà- ĐHSP HN
Phé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 HN
Phé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 đồ con R1 = 〈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 Ui mρ(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 HN
Phé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 E Ví dụ U = ABCDE, U1 = AD, U2 = AB, U3 = BE,U a b b a b1 1 12 13 4 15 U4 = CDE, U5 = AE U a a b b b 2 1 2 23 24 25 Tậ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 a C→D, DE→C, CE→A. 4 41 42 3 4 5 U a b b b a 5 1 52 53 54 5 Hồ Cẩm Hà- ĐHSP HN
Tách kết nối không mất thông tin Tập các phụ thuộc hàm là: A→C, B→C, C→D, DE→C, CE→A. A B C D E A B C D E U1 a1 b12 b13 a4 b15 U1 a1 b12 b13 a4 b15 U2 a1 a2 b24 b25 b13 U2 a1 a2 b23 b24 b25 U3 b31 a2 b34 a5 b13 U3 b31 a2 b33 b34 a5 U4 b41 b42 a3 a4 a5 U4 b41 b42 a3 a4 a5 U5 a1 b52 b54 a5 b13 U5 a1 b52 b53 b54 a5 Hồ Cẩm Hà- ĐHSP HN
Tách kết nối không mất thông tin Tập các phụ thuộc hàm là: A→C, B→C, C→D, DE→C, CE→A. A B C D E A B C D E U1 a1 b12 b13 a4 b15 U1 a1 b12 b13 a4 b15 U2 a1 a2 b13 b24 b25 U2 a1 a2 b23 b25 a4 U3 b31 a2 b13 b34 a5 U3 a2 a5 a1 a3 a4 U4 b41 b42 a3 a4 a5 U4 b42 a3 a4 a5 a1 U5 a1 b52 b13 b54 a5 U5 a1 b52 a5 a3 a4 Hồ Cẩm Hà- ĐHSP HN
Phép tách các lược đồ Mặc dù là những tính chất quan trọng của phép tách lược đồ quan hệ nhưng một phép tách có thể thoả mãn tính chất này nhưng lại không thoả mãn tính chất kia. Chẳng hạn, phép tách lược đồ quan hệ 〈ABCD, {A→B, C→D}〉 thành hai lược đồ 〈AB, {A→B}〉 và 〈CD, {C→D}〉 là phép tách bảo toàn phụ thuộc nhưng không phải là phép tách với kết nối không thất thoát. Hồ Cẩm Hà- ĐHSP HN
phép tách các lược đồ Ta xét lược đồ CSZ với ba thuộc tính C (City), S (Street) và Z (Zip code) và tập phụ thuộc hàm F = {CS→Z, Z→C}. Từ phụ thuộc hàm Z→C hay CS∩CZ→CS−CZ suy ra rằng phép tách CSZ thành hai lược đồ CS và CZ có tính chất kết nối không mất thông tin nhưng không có tính chất bảo toàn phụ thuộc. Hồ Cẩm Hà- ĐHSP HN
1NF Hồ Cẩm Hà- ĐHSP HN