Thiết kế CSDL

ó thể quản lí tối ưu kho dữ liệu thì những người sử dụng phải có các công cụ làm đơn giản hoá nhiệm vụ quản lí dữ liệu(DL). Yêu cầu đặt ra cho những người thiết kế là nghiên cứu những tính chất cơ bản để xây dựng cấu trúc CSDL tối ưu nhất. Mà vấn đề phụ thuộc hàm, phụ thuộc đa trị là nguyên nhân cho các vấn đề nảy sinh không đáng có trong thiết kế CSDL nên nghiên cứu về phụ thuộc hàm và phụ thuộc đa trị trong xây dựng CSDL để xây dựng tập các sơ đồ quan hệ cho phép người dùng lưu trữ các thông tin một cách không dư thừa đồng thời cho phép tìm kiếm thông tin một cách dễ dàng. Mục đích nghiên cứu của đề tài trước hết trang bị thêm kiến thức phục vụ cho thiết kế CSDL đồng thời kiến thức học hỏi được sẽ trở thành một công cụ để sinh viên và những lập trình viên sử dụng cho công việc thiết kế của mình có cái nhìn đúng đắn và mang lại hiệu quả tốt nhất trong xây dựng CSDL. Đối tượng nghiên cứu trong đề tài của em là phụ thuộc hàm, phụ thuộc đa trị và ứng dụng trong xây dựng CSDL. Và khi thiết kế một CSDL quan hệ phải nghiên cứu các tính chất cơ bản cũng như các thuật toán để có thể nhận được những tập sơ đồ phù hợp, tốt nhất cho công việc. Đề tài được chia làm ba phần lớn: Phần thứ nhất là cái nhìn tổng quan về CSDL quan hệ là phạm vi nghiên cứu của đề tài. Phần thứ hai: trình bày nội dung chính của đề tài , trong phần này giúp cho người sử dụng hiểu rõ mục đích và tầm quan trọng của việc thiết kế CSDL và ứng dụng trong thực tế. Phần cuối cùng là kết luận, qua đề tài để làm tối ưu quá trình xây dựng CSDL và trang bị cho người sử dụng thêm kiến thức cần thiết phục vụ cho ứng dụng ,và tìm hiểu để có những lựa chọn phù hợp nhất cho công việc của mình với mô hình quan hệ nào là tốt nhất. Qua đề tài nghiên cứu mong rằng sẽ trang bị cho người đọc những kiến thức bổ ích giúp ích cho những ai muốn tìm hiểu về phụ thuộc hàm,phụ thuộc đa trị có thêm những kiến thức mới bổ sung cho quá trình tìm hiểu của mình. Cơ sở lí luận. I. Khái quát CSDL: 1. Khái niệm CSDL: Cơ sở dữ liệu là lĩnh vực của tin học nghiên cứu các cơ chế ,nguyên lí , phương pháp tổ chức các nhóm DL trên các vật mang tin ngoài(các loại đĩa,trống từ, quang học…) nhằm phục vụ cho việc khai thác dữ liệu trong các hệ thống tin học ứng dụng như các hệ lưu trữ và tra cứu thông tin ,các hệ quản trị xí nghiệp hoặc ngành… Trong số 3 mô hình ba cách tiếp cận cho việc tổ chức và khai thác các CSDL là mô hình phân cấp , mô hình mạng và mô hình quan hệ thì mô hình quan hệ được quan tâm hơn cả vào khoảng vài chục năm trở lại đây . Các hệ quản trị CSDL quan hệ được thiết kế và cài đặt trên tất cả các máy : hệ micro, hệ mini, hệ mainframe và các hệ siêu máy tính. Trong các chương trình xây dựng máy tính thế hệ mới , mô hình quan hệ được quan tâm đáng kể. Sở dĩ mô hình quan hệ được phát triển rộng rãi như vậy là vì nó được xây dựng trên một cơ sở toán học chặt chẽ _lí thuyết về các quan hệ và có hình ảnh trực quan gần với quan niệm thông thường của người dùng cuối. Các ngôn ngữ thao tác trên các CSDL quan hệ khá dễ học và có hiệu suất phục vụ cao.Trong mô hình quan hệ thì giá trị đưa vào mỗi cột phải là đơn nhất, các giá trị đưa vào một cột phải cùng một miền dữ liệu và mỗi dòng trong bảng phải là duy nhất nên việc quản lí dễ dàng hơn. Vậy CSDL là một tập các DL về các đối tượng cần quản lí, được lưu trữ đồng thời trên các vật mang tin của máy tính điện tử và được quản lí theo một cơ chế thống nhất gọi là hệ quản lí CSDL nhằm thực hiện ba chức năng sau đây một cách tối ưu: mo tả DL, cập nhật DL, tìm kiếm DL. CSDL là một bộ phận không thể thiếu được trong các hệ lưu trữ và tìm kiếm thông tin, các hệ thống quản lí kinh tế các ngành các cấp, các hệ thống quản lí kho hàng, tư liệu, các hệ thống phục vụ công cộng như ngân hàng, bán vé máy bay và các phương tiện giao thông , các hệ thống thiết kế tự động ……… 2. Hệ quản trị CSDL: Đó là hệ thống phần mềm giúp cho người sử dụng khai thác các CSDL theo ba chức năng nói trên. Còn các CSDL là đối tượng quản lí của các HCSDL. Chúng được tạo lập và lưu trữ trên các vật mang tin ngoài. Hệ QTCSDL có nhiệm vụ rất quan trọng, như một bộ miễn dịch với ngôn ngữ bậc cao nhằm giúp người sử dụng có thể dùng được hệ thống mà ít nhiều không cần quan tâm đến thuật toán chi tiết hoặc biểu diễn DL trong máy. CSDL có người quản trị CSDL. Người quản trị CSDL có nhiệm vụ quản lí và theo dõi toàn bộ các thủ tục sau đây : _Nạp DL vào CSDL _Xoá DL ra khỏi CSDL _Sửa DL trong CSDL _Tạo lập CSDL _Tìm kiếm và xuất DL _Bảo trì DL trong CSDL không bị sai hỏng do các truy nhập không được phép hoặc không đúng qui cách dẫn đến sự sai lệch hoặc mất mát DL CSDL có một lớp người sử dụng cũng được phép thực hiện các thao tác như người quản trị nhưng giới hạn ở góc độ khai thác DL. Người sử dụng tuỳ theo vai trò ,trách nhiệm của mình được người quản trị cho phép sử dụng một phần nào đó của CSDL và với phần đó họ được phép thực hiện một số thao tác nhất định. Nếu người sử dụng là một nhân viên bán hàng tại một quầy nào đó thì có thể thông qua MTĐT theo dõi những mặt hàng bán được tại quầy của mình bao gồm các mục : mã hàng, tên hàng , giá đơn vị , thành tiền, số lượng còn lại , tổng số tiền đã bán…. Và được phép nạp DL, sửa ,xóa DL phản ánh đúng biến động của các mặt hàng có trong quầy của mình. Còn các DL khác , mặc dù được lưu trữ trên cùng một MTĐT thậm chí lưu trữ trong cùng một CSDL sẽ là” khuất “đối với người này. DL khuất có thể là thông tin về các quầy khác, tổng thu chi của cửa hàng, danh sách và thông tin chi tiết về các nhân viên ….. Tóm lại, mặc dù DL được lưu trữ chung trong một CSDL nhưng mỗi người sử dụng chỉ được nhìn vào CSDL qua một cái chung và họ cảm thấy CSDL chỉ vào cái khung đó thôi, như là dành riêng cho họ vậy. Hệ QTCSDL là những chương trình máy tính giúp cho ta thực hiện các thao tác trên. Vậy là các phần mềm như DBASE, FOXBASE, SYSTEM-R, IMS là những HCSDL. Các đối tượng do hệ thống trên tạo lập là các CSDL 3. Kiến trúc một HCSDL Một CSDL được phân nhánh các mức khác nhau như hình dưới. Ở đây cá thể xem như chỉ có một CSDL đơn giản và có một hệ phần mềm QTCSDL Phần mềm CSDL vật lí là tập các tệp DL theo một cấu trúc nào đó được lưu trên các thiết bị nhớ thứ cấp ( đĩa, băng từ….) CSDL mức khái niệm là một sự biểu diễn trừu tượng của CSDL vật lí. Các khung nhìn là cách nhìn là quan niệm của từng người sử dụng đối với CSDL mức khái niệm thực chất là không lớn Khung nhìn 1 Khung nhìn 2 Khung nhìn n  CSDL mức vật lí CSDL mức khaí niệm(logic) Thể hiện Một khi CSDL đã được thiết kế , thường người ta quan tâm tới “bộ khung” hay còn gọi là “mẫu” của CSDL. DL hiện có trong CSDL gọi là thể hiện CSDL, mặc dù khi DL thay đổi thao một chu kì thời gian nào đó thì “bộ khung” của CSDL vẫn không thay đổi Lược đồ Thường “bộ khung” nêu trên bao gồm một số danh mục , hoặc chỉ tiêu hoặc một số kiểu của các thực thể trong CSDL. Giữa các thực thể có thể có một mối quan hệ nào đó với nhau. Ở đây sử dụng thuật ngữ “lược đồ” để thay cho khái niệm “ bộ khung”. Lược đồ khái niệm là bộ khung của CSDL khái niệm ,còn lược đồ vật lí dùng cho bộ khung của CSDL mức vật lí, khung nhìn được gọi là Lựơc đồ con Tính độc lập DL Theo hình trên từ khung nhìn tới CSDL khái niệm và CSDL vật lí cho thấy có hai mức “ độc lập DL”. Thứ nhất : Lược đồ vlí có thể thay đổi do người quản trị CSDL mà không cần thay đổi lược đồ khái niệm hoặc các lược đồ con . việc tổ chức lại CSDL vật lí có thể làm thay đổi hiệu quả tính toán của các chương trình ứng dụng nhưng không đòi hỏi phải viết lại các chương trình đó . tính độc lập này gọi là độc lập DL mức vật lí Mối quan hệ giữa các khung nhìn và lược đồ khái niệm cho thêm một loại độc lập nữa, gọi là độc lập DL logic.khi sử dụng một CSDL , có thể cần thiết phải thay đổi lược đồ khái niệm như thêm thông tin về các loại khác nhau của các thực thể hoặc bớt , xóa các thông tin về các thực thể đang tồn tại trong CSDL . việc thay đổi lược đồ khái niệm không làm ảnh hưởng tới các lược đồ con đang tồn tại , do đó không cần thiết phải thay đổi các chương trình ứng dụng Vì thế, tính độc lập DL là mục tiêu chủ yếu của các hệ CSDL. Có thể định nghĩa tính độc lập CSDL là “ tính bất biến của các hệ ứng dụng đối với các thay đổi trong cấu trúc lưu trữ và chiến lược truy nhập” Có ba loại mô hình CSDL cơ bản là mô hình lưới , mô hình phân cấp, mô hình quan hệ. Trong ba loại mô hình này thì mô hình quan hệ có nhiều ưu điểm và được nhiều người quan tâm nhất, bởi lẽ mô hình quan hệ có tính độc lập DL cao,lại dễ dàng sử dụng. Điều quan trọng hơn cả, mô hình quan hệ được hình thức hoá toán học tốt , do đó được nghiên cứu, phát triển và cho được nhiều kết quả lí thuyết cũng như ứng dụng trong thực tiễn . Trên cơ sở mô hình DL quan hệ , đến nay đã phát triển thêm một số loại mô hình khác nhằm mô tả và thể hiện thế giới thực một cách chính xác và phù hợp hơn như mô hình quan hệ thực thể , mô hình DL hướng đối tượng. II.Một số vấn đề khi thiết kế CSDL: Phụ thuộc dữ liệu là các mối ràng buộc có thể có giữa các giá trị hiện hữu của các lược đồ, chẳng hạn thuộc tính này xác định duy nhất thuộc tính kia. Chúng ta xét lược đồ quan hệ sau và xem xét các vấn đề nảy sinh để qua đó có thể thiết kế một CSDL thế nào là tối ưu nhất. Ví dụ về việc phân công lái máy bay: phanCong (PHICONG, MAYBAY, NGAYKH, GIOKH) Với các thuộc tính : tên phi công(PHICONG), số máy bay(MAYBAY), ngày khởi hành(NGAYKH), giờ khởi hành(GIOKH). Dư thừa dữ liệu: Dễ dàng thấy một phi công sẽ lái nhiều máy bay nên tên của phi công sẽ lặp lại trong nhiều bộ quan hệ trên lược đồ này. Cụ thể là tên của người này sẽ lặp lại trong quan hệ. Không nhất quán: Là hệ quả của việc dư thừa DL, vì khi tên của phi công lặp lại trong nhiều bộ ,khi sửa thì chỉ có thể sửa ở một bộ nào đó còn các bộ khác vẫn giữ nguyên. Khi đó xảy ra hiện tượng một phi công có nhiều tên. 3. Bất thường khi thêm bộ: Nếu một phi công mới tuyển chưa lái một máy bay nào cả, khi thêm một bộ giá trị về phi công này để theo dõi thì nhà quản lí không biết phải đưa giá trị gì vào thuộc tính máy bay và ngày, giờ khởi hành. 4. Bất thường khi xoá bộ : Nếu một phi công vì một lí do nào đó mà chỉ lái một máy bay nhất định thì khi đó trong quan hệ chỉ có một bộ lưu trữ DL về phi công này. Khi muốn xoá DL về chuyến bay này thì sẽ làm mất thông tin về phi công này. Qua các vấn đề nảy sinh khi thiết kế CSDL cần tìm ra một sự thay thế tốt mà nội dung nghiên cứu đề tài sẽ cho phép giải đáp cho những vấn đề trên. B.Nội dung. I.Lược đồ quan hệ: 1.Định nghĩa: Lược đồ quan hệ a là một cặp , trong đó u= { A1,A2,……,An} là tập các thuộc tính, F là tập các phụ thuộc hàm trên u. Ví dụ: a= với u= ABCD, F= { AB C, BD AC, C D} Quan hệ R được gọi là quan hệ có lược đồ a nếu tập thuộc tính của R là u và thoả tập phụ thuộc hàm F. 2.Phép tách các lược đồ quan hệ: ∩ Phép tách một lược đồ quan hệ R={A1,A2,…..,An} là việc thay thế lược đồ quan hệ R bằng các lược đồ{ R1, R2,…,Rn}, trong đó Ri R, i=1,…..,k và R=R1 U R2 U…..U Rk. Ở đây không đòi hói các lược đồ Ri phải là phân biệt. Mục tiêu của phéo tách chủ yếu là loại bỏ các bất thường DL gây ra như đã nêu ở trên. 3.Chuẩn hoá lược đồ quan hệ: Do việc cập nhập DL gây nên những bất thường cho nên các quan hệ cần thiết phải được biến đổi thành các dạng phù hợp. Quá trình đó được gọi là quá trình chuẩn hoá, quan hệ được chuẩn hoá thì mỗi miền của thuộc tính chỉ chứa những giá trị nguyên tố tức là không thể phân nhỏ được nữa. Quan hệ có chứa các miền giá trị là không nguyên tố gọi là quan hệ không chuẩn hoá. Một quan hệ được chuẩn hoá có thể thành một hoặc nhiều quan hệ chuẩn hóa khác và không làm mất thông tin. II.Phụ thuộc hàm. 1.Khái niệm và vai trò của phụ thuộc hàm trong xây dựng CSDL: 1.1 Khái niệm phụ thuộc hàm: Phụ thuộc hàm (functional dependency) là một công cụ dùng để biểu diễn một cách hình thức các ràng buộc toàn vẹn (vắn tắt: ràng buộc). Phương pháp biểu diễn này có rất nhiều ưu điểm, và đây là một công cụ cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ sở 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 thiểu và chuẩn hóa cơ sở dữ liệu. Ở đây sẽ trình bày khái niệm một cách hình thức : a. Định nghĩa phụ thuộc hàm: Q(A1,A2,...,An) là lược đồ quan hệ. X, Y là hai tập con của Q+={A1,A2,...,An}. r là quan hệ trên Q. t1,t2 là hai bộ bất kỳ của r. X Y (t1.X = t2.X thì t1.Y = t2.Y) (Ta nói X xác định Y hay Y phụ thuộc hàm vào X (X functional determines Y,Y functional dependent on X ). Xét ví dụ phanCong trên ta thấy: Quan hệ phanCong diễn tả phi công nào lái máy bay nào và máy bay khởi hành vào thời gian nào. Không phải sự phối hợp bất kỳ nào giữa phi công, máy bay và ngày giờ khởi hành cũng đều được chấp nhận mà chúng có các điều kiện ràng buộc qui định sau: + Mỗi máy bay có một giờ khởi hành duy nhất. + Nếu biết phi công, biết ngày giờ khởi hành thì biết được máy bay do phi công ấy lái. + Nếu biết máy bay, biết ngày khởi hành thì biết phi công lái chuyến bay ấy. Các ràng buộc này là các ví dụ về phụ thuộc hàm và được phát biểu lại như sau: + MAYBAY xác định GIOKH + {PHICONG,NGAYKH,GIOKH} xác định MABAY + {MAYBAY,NGAYKH} xác định PHICONG hay + GIOKH phụ thuộc hàm vào MAYBAY + MABAY phụ thuộc hàm vào {PHICONG,NGAYKH,GIOKH} + PHICONG phụ thuộc hàm vào {MAYBAY,NGAYKH} và được ký hiệu như sau: + {MAYBAY} GIOKH + {PHICONG,NGAYKH,GIOKH} MABAY + {MAYBAY,NGAYKH} PHICONG b.Một số tính chất của phụ thuộc hàm: Định lí: phụ thuộc hàm trên tập thuộc tính thoả các tính chất sau đây: ∩ ∩ ∩ F1. Tính phản xạ : Nếu X, Y UvàY X thì X Y. ∩ ∩ F2. Tính bắc cầu : Nếu X, Y, Z U,X Y và Y Z thì X Z. F3. Tính mở rộng hai vế:Nếu X Y, X, Y U thì với mọi Z U ta có XZ YZ ∩ ∩ F4. Tính tựa bắc cầu : Nếu X Y, YZ W; X, Y, Z,W U thì XZ W . ∩ F5. Tính phản xạ chặt: Với mọi X U ta có X X. ∩ ∩ F6. Mở rộng vế trái và thu hẹp vế phải : Nếu X Y; X,Y U thì với mọi Z u và W U ta có XZ Y/W. F7.Cộng tính đầy đủ: Nếu X Y và Z W; X, Y, Z, W U thì XZ YW ∩ ∩ F8. Mở rộng vế trái : Nếu X Y thì với mọi Z U ta có XZ Y. F9. Cộng tính ở vế phải: Nếu X Y và X Z; X, Y, Z U thì X YZ. ∩ F10. Bộ phận ở vế phải: Nếu X YZ; X, Y, Z U thì X Y ∩ ∩ F11. Tính tích luỹ: Nếu X YZ; Z AW; X, Y, Z,W U; A U thì X YZA. Những tính chất trên đã được chứng minh và thừa nhận tính đúng đắn của nó nên ở đây chỉ nêu ra các tính chất cho người sử dụng tìm hiểu. c. Thuật toán Satifies: Cho quan hệ r và X, Y là hai tập con của Q+. Thuật toán SATIFIES sẽ trả về trị true nếu X Yngược lại là false SATIFIES Vào: quan hệ r và hai tập con X,Y. Ra: true nếu X Y, ngược lại là false SATIFIES(r,X,Y) 1. Sắp các bộ của quan hệ r theo X để các giá trị giống nhau trên X nhóm lại với nhau 2. Nếu tập các bộ cùng giá trị trên X cho các giá trị trên Y giống nhau thì trả về true ngược lại là False Ví dụ 1: SATIFIES(phanCong,MAYBAY,GIOKH) phanCong (PHICONG, MAYBAY, NGAYKH, GIOKH) Phi Công Máy Bay Ngày KH Giờ KH Dương 83 9/8 10:15a Hà 83 11/8 10:15a Tuấn Anh 83 13/8 10:15a Dương 116 10/8 1:25p Tuấn Anh 116 12/8 1:25p Hà 281 8/8 5:50a Thành 281 9/8 5:50a Thành 281 13/8 5:50a Tuấn Anh 301 12/8 6:35p cho kết quả là true nghĩa là {MAYBAY} GIOKH Ví dụ 2: SATIFIES(phanCong,GIOKH,MAYBAY) phanCong (PHICONG, MAYBAY, NGAYKH, GIOKH) Phi Công Máy Bay Ngày KH Giờ KH Tuấn Anh 281 8/8 5:50a Dương 281 9/8 5:50a Thành 281 13/8 5:50a Hà 83 9/8 10:15a Tuấn Anh 83 11/8 10:15a Quang 83 13/8 10:15a Dương 116 10/8 1:25p cho kết quả là false nghĩa là không có phụ thuộc hàm {GIOKH} MAYBAY. 1.2. Vai trò của phụ thuộc hàm trong xây dựng CSDL: Khi thiết kế một CSDL thường đòi hỏi phải chọn các lược đồ quan hệ. Việc chọn tập các lược đồ quan hệ có thể tốt hoặc xấu hơn dựa trên một số tiêu chuẩn nào đó. Do vậy cần thiết phải nghiên cứu các tính chất cơ bản cũng như những thuật toán để có thể nhận được những tập lược đồ phù hợp. Mà trọng tâm của thiết kế các lược đồ là sự phụ thuộc DL là sự ràng buộc có thể có giữa các giá trị hiện hữu của các lược đồ. Nên phụ thuộc hàm có tầm quan trọng rất lớn đối với việc thiết kế mô hình dữ liệu. Phân tích các phụ thuộc hàm có thể có để tối ưu mô hình DL nó có ảnh hưởng trực tiếp đến hiệu quả hoạt động của hệ thống. Bên cạnh đó sử dụng các phụ thuộc hàm người sử dụng có thể chuẩn hoá các lược đồ về dạng chuẩn ba hay dạng chuẩn Boye_Codd. 2 .Các vấn đề liên quan phụ thuộc hàm trong xây dựng CSDL. 2.1. Hệ tiên đề Armstrong. ∩ Gọi F là tập các phụ thuộc hàm trên sơ đồ quan hệ R(U) và X Y là một phụ thuộc hàm, X,Y U, khi đó X Y được suy diễn logic từ F nếu với mọi quan hệ r xác định trên R(U) thoả các phụ thuộc hàm trong U thì cũng thoả các X Y. Gọi F+ là bao đóng của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. Nếu F=F+ thi F là họ đầy đủ của các phụ thuộc hàm. Để có thể xác định khoá của một lược đồ quan hệ và các suy diễn logic giữa các phụ thuộc hàm cần thiết phải tính được F+ từ F. Do đó đòi hỏi phải có các hệ tiên đề. Nên ta có hệ tiên đề Armstrong đối với các phụ thuộc hàm như sau: ∩ Gọi R(U) là lược đồ quan hệ với U={A1,A2,….,An} là tập các thuộc tính và X, Y, Z, W U được kí hiệu XY= X U Y. ∩ ∩ Hệ tiên đề Armstrong : ∩ A1. Phản xạ : Nếu Y X U thì X Y A2. Tăng trưởng : Nếu X Y, Z U thì XZ YZ. A3. Bắc cầu : Nếu X Y, Y Z thì X Z. Hệ tiên đề Armstrong là đúng: Nói rằng X Y là phụ thuộc hàm được suy diễn nhờ vào tiên đề Armstrong nếu tồn tại các tập phụ thuộc hàm F0 F1 ... Fn sao cho X Y với F0,F1,...,Fn lần lượt được hình thành thỏa phương pháp sau: Bước1: F0 = F Bươc 2:Chọn một số phụ thuộc hàm trong Fi áp dụng hệ tiên đề Armstrong để thu được một số phụ thuộc hàm mới. Đặt Fi+1= Fi {các phụ thuộc hàm mới}. Hệ quả : Hệ luật dẫn Armstrong là đúng nghĩa là nếu F là tập các phụ thuộc hàm đúng trên quan hệ r và X Y là một phụ thuộc hàm được suy diễn từ F nhờ hệ luật dẫn Armstrong thì X Y đúng trên quan hệ r. Vậy X Y là phụ thuộc hàm được suy diễn logic từ F. Hệ tiên đề Armstrong là đầy đủ: Hệ luật dẫn Armstrong là đầy đủ nghĩa là mọi phụ thuộc hàm X Y được suy diễn logic từ F sẽ được suy diễn từ F nhờ hệ tiên đề Armstrong. .Bao đóng: ∩ Tính toán bao đóng của các thuộc tính với một tập phụ thuộc hàm có thuật toán sau đây: Vào: Tập hữu hạn thuộc tính U, tập các phụ thuộc hàm F trên U và X UU Ra: X+, bao đóng của X đối với F. Phương pháp: Tính liên tiếp tập các thuộc tính X0,X1,……..,Xn theo quy tắc: ∩ X0 = X ∩ ∩ ∩ Xi+1=Xi U A sao cho tồn tại ( Y Z) є F, A є Z và Y Xi. Vì rằng X= X0 …. Xi… U, U là hữu hạn cho nên sẽ tồn tại một chỉ số I nào đó mà Xi = Xi+1 Phép tách bảo toàn tập phụ thuộc hàm. Thông thường, chúng ta mong muốn một phép tách phải có tính chất không mất mát thông tin bởi vì nó đảm bảo rằng một quan hệ nào đó có thể được phục hồi từ các quan hệ chiếu của nó. Một tính chất quan trọng nào khác của phép tách sơ đồ quan hệ R thành ρ = (R1, R2,……., Rk) là tập các phụ thuộc hàm F trên R phải được suy diễn ra bởi tập các phụ thuộc hàm chiếu cuả F trên Ri với i= 1, 2,….., k. ∩ Giả sử R là một lược đồ quan hệ với tập phụ thuộc hàm F, ρ = ( R1, R2,…, Rk) là một phép tách của R trên F. Chúng ta nói Fi là hình chiếu của F trên Ri, và kí hiệu là П Ri (F), là tập tất cả các phụ thuộc hàm X Yє F+ sao cho XY Ri chú ý rằng X Y không cần thiết thuộc F mà chỉ cần thuộc F+. Chú ý rằng phép tách ρ bảo toàn tập phụ thuộc hàm F nếu hợp của tất cả các phụ thuộc hàm trong П Ri (F) với i = 1, 2,….,k suy diễn logic ra tất cả các phụ thuộc hàm trong F. Lí do chúng ta muốn một phép tách ρ bảo toàn tập phụ thuộc hàm F là các phụ thuộc hàm trong F có thể được quan sát như các ràng buộc toàn vẹn đối với sơ đồ quan hệ R. Nếu các hình chiếu của tập phụ thuộc hàm F không suy diễn được F thì khi chúng ta thay thế R bởi ρ =(R1,.. ...,Rk), chúng ta có thể thấy rằng giá trị hiện thời của các quan hệ Ri biểu diễn quan hệ R sẽ không thoả mãn F thậm chí nếu ρ có tính chất không mất mát thông tin đối với F. Một cách lựa chọn để khắc phục có thể là mỗi cập nhật đối với một trong các quan hệ R sẽ đòi hỏi một phép kết nối để kiểm tra các ràng buộc này có vi phạm không. Các dạng chuẩn và mục đích của nó trong lược đồ quan hệ. Trước khi đưa ra các dàng chuẩn có một số định nghĩa liên quan: Định nghĩa 1: Cho R(U) là lược đồ quan hệ với U={A1, A2, …., An} là tập các thuộc tính , F là tập các phụ thuộc hàm trên R và A thuộc U. Chúng ta nói rằng A là thuộc tính khoá nếu A thuộc một khoá tối thiểu nào đó của R, ngược lại A được gọi là thuộc tính không khoá . ∩ Định nghĩa 2: Cho R(U) là lược đồ quan hệ với U={A1, A2,…..,Ak} là tập các thuộc tính, F là tập các phụ thuộc hàm trên R và X, Y U chúng ta nói rằng Y phụ thuộc hàm đầy đủ vào X nếu Y là phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào bất kì một tập con thực sự nào của X. Lược đồ quan hệ được xây dựng ở thời điểm ban đầu thường chứa nhiều nhược điểm như dư thừa dữ liệu, dễ gây ra thiếu nhất quán khi bổ sung, sửa chữa hoặc loại bỏ các dòng trong quan hệ. Chất lượng của các lược đồ quan hệ được cải thiện trên cơ sở biến đổi chuẩn. Ta có các dạng chuẩn sau: Dạng chuẩn 1: Một quan hệ R là dạng chuẩn 1(1NF) nếu các thuộc tính của nó đều đơn trị. Nói cách khác, quan hệ R đạt chuẩn 1 nếu nó không chứa các thuộc tính lặp. Giá trị tại mỗi ô của bảng (giao của cột và dòng) phải là đơn trị Dạng chuẩn2: Một quan hệ R là dạng chuẩn 2(2NF) nếu nó là 1NF và các phụ thuộc hàm giữa các thuộc tính ngoài khóa và khóa đều là các phụ thuộc hàm sơ đẳng, nói cách khác, mọi thuộc tính ngoài khóa đều không có phụ thuộc hàm vào bộ phận của khóa. Dạng chuẩn 3: Một quan hệ R là dạng chuẩn 3 (3NF) nếu nó là 2NF và các phụ thuộc hàm giữa các thuộc tính khóa ngoài và khóa đều là các phụ thuộc hàm trực tiếp-nghĩa là không tồn tại những phụ thuộc hàm ngoài khóa.*Các bước chuẩn hóa: Các bước chuẩn hóa được mô tả theo sơ đồ sau  Dạng chuẩn 1. Quan hệ là 1NF nếu không chứa các thuộc tính lặp, các thuộc tính phải là đơn, nghĩa là giá trị của các ô là giao của hàng và cột phải có giá trị đơn, như vậy, mọi quan hệ đều là 1NF. Nếu bảng dữ liệu chứa các thuộc tính lặp thì không phải quan hệ, để chuyển bảng dữ liệu có lặp thành quan hệ, có thể tách các thuộc tính lặp thành một hoặc nhiều bảng khác và nếu cần thiết thì tăng cường khóa cho các bảng mới này. Tiếp tục xem xét các bảng mới để đảm bảo sao cho các bảng này cũng là quan hệ, tức là đạt chuẩn 1. Ví dụ: Từ bảng DONHANG ban đầu với các thuộc tính: SODH,MA_KH,TEN_KH,DIA_CHI,NG_LD,MA_MH,TEN_MH,DV,SL,DG và TIEN.Chứa các thuộc tính lặp: MA_MH,TEN_MH,DV,SL,DG,TIENCác thuộc tính lặp được tách thành bảng DONG_DH, trong đó có bổ sung thuộc tính SODH từ các thuộc tính còn lại để tạo khóa. Phần còn lại của bảng DONHANG và bảng mới DONG_DH không chứa thuộc tính lặp. Các bảng này thỏa mãn các tính chất của quan hệ, chúng đều đạt chuẩn 1, ta có lược đồ sau :DONHANG(SODH,MA_KH,TEN_KH,DIA_CHI,NG_LD)DONG_DH(SODH,MA_MH,TEN_MH,DV,SL,DG,TIEN) Dạng chuẩn 2: Một quan hệ R là dạng chuẩn 2(2NF) nếu nó là 1NF và các phụ thuộc hàm giữa các thuộc tính ngoài khóa và khóa đều là các phụ thuộc hàm sơ đẳng, nói cách khác, mọi thuộc tính ngoài khóa đều không có phụ thuộc hàm vào bộ phận của khóa. Nếu quan hệ R chứa những thuộc tính có phụ thuộc hàm vào một bộ phận của khóa thì cần tách các nhóm thuộc tính phụ thuộc vào bộ phận của khóa và bổ sung thêm cho các nhóm này một phần khóa mà chúng có phụ thuộc hàm, để thành quan hệ. Nhóm còn lại tạo thành một quan hệ với khóa như cũ. Các quan hệ được tạo lập đều là 2NF. Ví dụ: Xét quan hệ DONG_DH có lược đồ: DONG_DH(SODH,MA_DH,TEN_MH,DV,SL,DG,TIEN)Giả thiết là đơn giá bán không phụ thuộc vào từng đơn hàng, các phụ thuộc hàm trực tiếp trong quan hệ sẽ là: MA_MH {TEN_MH,DV,DG} SODH,MA_MH {SL,TIEN} Rõ ràng DONG_DH không phải là 2NF, tách các thuộc tính TEN_MH, DV,DG có phụ thuộc hàm vào bộ phận MA_MH của khóa thành một nhóm. Nhóm còn lại SODH,MA_DH,SL,TIEN là quan hệ 2NF: DONG_DH(SODH,MA_DH, SL,TIEN) Nhóm bị tách ra sẽ được bổ sung bộ phận của khóa MA_MH và nhận MA_MH làm khóa. Đó là quan hệ 2NF: MATHANG1(MA_MH,TEN_MH,DV,DG) Dạng chuẩn 3: : Một quan hệ R là dạng chuẩn 3 (3NF) nếu nó là 2NF và các phụ thuộc hàm giữa các thuộc tính khóa ngoài và khóa đều là các phụ thuộc hàm trực tiếp-nghĩa là không tồn tại những phụ thuộc hàm ngoài khóa.. Nếu R không phải là 3NF, nghĩa là trong R tồn tại thuộc tính không phụ thuộc hàm trực tiệp vào khóa, thì tách các nhóm thuộc tính có phụ hàm vào thuộc tính khóa thành một quan hệ. Khóa của quan hệ mới này chính là thuộc tính mà chúng có phụ thuộc hàm.Ví dụ: quan hệ DONHANG đã xét ở phần chuẩn 1NF không phải là 3NF: DONHANG(SODH,MA_KH,TEN_KH,DIA_CHI,NG_LD)Có các phụ thuộc hàm trực tiếp: SODH {MA_KH,NG_LD} MA_KH {TEN_KH,DIA_CHI} Nhóm mới này được tách ra gồm có MA_KH,TEN_KH và DIA_CHI. Thuộc tính MA_KH sẽ là khóa của quan hệ mới này. Nhóm còn lại tạo thành một quan hệ với khóa như cũ : DONHANG(SODH,MA_KH,NG_LD)KHACHHANG(MA_KH,TEN_KH,DIA_CHI) Dạng chuẩn Boye_Codd: Một sơ đồ quan hệ R với tập phụ thuộc hàm F được gọi là dạng chuẩn Boye_Codd nếu mọi X A thuộc F+ và A không thuộc X thì X chứa một khoá của R. Nói cách khác,sơ đồ quan hệ R chỉ có các phụ thuộc hàm không tầm thường là những phụ thuộc hàm trong đó một khoá xác định hàm một hay nhiều thuộc tính khác. Tách không mất mát thông tin về dạng chuẩn Boye_Codd có bổ đề sau: _Giả sử R là một sơ đồ quan hệ với tập phụ thuộc hàm F. Đặt ρ =R1,R2,….,Rk) là một phép tách không mất mát thông tin của R đối với F. Với mỗi i=1,2,…,k gọi Fi là hình chiếu của F trên Ri, và đặt σ =(S1,S2,….,Sm) là một phép tách không mất mát thông tin của Ri đối với Fi. Thì phép tách R thành ( R1,….,Ri-1,S1,S2,….,Sm,Ri+1,..,Rk) là không mất mát thông tin đối với F _ Giả sử có R, F và ρ như trên , π = (R1,R2,…,Rk,Rk+1,….,Rn) là một phép tách của R thành tập các sơ đồ chứa các sơ đồ của ρ thì π là một phép tách không mất mát thông tin. Thuật toán tách không mất mát thông tin về dạng chuẩn Boye_Codd Vào : Sơ đồ quan hệ R, tập phụ thuộc hàm F trên R. Ra: ρ- một phép tách không mất mát thông tin bao gồm một tập các sơ đồ con trong đó mỗi sơ đồ đều ở dạng chuẩn Boye_Codd với các phụ thuộc hàm là hình chiếu của F lên sơ đồ đó. Phương pháp: _ Chúng ta xây dựng một phép tách ρ đối với R theo phương pháp lặp. Mỗi lần lặp ρ sẽ được tách tiếp với một phép tách không mất mát thông tin đối với F. _ Ban đầu đặt ρ =(R) nếu S là một sơ đồ quan hệ trong ρ không ở dạng chuẩn Boye_Codd, xét một phụ thuộc hàm X A cuả S, với điều kiện X không chứa khoá của S và A є X. Ta thay thế S bởi S1, S2 với S1 = A U {X}, S2 = {S} \ A. _ Tiếp tục quá trình cho đến khi mọi sơ đồ con đều ở dạng chuẩn Boye_Codd chúng ta sẽ dây dựng được phép tách không mất mát thông tin chuẩn hoá R về dạng chuẩn Boye_Codd.  III. Phụ thuộc đa trị. Khái niệm và vai trò của phụ thuộc đa trị trong xây dựng CSDL. Khái niệm phụ thuộc đa trị. Phần trước người nghiên cứu đã được xem xét một loại DL giữa các tập thuộc tính của các sơ đồ quan hệ là phụ thuộc hàm và sử dụng phụ thuộc hàm để chuẩn hoá các lược đồ quan hệ về dạng chuẩn ba và dạng chuẩn Boye_Codd. Tuy nhiên, trong thực tế phụ thuộc hàm không phải là loại phụ thuộc duy nhất xuất hiện trong các quan hệ mà còn có những phụ thuộc khác nữa cũng là nguyên nhân gây nên sự dư thừa dữ liệu và vấn đề không nhất quán dữ liệu. Như một máy bay không phải chỉ xác định một ngày giờ khởi hành mà là nhiều ngày giờ khởi hành khác nhau. Mối quan hệ này được gọi là phụ thuộc đa trị. Có thể hình thức hoá phụ thuộc đa trị qua định nghĩa sau: Gọi R là một lược đồ quan hệ, X và Y là hai tập con của R, Z= R-XY. Quan hệ r(R) thoả phụ thuộc đa trị X Y nếu với bất kì hai bộ t1Є r, t2 Є r với t1[X] =t2[X] tồn tại một bộ t3 Є r sao cho t3[X] =t1[X], t3[Y]= t1[Y] và t3[Z] =t2[Z]. Do tính chất đối xứng của t1 và t2 dễ dàng thấy rằng trong r còn tồn tại một bộ t4 mà t4[X] = t1[X], t4[Y] = t2[Y] và t4[Z]= t1[Z]. Từ định nghĩa phụ thuộc đa trị suy ra: ∩ _Nếu X Y thoả trên quan hệ r thì X Y cũng thoả trên r, do vậy có thể thấy phụ thuộc hàm là trường hợp đặc biệt của phụ thuộc đa trị. ∩ _ Bổ đề: với mọi tập thuộc tính X, Y và U sao cho X, Y U, phụ thuôc đa trị X Y là thoả quan hệ r(U) khi và chỉ khi X Y – X thoả trên r(U). _ Định lí : Cho r là quan hệ của lược đồ R(U) , X, Y U và Z = U-XY. Quan hệ r thoả phụ thuộc đa trị X Y khi và chỉ khi r được tách không mất mát thông tin thành hai quan hệ trên các lược đồ tương ứng R1 = R[XY] và R2= R[XZ]. Vai trò của phụ thuộc đa trị trong xây dựng CSDL. Cũng giống như phụ thuộc hàm, phụ thuộc đa trị cũng cần được phân tích và nghiên cứu để từ đó lập trình viên thiết kế CSDL tối ưu nhất tránh được sự dư thừa hay bất thường về DL. Nhằm phục vụ tốt nhất đáp ứng được đòi hỏi yêu cầu của người sử dụng. Chính vì thế mà người phân tích thiết kế không được coi nhẹ vai trò của phụ thuộc đa trị vì chính nó cũng là một nguyên nhân nảy sinh các vấn đề đã nêu ở phần trước. Các vấn đề liên quan phụ thuộc đa trị trong xây dựng CSDL. Hệ tiên đề đối với phụ thuộc hàm và phụ thuộc đa trị: ∩ ∩ ∩ Gọi R(U) là lược đồ quan hệ với U={A1,A2,……,An} là tập các thuộc tính và X, Y, Z, W U. Kí hiệu XY =X U Y. ∩ A1: phản xạ đối với phụ thuộc hàm : NếuY X U thì X Y. A2: Tăng trưởng đối với phụ thuộc hàm: Nếu X Y, Z U thì XZ YZ. A3: Bắc cầu đối với phụ thuộc hàm : Nếu X Y, Y Z thì X Z. ∩ A4: Luật bù đối với phụ thuộc đa trị: Nếu X Y thì X U \ XY. A5: Tăng trưởng đối với phụ thuộc đa trị : Nếu X Y, và V W thì X VY . A6: Bắc cầu đối với phụ thuộc đa trị: Nếu X Y, Y Z thì X Z \ Y. ∩ A7: Nếu X Y thì X Y. A8: Nếu X Y, W Z với Z Y và W ∩Y=O thì X Z. Các luật suy diễn bổ sung đối với các phụ thuộc đa trị. _ Luật hợp: Nếu X Y, X Z thì X YZ. _ Luật tựa bắc cầu: Nếu X Y,WY Z thì WX Z\WY. _ Luật tựa bắc cầu hỗn hợp : Nếu X Y, XY Z thì X Z\Y. _ Luật tách: Nếu X Y,X Z thì X Y ∩ Z,X Y\Z,X Z\Y. 2.3. Bao đóng của tập phụ thuộc hàm và phụ thuộc đa trị. Cho một tập các phụ thuộc hàm và phụ thuộc đa trị._.