Bài giảng Phân tích thiết kế hệ thống thông tin: Chương 10 - ThS. Hoàng Mạnh Hà

Trong Bài giảng Phân tích thiết kế hệ thống thông tin Chương 10 Phụ thuộc hàm và dạng chuẩn nhằm trình bày về phụ thuộc hàm và dạng chuẩn. Bài giảng được trình bày khoa học, súc tích giúp các bạn sinh viên tiếp thu bài học nhanh.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế hệ thống thông tin: Chương 10 - ThS. Hoàng Mạnh Hà Phân tích thiết kế HTTTPhụ thuộc hàm & Dạng chuẩnThS. Hoàng Mạnh Hàhoangha84@gmail.comhttps://sites.google.com/site/ Nội dung• Phụ thuộc hàm• Dạng chuẩn SGU - CNTT - Cơ sở dữ 2 Phụ thuộc hàmSGU - CNTT - Cơ sở dữ 3 Định nghĩa• Là một khái niệm quan trọng trong lý thuyết thiết kế lược đồ quan hệ.• Một phụ thuộc hàm là một ràng buộc giữa 2 tập thuộc tính.• Giả sử có lược đồ quan hệ R(A1,A2,…,An) và X, Y là tập con của {A1,A2,…,An}• Ta nói: Y phụ thuộc hàm vào X (hay X xác định Y), ký hiệu XY nếu mỗi giá trị X trong R xác định duy nhất một giá trị Y trong R. SGU - CNTT - Cơ sở dữ 4 Định nghĩa• Nếu có X Y thì ta có: o ∀r1, r2 ∈ R sao cho r1.X=r2.X thì r1.Y=r2.Y• Xét lược đồ quan hệ:PHIM (TENPHIM, NAMSX, THOILUONG,LOAIPHIM, XUONGSX, DIENVIEN) SGU - CNTT - Cơ sở dữ 5 TEN NAMSX THOI Ví dụ LOAI XUONG DIENVIEN PHIM LUONG PHIM SX Star Wars 1977 124 Color Fox Carrie Fisher Star Wars 1977 124 Color Fox Mark Hamill Star Wars 1977 124 Color Fox Harrison Ford Mighty 1991 104 Color Disney Emilio Esteves Ducks Wayne’s 1992 95 Color Paramount Dana Carvey World Wayne’s 1992 95 Color Paramount Mike Meyers World• TENPHIM  LOAIPHIM SGU - CNTT - Cơ sở dữ 6 Hệ luật ArmstrongSGU - CNTT - Cơ sở dữ 7 Hệ luật ArmstrongSGU - CNTT - Cơ sở dữ 8 Hệ quả từ tập phụ thuộc Cho F là tập các phụ thuộc hàm định nghĩa hàm ộc hàm f cũng• trên R. Nếu có một phụ thu thỏa với mọi thể hiện của R thì ta gọi f là phụ thuộc hàm hệ quả của F.• VD: R(A, B, C, G, H, I) và tập phụ thuộc hàm F định nghĩa trên R:F={f1: A→B; f2: A→C; f3: CG→H; f4: CG→I;f5: B→H}Ta có f6: A→H là phụ thuộc hàm hệ quả từ F SGU - CNTT - Cơ sở dữ 9Bao đóng của tập phụ thuộc Cho F là một tập các phụ thuộc hàm được hàmp các phụ thuộc• định nghĩa trên R. Tập hợ hàm hệ quả từ F được gọi là bao đóng của F.• Bao đóng của F ký hiệu là F+• Ta có F⊆F+ SGU - CNTT - Cơ sở dữ 10Thuật toán tìm bao đóng của Bước 1: F+=F F•• Bước 2: o Áp dụng các luật dẫn Armstrong để tìm phụ thuộc hàm hệ quả f từ F+ o Bổ sung f vào F+• Bước 3: Lặp lại bước 2 cho đến khi không thể tìm được f khác từ F+ SGU - CNTT - Cơ sở dữ 11Thuật toán tìm bao đóng của Ví dụ: R(A, B, C) và F={f1: A → B; f2: B → F• C}• F+={f1: A → B; f2: B → C; f3: A → C} SGU - CNTT - Cơ sở dữ 12 Bao đóng của tập thuộc tính• Cho F là tập các phụ thuộc hàm được định nghĩa trên R và tập thuộc tính X (X ⊆ R+)• Bao đóng của tập thuộc tính X dựa trên F được ký hiệu là X+F• X+F={Y | X → Y được suy dẫn từ F} SGU - CNTT - Cơ sở dữ 13Thuật toán tìm bao đóng của XSGU - CNTT - Cơ sở dữ 14Thuật toán tìm bao đóng củaVí dụ: XCho lược đồ R(A, B, C, D, E, G) và tập phụthuộc hàmF={ f1:AB→C; f2: BC→AD; f3: D→E; f4: CG→B}Tìm (AB)+F ?(AB)+F=- {A, dB, C, D, E} SGU - CNTT Cơ sở ữ 15 Phụ thuộc hàm suy dẫn• Cho phụ thuộc hàm f: X→Y, f suy dẫn từ F (ký hiệu F ⊢ f) nếu và chỉ nếu Y ⊆ (X)+F• VD:f: AB→E suy dẫn từ F do E ∈ (AB)+F SGU - CNTT - Cơ sở dữ 16 Tập phụ thuộc hàm tương đươngSGU - CNTT - Cơ sở dữ 17 Phủ• Một tập phụ thuộc hàm G được gọi là phủ của F nếu G tương đương với F (G ≡ F)• Ví dụ:F = {A→BC; A→ D; CD → E}G= {A → BCE; A → ABD; CD → E} SGU - CNTT - Cơ sở dữ 18 Phủ tối tiểu• Phủ tối tiểu là một tập hợp các phụ thuộc hàm sao cho nếu ta loại bớt một phụ thuộc hàm trong đó thì tập phụ thuộc hàm còn lại không còn là một phủ của F.• Phủ tối tiểu được định nghĩa thông qua 2 khái niệm phụ thuộc hàm đầy đủ và phụ thuộc hàm dư thừa. SGU - CNTT - Cơ sở dữ 19 Phụ thuộc hàm đầy đủ• Xét phụ thuộc hàm X → Y• Nếu không có X’ ⊂ X sao cho F ≡ F – {X → Y} ∪ {X’ → Y} thì Y phụ thuộc đầy đủ ...