Đề tài Thuật toán thiết kế cơ sở dữ liệu

MỤC LỤC GIỚI THIỆU ĐỀ TÀI Bối cảnh của đề tài: Trong đời sống, mọi hoạt động của con người đều liên quan đến dữ liệu. Ngay cả một bài toán nhỏ cũng cần đến dữ liệu, nhưng không nhất thiết phải quản lý dữ liệu này theo các phương pháp khoa học. Do khả năng tổng hợp của người xử lý, các dữ liệu được lấy ra, được xử lý mà không vấp phải khó khăn nào. Tuy nhiên khi bài toán có kích thước lớn hơn hẳn và số lượng dữ liệu cần phải xử lý tăng lên thì e rằng tầm bao quát của con người bình thường khó có thể quản lý hết được. Ấy là chưa kể đến một số loại dữ liệu đặc biệt, chúng đòi hỏi được quản lý tốt không phải vì kích thước mà vì sự phức tạp của bản thân chúng. Do đó, nhu cầu tích lũy và xử lý các dữ liệu đã nảy sinh. Tổ chức việc tích lũy và xử lý dữ liệu một cách khoa học đòi hỏi con người sử dụng một hệ thống các thông tin có cấu trúc được lưu trữ trên các thiết bị lưu trữ thông tin thứ cấp (như băng từ, đĩa từ …) để có thể thỏa mãn yêu cầu khai thác thông tin đồng thời của nhiều người sử dụng hay nhiều chương trình ứng dụng với nhiều mục đích khác nhau. Hệ thống đó được gọi là cơ sở dữ liệu. Trong những năm gần đây thuật ngữ “CƠ SỞ DỮ LIỆU” (CSDL) đã trở nên khá quen thuộc không chỉ với những người làm Tin học mà còn đối với cả những người làm trong nhiều lĩnh vực khác như Kinh tế, Quản lý Doanh nghiệp … Các ứng dụng của tin học vào công tác quản lý ngày càng nhiều hơn và càng đa dạng hơn. Có thể nói hầu hết các lĩnh vực kinh tế, xã hội, giáo dục, y tế … đều đã ứng dụng các thành tựu mới của Tin học vào phục vụ công tác chuyên môn của mình. Chính vì lẽ đó mà ngày càng nhiều người quan tâm đến lĩnh vực thiết kế và xây dựng các CSDL. Và có thể thấy mục tiêu chính của việc thiết kế CSDL là làm thế nào chuyển đổi các nhu cầu lưu trữ và khai thác dữ liệu của người sử dụng thành một hệ thống CSLD hiệu quả. Người thiết kế CSDL có thể chia nhỏ hệ thống dữ liệu tổng quát thành các lược đồ quan hệ (hay còn gọi là các table). Đó là một kỹ thuật dựa vào khinh nghiệm của người thiết kế còn trong thực tế để có được một CSDL tốt người thiết kế phải ứng dụng nhiều thuật toán như: thuật toán xác định khóa, thuật toán xác định các dạng chuẩn, thuật toán phân rã lược đồ quan hệ… để đi tìm khóa, xác định dạng chuẩn, chuẩn hóa mỗi quan hệ trong CSDL, nhằm đảm bảo cho hệ dữ liệu có thể quản lý đầy đủ, chính xác các thông tin trong thực tế tránh tình trạng trùng lắp thông tin, không để xảy ra tình trạng thừa hoặc thiếu thông tin. Trong quá trình đó, người thiết kế thường gặp một số vấn đề sau: Khi xác định một số đặc điểm của đối tượng được lưu trữ, người thiết kế sẽ liệt kê tất cả các thuộc tính cần quản lý của đối tượng mà không quan tâm đến vấn đề liệu khi thêm thuộc tính đó thì có bị trùng lắp thông tin không, dữ liệu có nhất quán không. Chẳng hạn như trong hệ thống bán hàng, chúng ta lưu trữ thông tin của nhà cung cấp để đặt hàng thì một số thông tin ta cần là: mã nhà cung cấp, tên nhà cung cấp, địa chỉ, số điện thoại, mã hàng, tên hàng…Với đối tượng nhà cung cấp nếu ta quản lý rằng mỗi nhà cung cấp chỉ cung cấp một mặt hàng thì ta biết được nhà cung cấp nào cung cấp mặt hàng tên gì nhưng dữ liệu về tên mặt hàng không nhất quán. Khi nhập liệu ta có thể nhập như sau: Mã nhà cung cấp … Mã hàng Tên hàng 01 01 Abc 02 02 Abc Bảng 1. Quan hệ nhà cung cấp Điều đó sẽ gây khó khăn cho ta trong quá trình truy xuất thông tin. Để khắc phục được vấn đề trên, đầu tiên người thiết kế phải dựa vào các qui tắc quản lý (phụ thuộc hàm), áp dụng hệ luật dẫn Amstrong trên các phụ thuộc hàm để xác định mối liên hệ giữa các thuộc tính trong một đối tượng hoặc giữa các đối tượng trong một CSDL. Sau đó, sử dụng thuật toán tìm khóa của đối tượng. Dựa vào khóa và các phụ thuộc hàm, người thiết kế sẽ đi xác định dạng chuẩn để đánh giá tính chất của lược đồ quan hệ hay là đối tượng cần quản lý. Trong thực tế, người ta chỉ đánh giá cao các lược đồ quan hệ đạt từ dạng chuẩn 3 trở lên vì ở dạng chuẩn này CSDL sẽ tránh được sụ trùng lắp thông tin. Do đó, khi lược đồ quan hệ không đạt được dạng chuẩn 3, người thiết kế phân rã lược đồ quan hệ đó thành những lược đồ con đảm bảo dạng chuẩn cao hơn, dữ liệu không bị trùng lắp mà vẫn giữ được tính bảo toàn, tính chính xác của dữ liệu, không gây mất thông tin. Chỉ với một đối tượng mà người thiết kế phải làm biết bao công việc như vậy, trong thực tế có muôn vàn đối tượng cần được quản lý thì người thiết kế phải tốn rất nhiều thời gian và công sức cho mỗi đối tượng. Vì để làm tất cả các công việc đó, người thiết kế vẫn phải làm trên giấy chứ chưa có 1 chương trình nào hỗ trợ cả. Trước thực tế đó, chúng em xin thực hiện đề tài này để giúp người thiết kế thực hiện các công việc trên một cách nhanh chóng và chính xác. Giới thiệu chung về đề tài: Nội dung chính của đề tài là xây dựng một chương trình cho phép người dùng tạo ra một lược đồ quan hệ và thực hiện một số chức năng như: Tìm khóa của quan hệ. Tìm phủ tối tiểu của quan hệ. Xác định dạng chuẩn của quan hệ. Chuẩn hóa quan hệ. Tìm con đường truy xuất của một nút. Công cụ: Chương trình được viết bằng ngôn ngữ C# trên môi trường .NET. LÝ THUYẾT VỀ CƠ SỞ DỮ LIỆU Một số khái niệm: Thuộc tính (Attribute): Thuộc tính là một tính chất riêng biệt của một đối tượng cần lưu trữ trong CSDL để phục vụ cho việc khai thác dữ liệu về đối tượng. Ví dụ: Đối tượng Sinh Viên có một số thuộc tính Mã lớp, Mã sinh viên, Tên sinh viên, Ngày sinh, Quê quán. Quan hệ: Một quan hệ R có n ngôi được định nghĩa trên tập các thuộc tính U = {A1, A2, …, An} (thứ tự các thuộc tính không quan trọng) và kèm theo nó là một tân từ, tức là một quy tắc để xác định mối quan hệ giữa các thuộc tính Ai và được ký hiệu R(A1, A2, …, An). tập thuộc tính của quan hệ R đôi khi còn được ký hiệu là R+. Ví dụ: SinhViên(Mã sinh viên, Tên sinh viên, Ngày sinh, Quê quán, Mã lớp) là quan hệ 5 ngôi. Tân từ: “Mỗi sinh viên có một họ tên, ngày sinh, quê quán, và được cấp một mã số duy nhất để phân biệt với mọi sinh viên khác trong trường; sinh viên thuộc một lớp duy nhất trong trường.” Lược đồ quan hệ (Relation shema): Lược đồ quan hệ là sự trừu tượng hóa của quan hệ, một sự trừu tượng hóa ở mức độ cấu trúc của một bảng hai chiều. Khi nói đến lược đồ quan hệ là đề cập đến cấu trúc tổng quát của một quan hệ; khi đề cập tới quan hệ thì điều đó được hiểu rằng đó là một bảng có cấu trúc cụ thể hoặc một định nghĩa cụ thể trên một lược đồ quan hệ với các bộ giá trị của nó. Khóa – Siêu khóa: Khóa (Key): Quan hệ R định nghĩa trên tập các thuộc tính U={A1,A2,…,An} K Í U là khóa của quan hệ R nếu thỏa 2 điều kiện sau: K xác định được giá trị của Aj với mọi j = 1, 2, …, n. !$ K’ Í K mà K’ có thể xác định được giá trị của Aj với mọi j = 1, 2, …, n. Nghĩa là K là tập con nhỏ nhất mà giá trị của nó có thể xác định duy nhất một bộ giá trị của quan hệ. K còn được gọi là khóa chỉ định (Candidate) và là khóa nội của quan hệ. Siêu khóa: K được gọi là siêu khóa của quan hệ R nếu K’ Í K là một khóa của quan hệ. Một lược đồ quan hệ Q của quan hệ R luôn có ít nhất một siêu khóa và có thể có nhiều siêu khóa. Ví dụ: Quan hệ SinhViên(MãSinhViên, TênSinhViên, NgàySinh, QuêQuán, MãLớp) Tìm khóa và siêu khóa của quan hệ SinhVien. Giải: Quan hệ SinhViên có khóa là Mã sinh viên và một số siêu khóa: K1 = {MãSinhViên, TênSinhViên} K2 = {MãSinhViên, TênSinhViên, NgàySinh} K3 = {MãSinhViên, MãLớp} Thuộc tính khóa: Thuộc tính khóa là các thuộc tính tham gia vào khóa. Thuộc tính không khóa: Thuộc tính không khóa là các thuộc tính không tham gia vào bất kỳ khóa nào. Phụ thuộc hàm: Phụ thuộc hàm là công cụ dùng để biểu diễn mối quan hệ dữ liệu của các thuộc tính trong quan hệ. Quan hệ R được định nghĩa trên tập thuộc tính U={A1,A2,…,An}. X, Y Ì U là hai tập con của tập thuộc tính U. Nếu $ f: X ® Y thì ta nói rằng X xác định Y hay Y phụ thuộc hàm vào X và ký hiệu là X ® Y. Ràng buộc toàn vẹn: Trong mỗi CSDL luôn tồn tại nhiều mối liên hệ giữa các thuộc tính, giữa các bộ. Sự liên hệ này có thể xảy ra trong một lườc đồ quan hệ hoặc trong các lược đồ quan hệ của một CSDL. Các mối liên hệ này là những điều kiện bất biến mà tất cả các bộ của những quan hệ có liên quan trong CSDL đều phải thỏa mãn ở mọi thời điểm. Những điều kiện bất biến đó được gọi là ràng buộc toàn vẹn (RBTV). Trong thực tế RBTV là các quy tắc quản lý được áp đặt trên các đối tượng của thế giới thực. Đó là quy tắc để đảm bảo tính nhất quán của dữ liệu trong CSDL. Mỗi RBTV được định nghĩa bằng một thuật toán trong CSDL. Ví dụ: Quan hệ kếtquảthi (mãsinhviên, mãmôn, lầnthi, ngàythi, điểmthi, ghichú) Quy tắc: Điểm thi của sinh viên phải lớn hơn hoặc bằng 1 và bé hơn hoặc bằng 10. Thuật toán: " kqt Î kếtquảthi thì kqt.điểmthi >= 1 & kqt.điểmthi <= 10. Trong một CSDL, RBTV được xem như là một công cụ để diễn đạt ngữ nghĩa của CSDL. Một CSDL được thiết kế cồng kềnh nhưng nó thể hiện được đầy đủ ngữ nghĩa của thực tế vẫn có giá trị cao hơn rất nhiều so với một cách thiết kế gọn nhẹ nhưng nghèo nàn về ngữ nghĩa vì thiếu các RBTV của CSDL. Trên đây là những khái niệm cơ bản, bây giờ chúng ta đi sâu vào tìm hiểu một số vấn đề cốt lõi của quá trình thiết kế CSDL. Ràng buộc toàn vẹn và phụ thuộc hàm: Ràng buộc toàn vẹn: Nhiệm vụ của người phân tích thiết kế là phải phát hiện càng đầy đủ và chính xác các RBTV càng tốt và mô tả chúng một cách chính xác trong hồ sơ phân tích thiết kế - đó là một việc làm rất quan trọng và cần thiết. Công việc kiểm tra RBTV thường được tiến hành vào thời điểm cập nhật dữ liệu (thêm, xóa, sửa). Các yếu tố của RBTV: Mỗi RBTV có 3 yếu tố ảnh hưởng: điều kiện, bối cảnh, tầm ảnh hưởng. Điều kiện: Điều kiện của một RBTV R có thể được biểu diễn bằng ngôn ngữ tự nhiên, thuật giải, ngôn ngữ đại số quan hệ, …ngoài ra điều kiện của một RBTV cũng có thể được biểu diễn bằng phụ thuộc hàm. Bối cảnh: Là những quan hệ mà ràng buộc đó có hiệu lực hay nói một cách khác, đó là những quan hệ cần phải được kiểm tra RBTV. Bối cảnh của một RBTV có thể là một hoặc nhiều quan hệ. Tầm ảnh hưởng: Trong quá trình phân tích thiết kế một CSDL, người thiết kế cần lập bảng tầm ảnh hưởng cho một RBTV nhằm xác định thời điểm cần phải tiến hành kiểm tra các RBTV đó. Các thời điểm cần phải kiểm tra RBTV chính là những thời điểm cập nhật dữ liệu (thêm, sửa, xóa). Một bảng tầm ảnh hưởng của một RBTV có dạng sau: (Tên RBTV) Thêm(T) Sửa(S) Xóa(X) r1 + - - r2 ... ... .. .. ... ... ... ... rn Bảng này chứa toàn các ký hiệu + hoặc – Chẳng hạn + tại ô tương ứng với dòng r1, cột thêm thì có nghĩa là khi thêm một bộ vào quan hệ r1 thì cần phải kiểm tra RBTV. Dấu – tại ô tương ứng với dòng r1, cột sửa thì có nghĩa là khi sửa một bộ trên quan hệ r1 thì không cần kiểm tra RBTV này. Phân loại RBTV: Trong quá trình phân tích thiết kế CSDL, người phân tích phải phát hiện tất cả các RBTV tiềm ẩn trong CSDL đó. Việc phân loại các RBTV là rất có ích, nó nhằm giúp cho người phân tích có được một định hướng, tránh bỏ sót những RBTV. Các RBTV có thể được chia làm hai loại chính như sau: RBTV trên phạm vi một quan hệ: RBTV miền giá trị, RBTV liên thuộc tính, RBTV liên bộ. RBTV trên phạm vi nhiều quan hệ: RBTV phụ thuộc tồn tại, RBTV liên bộ - liên quan hệ, RBTV liên thuộc tính - liên quan hệ. RBTV liên bộ: RBTV liên bộ là sự RBTV giữa các bộ trong cùng một quan hệ. RBTV liên bộ hay còn gọi là RBTV về khóa. Đây là loại RBTV rất phổ biến, nó có mặt trong mọi lược đồ quan hệ của CSDL và thường được các hệ quản trị CSDL tự động kiểm tra. Ví dụ: với r là một quan hệ của Khách ta có RBTV như sau: R1: " t1, t2 Î r t1. MAKH ¹ t2. MAKH Cuối " Bảng tầm ảnh hưởng: R1 Thêm Sửa Xóa r + + - RBTV về phụ thuộc tồn tại: RBTV về phụ thuộc tồn tại còn được gọi là RBTV về khóa ngoại. Cũng giống như RBTV về khóa chính, RBTV về phụ thuộc tồn tại rất phổ biến trong CSDL. Ví dụ: Với r, s lần lượt là một quan hệ của DatHang, Khach ta có RBTV sau: R2: r[MAKH] Í s[MAKH] Bảng tầm ảnh hưởng: R2 Thêm Sửa Xóa R + + - S - + + RBTV về miền giá trị: RBTV về miền giá trị có liên quan đến miền giá trị của các thuộc tính trong một quan hệ. RBTV này thường gặp. một số hệ quản trị CSDL đã tự động kiểm tra một số ràng buộc loại này. Ví dụ: Với r là một quan hệ của HoaDon ta có RBTV sau: R3: " t Î r t.TRIGIAHD > 0 Cuối " Bảng tầm ảnh hưởng: R3 Thêm Sửa Xóa R + + - RBTV liên thuộc tính: RBTV liên thuộc tính là mối liên hệ giữa các thuộc tính trong một lược đồ quan hệ. Ví dụ: Với r là một quan hệ của HoaDon ta có RBTV sau: R4: " t Î r t.NGAYLAP <= t.NGAYXUAT Cuối " Bảng tầm ảnh hưởng: R4 Thêm Sửa Xóa R + + - RBTV liên thuộc tính – liên quan hệ: RBTV loại này là mối liên hệ giữa các thuộc tính trong nhiều lược đồ quan hệ. Ví dụ: Với r, s lần lượt là quan hệ của DatHang, HoaDon ta có RBTV sau: R5: " t1 Î r, t2 Î s Nếu t1.SODH = t2.SODH thì t1.NGAYDH <= t2.NGAYXUAT Cuối " Bảng tầm ảnh hưởng: R5 Thêm Sửa Xóa R + + + S + + + RBTV tổng hợp: RBTV về thuộc tính tổng hợp được xác định trong trường hợp mỗi thuộc tính A của một lược đồ quan hệ Q được tính toán giá trị từ các thuộc tính của các lược đồ quan hệ khác. Phụ thuộc hàm: Phụ thuộc hàm có tầm quan trọng rất lớn trong việc phân tích và thiết kế mô hình dữ liệu. phụ thuộc hàm được ứng dụng trong việc giải quyết các bài toán tìm khóa, tìm phủ tối tiểu và chuẩn hóa CSDL. Định nghĩa hình thức của phụ thuộc hàm như sau: Quan hệ Q (A, B, C) có phụ thuộc hàm A xác định B (ký hiệu là A→B) nếu: " q, q’ Î Q, sao cho q.A = q’.A thì q.B = q’.B (Nghĩa là: ứng với 1 giá trị của A thì có một giá trị duy nhất của B) A là vế trái của phụ thuộc hàm, B là vế phải của phụ thuộc hàm. A→B được gọi là phụ thuộc hàm hiển nhiên nếu BÌA. Nghĩa là, một tập A lớn hơn và bao tập con B thì A xác định được giá trị của các thuộc tính trong tập B lad điều hiển nhiên. A→B được gọi là phụ thuộc hàm nguyên tố, hoặc nói cách khác B được gọi là phụ thuộc hàm đầy đủ (fully functional defendence) vào A nếu "A’Ë A đều không có A’→B. Ví dụ: Trong quan hệ HóaĐơn (SốHóaĐơn, SốChủngLoạiMặtHàng, TổngTrịGiá) có các phụ thuộc hàm sau: f1: SốHóaĐơn → SốChủngLoạiMặtHàng; f2: SốHóaĐơn → TổngTrịGiá; SốHóaĐơn là khóa của lược đồ quan hệ HóaĐơn. Nếu biết số hóa đơn thì ta có thể xác định được tất cả các thông tin còn lại liên quan đến hóa đơn đó, trong đó có thông tin về SốChủngLoạiMặtHàng và TổngTrịGiá tất cả các mặt hàng của hóa đơn. Các phụ thuộc hàm trên đều là nguyên tố. Quan hệ ChiTiếtHóaĐơn (SốHóaĐơn, MãHàng, SốLượngĐặt, ĐơnGiá, TrịGiá) có các phụ thuộc hàm sau: f1: SốHóaĐơn, MãHàng → SốLượngĐặt; f2: SốHóaĐơn, MãHàng → ĐơnGiá; f3: SốHóaĐơn, MãHàng → TrịGiá; f4: SốLượngĐặt, ĐơnGiá → TrịGiá. Thuộc tính ĐơnGiá phụ thuộc hàm không đầy đủ vào khóa (SốHóaĐơn, MãHàng), bỡi vì nó chỉ phụ thuộc vào mặt hàng (thông qua MãHàng). Trên một lược đồ quan hệ có thể tồn tại nhiều phụ thuộc hàm. Tập các phụ thuộc hàm thường được ký hiệu bằng chữ F. Hệ tiên đề Amstrong: Năm 1974, Amstrong đã đưa ra hệ tiên đề (còn gọi là hệ luật dẫn Amstrong, hay các tính chất của phụ thuộc hàm) như sau: X, Y, Z, W Í U. phụ thuộc hàm có các tính chất sau đây: Tính phản xạ: Nếu Y Í X thì X → Y. Tính tăng trưởng: Nếu X → Y và Z Í W thì XW → YZ. Tính bắt cầu: Nếu X → Y và Y → Z thì X → Z. Và người ta đã chứng minh rằng hệ tiên đề Amstrong là đúng đắn và đầy đủ thông qua 3 bổ đề sau: Bổ đề 1: Hệ tiên đề Amstrong là đúng, nghĩa là, với F là tập phụ thuộc hàm đúng trên quan hệ R, nếu X → Y là một phụ thuộc hàm. Bổ đề 2: Từ hệ tiên đề Amstrong suy ra một số luật bổ sung sau: Tính phân rã (hoặc luật tách): Nếu X → YZ thì X → Y và X → Z. Tính hợp (hoặc luật hợp): Nếu X → Y và X → Z thì X → YZ. Tính tựa bắt cầu hoặc bắt cầu giả: Nếu X → Y và YZ → W thì XZ → W. Định nghĩa: Bao đóng (Closure) của tập các thuộc tính X đối với tập các phụ thuộc hàm F (ký hiệu là X+F) là tập tất cả các thuộc tính A có thể suy dẫn từ X nhờ tập bao đóng của các phụ thuộc hàm F+: X+ = {A | X → A Î F+}. Ví dụ: Q (A, B, C, D, E, G, H) và F = { f1: B → A; f2: DA→ CE; f3: D → H; f4: GH → C; f5: AC → D} Tìm bao đóng của tập thuộc tính {B, D} Giải: Ta có: X+F = BD. Do f1: X+F = BDA. Do f2: X+F = BDACE Do f3: X+F = BDACEH Vậy bao đóng của tập thuộc tính {B, D} là X+F = BDACEH. Bổ đề 3: X → Y được suy diễn logic từ F nhờ hệ tiên đề Amstrong khi và chỉ khi Y Î X+F. Hệ tiên đề Amstrong là đúng và đầy đủ. Nhờ hệ luật dẫn này người ta đã giải quyết được bài toán thành viên của tập các phụ thuộc hàm: thay vì đi tìm bao đóng (Closure) của tập phụ thuộc hàm F (ký hiệu là F+, đó là tập các phụ thuộc hàm có thể được suy dẫn logic từ F) để kiểm tra xem một phụ thuộc hàm X→Y có thuộc F+ hay không, người ta chỉ cần đi tìm bao đóng của X dựa trên tập các phụ thuộc hàm F (ký hiệu là XF+, đó là tập các thuộc tính có thể suy diễn từ X nhờ F), rồi kiểm tra xem Y có thuộc XF+ hay không. Ví dụ: Cho lược đồ quan hệ R (A,B,C,D,E,G,H) và tập phụ thuộc hàm F={AB®C, B®D, CD®E, CE®GH, G®A}. Áp dụng hệ tiên đề Amstrong, tìm một chuỗi suy diễn AB®E. Giải: 1. AB®C (cho trước phụ thuộc hàm f1) 2. AB®AB (tính chất phản xạ) 3. AB®B (luật tách) 4. B®D (cho trước phụ thuộc hàm f2) 5. AB®D (bắt cầu 3 & 4) 6. AB®CD (hợp 1 & 5) 7. CD®E (cho trước phụ thuộc hàm f3) 8. AB®E (bắt cầu 6 & 7). Kết thúc.  Ví dụ: Cho lược đồ quan hệ R (A,B,C,D,E,G,H,I,J) và tập các phụ thuộc hàm F = {AB®E, AG®J, BE®I, E®G, GI®H }. Tìm chuỗi suy diễn AB®GH. Giải: 1. AB®E (cho trước phụ thuộc hàm f1) 2. AB®AB (phản xạ) 3. AB®B (luật tách) 4. AB®BE (hợp của 1 & 3) 5. BE®I (cho trước phụ thuộc hàm f3) 6. AB®I (bắt cầu 4 & 5) 7. E®G (cho trước phụ thuộc hàm f4) 8. AB®G (bắt cầu 1 & 7) 9. AB®GI (hợp 6 & 8) 10. GI®H (cho trước phụ thuộc hàm f5) 11. AB®H (bắt cầu 9 & 10) 12. AB®GH (hợp 8 & 11) Phủ và phủ tối tiểu: Trong rất nhiều bài toán liên quan đến CSDL thì độ phức tạp tùy thuộc vào số phụ thuôc hàm cũng như các thuộc tính bên vế trái, vế phải của phụ thuộc hàm. Do đó, để giảm bớt độ phức tạp người ta thường xây dựng các tập phụ thuộc hàm tương đương với tập phụ thuộc hàm ban đầu nhưng đơn giản hơn. Phụ thuộc hàm tương đương: Hai tập phụ thuộc hàm F và G được gọi là tương đương với nhau nếu F+ = G+. Ký hiệu: F º G. " f Î F thì f Î G+ và " g Î G thì g Î F+. Phủ của 1 phụ thuộc hàm: Cho hai tập phụ thuộc hàm F, G. Ta nói F phủ G nếu F+ Ê G+. Phụ thuộc hàm đầy đủ: F là tập các phụ thuộc hàm trên lược đồ quan hệ Q, X là tập thuộc tính, ta có phụ thuộc hàm: X → Y Î F. Ta nói phụ thuộc hàm X → Y là đầy đủ nếu !$ A Î Z sao cho (X – A) → Y. Phụ thuộc hàm không dư thừa: F là tập phụ thuộc hàm không dư thừa nếu !$ F’ Ì F sao cho F’ = F. Ngược lại F là tập phụ thuộc hàm dư thừa. Ví dụ: Cho F = {A → BC, B → D, AB → D} F dư thừa vì: F º F’ = {A → BC, B → D} Phủ tối tiểu: Mục đích của việc tìm phủ tối tiểu là: Giảm lược bớt số thuộc tính của vế phải. Giảm số phụ thuộc hàm. Định nghĩa: Cho tập PTH F, G là phủ tối tiểu của F nếu G là phủ của F đồng thời thỏa 3 điều kiện sau: Vế phải của các PTH trên G chỉ chứa 1 thuộc tính. G chỉ gồm những phụ thuộc hàm đầy đủ. Không chứa phụ thuộc hàm thừa. Thuật toán xác định phủ tối tiểu: Bước 1: Loại khỏi F các phụ thuộc hàm có vế trái dư thừa. Lần lượt thực hiện các bước sau cho các phụ thuộc hàm X→Y của F. Với mọi tập con thật sự X’→Y Î F+ thì thay X→Y trong F bằng X’ → Y, thực hiện lại bước này. Bước 2: Tách phụ thuộc hàm có vế phải lớn hơn một thuộc tính thành các phụ thuộc hàm có vế phải có một thuộc tính. Bước 3: Loại khỏi F các phụ thuộc hàm dư thừa. Lần lượt xét các phụ thuộc hàm X ® Y của F Nếu X ® Y là thành viên của F – { X ® Y } thì loại X ® Y khỏi F. Thực hiện bước trên cho các phụ thuộc hàm tiếp theo của F. Các dạng chuẩn của lược đồ quan hệ: Trong thực tế, một ứng dụng có thể được phân tích thành nhiều lược đồ CSDL khác nhau và dĩ nhiên chất lượng thiết kế của các lược đồ này cũng khác nhau. Chấ