Giáo trình Cơ sở dữ liệu: Phần 2 - TS. Nguyễn Hoàng Sơn

Tiếp nội dung phần 1, Giáo trình Cơ sở dữ liệu: Phần 2 được biên soạn gồm các nội dung chính sau: Thiết kế cơ sở dữ liệu quan hệ; Những vấn đề liên quan đến thiết kế. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Giáo trình Cơ sở dữ liệu: Phần 2 - TS. Nguyễn Hoàng Sơn Chương 4. THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ 4.1. Dư thừa dữ liệu và các dị thường cập nhật Mục đích chính của thiết kế CSDL quan hệ là nhóm các thuộc tính vào các bảng (quan hệ) sao cho giảm được nhiều nhất sự dư thừa dữ liệu và dẫn đến giảm được không gian lưu trữ cần thiết cho các quan hệ cơ sở. Ngoài ra, khi dữ liệu dư thừa một số vấn đề khác có thể nảy sinh như dị thường thêm bộ, dị thường xóa bộ và dị thường sửa bộ. Các dị thường này còn được gọi chung lại là dị thường cập nhật. Để minh họa chúng ta xét ví dụ sau: Ví dụ 4.1. Xét các quan hệ N CC (người cung cấp) trên tập thuộc tính {Hoten, Diachi} và quan hệ CCH (cung cấp hàng) trên tập thuộc tính {Hoten, M athang, Gia}. Giả sử chúng ta đã kết nối hai quan hệ này thành quan hệ N CCH (người cung cấp hàng) với tập thuộc tính {Hoten, Diachi, M athang, Gia}. Có thể thấy, quan hệ N CCH chứa tất cả các thông tin về người cung cấp hàng (cho siêu thị). Rõ ràng quan hệ này có dữ liệu dư thừa, đó là địa chỉ (duy nhất) của người cung cấp hàng lặp lại mỗi lần cho mỗi mặt hàng được cung cấp. Lúc này, các dị thường cập nhật có thể xuất hiện là: • Dị thường khi sửa bộ: chúng ta có thể cập nhật địa chỉ mới của một người cung cấp hàng trong một bộ nhưng vẫn để lại địa chỉ cũ trong một bộ khác (do hậu quả của dư thừa). Khi đó, người cung cấp hàng không có địa chỉ duy nhất như chúng ta đã nghĩ (dữ liệu không nhất quán). • Dị thường khi thêm bộ: chúng ta không thể biết được địa chỉ của một người cung cấp hàng nếu hiện tại họ không cung cấp ít nhất một mặt hàng. Có thể đặt những giá trị null trong các thuộc tính M athang 105 và Gia của một bộ cho một người cung cấp hàng nào đó, nhưng khi thêm một mặt hàng cho người cung cấp hàng đó, chúng ta có nhớ xóa đi bộ mang giá trị null hay không. Mặt khác, nếu giả thiết {Hoten, M athang} là một khóa tối tiểu của quan hệ N CCH, thì lúc đó chúng ta không thể tìm ra các bộ nhờ chỉ mục sơ cấp được nếu có những giá trị null trong thuộc tính M athang của khóa tối tiểu. • Dị thường khi xóa bộ: nếu giả sử chúng ta xóa tất cả các mặt hàng được cung cấp bởi một người cung cấp hàng thì vô ý làm mất dấu vết để tìm ra địa chỉ của người cung cấp hàng này. Các dị thường cập nhật trên sẽ không tồn tại nữa nếu chúng ta tách quan hệ N CCH thành hai quan hệ N CC và CCH. Khi đó quan hệ N CC cung cấp địa chỉ của mỗi người cung cấp hàng đúng một lần, do vậy không có dư thừa dữ liệu. Ngoài ra, chúng ta cũng có thể nhập địa chỉ của người cung cấp hàng dù hiện tại họ không cung cấp một mặt hàng nào. Tuy vậy, vẫn còn một số vấn đề cần quan tâm khi thực hiện việc phân tách như trên, chẳng hạn để (truy vấn) tìm địa chỉ của tất cả những người cung cấp hàng có cung cấp một mặt hàng nào đó, thì đầu tiên chúng ta phải thực hiện một phép kết nối và sau đó thực hiện phép chọn, phép chiếu để trả lời truy vấn. Trong khi đối với quan hệ N CCH, chúng ta chỉ cần thực hiện một phép chọn và một phép chiếu đơn giản với thời gian thực hiện nhanh hơn. Vậy nên chúng ta cần xem sự thay thế ở trên lúc nào là có lợi. Ngoài ra, liệu còn có những vấn đề khác ngoài các vấn đề đề cập ở trên hay không? Chúng ta sẽ tìm một sự thay thế tốt đối với một LĐQH có các quan hệ thể hiện tồi như thế nào? Nội dung chương này sẽ cho phép trả lời những câu hỏi như vậy. Một trong những cách tiếp cận đối với vấn đề thiết kế CSDL quan hệ là thiết kế các LĐQH ở một dạng chuẩn thích hợp. Trọng tâm của việc thiết kế các LĐQH là các phụ thuộc dữ liệu, tức là các ràng buộc có thể giữa các tập thuộc tính của các LĐQH. Các phụ thuộc dữ liệu này chính là nguyên nhân gây nên sự dư thừa dữ liệu và các dị thường cập nhật. 106 4.2. Phụ thuộc hàm Khái niệm phụ thuộc hàm (trên quan hệ) được giới thiệu bởi E. F. Codd vào những năm 1970, là một loại phụ thuộc dữ liệu xảy ra tự nhiên nhất giữa các tập thuộc tính và có tầm quan trọng hết sức lớn đối với việc thiết kế CSDL quan hệ. Mặc dù hiện nay có nhiều loại phụ thuộc dữ liệu được giới thiệu (như phụ thuộc mạnh, phụ thuộc yếu, phụ thuộc đối ngẫu, phụ thuộc đa trị, phụ thuộc Boole dương, ...), xong về cơ bản các hệ quản trị CSDL lớn đều sử dụng phụ thuộc hàm. 4.2.1. Định nghĩa Cho một tập hữu hạn khác rỗng các thuộc tính U = {a1 , a2 , . . . , an } và một quan hệ R = {t1 , t2 , . . . , tm } ∈ Rel(U ). Một phụ thuộc hàm (PTH) trên U là một mệnh đề có dạng X → Y trong đó X, Y ⊆ U và đọc là “X xác định hàm Y ” hay “Y phụ thuộc hàm vào X”. Tập X gọi là vế trái, tập Y gọi là vế phải của phụ thuộc hàm X → Y . PTH X → Y được gọi là đúng trên quan hệ R nếu ∀ti , tj ∈ R : ti (X) = tj (X) ⇒ ti (Y ) = tj (Y ). Khi PTH X → Y đúng trên quan hệ R thì ta còn nói quan hệ R thỏa PTH X → Y và ký hiệu là R(X → Y ). Ký hiệu F D(R) là tập tất cả các PTH đúng trên quan hệ R. Nghĩa là: F D(R) = {X → Y : R(X → Y )}. Trường hợp nếu quan hệ R không thỏa PTH X → Y thì ta viết R(¬X → Y ). Có thể thấy PTH (trên quan hệ) là sự phụ thuộc (theo nghĩa hàm) của một số thuộc tính vào một số thuộc tính khác. Ví dụ 4.2. Xét quan hệ R ∈ Rel(U ), với U = {a, b, c}, như sau: 107 a b c 0 0 1 R= 1 0 1 2 0 0 Ta có các PTH đúng trên R là {a} → {b}, {a} → {c}, {a} → {b, c}, {c} → {b}, {a, b} → {c} và {a, c} → {b}. Các PTH không đúng trên R là {b} → {a}, {b} → {c}, {c} → {a}, {c} → {a, b} và {b, c} → {a}. Lưu ý, trên tập thuộc tính U có thể có nhiều quan hệ R khác nhau nhưng tập F D(R) lại như nhau. Chẳng hạn, hai quan hệ khác nhau R1 , R2 ∈ Rel(U ) với U = {a, b} có F D(R1 ) = F D(R2 ): a b a b R1 = 0 0 , R2 = 0 1 1 0 1 1 Để đơn ...