CÁC KIẾN THỨC CHUẨN BỊ
Các khái niệm cơ bản
Dữ liệu: Dữ liệu là các sự kiện, văn bản, đồ họa, hình ảnh và đoạn phim video có ý nghĩa trong môi trường người dùng
Thông tin: Thông tin là dữ liệu được xử lý để tăng hiểu biết của người dùng về dữ liệu này
Cơ sở dữ liệu là tập hợp các dữ liệu liên quan, chứa thông tin của một tổ chức như công ty, xí nghiệp hay trường học Những dữ liệu này được lưu trữ trên thiết bị nhớ ngoài, phục vụ nhu cầu khai thác thông tin của nhiều người dùng với các mục đích khác nhau.
Hình 1.1: Quan hệ giữa thông tin, dữ liệu và cơ sở dữ liệu
Hệ quản trị cơ sở dữ liệu là phần mềm chuyên dụng giúp quản lý và xử lý dữ liệu trong cơ sở dữ liệu một cách hiệu quả.
Hệ quản trị cơ sở dữ liệu (CSDL) đóng vai trò quan trọng trong việc giúp người dùng tương tác với hệ thống mà không cần hiểu sâu về thuật toán hay cách biểu diễn dữ liệu Một số hệ quản trị CSDL phổ biến hiện nay bao gồm Oracle, SQL Server, DB2 và MySQL.
Lưu trữ có chọn lọc
Hình 1.2: Hệ thống Cơ sở dữ liệu
Tổ chức dữ liệu hiệu quả là yếu tố quyết định để xây dựng một hệ thống cơ sở dữ liệu (CSDL) chất lượng, giúp người quản trị dễ dàng quản lý và điều hành hệ thống.
Chức năng của hệ quản trị cơ sở dữ liệu: a Thiết lập cơ sở dữ liệu:
Định nghĩa b Cập nhật dữ liệu:
Bổ sung dữ liệu vào cơ sở dữ liệu
Loại bỏ dữ liệu khỏi cơ sở dữ liệu
Sửa dữ liệu trong cơ sở dữ liệu c Khai thác dữ liệu trong cơ sở dữ liệu
Tìm kiếm thông tin theo yêu cầu
Kết xuất thông tin theo yêu cầu.
Sơ đồ cơ sở dữ liệu quan hệ
Là đối tƣợng có trong thực tế mà chúng ta cần khảo sát và giải quyết nhiều vấn đề liên quan đến đối tƣợng này
Tên thực thể: Là tên của một đối tƣợng Trong 1 CSDL, tên thực thể không đƣợc trùng nhau
Ví dụ: Thực thể xe máy, thực thể giáo viên, nhân viên, thực thể hóa đơn bán hàng,…
Tiêu chuẩn xác định thực thể:
Có ích cho quản lý
Phân biệt đƣợc giữa các thực thể với nhau
Kiểu thực thể là tập hợp các đối tượng cùng loại, được hình thành dựa trên những đặc trưng giống nhau Nói cách khác, kiểu thực thể đại diện cho các thực thể có những đặc điểm chung, giúp phân loại và mô tả chúng một cách rõ ràng.
Ví dụ: Một Sinh viên là một thực thể, tập hợp các sinh viên của cùng một hệ thống tạo thành một kiểu thực thể
Thuộc tính là giá trị dùng để mô tả một khía cạnh của thực thể hoặc liên kết, giúp phân biệt thực thể này với thực thể khác.
Ví dụ: Thực thể Xe máy có các thuộc tính sau: Mã_Xe, Tên_Xe, Số_Máy,
Thực thể Sinh viên có các thuốc tính: Mã_SV, Họ_Tên, Ngày_Sinh, Giới_Tính Các kiểu của thuộc tính:
Thuộc tính nguyên tố là những đặc điểm không thể chia nhỏ hơn của một thực thể, chẳng hạn như Giới tính và Ngày sinh của sinh viên.
Thuộc tính đơn trị: Là thuộc tính mà mỗi thực thể chỉ có thể nhận nhiều nhất một giá trị Ví dụ: Giới Tính, Ngày Sinh,…
Thuộc tính đa trị: Là thuộc tính mà mỗi thực thể có thể có nhiều giá trị tại một thời điểm Ví dụ thuộc tính Số diện thoại
Thuộc tính phức hợp: Là thuộc tính đƣợc kết hợp của một số thành phần
Ví dụ: Địa_Chỉ( Xã, Huyện, Tỉnh ) hoặc Họ_Tên( Họ, Tên ) là thuộc tính phức hợp
Thuộc tính dẫn xuất là thuộc tính mà giá trị của nó được suy ra từ các thuộc tính khác Chẳng hạn, thuộc tính Tuổi có thể được tính toán từ Ngày_Sinh, trong khi thuộc tính Thành_Tiền có thể được xác định từ Số_Lượng và Đơn_Giá.
1.2.3 Mối liên kết giữa các thực thể
Liên kết (Relationship) thể hiện mối quan hệ giữa các thực thể khác nhau, chẳng hạn như nhân viên A và nhân viên B cùng làm việc cho dự án X Các liên kết cùng loại được nhóm lại thành kiểu liên kết, ví dụ như kiểu liên kết Làm_Việc (làm việc cho) và kiểu liên kết Quản_Lý (làm quản lý).
Bậc của kiểu liên kết là số lƣợng các kiểu thực thể tham gia vào liên kết
Ràng buộc liên kết là những quy định xác định các thực thể có thể kết hợp trong một liên kết nhất định Những ràng buộc này phản ánh tình huống thực tế mà liên kết đó đại diện Có nhiều loại ràng buộc khác nhau trong các mối quan hệ này.
- Về tỷ số lực lƣợng:
Liên kết 1-1 (liên kết một-một) xảy ra khi hai thực thể A và B tương tác với nhau theo cách mà một thực thể kiểu A chỉ kết hợp với một thực thể kiểu B và ngược lại Ví dụ điển hình của liên kết này là trong quản lý, nơi một nhân viên quản lý một phòng và mỗi phòng chỉ có một nhân viên quản lý duy nhất.
Liên kết 1-n (liên kết một nhiều) mô tả mối quan hệ giữa hai thực thể A và B, trong đó một thực thể kiểu A có thể liên kết với nhiều thực thể kiểu B, nhưng mỗi thực thể của B chỉ liên kết với một thực thể kiểu A Ví dụ điển hình là một nhân viên làm việc cho một phòng, trong khi một phòng có thể có nhiều nhân viên làm việc.
Liên kết n-n (liên kết nhiều nhiều ): Hai thực thể A và B có mối liên kết n- n nếu một thực thể kiểu A liên kết với nhiều thực thể kiểu B và ngƣợc lại
Ví dụ: Một nhân viên có thể làm việc cho nhiều dự án và một dự án có thể có nhiều nhân viên làm việc
Sự tham gia được xác định qua từng thực thể trong các kiểu liên kết mà thực thể đó tham gia, bao gồm lực lượng tham gia toàn bộ và lực lượng tham gia bộ phận.
Ví dụ: Trong kiểu liên kết QUẢN_LÝ giữa hai kiểu thực thể NHÂN_VIÊN và
Trong hệ thống quản lý, kiểu thực thể PHÒNG bao gồm toàn bộ lực lượng tham gia, vì mỗi NHÂN_VIÊN đều có người quản lý Ngược lại, lực lượng tham gia của kiểu thực thể NHÂN_VIÊN chỉ là bộ phận, do không phải tất cả NHÂN_VIÊN đều đảm nhận vai trò quản lý trong PHÒNG.
Một quan hệ là một bảng dữ liệu hai chiều bao gồm cột và dòng, dùng để mô tả một kiểu thực thể Mỗi cột đại diện cho một thuộc tính của thực thể, trong khi mỗi dòng chứa các giá trị dữ liệu tương ứng với một đối tượng cụ thể thuộc thực thể đó.
Các tính chất của một quan hệ:
Các giá trị trong cùng một cột phải thuộc cùng một miền giá trị (cùng kiểu dữ liệu)
Thứ tự các dòng, các cột tuỳ ý
1.2.5 Khóa của một sơ đồ quan hệ
Mỗi quan hệ trong cơ sở dữ liệu có một hoặc nhiều thuộc tính với giá trị duy nhất để phân biệt các bản ghi Thuộc tính này được gọi là khoá của sơ đồ quan hệ Trong một lược đồ quan hệ R, có thể tồn tại nhiều khoá, trong đó một khoá được chọn làm khoá chính (primary key) và các khoá còn lại được gọi là khoá dự phòng.
Khóa ngoại (Foreign key) trong sơ đồ quan hệ R là một tập thuộc tính K tham chiếu đến một tập thuộc tính có ràng buộc duy nhất của một lược đồ quan hệ khác Đặc biệt, tập thuộc tính này cũng có thể là khóa chính.
Phụ thuộc hàm và các tính chất
Khi thiết kế cơ sở dữ liệu quan hệ, việc lựa chọn lược đồ quan hệ phù hợp là rất quan trọng Để đưa ra quyết định đúng đắn, cần chú ý đến mối ràng buộc giữa các dữ liệu, đặc biệt là các phụ thuộc hàm.
Phụ thuộc hàm là mối quan hệ giữa các thuộc tính trong cơ sở dữ liệu quan hệ, đóng vai trò quan trọng trong thiết kế mô hình dữ liệu Nó chỉ ra rằng giá trị của một thuộc tính được xác định duy nhất bởi giá trị của thuộc tính khác.
Trong cơ sở dữ liệu (CSDL), tồn tại nhiều mối liên hệ giữa các thuộc tính và các bộ, có thể xảy ra trong cùng một quan hệ hoặc giữa các quan hệ trong lược đồ CSDL Những mối liên hệ này là điều kiện bất biến mà tất cả các bộ của các quan hệ liên quan phải thỏa mãn mọi lúc, được gọi là ràng buộc toàn vẹn Phụ thuộc hàm là công cụ biểu diễn hình thức cho một dạng ràng buộc toàn vẹn Theo định nghĩa, trong lược đồ quan hệ R(U), tập thuộc tính Y được gọi là phụ thuộc hàm vào tập thuộc tính X nếu hai bộ bất kỳ trong mỗi quan hệ r ⊆ R(U) có cùng giá trị trên X thì cũng phải có cùng giá trị trên Y.
Y phụ thuộc vào X nếu hai dòng bất kỳ có các giá trị thuộc tính X bằng nhau từng cặp thì các giá trị trên tập thuộc tính Y cũng phải bằng nhau.
Y cũng phải bằng nhau từng cặp một
Ví dụ: Cho quan hệ R = Học_Sinh
Mã SV Họ tên Năm sinh Số_điện_thoại Email
107058 Trần Tuấn Anh 12/08/1963 01698745457 tuananh93@gmail.com
157017 Lê Thị Hoa 11/02/1992 0978416827 hoalethi@yahoo.com
798542 Bùi Tiến Thịnh 28/12/1993 0912654824 tienthinh4@gmail.com
Bảng 2.1: Quan hệ Học_sinh
Theo định nghĩa, khi có mã sinh viên, chúng ta có thể xác định được các thông tin quan trọng như Họ tên, Ngày sinh, Số điện thoại và Email của sinh viên.
Mã SV Số điện thoại
Các phụ thuộc dữ liệu là yếu tố quan trọng trong thiết kế cơ sở dữ liệu, với lớp phụ thuộc hàm là một trong những loại phụ thuộc đầu tiên Nghiên cứu về lớp phụ thuộc hàm trong cơ sở dữ liệu quan hệ đã được Amstrong thực hiện.
Gọi R là quan hệ trên tập thuộc tính U Khi đó với các thuộc tính X,Y, Z, W U ta có hệ tiên đề Amstrong [3] nhƣ sau :
2) Tăng trưởng : Nếu W U và X Y thì XW YW
1) Giả sử t1,t2 ∈ R và t1[X] = t2[X] cần chứng minh t1[Y] = t2[Y]
Thật vậy do Y X suy ra t1[Y] = t2[Y] (đúng)
2) Giả sử t1,t2 ∈ R và t1[XW] = t2[XW] cần chứng minh t1[YW] = t2 [YW]
Phản chứng: Giả sử t1[YW] ≠ t2[YW] Do t1[W] = t2 [W] nên để có t1[YW]
≠ t2 [YW] thì t1[Y] ≠ t2[Y] Nhƣng theo giả thiết ta có X → Y nghĩa là t1[X]=t2[X] thì t1[Y]=t2[Y] mâu thuẫn.Vậy t1[YW] = t2[YW]
3) Theo giả thiết ta có X → Y,Y → Z là hai PTH trên quan hệ R
Giả sử t1,t2 ∈ R và t1[X] = t2[X] cần chứng minh t1[Z] = t2[Z]
Phản chứng : Giả sử t1[Z] ≠ t2 [Z] Từ X → Y suy ra t1[X] = t2[X] thì t1[Y]
= t2[Y] Mặt khác ta lại có PTH Y → Z nghĩa là t1[Y] = t2[Y] thì t1[Z] = t2[Z] nhƣng theo giả thiết phản chứng ta có t1[Z] ≠ t2[Z] (mâu thuẫn) Vậy t1[Z] = t2[Z]
Cần chứng minh AB → ABC
2 AB → BC (luật tăng trưởng của (1) thêm thuộc tính C )
4 BC → ABC (luật tăng trưởng của (3) thêm BC )
5 AB → ABC (bắc cầu từ (2) và (4))
Từ các tính chất trên chúng ta có các hệ quả sau đây:
1) Luật hợp : Nếu X → Y và X → Z thì X → YZ
2) Luật tựa bắc cầu : Nếu X → Y và WY → Z thì XW → Z
3) Luật tách : Nếu X → Y và Z Y thì X → Z
1) Từ X → Y dùng luật tăng trưởng thêm X có X → XY(1) Từ X → Z dùng luật tăng trưởng thêm Y có XY → YZ (2)
Vậy từ (1) và (2) áp dụng luật bắc cầu suy ra X → YZ
2) Từ X → Y dùng luật tăng trưởng, thêm W có XW → WY (3) Mặt khác theo giả thiết ta có WY → Z (4)
Vậy từ (3) và (4) áp dụng luật bắc cầu ta có XW → Z
3) Do Z Y suy ra Y → Z (theo luật phản xạ) Áp dụng luật bắc cầu cho
1.3.3 Bao đóng của tập phụ thuộc hàm
Một phụ thuộc hàm f được gọi là suy dẫn từ tập phụ thuộc hàm F nếu tồn tại một chuỗi phụ thuộc hàm f1, f2,…, fn trong đó fn = f và mỗi fi là thành viên của F hoặc được suy dẫn từ các phụ thuộc hàm j=1,…,i-1 trước đó thông qua hệ tiên đề Armstrong.
Bao đóng của F: ký hiệu là F+ là tập tất cả các phụ thuộc hàm đƣợc suy dẫn từ F nhờ vào hệ tiên đề Armstrong
Bao đóng của F đƣợc ký hiệu là F + ,ta luôn có F F +
1.3.4 Bao đóng của tập thuộc tính
Trong một quan hệ R, có thể có nhiều phụ thuộc hàm giữa các thuộc tính, với khả năng một thuộc tính phụ thuộc vào nhiều thuộc tính khác hoặc nhiều thuộc tính phụ thuộc vào một thuộc tính Để tổng quát hóa các phụ thuộc hàm này, khái niệm Bao đóng tập thuộc tính được giới thiệu.
Cho tập thuộc tính U, với X là một tập con của U và F là tập hợp các phụ thuộc hàm trên U Bao đóng của tập thuộc tính X theo phụ thuộc hàm F được định nghĩa và ký hiệu là.
X + F đƣợc xác định nhƣ sau:
Ta viết gắn gọn X + F là X +
Khái niệm Bao đóng tập thuộc tính đóng vai trò quan trọng trong nghiên cứu lớp phụ thuộc dữ liệu Đây là một trong những khái niệm then chốt, vì các kết quả quan trọng trong lớp phụ thuộc hàm đều liên quan mật thiết đến nó.
1.3.5 Tính chất của bao đóng tập thuộc tính
Dựa vào các tính chất của phụ thuộc hàm ta có các tính chất của bao đóng tập thuộc tính nhƣ sau:
2) Tính đơn điệu: Nếu X Y thì X + Y +
1.3.6 Tập phụ thuộc hàm tương đương
Hai tập phụ thuộc hàm F và G là tương đương nếu:
1 Tất cả các phụ thuộc hàm trong F có thể đƣợc suy ra từ G
2 Tất cả các phụ thuộc hàm trong G có thể suy ra từ F
Vì thế, F và G là tương đương nếu F + = G +
Nếu F và G là tương đương thì ta nói F phủ G hay G phủ F
Thuật toán sau đây cho phép kiểm tra sự tương đương của hai tập phụ thuộc hàm:
F phủ E: X Y E, tính X + từ F, sau đó kiểm tra xem Y X +
E phủ F: X Y F, tính X + từ E, sau đó kiểm tra xem Y X +
1.3.7 Phủ tối thiểu của một tập phụ thuộc hàm
Tập phụ thuộc hàm là tối thiểu nếu nó thoả mãn các điều kiện sau:
1 F không dư thừa về phải: Chỉ có một thuộc tính nằm ở phía bên tay phải của tất cả các phụ thuộc hàm trong F
2 F không dư thừa phụ thuộc hàm : Không thể bỏ đi bất kỳ một phụ thuộc hàm nào trong F mà vẫn có được một tập phụ thuộc hàm tương đương với F Trong F không chứa các phụ thuộc hàm LjR để: (F \ {LjRj})+ = F+
3 F không dư thừa vế trái : Không thể thay thế bất kỳ phụ thuộc hàm X→A nào trong F bằng phụ thuộc hàm Y→A, với YX mà vẫn có đƣợc một tập phụ thuộc hàm tương đương với F (tức là, không có thuộc tính dư thừa trong phụ thuộc hàm)
Các dạng chuẩn trong mô hình quan hệ
Sau khi nghiên cứu các phụ thuộc hàm và tính chất của chúng, chúng ta sẽ áp dụng chúng để hiểu ngữ nghĩa của các lược đồ quan hệ Giả sử mỗi quan hệ có một tập phụ thuộc hàm và một khoá chính Phần này sẽ tập trung vào việc nghiên cứu các dạng chuẩn và quá trình chuẩn hoá các lược đồ quan hệ.
1.4.1 Sự cần thiết phải chuẩn hóa dữ liệu
Ví dụ với CSDL là Bảng hóa đơn cho khách hàng nhƣ sau:
Hình 1.3 Hoá đơn bán lẻ Khi cập nhật dữ liệu thì sẽ có các bất thường xảy ra:
Bất thường khi thêm dữ liệu: Không thể thêm một khách hàng vào CSDL nếu khách hàng không mua một mặt hàng nào
Khi cập nhật dữ liệu, việc thay đổi địa chỉ của khách hàng cần phải được thực hiện trên tất cả các hóa đơn liên quan, do địa chỉ của khách hàng được lưu trữ dư thừa trên từng hóa đơn.
Bất thường khi xóa dữ liệu: Nếu xóa hóa đơn cuối cùng của một khách hàng thì tất cả dữ liệu về khách hàng đó bị mất
Chuẩn hóa cơ sở dữ liệu nhằm mục đích nhóm các thuộc tính vào các quan hệ, từ đó giảm thiểu tình trạng dư thừa dữ liệu và loại bỏ các bất thường trong quá trình cập nhật.
Cần có các bước chuẩn hoá từ một CSDL chưa chuẩn hóa sang chuẩn hóa
Dạng chƣa chuẩn hóa (unnormalized form - UNF): quan hệ chƣa chuẩn hóa là quan hệ chứa các bộ dữ liệu bị lặp lại giá trị
Bảng hóa đơn ở trên biểu diễn dưới dạng bảng như sau Với 2 hàng và 10 cột tương ứng với 10 thuộc tính trong bảng hoá đơn
HD NgayGio TenKH DiaChi MaSP TenSP Don
192 Lê Duẩn, Vinh, Nghệ An
192 Lê Duẩn, Vinh, Nghệ An
Bảng này ở dạng không chuẩn
Sau khi chuẩn hoá bảng này đƣợc tách thành hai bảng nhƣ sau:
15 20/12/2012 9:34 AM Khach Hang 192 Lê Duẩn, Vinh, Nghệ An
SoHD MaSP TenSP DonVi SL DonGia ThanhTien
15 BOTXXX Giày Dép Nhựa Đôi 3 80 000 240 000
Hình 1.4: Quy trình chuẩn hóa sơ đồ quan hệ
2.4.2.1 Dạng chuẩn 1 (1NF) Định nghĩa: Lƣợc đồ quan hệ R đƣợc gọi là 1NF nếu và chỉ nếu tất cả các thuộc tính của R thoả mãn cả 2 điều kiện sau:
Các thuộc tính trong R đều nguyên tố
Giá trị của các thuộc tính trên các bộ là đơn trị, không chứa nhóm lặp
Không chứa thuộc tính suy dẫn
Quy tắc chuyển bảng từ dạng chƣa chuẩn về chuẩn 1NF
Nguyên tắc chung: Loại bỏ thuộc tính lặp hoặc đa trị
Tách nhóm thuộc tính lặp / đa trị sang một bảng mới
Khóa của bảng mới là Khóa của bảng ban đầu và khóa nhóm lặp
Bảng còn lại là bảng gồm có khóa và các thuộc tính còn lại
Ví dụ: Cho bảng NhanVien_DuAn
DA02 Xây chung cƣ Nam 30
DA03 Xây trường học An 27
Quan hệ này là R (MaDA, TenDA, {TenNhanVien, SoGio})
Thuộc tính lặp là { TenNhanVien, SoGio } Vì vậy, quan hệ này đƣợc tách thành:
R1 ( MaDA, TenDA ) R2( MaDA, TenNhanVien, SoGio )
Quan hệ R được coi là ở dạng 2NF khi nó đã đạt yêu cầu của dạng 1NF và tất cả các thuộc tính không khóa đều phụ thuộc đầy đủ vào khóa chính Điều này có nghĩa là không có thuộc tính không khóa nào phụ thuộc một phần vào khóa chính.
Thuộc tính không khóa: là thuộc tính không tham gia vào bất kỳ khoá nào
Quy tắc chuẩn hoá từ 1NF lên 2NF:
Kiểm tra 2NF yêu cầu xác định các phụ thuộc hàm mà thuộc tính ở vế trái là một phần của khoá chính Nếu khoá chính chỉ có một thuộc tính, không cần kiểm tra Một lược đồ quan hệ R được xem là ở dạng chuẩn 2NF nếu nó đáp ứng chuẩn 1 và mỗi thuộc tính không khoá A trong R phụ thuộc đầy đủ vào khoá chính của R Nếu quan hệ chưa đạt 2NF, cần thực hiện các bước tiếp theo để chuẩn hóa.
Để tối ưu hóa cơ sở dữ liệu, bước đầu tiên là loại bỏ các thuộc tính không khóa phụ thuộc vào một phần của khóa chính và tách chúng thành một bảng riêng Khóa chính của bảng mới sẽ là phần khóa mà các thuộc tính này phụ thuộc vào.
Bước 2: Các thuộc tính còn lại lập thành một quan hệ, khóa chính của quan hệ này là khóa chính ban đầu
Ví dụ: Xét lƣợc đồ quan hệ:
NHÂNVIÊN_DỰÁN (MãsốNV, MãsốDA, Sốgiờ, HọtênNV, TênDA, ĐịađiểmDA) với các phụ thuộc hàm:
MãsốNV, MãsốDA → Sốgiờ MãsốNV →HọtênNV
MãsốDA→TênDA, ĐịađiểmDA Khoá chính của quan hệ trên là MãsốNV, MãsốDA
Trong bài viết này, chúng ta nhận thấy có những thuộc tính không phụ thuộc hoàn toàn vào khoá chính, do đó không đáp ứng được điều kiện của chuẩn 2NF Bằng cách áp dụng phương pháp chuẩn hoá, lược đồ đã được phân tách thành các lược đồ riêng biệt.
2.4.2.3 Dạng chuẩn 3 ( 3NF ) Định nghĩa: Cho quan hệ R, F là tập phụ thuộc hàm trên R R đƣợc gọi là đạt dạng chuẩn 3 nếu thoả mãn các điều kiện sau:
R phải đạt dạng chuẩn 2NF
Mọi thuộc tính không khoá không phụ thuộc bắc cầu vào khóa chính (tức là tất cả các thuộc tính phải đƣợc suy ra trực tiếp từ khóa chính)
Quy tắc chuẩn hoá về 3NF:
Để tối ưu hóa quan hệ trong cơ sở dữ liệu, bước đầu tiên là loại bỏ các thuộc tính phụ thuộc bắc cầu, tách chúng thành một quan hệ riêng, trong đó khoá chính sẽ là thuộc tính bắc cầu.
Bước 2: Các thuộc tính còn lại lập thành một quan hệ có khóa chính là quan hệ ban đầu
Ví dụ: Xét lƣợc đồ quan hệ
NHÂNVIÊN_ĐƠNVỊ(HọtênNV, MãsốNV, Ngàysinh, Địachỉ, MãsốĐV, TênĐV, MãsốNQL)
Với các phụ thuộc hàm:
MãsốNV→ HọtênNV, Ngày sinh, Địachỉ, MãsốĐV, TênĐV, MãsốNQL
Khoá chính của quan hệ là K = { MãsốNV }
Các thuộc tính TênĐV và MãsốNQL phụ thuộc bắc cầu vào khoá chính, dẫn đến việc lược đồ quan hệ không đạt điều kiện 3NF Sau khi áp dụng phương pháp chuẩn hoá, lược đồ đã được tách ra để cải thiện cấu trúc dữ liệu.
NV_DV1(HọtênNV, MãsốNV, Ngàysinh, Địachỉ, MãsốĐV)
NV_DV2(MãsốĐV, TênĐV, MãsốNQL)
2.4.2.4 Dạng chuẩn BCNF ( Boyce-Codd ) Định nghĩa: Một lƣợc đồ quan hệ R đƣợc gọi là ở dạng chuẩn Boyce-Codd
(BCNF) nếu nó thoả mãn 2 điều kiện sau:
Không có các thuộc tính khóa phụ thuộc hàm vào thuộc tính không khóa
Quy tắc chuẩn hoá về BCNF:
Nếu lược đồ quan hệ không đạt điều kiện BCNF, ta có thể chuẩn hóa nó bằng cách loại bỏ các thuộc tính khóa phụ thuộc hàm vào thuộc tính không khóa Việc này sẽ giúp tách các thuộc tính này thành một lược đồ riêng, trong đó khóa chính là thuộc tính không khóa gây ra phụ thuộc.
Ví dụ: Cho lƣợc đồ quan hệ R (A1,A2,A3,A4,A5)
Với các phụ thuộc hàm:
Quan hệ này không tuân thủ chuẩn BCNF do thuộc tính khóa {A2} phụ thuộc hàm vào thuộc tính không khóa {A4} Để khắc phục vấn đề này, chúng ta áp dụng phương pháp chuẩn hóa, dẫn đến việc tách rời lược đồ thành các phần phù hợp hơn.
Kết luận chương 1
Chương 1 ta đã biết được các định nghĩa cơ bản của lược đồ quan hệ như thực thể, thuộc tính, quan hệ, khoá của một sơ đồ quan hệ Phụ thuộc hàm và các tính chất của phụ thuộc hàm đây là cơ sở cho chúng ta chuẩn hoá lƣợc đồ quan hệ
Chúng ta đã biết đƣợc các dạng chuẩn hoá và cách quy tắc chuẩn hoá về dạng chuẩn 1, dạng chuẩn 2, dạng chuẩn 3, dạng chuẩn BCNF.
LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ
Sự cần thiết phải thiết kế cơ sở dữ liệu
Cơ sở dữ liệu và hệ cơ sở dữ liệu đã trở thành phần thiết yếu trong cuộc sống hiện đại, với nhiều hoạt động hàng ngày như giao dịch ngân hàng, đặt chỗ máy bay hoặc khách sạn, và truy cập thư viện số Những ứng dụng này yêu cầu quản lý tự động thông tin tài chính và hàng hóa Việc thiết kế một cơ sở dữ liệu cho ứng dụng là quá trình phức tạp, đòi hỏi chuyên môn cao và kinh nghiệm Hệ thống cần được thiết kế để giải quyết các vấn đề cụ thể trong hoạt động của nó Thiết kế là bước quan trọng trong xây dựng cơ sở dữ liệu, nơi không chỉ thu thập, lưu trữ và khôi phục dữ liệu mà còn chuyển đổi chúng thành thông tin có giá trị Thông tin thu được càng nhanh chóng và thực tiễn thì quyết định đưa ra càng chính xác và có ý nghĩa hơn.
Trong thiết kế cơ sở dữ liệu, việc phân tích các tính chất cơ bản của dữ liệu là rất quan trọng Quá trình thiết kế bao gồm các bước nhằm giúp hệ quản trị cơ sở dữ liệu phát triển, cài đặt và duy trì một cách hiệu quả Mục tiêu chính của thiết kế là xây dựng mô hình vật lý và logic cho hệ thống cơ sở dữ liệu.
Các bước thiết kế cơ sở dữ liệu
Hình 2.1: Sơ đồ mô tả các bước chính của việc thiết kế cơ sở dữ liệu cho ứng dung
1 Tập hợp và phân tích các yêu cầu
Xác định quan điểm của người sử dụng, các loại báo cáo, biểu mẫu Do đó, người thiết kế cần chú ý tới những vấn đề nhƣ:
Thông tin cần thiết: Thông tin nào là cần thiết? Những dạng báo cáo nào cần phải đƣa vào trong hệ thống thông tin?
Nguồn thông tin có thể thu thập từ nhiều nguồn khác nhau, bao gồm nghiên cứu, báo cáo, và dữ liệu trực tuyến Để rút ra thông tin hữu ích, cần phân tích và xử lý các dữ liệu liên quan một cách có hệ thống Việc xác định nguồn đáng tin cậy và áp dụng các phương pháp phân tích phù hợp sẽ giúp tối ưu hóa quá trình này.
Để thiết lập thông tin từ dữ liệu, cần xác định các yếu tố thiết yếu như tính chất của dữ liệu, mối quan hệ giữa các dữ liệu khác nhau và tần suất sử dụng chúng Việc chuyển đổi dữ liệu thành thông tin cần thiết thường sử dụng các phương pháp cụ thể nhằm tạo ra thông tin có giá trị và dễ hiểu.
Người sử dụng thông tin: Ai sẽ là người sử dụng thông tin? Những người này có quan điểm khác nhau nhƣ thế nào về dữ liệu?
Người thiết kế cần phải trả lời đựơc tất cả những thông tin đó theo nhiều khía cạnh khác nhau
Trong quá trình thiết kế cơ sở dữ liệu, việc mô hình hóa dữ liệu là rất quan trọng để tạo ra một cấu trúc ngắn gọn, chỉ bao gồm những đối tượng cần thiết và có tính thực tiễn cao Ở giai đoạn này, mô hình cơ sở dữ liệu chưa cần phải hoàn thiện, nhưng cần đảm bảo rằng tất cả dữ liệu được đưa vào là thiết yếu Kết quả của bước này thường là sơ đồ thực thể-liên kết.
Thiết kế logic là quá trình chuyển đổi từ mô hình khái niệm thành mô hình bên trong một hệ thống quản lý cơ sở dữ liệu, thường sử dụng mô hình quan hệ Trong thiết kế logic cho hệ thống quản lý cơ sở dữ liệu quan hệ, các yếu tố như bảng, giao diện, chuyển đổi và thủ tục truy cập thông tin được thiết kế chi tiết Nói cách khác, thiết kế logic là việc dịch mô hình khái niệm độc lập với phần mềm thành các bảng biểu cần thiết, thực hiện trên giấy mà không cần xem xét tài nguyên vật lý của hệ thống.
Một trong những vấn đề quan trọng trong thiết kế logic của cơ sở dữ liệu quan hệ là quá trình chuẩn hóa các lược đồ quan hệ Mỗi sơ đồ quan hệ cần đạt tối thiểu dạng chuẩn 3, hay còn gọi là 3NF Chương 3 của đồ án sẽ trình bày việc cài đặt thuật toán chuẩn hóa một sơ đồ quan hệ về 3NF, đảm bảo tách không mất thông tin và bảo toàn tập phụ thuộc hàm, đây là nội dung cốt lõi của đồ án.
Thiết kế mô hình vật lý là quá trình chuyển đổi từ thiết kế logic của cơ sở dữ liệu sang cấu trúc vật lý sử dụng tài nguyên phần cứng và phần mềm Quá trình này không chỉ quyết định vị trí lưu trữ dữ liệu mà còn ảnh hưởng đến cách thức thực hiện hệ thống Việc sử dụng cơ sở dữ liệu chuẩn giúp giảm thiểu dư thừa dữ liệu trong phát triển phần mềm Trong thiết kế cơ sở dữ liệu quan hệ, tổ chức dữ liệu nhằm loại bỏ các bất thường và tối ưu hóa việc cập nhật Chuẩn hóa dữ liệu chia nhỏ bảng lớn thành nhiều bảng liên kết với nhau qua các trường dữ liệu, từ đó tiết kiệm không gian, giảm trùng lặp và bảo vệ tính nhất quán của dữ liệu Thiết kế bảng dữ liệu cẩn thận còn giúp cải thiện tốc độ giao dịch và truy vấn cho người dùng.
Edgar Codd, người sáng lập mô hình quan hệ, đã giới thiệu các khái niệm về chuẩn hóa cơ sở dữ liệu nhằm đề xuất các dạng chuẩn và tiêu chí xác định mức độ của một quan hệ Mục tiêu của việc chuẩn hóa là tránh các bất thường khi cập nhật dữ liệu và lỗi mâu thuẫn về logic Các dạng chuẩn này là nền tảng quan trọng trong việc quản lý và tổ chức dữ liệu hiệu quả.
Dạng chuẩn 1: 1NF ( First Normal Form )
Dạng chuẩn 2: 2NF ( Secand Normal Form )
Dạng chuẩn 3: 3NF ( Third Normal Form )
Dạng chuẩn 4: BCNF (BoyceCold Normal Form )
Vi phạm một trong ba quy tắc đầu tiên của chuẩn hóa cơ sở dữ liệu có thể dẫn đến các vấn đề bất thường trong quá trình cập nhật dữ liệu, bao gồm tình trạng dữ liệu dư thừa và các phụ thuộc không hợp lý.
Chuẩn hóa quy trình thu thập, truy cập, cập nhật và xử lý thông tin trong hệ thống là yếu tố then chốt, quyết định thành công hay thất bại trong việc áp dụng công nghệ thông tin.
Chuẩn hóa cơ sở dữ liệu là kỹ thuật quan trọng trong phân tích cơ sở dữ liệu quan hệ, nhằm tạo ra các bảng quan hệ với thừa dữ liệu tối thiểu và đảm bảo tính nhất quán Kỹ thuật này giúp tối ưu hóa quy trình chèn, xóa và sửa đổi dữ liệu, đồng thời giảm thiểu thời gian phân tích dữ liệu so với phương pháp thủ công truyền thống.
Báo cáo này đề xuất một ứng dụng tự động hóa giai đoạn phức tạp nhất trong thiết kế cơ sở dữ liệu ở dạng chuẩn 3NF Ứng dụng này giúp cải thiện thiết kế cơ sở dữ liệu, đồng thời khắc phục những hạn chế của sách hướng dẫn quá trình chuẩn hoá Nó được thiết kế để tự động loại bỏ các thuộc tính dư thừa và các phụ thuộc hàm không phù hợp, nhằm xử lý đưa quan hệ về dạng chuẩn.
Thuộc tính và phụ thuộc hàm
Loại bỏ các thuộc tính đa trị
Loại bỏ các thuộc tính phụ thuộc bộ phận
Loại bỏ phụ thuộc bắc cầu và áp dụng các dạng chuẩn khác ngoài 3NF là bước quan trọng trong thiết kế cơ sở dữ liệu Quá trình này bao gồm việc tạo ra các bảng, viết các câu lệnh SQL và thiết lập khóa chính cho các quan hệ đã được tách rời Sau khi hoàn tất, ứng dụng sẽ được thử nghiệm trên nhiều ví dụ từ các nguồn khác nhau để đảm bảo tính hiệu quả và chính xác.
Phép tách một sơ đồ quan hệ
2.3.1 Phép tách không mất thông tin
Thuật toán kiểm tra phép tách kết nối có mất thông tin hay không?
ĐẦU RA: Xác định liệu phép tách δ có mất thông tin hay không
Ta xây dựng một bảng gồm k + 1 dòng, n + 1 cột (n=|U|, k=| δ|)
Cột thứ i (i=1 n) của bảng ứng với thuộc tính Ai
Trong bảng, hàng thứ j (j=1 k) tương ứng với lược đồ con αj=(Uj, Fj) Tại cột i (i=1 n) và hàng j, chúng ta sẽ điền ký hiệu aj (được gọi là tín hiệu chính) nếu thuộc tính Aj thuộc tập Ui.
Ngƣợc lại ta điền bji ( ta gọi bji là tín hiệu phụ)
Bước 2: Biến đổi bảng như theo quy tắc như sau:
Đối với mỗi phụ thuộc hàm X→Y thuộc tập F, nếu bảng dữ liệu có hai hàng giống nhau trong tập thuộc tính X, thì chúng cũng phải giống nhau trong tập thuộc tính Y theo quy tắc đã được xác định.
Nếu một trong hai giá trị là tín hiệu phụ thì ta sửa lại tín hiệu phụ thành tín hiệu chính tức là bji thành aj
Nếu cả hai tín hiệu đều là tín hiệu phụ, chúng ta cần điều chỉnh một trong hai tín hiệu bằng cách sử dụng một trong các ký hiệu bji, nhằm đồng nhất chỉ số giữa chúng.
Tiếp tục áp dụng các phụ thuộc hàm trong bảng cho tới khi không còn áp dụng đƣợc nữa
Bước 3: Quan sát trong bảng cuối cùng:
Nếu xuất hiên ít nhất một hàng gồm toàn tín hiệu chính (hàng gồm toàn ký hiệu a) thì phép tách δ có kết nối không mất thông tin
Ngƣợc lại thì phép tách δ là phép tách có kết nối mất thông tin
Ví dụ: Cho lƣợc đồ quan hệ α =( U, F) với
Hỏi rằng phép tách δ trên có kết nối không mất thông tin không?
Xây dựng bảng gồm 4 hàng, 6 cột: Điền các tín hiệu vào bảng:
Biến đổi bảng trên dựa vào tập phụ thuộc hàm F:
Sử dụng phụ thuộc hàm A 1 →A 2 A 3 ta biến đổi bảng
Sử dụng phụ thuộc hàm A 2 A 4 → A5 ta biến đổi bảng
Sử dụng phụ thuộc hàm A 2 → A 3 ta biến đổi bảng
Từ bảng ta thấy phép tách δ là phép tách kết nối không mất thông tin
2.3.2 Phép tách bảo toàn tập phụ thuộc hàm
Điều kiện bảo toàn phụ thuộc hàm là khi mỗi phụ thuộc hàm X → Y trong tập hợp F xuất hiện trực tiếp trong các lược đồ quan hệ Ri trong phép tách δ hoặc có thể được suy diễn từ các phụ thuộc hàm có trong Ri Việc này mang lại nhiều lợi ích cho việc quản lý và tổ chức dữ liệu.
Chúng ta cần bảo toàn phụ thuộc hàm vì mỗi phụ thuộc trong F đại diện cho một ràng buộc quan trọng trong cơ sở dữ liệu Nếu một trong các phụ thuộc không được thể hiện trong một quan hệ Ri nào đó sau khi tách, các ràng buộc dữ liệu sẽ bị mất, dẫn đến việc không thể hiện rõ bài toán và tính nhất quán trong dữ liệu Điều này cho thấy rằng việc tách này không hiệu quả và không thực tiễn.
Cho một tập hợp các phụ thuộc F trên R, phép chiếu của F trên Ri, ký hiệu là πRi(F), là tập hợp các phụ thuộc hàm X→Y trong F+ với các thuộc tính trong X ∪ Y đều thuộc Ri Do đó, phép chiếu của F trên mỗi lược đồ quan hệ Ri trong phép tách δ = {R1, R2, …, Rm} sẽ là tập hợp các phụ thuộc hàm trong F+ mà cả hai vế trái và vế phải đều nằm trong Ri Khi đó, ta nói rằng phép tách δ bảo toàn phụ thuộc hàm.
Một số phương pháp chuẩn hóa sơ đồ quan hệ
ĐẦU RA: Tập các lƣợc đồ 3NF
Phương pháp: DS thuộc tính 1NF 2NF 3NF
DS Thuộc tính 1NF 2NF 3NF
(1) Tách một danh sách thuộc tính thành các kiểu thực thể 1NF
– Tách các nhóm thuộc tính lặp (không đơn) Phần còn lại là một kiểu thực thể 1NF Tìm khoá của nó
Xây dựng kiểu thực thể mới là một quá trình quan trọng trong thiết kế cơ sở dữ liệu Mỗi kiểu thực thể mới được tạo ra bao gồm một nhóm lặp tách ra cùng với khóa của kiểu thực thể trên Để xác định khóa của kiểu thực thể này, cần phải tìm kiếm và xác định các thuộc tính quan trọng nhất của kiểu thực thể Quá trình này giúp đảm bảo rằng kiểu thực thể mới được thiết kế một cách hợp lý và hiệu quả, đồng thời giúp cho việc quản lý và truy xuất dữ liệu trở nên dễ dàng hơn.
(2) Tách một kiểu thực thể 1NF thành các kiểu thực thể 2NF
– Tách các nhóm thuộc tính phụ thuộc hàm bộ phận vào khoá Phần còn lại là một kiểu thực thể 2NF
Xây dựng các kiểu thực thể mới bao gồm việc xác định các thuộc tính và mối quan hệ phụ thuộc vào một tập con của khóa gộp Mỗi kiểu thực thể sẽ có khóa được xác định bởi các thuộc tính của tập con này, tạo nên sự liên kết chặt chẽ giữa các thuộc tính và khóa.
(3) Tách một kiểu thực thể 2NF thành các kiểu thực thể 3NF:
– Tách các thuộc tính phụ thuộc hàm vào các thuộc tính ngoài khoá Phần còn lại là một kiểu thực thể 3NF
Xây dựng các kiểu thực thể mới yêu cầu xác định các thuộc tính và phụ thuộc hàm liên quan đến một nhóm thuộc tính không khoá Mỗi kiểu thực thể sẽ có khóa được xác định từ các thuộc tính trong nhóm này, tạo ra sự liên kết chặt chẽ giữa các thuộc tính và nhóm của chúng.
2.4.2 Kỹ thuật phủ tối thiểu
Thuật toán tách một sơ đồ quan hệ về 3NF không mất thông tin và bảo toàn tập phụ thuộc hàm
ĐẦU VÀO: - Danh sách thuộc tính
ĐẦU RA: Tập các lƣợc đồ 3NF
Bước 1: Tìm phủ tối thiểu F’ của LĐQH đã cho
Bước 2: Tìm một khóa key của LĐQH
Bước 3: Gộp các phụ thuộc hàm có cùng vế trái trong phủ tối tiểu F’ ta thu được F’’
Bước 4: Tìm các thuộc tính trong U nhưng không có trong F’’và loại bỏ chúng
Bước 5: Nếu có một phụ thuộc hàm trong F’’ mà Vế trái Vế phải = U thì sơ đồ quan hệ đã cho đã ở dạng 3NF Chuyển sang Bước 7
Bước 6: Ghép vế trái và vế phải của phụ thuộc hàm trong F’’ tạo thành các sơ đồ quan hệ KQ
Nếu key không thuộc vào một nào trong KQ thì thêm key vào KQ
Bước 7: Đưa ra các sơ đồ quan hệ và kết thúc.
Kết luận chương 2
Chương 2 này ta đã biết được thiết kế cơ sở dữ liệu là một loạt các quá trình xử lý thiết kế làm cho hệ quản trị cơ sở dữ liệu dễ dàng phát triển, cài đặt và duy trì Để thiết kế một cơ sở dữ liệu phải trải qua một quá trình dài, gồm các bước:
- Tập hợp và phân tích các yêu cầu: Tạo ra các yêu cầu của cơ sở dữ liệu
- Thiết kế quan niệm: Tạo ra lƣợc đồ quan niệm
- Thiết kế logic: Tạo ra lƣợc đồ logic
- Thiết kế vật lý: Tạo ra lƣợc đồ bên trong
Chúng ta hiểu rằng thuật toán kiểm tra phép tách kết nối có thể xác định xem có mất thông tin hay không, cũng như kiểm tra tính bảo toàn của phụ thuộc hàm Hơn nữa, việc chuẩn hóa lược đồ quan hệ có thể thực hiện thông qua kỹ thuật phân tách hoặc kỹ thuật phủ tối thiểu.
CÀI ĐẶT THUẬT TOÁN CHUẨN HOÁ SƠ ĐỒ QUAN HỆ
Xây dựng kiểu dữ liệu cho các phụ thuộc hàm
Phụ thuộc hàm là mối quan hệ giữa các thuộc tính trong một quan hệ, trong đó giá trị của một thuộc tính được xác định bởi một số thuộc tính khác Các phụ thuộc hàm đóng vai trò quan trọng trong quản lý cơ sở dữ liệu và tối ưu hóa truy vấn, giúp cải thiện hiệu quả và tính chính xác của dữ liệu.
Trong ứng dụng, các thao tác và xử lý chủ yếu xoay quanh phụ thuộc hàm, trong đó mỗi phụ thuộc hàm bao gồm hai vế trái và phải Vấn đề cần giải quyết là cách thể hiện mối quan hệ giữa hai vế này một cách rõ ràng và hiệu quả.
Giải pháp đề xuất là xây dựng một lớp phụ thuộc hàm, bao gồm hai thuộc tính chính là vt (vế trái) và vp (vế phải) Lớp này sẽ có các phương thức như phương thức khởi tạo có tham số, phương thức khởi tạo không tham số, và phương thức ToString để thể hiện thông tin Dưới đây là đoạn mã chi tiết: public class PhuThuocHam.
{ private string vt; private string vp; public PhuThuocHam()
} public PhuThuocHam(string vt, string vp)
{ this.vt = vt; this.vp = vp;
{ get { return vt; } set { vt = value; }
{ get { return vp; } set { vp = value; }
{ return string.Format( {0} - {1} ,this.vt,this.vp); }
Để biểu diễn phụ thuộc hàm trong file text, cấu trúc của file cần được thiết lập như sau: dòng đầu tiên sẽ chứa một chuỗi ký tự in hoa liên tiếp, dùng để liệt kê các thuộc tính U.
Các dòng tiếp theo sẽ trình bày các phụ thuộc hàm F, trong đó vế trái và vế phải được phân cách bởi một khoảng trống " " Mỗi phụ thuộc hàm sẽ được thể hiện trên một dòng riêng biệt.
A B : thể hiện phụ thuộc hàm A → B
AB C : thể hiện phụ thuộc hàm AB → C
D EF : thể hiện phụ thuộc hàm D → EF
Thuật toán tìm bao đóng của một tập thuộc tính
S là tập thuộc tính cần tìm bao đóng,
nf là số phụ thuộc hàm,
nu là số thuộc tính của U
ĐẦU RA: Bd là bao đóng cần tìm
Bước 2: Gán nBd = độ dài Bd
Bước 3: Nếu i >= nf ? thì sang Bước 9
Bước 4: Nếu F[i].VT Bd thì sang Bước 8
Bước 5: Nếu k >= Độ dài F[i].VP thì sang Bước 8
Bước 6: Nếu Bd không chứa F[i].VP[k] thì Bd = Bd + F[i].VP[k]
Bước 7: Tăng k = k +1 Quay lại Bước 5
Bước 8: Tăng i = i +1, k = 0 Quay lại Bước 3
Bước 9: Nếu nBd < độ dài Bd và độ dài Bd != nu sai thì đưa ra Bd và kết thúc
Ngược lại quay về Bước 2
Hình 3.1: Sơ đồ thuật toán tìm bao đóng
Thuật toán tìm một khóa
nf là số phụ thuộc hàm,
ĐẦU RA: Một khóa K của LĐQH đã cho
Bước 2: Nếu i >= nu thì sang Bước 5
Bước 3: Nếu bao đóng của (K - U[i]) bằng U thì K = K - U[i]
Bước 4: i = i + 1 và quay về Bước 2
// Bước2 đến Bước 4 :Lần lượt duyệt từng thuộc tính trong K kiểm tra và loại bỏ chúng ra khỏi K
Bước 5: Đưa ra K và kết thúc
Hình 3.2: Sơ đồ thuật toán tìm một khoá
Thuật toán tìm mọi khóa
3.4.1 Mô tả thuật toán chung
Bước 1: Tìm nhân của mọi khóa - CORE - bao gồm các thuộc tính có trong U nhƣng không xuất hiện ở vế phải phụ thuộc hàm hoặc không xuất hiện ở cả 2 vế
Bước 2: Kiểm tra xem bao đóng của CORE có phải là U hay không Nếu đúng, kết luận rằng CORE là khóa duy nhất, đưa vào mảng Key và tiếp tục với Bước 7 Nếu không, chuyển sang Bước 3.
Bước 3: Tìm các thuộc tính tiềm năng - POSS - là các thuộc tính có mặt ở cả 2 vế phụ thuộc hàm đƣa vào mảng POSS
Bước 4: Sinh các tập con của tập POSS
Bước 5: Với mỗi Pi thuộc mảng POSS, nếu bao đóng của (CORE Pi) = U thì lưu (CORE Pi) thành vào mảng Key
Bước 6: Lặp: Với mọi Ki và Kj thuộc Key, nếu Ki Kj thì loại Kj khỏi Key
Bước 7: Đưa ra Key và kết thúc
3.4.2 Các thuật toán chi tiết
nf là số phụ thuộc hàm,
nu số thuộc tính của U
ĐẦU RA: Đƣa ra CORE
Bước 1: Gán CORE = U, nc là số thuộc tính CORE Gán nc = nu Khởi tạo i = 0, j= 0, k = 0
Bước 2: Kiểm tra j < nf hoặc nc = 0? Nếu đúng thì sang Bước 3, sai sang Bước 10
Bước 3: Nếu i >= nc thì sang Bước 9
Bước 4: Nếu k >= Độ dài F[i].VP thì sang Bước 8
Bước 5: Nếu CORE[k] != F[j].VP thì sang Bước 7
Bước 6: Xoá CORE[k] ra khỏi CORE, nc = nc -1
Bước 10: Đưa ra CORE và kết thúc
Hình 3.3: Sơ đồ thuật toán tìm CORE
nf là số phụ thuộc hàm,
TD là tập các phần tử chỉ xuất hiện ở vế phải phụ thuộc hàm
ĐẦU RA: POSS tập tiềm năng (thuộc tính có mặt ở cả 2 vế của F) cần tìm
Bước 1: Khai báo mảng chuỗi POSS Khởi tạo i = 0, j = 0, np = 0
Bước 2: Nếu i >= nf thì sang Bước 8
Bước 3: Nếu j >= Độ dài F[i].VT thì sang Bước 7
Bước 4: Nếu TD F[i].VT[j] thì sang Bước 6
Bước 8: Đưa ra mảng POSS và kết thúc
3.4.2.3 Thuật toán sinh tập con từ tập poss
np là số phẩn tử poss
ĐẦU RA: Tập mảng poss
Bước 1: Khởi tạo m, h, j = 0, i = 0 và chuỗi s
Bước 2: Nếu i >= np thì sang Bước 12
Bước 4: Nếu j >= np thì sang Bước 11
Bước 5: Nếu poss[i] chứa poss[j] thì sang Bước 10
Bước 6: Gán s = poss[i] + poss[j] Gán m = h
Bước 7: Nếu m >= np thì sang Bước 9
Bước 8: Nếu poss[m] s thì sang Bước 10 Ngược lại, m = m + 1 và quay lại Bước 7
Bước 10: j = j + 1 và quay lại Bước 4
Bước 11: i = i +1 và quay lại Bước 2
Bước 12: Đưa ra tập mảng poss
Tập tiềm năng poss và nhân CORE,
np là số phần tử poss
ĐẦU RA: Tất cả các khóa của lƣợc đồ quan hệ
Bước 1: Khởi tạo chuỗi key = CORE, i = 0, nk = 0
Bước 2: Nếu i >= np thì sang Bước 6
Bước 3: Gán key = key + poss[i]
Bước 4: Nếu độ dài của bao đóng key = nu thì gán khoa[nk] = key và nk = nk + 1
Bước 5: i = i +1 và quay về Bước 2
Hình 3.5: Sơ đồ thuật toán tìm siêu khoá
3.4.2.5 Tìm các khoá từ tập siêu khoá
Khoa là tập tất cả các khoá (có thể khóa này là tập con của khóa kia)
n là số phần tử của tập khoá
ĐẦU RA: Tất cả các khóa của lƣợc đồ quan hệ cần tìm
Bước 2: Nếu i >= n – 1 thì sang Bước 12
Bước 4: Nếu k >= n thì sang Bước 11
Bước 5: Nếu Khoa[k] mà không chứa Khoa[i] thì sang Bước 10
Bước 7: Nếu j >= n – 1 thì sang Bước 9
Bước 8: Khoa[j] = Khoa[j+1] j++ Quay về Bước 7
//Bước 5 đến 9: Kiểm tra Khoa[k] mà chứa Khoa[i] thì dồn phần tử để loại bỏ Khoa[k]
Bước 10: Tăng k = k+1 Quay về Bước 4
Bước 11: Tăng i = i+1, k = 0 Quay về Bước 2
Bước 12: Đưa ra tất cả các khóa cần tìm
Hình 3.6: Sơ đồ thuật tìm các khoá từ tập siêu khoá
Thuật toán tìm phủ tối thiểu
Mô tả thuật toán chung
Bước 1: Tách các phụ thuộc hàm ở vế phải thành các thuộc tính đơn và lưu vào phủ
Bước 2: Tạo các tổ hợp thuộc tính từ vế trái, tạo thành các tập thuộc tính con S[i] Nếu bất kỳ S[i] nào có bao đóng chứa vế phải, thì gán vế trái bằng S[i] Đây là bước loại bỏ phụ thuộc hàm, đưa LĐQH về dạng chuẩn 2NF.
Bước 3: Tiến hành xóa bỏ các phụ thuộc hàm bên phải nếu bên trái có bao đóng chứa bên phải, nhằm loại bỏ phụ thuộc hàm bắc cầu và đưa lược đồ quan hệ về dạng chuẩn 3NF.
Bước 4: Đưa ra phủ tối thiểu cần tìm
3.5.1 Tách vế phải phụ thuộc hàm thành các thuộc tính đơn:
nf là số phụ thuộc hàm
ĐẦU RA: Phụ thuộc hàm có vế phải là các thuộc tính đơn
Bước 1: Khởi tạo mảng cấu trúc Phu, i = 0, j = 0
Bước 2: Nếu i > nf thì sang Bước 7
Bước 3: Nếu j >= độ dài chuỗi F[i].VP thì sang Bước 6
Bước 4: Gán Phu[np].VT = F[i].VT và Phu[np].VP = F[i].VP[j], np = np + 1
Bước 7: Đưa ra Phu và kết thúc
Ta có sơ đồ thuật toán sau
Hình 3.5: Sơ đồ thuật toán tách vế phải thành các thuộc tính đơn
3.5.2 Loại bỏ dƣ thừa thuộc tính ở vế trái
Phủ có vế phải là các thuộc tính đơn,
nphu là số phụ thuộc hàm trong phủ trên
ĐẦU RA: Phủ không dƣ thừa thuộc tính vế trái
Bước 2: Nếu i < nphu sang Bước 3 Ngược lại, sang Bước 6
Bước 3: Gán len = độ dài phu[i].VT Nếu len = 1 thì sang Bước 5 Ngược lại sang Bước 4
Bước 4: Tạo tập con từ tập thuộc tính bên trái Nếu có tổ hợp nào từ tohop[k] có bao đóng chứa phu[i].VP, thì gán phu[i].VT bằng tohop[k].
Bước 5: Tăng i = i + 1 Quay về Bước 2
Bước 6: Đưa ra phủ và kết thúc
3.5.3 Loại bỏ dƣ thừa phụ thuộc hàm
Phủ không dƣ thừa thuộc tính vế trái phụ thuộc hàm,
nphu là số phụ thuộc hàm trong phủ trên
ĐẦU RA: Phủ tối thiểu của LĐQH
Bước 2: Nếu i >= nphu thì sang Bước 8
Bước 3: Gán S = phu[i].VP, phu[i].VP = “ ”
Bước 4: Nếu bao đóng của phu[i].VT không chứa S thì sang Bước 6
Bước 5: phu[i ] = phu[ nphu], sang Bước 7
Bước 8: Đưa ra phủ tối thiểu.
Thuật toán tách lƣợc đồ quan hệ về dạng 3NF, bảo toàn phụ thuộc hàm và không mất thông tin
và không mất thông tin
Mô tả thuật toán chung:
Bước 1: Tìm phủ tối thiểu của LĐQH đã cho
Bước 2: Tìm một khóa key của LĐQH
Bước 3: Gộp các phụ thuộc hàm có cùng vế trái trong phủ
Bước 4: Tìm các thuộc tính trong U nhưng không có trong table và loại bỏ chúng ra khỏi U
Nếu có phu[i].VT phu[i].VP = U, thì bảng đó đạt chuẩn 3NF và bảo toàn phụ thuộc hàm Ngược lại, nếu không, bảng sẽ không đạt chuẩn 3NF và không bảo toàn phụ thuộc hàm.
Bước 6: Nếu key không thuộc bất kỳ table nào thì thêm key vào table
Bước 7: Đưa ra table và kết thúc.
Kết luận chương 3
Chương này trình bày việc xây dựng kiểu dữ liệu phụ thuộc hàm với vế trái và vế phải, cùng với cách biểu diễn phụ thuộc hàm trong file text Để thiết kế cơ sở dữ liệu lớn và phức tạp, cần áp dụng nhiều thuật toán nhằm xác định khóa và các khóa tối thiểu của tập phụ thuộc hàm Cuối cùng, quá trình này giúp tách lược đồ quan hệ về dạng chuẩn 3NF, đảm bảo phép tách bảo toàn phụ thuộc hàm và không mất thông tin.
DEMO CHƯƠNG TRÌNH ỨNG DỤNG
Chức năng đọc từ tệp
4.1.1 Giao diện chính của chương trình
Chương trình có giao diện chính với hai chức năng chính: đọc dữ liệu từ tệp hoặc nhập dữ liệu từ bàn phím Khi chọn chế độ đọc từ tệp, các tùy chọn nhập dữ liệu từ bàn phím sẽ được ẩn và ngược lại.
4.1.2 Đọc dữ liệu từ tệp
Bấm vào mở tệp xuất hiện form mở tệp, ta chỉ đến đường dẫn tệp Tệp có cấu trúc nhƣ đã nêu trên
Hình 4.3: Cấu trúc tệp đầu vào
Sau khi mở tệp thì bài toán được hiện thị như hình bên dưới
Hình 4.4: Sau khi mở tệp
Hình 4.5: Kết quả tìm phủ tối thiểu
Hình 4.6: Kết quả tìm các khoá
4.1.5 Tách lƣợc đồ quan hệ
Sau khi xác định các khóa, để tách rời đồ quan hệ mà vẫn giữ nguyên phụ thuộc hàm mà không làm mất thông tin, chúng ta có thể áp dụng hai phương pháp khác nhau.
Khi bấm nút tách 3NF thì sẽ chọn 1 khoá trong lƣợc đồ quan hệ để thực hiện phép tách và cho kết quả nhƣ sau
Hình 4.7: Kết quả tách lƣợc đồ về 3NF tìm một khoá
Chọn khóa HI để thực hiện phép tách, nhưng vì HI không thuộc lược đồ quan hệ nào, ta cần thêm HI vào một lược đồ mới Điều này thể hiện tính chất bảo toàn thông tin trong quá trình tách.
Hình 4.8: Kết quả tách lƣợc đồ về 3NF chọn khoá.
Chức năng nhập dữ liệu
4.2.1 Nhập thuộc tính và mã hoá dữ liệu
Đầu tiên, người dùng cần nhập số lượng thuộc tính dữ liệu theo kiểu số Nếu nhập sai, hệ thống sẽ yêu cầu nhập lại Khi nhập đúng, số lượng textbox sẽ tự động tạo ra, bao gồm tên thuộc tính và thuộc tính được mã hóa Lưu ý rằng thuộc tính mã hóa chỉ được phép là một ký tự chữ cái và không được nhập thêm ký tự nào khác.
Hình 4.9: Giao diện nhập thuộc tính và mã hoá
Sau khi hoàn tất việc nhập thuộc tính và mã hóa, nhấn nút "Nhập xong" để hiển thị thông báo liệt kê các thuộc tính đã nhập Nếu thông tin chính xác, hãy bấm "OK"; nếu có sai sót, chọn "Cancel" để chỉnh sửa lại.
Hình 4.10: Giao diện kết quả nhập thuộc tính và mã hoá
Giao diện nhập phụ thuộc hàm có:
- Danh sách các thuộc tính: Liệt kê toàn bộ thuộc tính ta đã nhập ở bước thứ nhất
Nhập phụ thuộc hàm có vế trái và vế phải
Khi nhập phụ thuộc hàm thì thuộc tính mã hoá sẽ tự động xuất hiện
Hình 4.11: Giao diện nhập phụ thuộc hàm
Nếu vế trái hay vế phải phụ thuộc hàm có nhiều hơn một thuộc tính thì các thuộc tính các nhau bởi dấu phẩy ,
Nếu nhập phụ thuộc hàm đã có thì sẽ thông báo đã tồn tại, không phải nhập lại
Nếu nhập thừa phụ thuộc hàm ta có thể xoá phụ thuộc hàm đó
Hình 4.12: Giao diện xoá phụ thuộc hàm
Khi nhấn nút "Hiện thị bài toán", hệ thống sẽ hiển thị bài toán với các thuộc tính và phụ thuộc hàm trước và sau khi mã hóa.
Hình 4.13: Giao diện hiện bài toán chƣa mã hoá và sau mã hoá
Kết quả tìm phủ tối thiểu mã hoá được thể hiện trong Hình 4.14 Đối với chức năng nhập dữ liệu từ bàn phím, sẽ có thêm hiển thị phủ tối thiểu chưa mã hoá, tương ứng với phủ tối thiểu của tập phụ thuộc hàm ban đầu được nhập vào.
Hình 4.15: Kết quả tìm phủ tối thiểu không mã hoá
4.2.5 Tách lƣợc đồ quan hệ
Kết quả của phép tách lƣợc đồ quan hệ về 3NF với phép tách bảo toàn phủ thuộc hàm và không mất thông tin
Từ các lược đồ quan hệ, chúng ta có thể sinh mã lệnh SQL bằng cách chọn kiểu dữ liệu cho các thuộc tính Một số kiểu dữ liệu phổ biến trong SQL Server bao gồm nvarchar (20), int, bit, float, Date và DateTime.
Hình 4.17: Giao diện chọn kiểu dữ liệu cho thuộc tính
Nhập tên cơ sở dữ liệu Nếu chưa nhập chương trình kiểm tra bắt buộc nhập
Chương trình hỗ trợ xuất file ở 2 định dạng là file SQL SerVer ( *.sql ) hay file text (*.txt)
Hình 4.18: Giao diện xuất file mã lệnh
Nội dung file mã lệnh sau khi tạo.