Xây dựng chương trình hỗ trợ 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ất lượng thiết kế của một lược đồ CSDL được đánh giá dựa trên các tiêu chuẩn như: Sự trùng lắp thông tin: vì nó sẽ làm tăng không gian lưu trữ và gây nên tình huống thông tin bị mâu thuẫn sau những lần cập nhật CSDL. Chi phí kiểm tra ràng buộc toàn vẹn. Bảo toàn quy tắc quản lý tức là bảo toàn các phụ thuộc hàm. Bảo toàn thông tin. Ví dụ: Quan hệ QuảnLýHọcTập (MaSV, TenSV, NgaySinh, Phai, DiaChi, MaLop, TenLop, MaMonHoc, TenMonHoc, Diem) F = { f1: MaSV→TenSV, NgaySinh, Phai, DiaChi, MaLop. f2: MaLop → TenLop. f3: MaMonHoc → TenMonHoc. f4: TenMonHoc → MaMonHoc. f5: MaSV, MaMonHoc → Diem.} Quan hệ trên có sự trùng lắp thông tin. Sự trùng lắp thông tin này có thể gây một số vấn đề khi thao tác trên quan hệ. Giả sử: có 1 sinh viên thay đổi địa chỉ, thì hệ thống cần phải duyệt trên toàn bộ quan hệ để tìm và sửa địa chỉ các bộ liên quan đến sinh viên này. Nếu để xót thì sẽ dẫn đến tình trạng thông tin không nhất quán. Giả sử sinh viên có mã số 1180 hiện nay chỉ đăng ký học môn CSDL. Nếu muốn xóa kết quả điểm của môn này thì dẫn đến mất luôn thông tin của sinh viên. Khóa của quan hệ là: {MaSV, MaMonHoc}, {MaSV, TenMonHoc} nên ta không thể thêm một sinh viên vào nếu sinh viên đó chưa đăng ký môn học. Qua ví dụ trên, chúng ta thấy sự trùng lắp thông tin là nguyên nhân làm cho CSDL có chất lượng kém. Để hạn chế sự trùng lắp thông tin, người ta đưa ra các yêu cầu thiết kế cần thiết cho một quan hệ dựa trên khái niệm phụ thuộc hàm, được gọi là các dạng chuẩn của một quan hệ. Dạng chuẩn 1: Thuộc tính đơn: là thuộc tính mà giá trị của nó không phải là sự kết hợp bỡi nhiều thông tin có ý nghĩa khác nhau và hệ thống luôn truy xuất trên toàn bộ giá trị của nó ít khi truy xuất đến từng phần dữ liệu của nó. Ví dụ: Quan hệ VatTu (MãVậtTư, TênVậtTư, ĐơnVịTính) Nếu TênVậtTư bao gồm cả tên vật tư và quy cách của nó. Như vậy, TênVậtTư là thuộc tính kép. Định nghĩa dạng chuẩn 1: Một lược đồ quan hệ Q đạt dạng chuẩn 1 nếu mọi thuộc tính của Q đều là thuộc tính đơn. Dạng chuẩn 2: Phụ thuộc đầy đủ: Thuộc tính A được gọi là phụ thuộc đầy đủ vào tập thuộc tính X nếu: A Î X+F X ® A là PTH nguyên tố. Ví dụ: Quan hệ LopHoc (Lop, Mon, NgayKhaiGiang, HocPhi) F = { f1: Lop, Mon → NgayKhaiGiang ; f2: Mon → HocPhi}. Dựa vào F ta có khóa của quan hệ là {Lop, Mon}. Do đó: Lop, Mon → HocPhi là phụ thuộc hàm không đầy đủ vì chỉ cần Mon là xác định được HocPhi: Mon→HocPhi. Định nghĩa dạng chuẩn 2: Một lược đồ quan hệ Q đạt dạng chuẩn 2 nếu: Q ở dạng chuẩn 1. Mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào các khóa của Q. Hệ quả: Nếu mỗi khóa của quan hệ Q chỉ có 1 thuộc tính thì Q đạt dạng chuẩn 2. Ví dụ: Quan hệ LopHoc (Lop, Mon, NgayKhaiGiang). F = {Lop, Mon → NgayKhaiGiang} Ta nói quan hệ LopHoc đạt dạng chuẩn 2 vì thuộc tính không khóa NgayKhaiGiang phụ thuộc hàm đầy đủ vào khóa. Dạng chuẩn 3: Phụ thuộc bắt cầu: Thuộc tính A Î Q+ được gọi là phụ thuộc bắt cầu vào thuộc tính X nếu tồn tại nhóm thuộc tính Y Í Q+ thỏa mãn 4 điều kiện sau: X ® Y Î F+ Y ® A Î F+ Y --/--> X A Ï {X Ç Y} Ví dụ: Quan hệ SinhVien (MaSV, TenSV, NgaySinh, QueQuan, MaLop, TenLop). TenLop phụ thuộc bắt cầu vào MaSV vì: MaSV → MaLop MaLop → TenLop MaLop --/--> MaSV TenLop Ï {MaSV Ç MaLop} Định nghĩa dạng chuẩn 3: Một lược đồ quan hệ Q đạt dạng chuẩn 3 nếu: Q ở dạng chuẩn 2 Mọi thuộc tính không khóa Q đều không phụ thuộc bắt cầu vào một khóa nào của Q. Ví dụ: Quan hệ SinhVien (MaSV, TenSV, NgaySinh, QueQuan, MaLop) là quan hệ đạt dạng chuẩn 3. Vì các thuộc tính không khóa TenSV, NgaySinh, QueQuan, MaLop không phụ thuộc bắt cầu vào khóa. Dạng chuẩn BCK: Định nghĩa: Một lược đồ quan hệ Q ở dạng chuẩn BCK nếu mọi phụ thuộc hàm không hiển nhiên đều có vế trái chứa khóa. X ® A Î F+ : A Ï X và phải chứa khóa của Q. Hệ quả: Nếu Q đạt dạng chuẩn BCK thì mọi vế trái của phụ thuộc hàm đều là siêu khóa. Ví dụ: Quan hệ TonKho (MaHangHoa, MaKho, SoLuongTon) Ta nói quan hệ TonKho đạt dạng chuẩn BCK. Chuẩn hóa quan hệ: Xuất phát từ giai đoạn phân tích yêu cầu, ta có thể có 1 trong 2 kết quả sau: Một cấu trúc CSDL ban đầu gồm các quan hệ con Qi cùng các phụ thuộc hàm F. Hoặc chỉ có một quan hệ phổ quát duy nhất Q chứa tất cả các thuộc tính cần được lưu trữ và các phụ thuộc hàm F. Chúng ta cần kiểm tra và chuẩn hóa các kết quả đầu tiên này dựa trên một số tiêu chuẩn thiết kế để có được một cấu trúc quan niệm CSDL được đánh giá tốt hơn, phù hợp hơn với yêu cầu của môi trường ứng dụng. Các tiêu chuẩn của quá trình chuẩn hóa: Hai tiêu chuẩn quan trọng cần đạt được trong quá trình chuẩn hóa một CSDL ở mức quan niệm là: CSDL kết quả cần đạt dạng chuẩn cao nhất: Dạng chuẩn được đề ra nhằm đáp ứng 2 yêu cầu sau: Cập nhật: hạn chế tối đa sự trùng lắp thông tin trong CSDL. Kiểm tra ràng buộc toàn vẹn: tạo điều kiện thuận lợi cho việc kiểm tra ràng buộc toàn vẹn ở dạng phụ thuộc dữ liệu. CSDL kết quả phải tương đương với CSDL phân tích lúc ban đầu: Với tiêu chuẩn này, các thông tin lưu trữ CSDL ban đầu đều phải được tìm thấy đầy đủ trong CSDL kết quả. Có ba quan niệm khác nhau về tiêu chuẩn này: Quan điểm 1: bảo toàn phụ thuộc hàm. Quan điểm này cho rằng các thông tin được lưu trữ trong CSDL là những thông tin được thể hiện thông qua các phụ thuộc hàm. Do đó cần phải bảo toàn phụ thuộc hàm trong khi biến đổi. Quan điểm 2: bảo toàn thông tin. Quan điểm này cho rằng các thông tin được lưu trữ trong CSDL ban đầu đều phải được tìm thấy đầy đủ trong CSDL kết quả. Quan điểm 3: biểu diễn tron vẹn. Yêu cầu CSDL kết quả vừa bảo toàn thông tin, vừa bảo toàn phụ thuộc hàm. Các phương pháp chuẩn hóa một lược đồ CSDL: Phương pháp phân rã: Định lý Delobel (1973): Cho lược đồ quan hệ Q và tập phụ thuộc hàm F. Nếu f: X → A Î F+ sao cho X È A là tập con thật sự của Q+ thì phép phân rã Q thành 2 lược đồ quan hệ con: Q1(X, A), F+1 = {f: Î F+ : VT(f) È VP(f) Ì Q+1} Q1(Q+\A), F+1 = {f: Î F+ : VT(f) È VP(f) Ì Q+2} Là bảo toàn thông tin. Ý tưởng: Dựa vào định lý Delobel, ta phân rã quan hệ Q thành 2 quan hệ Q1, Q2 bằng 1 phụ thuộc hàm f thỏa điều kiện của định lý. Lặp lại phân rã trên Q1, Q2 cho đến khi không còn phụ thuộc hàm f như vậy nữa. Thuật toán: PhanRa(Q, F) Vào: Ra: C = {Qi} //tập các quan hệ được phân rã. Begin: Bước 1: Loại bỏ các phụ thuộc hàm có VT È VP = Q+ khỏi F. F* = F\{f Î F : VT(f) È VP(f) = Q+} Bước 2: Nếu F* = Æ thì C = C È {Q} và kết thúc {Điểm dừng} Ngược lại, thực hiện phân rã Tìm tất cả các khóa của quan hệ. Chọn f: X → Y Î F với X không là siêu khóa và Y không chứa thuộc tính khóa. Phân rã thành 2 lược đồ con: Q+1 = {X, Y}; F1 = {f Î F+: VT(f) È VP(f) Í Q+1} Q+2 = Q+\Y; F2 = {f Î F+: VT(f) È VP(f) Í Q+2} Phân rã đệ qui Q1, Q2: Phanra(Q1, F1); Phanra(Q2, F2); End. Thuật toán trên là bảo toàn thông tin theo định lý Delobel. Ví dụ: Cho Q(S,D,I,M) F={SI®D;SD®M} Hãy phân rã Q thành các lược đồ con đạt dạng chuẩn 3 (dạng chuẩn BCK) bảo toàn thông tin. Giải: Bước 1: tìm tất cả khóa của Q Xi TNÈXi (TNÈXi)+ Siêu khóa Khóa Æ SI SDIM SI SI D SID SDIM SID Bước 2: phụ thuộc hàm SD ® M Î F có SD không là siêu khóa. Ta được phân rã như bên dưới. Nhược điểm của phương pháp này: Không bảo toàn phụ thuộc hàm. Có thể chứa một quan hệ con mà ngữ nghĩa của nó không có ích cho ứng dụng. Thuật toán này chỉ tiện trong trường hợp khối lượng tính toán trong việc tìm tất cả các khóa của quan hệ Q không lớn. Phương pháp tổng hợp: Mục tiêu của phương pháp: Tìm một cấu trúc CSDL gồm các Qi sao cho: Dễ dàng kiểm tra các phụ thuộc hàm. Tối thiểu đạt dạng chuẩn 3. Thuật toán: TongHop(Q, F) Vào: Ra: C = {} Begin Bước 1: Tìm phủ tối tiểu của F. Bước 2: Chia phủ tối tiểu thành những nhóm Fi. Mỗi nhóm Fi chứa các phụ thuộc hàm có cùng vế trái. Bước 3: Gộp các Fi có vế trái phụ thuộc lẫn nhau lại thành một nhóm. Bước 4: Tạo các quan hệ con Qi từ các nhóm phụ thuộc hàm Fi đã tạo ở bước 3. End. Ví dụ: Quan hệ Q(MSCĐ, MSSV, CĐ, HG) F = { f1 = MSCĐ ® CĐ, f2 = CĐ ® MSCĐ, f3 = CĐ, MSSV ® HG, f4 = MSCĐ, HG ® MSSV, f5 = CĐ, HG ® MSSV, f6 = MSCĐ, MSSV ® HG} Hãy phân rã quan hệ trên theo thuật toán tổng hợp. Giải: Bước 1: tìm phủ tối tiểu của F: Ftt = {f1, f2, f3, f4} Bước 2: phân nhóm Ftt mỗi nhóm chứa các phụ thuộc hàm có cùng vế trái. F1 f1 = MSCĐ ® CĐ F2 f2 = CĐ ® MSCĐ F3 f3 = CĐ, MSSV ® HG F4 f4 = MSCĐ, HG ® MSSV Bước 3: gộp các phụ thuộc hàm F’i có vế trái phụ thuộc lẫn nhau: F12 f1 = MSCĐ ® CĐ, f2 = CĐ ® MSCĐ F34 f3 = CĐ, MSSV ® HG,f4 = MSCĐ, HG ® MSSV Bước 4: tạo các quan hệ con Qi từ các phụ thuộc hàm F’i Q12 (MSCĐ, CĐ) F12 = {f1 = MSCĐ ® CĐ, f2 = CĐ ® MSCĐ} Q34 (CĐ, MSSV, MSCĐ, HG) F34 = {f3 = CĐ, MSSV ® HG,f4 = MSCĐ, HG ® MSSV} Đồ thị quan hệ: Dẫn nhập: Thao tác quan trọng và thường xảy ra nhất trong CSDL quan hệ là phép kết. Để thao tác này được thực hiện hiệu quả, hệ quản trị thường dựa trên các chỉ mục của các quan hệ liên quan. Do đó, vai trò của người thiết kế là làm thế nào xác định được đủ các chỉ mục cần thiết, với số thuộc tính vừa đủ để khai thác. Chỉ mục bao gồm nhiều thuộc tính hoặc tạo quá nhiều chỉ mục sẽ gây tốn chỗ và tốn kém trong quá trình bảo trì hệ thống và CSDL sẽ hoạt động chậm chạp. Để có thể xác định đúng các chỉ mục cần thiết, người ta sử dụng phương pháp biểu diễn quan hệ ở dạng đồ thị. Dạng đồ thị này cho phép làm nổi bậc các thuộc tính chung giữa hai hay nhiều quan hệ (vì đây là cơ sở của phép kết) qua đó giúp cho người thiết kế sau này dễ dàng đánh giá và chọn lựa đúng các chỉ mục. Một số khái niệm trong lý thuyết đồ thị: Đồ thị: Một đồ thị DT (N, C) được định nghĩa trên 1 tập nút N={n1,n2,…,nn} và một tập cung C={c1,c2,…,cn}. Nếu hiện diện cung có hướng thì đó là đồ thị có hướng, và 2 nút nối bỡi 1 cung có hướng được gọi là nút đi và nút đến. Nếu tất cả các cung đến vô hướng thì đó là đồ thị vô hướng, và các nút trên đồ thị đều được xem là nút xuất phát. Cung kề cận: 2 cung c1, c2 được gọi là kề cận nhau khi: Đồ thị có hướng: nếu nút đến của cung c1 là nút đi của cung c2. Đồ thị vô hướng: nếu chúng có cùng 1 nút xuất phát. Khuyên: Cung c là khuyên nếu 2 nút đi và đến của c là một. Đường đi trên đồ thị vô hướng: Đường đi trên đồ thị vô hướng là một chuỗi cung (c1,c2,…,cp) sao cho: ci và ci+1 có chung một nút xuất phát. Nút xuất phát của c1, không chung nút xuất phát của c2, c1 được gọi là nút đầu của đường đi. Nút xuất phát của cp, không chung với nút xuất phát của cp+1, cp được gọi là nút cuối của đường đi. Mạc._.