CHƯƠNG V: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU

Hợp lý, nghĩa là phải đủ, không dư thừa. 2. Tiện lợi khi truy nhập, nghĩa là thao tác tìm kiếm, cập nhật, bổ sung và loại bỏ các thông tin phải diễn ra một cách nhanh chóng, thuận tiện. Nội dung của chương này là giới thiệu một số công cụ thường dùng trong quá trình xây dựng CSDL.
Nội dung trích xuất từ tài liệu:
CHƯƠNG V: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU CHƯƠNG V: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU Cơ sở dữ liệu (CSDL) là nơi lưu trữ lâu dài các dữ liệu của hệ thống ở bộ nhớngoài. CSDL này phải được tổ chức tốt theo hai tiêu chí: 1. Hợp lý, nghĩa là phải đủ, không dư thừa. 2. Tiện lợi khi truy nhập, nghĩa là thao tác tìm kiếm, cập nhật, bổ sung và loại bỏ các thông tin phải diễn ra một cách nhanh chóng, thuận tiện. Nội dung của chương này là giới thiệu một số công cụ thường dùng trong quátrình xây dựng CSDL.I. PHỤ THUỘC HÀM Khái niệm về phụ thuộc hàm (trong một quân hệ) là một khái niệm có tầm quantrọng hết sức lớn đối với việc thiết kế các mô hình dữ liệu. Để biết được phụ thuộchàm là gì ta xét ví dụ sau: Ví dụ: SOXE LOAIXE XEMAY= CHUSH 92N95501 DREAMII NAM 92N95502 WAVE@ HOA 92N95504 DREAMII MY 92N95501 @ NAM Þ Bất hợp lý à đưa ra rang buộc nếu 2 bộ dữ liệu bằng nhau trên SOXE thìbằng nhau trên LOAIXE và bằng nhau CHUSH Þ Ràng buộc như vậy ta gọi là phụ thuộc hàm. Như vậy: Phụ thuộc hàm là một loại ràng buộc dữ liệu nhằm đảm bảo các bộ dữliệu nếu bằng nhau trên tập thuộc tính này thì bằng nhau trên tập thuộc tính khác.I.1.Một số định nghĩa Định nghĩa 1: Cho một quan hệ r định nghỉatên lược đồ quan hệ R. X,Y ⊆ R ta nói phụ thuộchàm X xác địnhu hàm Y hay Y thuộc hàm vào X, ký hiệu: X → Y đúng trên r nếu ởtrong r không tồn tại bất kỳ 2 bộ dữ liệu t1, t2 mà: + t1[X] = t2[X] + t1[Y] ≠ t2[Y] Nhận xét: · Nếu phụ thuộc hàm X xác định hàm Y đúng trên r thì ta nói r thỏa X → Y. · Cho quan hệ r (R), F là một tập các phụ thuộc hàm được định nghĩa như sau: F= {Χ → Υ / Χ, Υ ⊆ R} Ta nói r thỏa F ( hay đúng trên R) nếu r thỏa tất cả các phụ thuộc hàm trongF. · Cho lược đồ quan R, F là một tập phụ thuộc hàm trên R. Một quan hệ tương ứng với R chỉ được gọi là thể hiện của R nếu quan hệ đó thỏa F. Định nghĩa: Cho một quan hệ r định nghĩa trên lược đồ quan hệ R: X, Y Í R. Xét quan hệ r, giả sử thỏa thuộc hàm X®Y và nếu không tồn tại một tập con thật sự X’ của X sao cho r cũng thỏa phụ thuộc hàm X®Y thì ta nói Y phụ thuộc hàm đầy đủ vào X trong r. Người ta dùng ký hiệu FD (Functional Dependency) để chỉ phụ thuộc hàm và FFD (Functinoal Dependency) để chỉ phụ thuộc hàm đầy đủ. Định lý 2.1: Cho một quan hệ r định nghĩa trên lược đồ quan hệ R. X,Y R, ta có: - X ® Y là phụ thuộc hàm trên r khi và chỉ khi X là khóa của quan hệ r(XY). - X ® Y là phụ thuộc hàm đầy đủ trên r khi và chỉ khi X là khóa tối thiểu của quan hệ r(XY).II.2. Hệ tiên đề cho phụ thuộc hàm Hệ tiên đề Armstrong Gọi r(R) là lược đồ quan hệ với R={A1, A2,....,An} là tập các thuộc tính; giả sửX, Y, Z Í R, hệ tiên đề Armstrong bao gồm: A1: Tính phản xạ: Nếu Y Í X thì X ® Y A2: Tính tăng trưởng: Nếu Z Í R, X ®Y thì ZX® ZY, trong đó ZX = Z È X. A3: Tính bắc cầu: Nếu X®Y và Y® Z thì X ®Z. Ví dụ: Xét một số ví dụ áp dụng: Cho AB ® C, C®A. Chứng minh: BC®ABC Chứng minh: Theo giả thiết: C ® A suy ra BC ® AB (1) (Tính tăng trưởng) Mặt khác ta có: AB ® C (giả thiết) Suy ra: AB ® ABC (2) (tính tăng trưởng) Từ (1) và (2) suy ra B ® ABC (tính bắc cầu). a. Bổ đề 1 Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng trên quan hệ r và f: X ® Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Armstrong thì f đúng trên r. b. Bổ đề 2: A4: Tính hợp: Nếu X® Y và X ® Z thì X ®Y Z. A5: Tính tự bắc cầu: Nếu X→ Y và WY →Z thì XW→Z. Nếu X→Y và Z→Y thì X→Z. A6: Tính tách: c. Bao đóng của tập thuộc tính: Định nghĩa: Cho lược đồ quan hệ R, tập thuộc tính hàm F trên R . X ⊆ R, bao đóng của Xtheo F là một tập các thuộc tính được định như sau: A X+F ={A/A ∈ R, F |= X→A} Ví dụ: Cho R = (A, B, C, D ) F = {A→C, CD→ B, BD→E} Tính bao đóng: AD, AB AD+F = ADCBE AB+F = ABC Thuật toán tìm bao đóng của tập thuộc tính trong lược đồ quan hệ: - Cho tập phụ thuộc hàm F trên tập thuộc tính R và một tập con các thuộc tínhX, X+ ta xuất phát từ thuộc tập X và bổ sung dần cho X các thuộc tính vế phải Pcủa các phụthuộc hàm T → P Î F thỏa điều kiện T ⊆ X. Thuật toán sẽ dừng khikhông thể bổ sung thêm thuộc tính nào cho X. Thuật toán : Đầu vào ...