Bài giảng Cơ sở dữ liệu - Đại học Quy Nhơn

hưng hai giải thuật tương ứng trên Hình 3.1.5 thì không đối xứng (ngược lại với mô hình quan hệ). Đây là nhược điểm chủ yếu của cách tiếp cận phân cấp vì nó dẫn đến sự phức tạp không cần thiết cho người sử dụng Điều này có nghĩa là các chương trình sẽ trở nên phức tạp hơn sự thực cần thiết và hậu quả là việc viết chương trình, gỡ rối và bảo trì sẽ đòi hỏi ở người lập trình nhiều thời gian hơn cần thiết. b. Mô hình phân cấp (Hierarchical Data Model) Tồn tại các dị thường đối với các thao tác lưu trữ cơ bản Phép chèn: Phép xoá: Phép thay đổi: b. Mô hình phân cấp (Hierarchical Data Model) Hình 3.6 Dữ liệu mẫu trong mô hình mạng c. Mô hình mạng (Network Data Model) 300 Nhận xét qua ví dụ: Cũng như trong mô hình phân cấp, dữ liệu được biểu hiện thông qua các bản ghi (record) và các mối kết nối (link) Ngoài các kiểu bản ghi biểu diễn nhà cung cấp và các mặt hàng, còn có kiểu bản ghi thứ ba: các kết nối (link or connector) Tất cả các thể hiện kết hợp đối với một hãng cung cấp đều đặt trong một chuỗi mà điểm bắt đầu và kết thúc chuỗi đều ở tại đó Tương tự, tất cả các thể hiện kết hợp đối với một mặt hàng đã cho đều đặt trong một chuỗi được bắt đầu và kết thúc tại chính nó Như vậy, mỗi mối kết hợp được xuất hiện trên đúng hai chuỗi: một chuỗi hãng cung cấp và một chuỗi mặt hàng Cấu trúc bên trong của tệp cho mô hình mạng phức tạp hơn cho mô hình phân cấp c. Mô hình mạng (Network Data Model) c. Mô hình mạng (Network Data Model) Mô hình mạng (Hình 3.6) đối xứng hơn mô hình phân cấp (Hình 3.4), tuy nhiên, các thủ tục này phức tạp hơn so với cả 2 mô hình quan hệ và mô hình phân cấp Không có các dị thường xảy ra đối với các thao tác lưu trữ cơ bản: Phép Chèn (Insert): Phép xoá (Delete): Phép thay đổi (Update) c. Mô hình mạng (Network Data Model) Nhược điểm chính của mô hình mạng là sự phức tạp, phức tạp từ cấu trúc của chính mô hình đến ngôn ngữ con dữ liệu có liên quan đến nó Nguồn gốc của sự phức tạp này nằm ở khối lượng thông tin về cấu trúc của mô hình dữ liệu này Thông tin phải bao gồm hai phần: bản ghi mối liên kết Các cấu trúc dữ liệu này rất gần với cấu trúc bộ nhớ c. Mô hình mạng (Network Data Model) Tầm quan trọng Tính độc lập dữ liệu là mục tiêu chủ yếu của các CSDL J. Date định nghĩa: Tính độc lập dữ liệu 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 cập" Phân loại mức độ độc lập Theo sơ đồ kiến trúc của hệ thống CSDL (Hình 3.1.1) cho thấy có hai mức "độc lập dữ liệu": Độc lập dữ liệu ở mức logic Độc lập dữ liệu ở mức vật lý 1.5. Tính độc lập dữ liệu Độc lập dữ liệu ở mức logic Vấn đề đặt ra: Có thể cần thiết phải thay đổi lược đồ khái niệm như thêm thông tin các loại khác nhau của các thực thể hoặc bớt, xoá các thông tin về các thực thể đang tồn tại trong CSDL Độc lập dữ liệu ở mức logic 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 => độc lập dữ liệu mức logic 1.5. Tính độc lập dữ liệu Độc lập dữ liệu ở mức vật lý Vấn đề đặt ra: Lược đồ vật lý có thể thay đổi do người quản trị CSDL mà không cần thay đổi lược đồ con Độc lập dữ liệu ở mức vật lý Việc tổ chức lại CSDL vật lý (thay đổi các tổ chức, cấu trúc dữ liệu trên các thiết bị nhớ thứ cấp) 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 đó => độc lập dữ liệu mức vật lý 1.5. Tính độc lập dữ liệu Qua các ví dụ trên => một hệ CSDL phải có khả năng biểu diễn hai dạng đối tượng: Các "thực thể" ("entities") và Các kết nối ("associations") Không có sự khác biệt thực sự giữa hai loại đối tượng trên: Một kết nối chỉ đơn thuần là một dạng riêng của thực thể 1.6. Kết luận Sự khác nhau giữa ba loại mô hình đã xét (mô hình quan hệ, mô hình phân cấp, mô hình mạng): Thể hiện ở cách thức cho phép người sử dụng quan sát và thao tác các kết nối. Mô hình quan hệ có nhiều ưu điểm và được nhiều người quan tâm hơn cả vì: Mô hình dữ liệu quan hệ có tính độc lập dữ liệu cao Mô hình dữ liệu quan hệ dễ 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 1.6. Kết luận 2.Mô hình CSDL quan hệ 2.1. Các khái niệm cơ bản. a. Quan hệ, bộ. b. Miền và thuộc tính. 2.2. Khoá. 2.3. Kết luận. 2.4. Các phép toán trên CSDL quan hệ. 2.1. Các khái niệm cơ bản. Khái niệm toán học của mô hình quan hệ: hiểu theo nghĩa lý thuyết tập hợp, đó là tập con của tích Đề-Các của các miền Miền (domain) là một tập các giá trị Ví dụ của miền: tập các số nguyên tập các xâu ký tự tạo thành tên các tỉnh, thành phố ở Việt Nam có độ dài không quá 30 ký tự tập hai giá trị {True, False} 2.1. Các khái niệm cơ bản. 1. Quan hệ, bộ. Tích Đề - Các của n miền: D1 x D2 x... x Dn là tập tất cả n-bộ (n-tuples) (1, 2,... n) sao cho i  Di với i = 1, 2, ... n Ví dụ: n = 2 D1 = {False, True} D2 = {a, b, c}, khi đó: D1 x D2 = {(False, a), (False, b), (False, c), (True, a), (True, b), (True, c)} 2.1. Các khái niệm cơ bản. Quan hệ (Relation) Một tập con của tích Đề-Các của một hoặc nhiều miền Như vậy, mỗi quan hệ có thể là vô hạn ở đây luôn luôn giả thiết rằng, quan hệ là một tập hữu hạn Quan hệ là tập con của tích Đề-Các D1 x D2 x ... x Dn được gọi là quan hệ n-ngôi Các thành phần của các bộ trong quan hệ gọi là các thuộc tính (attributes) Sự khác nhau giữa miền và thuộc tính: Một thuộc tính biểu thị cách sử dụng một miền trong một quan hệ 2.1. Các khái niệm cơ bản. Quan hệ được định nghĩa một cách hình thức như sau: Gọi R = {A1, A2, ... , An} là tập hữu hạn của các thuộc tính, mỗi thuộc tính Ai với i = 1, 2,..., n có miền giá trị tương ứng là dom(Ai) (các miền không nhất thiết là phải khác nhau) Quan hệ r trên tập thuộc tính R = {A1, A2, ..., An} là tập con của tích Đề - Các được biểu diễn như sau: r  dom (A1) x dom (A2) x... dom (An) Ví dụ: Hình 3.6, ba quan hệ được gọi là S, P, SP Quan hệ P là quan hệ 5-ngôi được định nghĩa trên 5 miền: P#, PNAME, COLOR, WEIGHT, CITY Ví dụ, miền COLOR là tập của tất cả các màu sắc hợp lệ của các mặt hàng Ta có p1 = (P1, Nut, Red, 12, London) là một bộ (tuple, row) của quan hệ P Bộ (tuples) Hình 3.6 Dữ liệu mẫu trong dạng quan hệ. Supplier - Hãng cung cấp Part - Mặt hàng Shipment – Gửi hàng 2.1. Các khái niệm cơ bản. 2.1. Các khái niệm cơ bản. 2. Miền và thuộc tính. Cần phân biệt rõ sự khác nhau giữa miền và các thuộc tính - hay còn gọi là các cột - được rút ra từ miền này Một thuộc tính biểu thị sự sử dụng một miền trong một quan hệ (các thành phần của các bộ trong quan hệ gọi là các thuộc tính) Để nhấn mạnh sự khác nhau này, chúng ta có thể đặt tên cho thuộc tính khác với tên của miền đã cho, ví dụ như trên Hình 2.1. 2.1. Các khái niệm cơ bản. Ví dụ: Hình 3.7, Khai báo lược đồ mẫu 2.1. Các khái niệm cơ bản. Hình 3.7 là một phần của lược đồ khái niệm, trong đó có: Năm miền (P#, PNAME, COLOR, WEIGHT, CITY) Một quan hệ (PART) đã được khai báo Quan hệ PART này được định nghĩa với năm thuộc tính: PARTNO PARTNAME COLOR WT LOC và Mỗi thuộc tính được chỉ rõ đã rút ra từ miền tương ứng nào Để thuận tiện, người ta thường bỏ qua phần khai báo tên miền ("DOMAIN name") khi khai báo thuộc tính nếu tên thuộc tính giống tên miền Tuy nhiên, không phải luôn có thể đặt tên thuộc tính trùng với tên miền Hình 3.8 Quan hệ COMPONENT 2.1. Các khái niệm cơ bản. 2.1. Các khái niệm cơ bản. Trong ví dụ này, chúng ta có một quan hệ với ba thuộc tính nhưng chỉ có hai miền khác nhau ý nghĩa của một bộ (tuple) trong quan hệ COMPONENT là một mặt hàng chính (MAJOR_P#) có kèm theo mặt hàng phụ (MINOR_P#) và số lượng các mặt hàng phụ này (QUANTITY) Ví dụ này cũng minh hoạ một sự thuận tiện thông thường khác: Cách tạo tên thuộc tính khác nhau bằng cách đặt phần tiền tố (MAJOR, MINOR) trước tên miền chung (P#) để phân biệt vai trò của các thuộc tính có cùng chung một miền (P#) 2.1. Các khái niệm cơ bản. Khái niệm "chuẩn hoá": Mô hình quan hệ chỉ chấp nhận duy nhất các quan hệ thoả mãn điều kiện “Mọi giá trị trong quan hệ - nghĩa là tất cả các giá trị của các thuộc tính trong tất cả các bộ - đều phải là nguyên tố (atomic) (nghĩa là không chia nhỏ được nữa)” . Nói một cách khác, tại mỗi vị trí cắt nhau của một hàng và một cột trong bảng tồn tại đúng một giá trị và không bao giờ là một tập các giá trị. Quan hệ thoả mãn điều kiện trên được gọi là “đã được chuẩn hoá”. 2.1. Các khái niệm cơ bản. Ví dụ: 2.1. Các khái niệm cơ bản. Luôn có thể chuyển một quan hệ chưa chuẩn hoá sang dạng chuẩn hoá tương đương Quan hệ BEFORE (hình 2.3) được định nghĩa trên các miền: S# (Supplier number: số hiệu hãng cung cấp) và PQ (Part-Quantity: mặt hàng - số lượng) Các phần tử của PQ chính là các quan hệ được định nghĩa trên các miền: P# (số hiệu mặt hàng) và QTY (Quantity: số lượng hàng)  do đó, quan hệ BEFORE là chưa được chuẩn hoá Quan hệ AFTER là quan hệ tương đương đã được chuẩn hoá Về mặt toán học: BEFORE là quan hệ hai ngôi nhưng không phải tất cả các miền đều là đơn giản (Miền đơn giản là miền mà trong đó tất cả các phần tử là nguyên tố) AFTER là quan hệ ba ngôi tương đương về mặt ngữ nghĩa với quan hệ BEFORE nhưng tất cả các miền của các thuộc tính của nó đều là đơn giản. 2.2. Khoá 1. Khoá chính (Primary key). 2. Khóa ứng cử (Candidate key). 3. Khóa ngoại lai (Foreign key). 4. Khóa phụ (Sub-Key). 2.2. Khóa Khóa chính (Primary key) Khóa chính là một thuộc tính hoặc một kết hợp tối thiểu các thuộc tính cho phép ta nhận diện duy nhất một thực thể riêng biệt nào đó. Tính “nhận diện duy nhất”: Trong một quan hệ đã cho luôn có một thuộc tính hoặc một kết hợp các thuộc tính với các giá trị cho phép nhận dạng duy nhất các bộ của quan hệ này. Trong lược đồ quan hệ có thể có rất nhiều khoá Việc tìm tất cả các khoá của lược đồ quan hệ là rất khó khăn Tính “tối thiểu”: Không phải thường xuyên cần đến tất cả các thuộc tính. Không một thuộc tính thành phần nào của khoá chính là thừa với mục đích nhận dạng duy nhất. 2.2. Khóa 2. Khoá ứng cử (Candidate key) Khóa ứng cử là thuộc tính hoặc kết hợp các thuộc tính có tính chất như khóa chính. Đôi khi có thể gặp một quan hệ trong đó có hơn một kết hợp các thuộc tính có khả năng nhận diện duy nhất và tối thiểu như khóa chính  do đó có hơn một khoá ứng cử (candidate key) Ví dụ: Giả thiết, tên hãng cung cấp là duy nhất => Khóa ứng cử: S#; SNAME 2.2. Khóa 2.2. Khóa 3. Khoá ngoại lai (Foreign key) Một thuộc tính của quan hệ R1 được gọi là một khoá ngoại lai nếu nó không phải là khoá chính của quan hệ R1 nhưng các giá trị của nó là các giá trị của khoá chính trong một quan hệ R2 nào đó (quan hệ R1 và R2 không nhất thiết phải khác nhau). Các khoá chính và khoá ngoại lai cho ta các phương tiện để biểu diễn các liên kết giữa các bộ. Tuy nhiên, cần lưu ý là không phải tất cả các thuộc tính có thể biểu diễn các liên kết như vậy đều là khoá 2.2. Khóa 4. Khoá phụ (Secondary key) Dùng để xắp sếp hoặc tìm kiếm Lưu ý: khi sử dụng một ngôn ngữ con dữ liệu dạng quan hệ không nên giới hạn việc truy nhập vào một quan hệ là "chỉ có thể thông qua khoá chính" 2.2. Khóa Theo lý thuyết quan hệ, khoá (key) của một quan hệ r trên tập thuộc tính R = {A1, ..., An} là tập con K  {A1 ... An} thoả mãn các tính chất sau đây: Với bất kỳ hai bộ t1, t2  r đều tồn tại một hoặc một kết hợp các thuộc tính A  K sao cho t1(A)  t2(A) Điều kiện này có thể viết t1(K)  t2(K). Do vậy mỗi giá trị của K là xác định duy nhất Để có thể định nghĩa khoá một cách tốt hơn, lưu ý rằng, nếu K' là khoá của quan hệ r(A1, ..., An) thì K'  K  R, K cũng là khoá của r, nghĩa là với bất kỳ t1, t2  r với t1 (K')  t2 (K') luôn có t1 (K)  t2 (K) 2.2. Khóa Lưu ý:nếu K' là khoá của quan hệ r(A1, ..., An) thì K'  K  R, K cũng là khoá của quan hệ r. Để đảm bảo tính không dư thừa của khoá chính ta có định nghĩa sau về khoá chính: Khoá chính của quan hệ r trên tập thuộc tính R = {A1, ..., An} là tập con K  R sao cho bất kỳ hai bộ khác nhau t1, t2  r luôn thoả t1(K)  t2(K) và bất kỳ tập con thực sự K'  K nào đó đều không có tính chất đó a r, nghĩa là với bất kỳ t1, t2  r với t1 (K')  t2 (K') luôn có t1 (K)  t2 (K) 2.3. Kết luận Có thể định nghĩa mô hình quan hệ của một CSDL là một khung nhìn của CSDL đó gồm một tập các quan hệ đã được chuẩn hoá và thay đổi theo thời gian với các ngôi đã được xếp hạng Nhất thiết phải chỉ rõ đặc điểm "thay đổi theo thời gian" để cho phép thực hiện các phép toán chèn (insert), xoá (delete) và cập nhật (update) các bộ của quan hệ. 2.3. Kết luận Lược đồ khái niệm 2.3. Kết luận Lược đồ khái niệm 2.3. Kết luận Theo các khái niệm truyền thống, một quan hệ tạo nên một file, một bộ tạo nên một bản ghi (thể hiện chứ không phải là kiểu) và một thuộc tính tạo nên một trường (kiểu chứ không phải thể hiện) Nói một cách khác, các quan hệ có thể được coi như các file mang tính quy tắc cao (highly disciplined files) Tính quy tắc này dẫn đến sự đơn giản hoá mong muốn cho các cấu trúc dữ liệu liên quan đến người sử dụng và do đó dẫn đến sự đơn giản hoá tương ứng trong các phép toán cần thiết để thao tác dữ liệu 2.4. Các phép toán trên CSDL quan hệ Chèn (insert) Loại bỏ (delete) Thay đổi (change) Trong mô hình CSDL quan hệ được nêu trên, các phép toán này được áp dụng cho từng bộ của các quan hệ lưu trữ trong máy 2.4. Các phép toán trên CSDL quan hệ 1. Phép chèn (INSERT) Phép chèn thêm một bộ t vào quan hệ r {A1, ..., An} có dạng: r = r  t Ta có thể biểu diễn chi tiết phép chèn như sau: INSERT (r; A1 = d1, A2 = d2, ..., An = dn) Trong đó: - Ai với i = 1, ..., n là tên các thuộc tính và di với di  dom(Ai) là các giá trị thuộc miền trị tương ứng của thuộc tính Ai. Ví dụ: Để thêm một bộ t4 = (S4, Clark, 20, London) vào quan hệ S trong hình 1.2 ta làm như sau: INSERT(S; S# = S4, SNAME = Clark, STATUS = 20, CITY = London) 2.4. Các phép toán trên CSDL quan hệ Nếu xem thứ tự các trường là cố định, khi đó có thể biểu diễn phép chèn dưới dạng không tường minh như sau: INSERT (r; d1, d2, ..., dn) Mục đích của phép chèn là thêm một bộ vào một quan hệ nhất định Kết quả của phép toán này có thể gây ra một số sai sót với những lý do sau đây: Bộ mới cần thêm vào không phù hợp với lược đồ quan hệ đã cho Một số giá trị của một số thuộc tính nằm ngoài miền giá trị của thuộc tính đó Giá trị khoá của bộ mới có thể là giá trị đã có trong quan hệ đang lưu trữ Do vậy, tuỳ từng hệ thống cụ thể sẽ có những cách khắc phục riêng 2.4. Các phép toán trên CSDL quan hệ 2. Phép loại bỏ (DEL) Phép loại bỏ (DEL) là phép xoá một bộ ra khỏi một quan hệ cho trước Giống như phép chèn, phép loại bỏ có dạng: r = r \ t Ta có thể biểu diễn chi tiết phép loại bỏ như sau: DEL (r; A1 = d1, A2 = d2, ..., An = dn) Hoặc nếu xem thứ tự các trường là cố định thì: DEL (r; d1, d2, ... dn) Ví dụ: Cần loại bỏ bộ tương ứng với P2, S3 trong quan hệ SP trên hình 1.2 ta làm như sau: DEL (SP; S# = S3, P# = P2, QTY = 200) 2.4. Các phép toán trên CSDL quan hệ Tuy nhiên, không phải lúc nào phép loại bỏ cũng cần đầy đủ tất cả các loại thông tin của bộ cần loại bỏ Nếu có giá trị về bộ đó tại các thuộc tính khoá K = {B1, B2,..., Bj} thì phép loại bỏ chỉ cần viết: DEL (r; B1 = f1, B2 = f2, ..., Bi = fj) Ví dụ, trong phép loại bỏ nêu trên, vì (S#, P#) là khoá của quan hệ SP nên ta chỉ cần viết: DEL (SP; S# = S3, P# = P2) 2.4. Các phép toán trên CSDL quan hệ 3. Phép thay đổi (CHANGE hoặc UPDATE) Trong thực tế không phải lúc nào cũng chỉ dùng phép chèn hoặc loại bỏ đi một bộ mà nhiều khi chỉ cần sửa đổi một số giá trị nào đó tại một số thuộc tính, lúc đó cần thiết phải sử dụng phép thay đổi ("Change" hay viết tắt là CH) Gọi tập {C1, ..., Cp}  {A1, ..., An} là tập các thuộc tính mà tại đó các giá trị của bộ cần thay đổi, khi đó phép thay đổi có dạng: r = r \ t  t' Hay ta có thể biểu diễn chi tiết phép loại bỏ như sau: CH (r; A1 = d1, A2 = d2, ..., An = dn; C1 = e1, C2 = e2, ..., Cp = ep) 2.4. Các phép toán trên CSDL quan hệ Nếu K = {B1, ..., Bm} là khoá của quan hệ, khi đó chỉ cần viết: CH (r; B1 = f1, B2 = f2, ..., Bm = fm; C1 = e1, C2 = e2, ..., Cp = ep) Ví dụ: Cần thay đổi địa chỉ hãng cung cấp S1 từ London thành Amsterdam trong quan hệ S. Khi đó phép thay đổi có dạng như sau: CH (S; S# = S1; CITY = Amsterdam) Cũng có thể không dùng phép thay đổi mà dùng tổ hợp của phép loại bỏ và phép chèn một bộ mới Do vậy, sai sót đối với phép thay đổi cũng sẽ xảy ra tương tự như với phép chèn và phép loại bỏ 3. Chuẩn hóa CSDL 3.1. Giới thiệu. 1. Mục đích & Các khái niệm. 2. Các mức (dạng) chuẩn hóa. 3.2. Khái niệm phụ thuộc hàm. 1. Định nghĩa. 2. Hệ tiên đề Amstrong và các bổ đề. 3. Khái niệm bao đóng. 4. Phụ thuộc hàm đầy đủ. 3. Chuẩn hóa CSDL 3.3. Các mức (dạng) chuẩn hóa. 1. Mức chưa chuẩn hóa. 2. Mức 1NF. 3. Mức 2NF. 4. Mức 3NF. 5. Mức BCNF. 3.4. Phép tách sơ đồ quan hệ. 1. Phép tách bảo toàn thông tin. 2. Phép tách bảo toàn tập phụ thuộc hàm. 3.5. Kết luận. 1. Các bước đưa về các dạng chuẩn hóa. 2. Kết luận. 3.1. Giới thiệu. 1. Mục đích & Các khái niệm. Mục đích Mục đích của chuẩn hóa Khái niệm Các vấn đề với dữ liệu Redundancy Inconsistency Các dị thường (anomalies) Update Insert Delete 3.1. Giới thiệu. 2. Các mức chuẩn hoá. Hình 3.1. Các mức của chuẩn hoá 3.2. Phụ thuộc hàm. 1. Định nghĩa: Cho trước một quan hệ R, chúng ta nói rằng, thuộc tính Y của R là phụ thuộc hàm vào thuộc tính X của R nếu và chỉ nếu mỗi giá trị của X trong R được kết hợp với đúng một giá trị của Y trong R tại bất kỳ thời điểm nào. 3.2. Phụ thuộc hàm. a. Định nghĩa (theo lý thuyết quan hệ) Cho trước quan hệ R với tập thuộc tính U={A1, A2, ...An}, ta có X, Y  U là tập các thuộc tính con của U. Ta nói Y là phụ thuộc hàm vào X (hay X suy ra Y) nếu và chỉ nếu với mọi quan hệ r xác định trên R và với mọi 2 bộ t1, t2 bất kỳ, nếu t1[X] = t2[X] thì suy ra t1[Y] = t2[Y] tại bất kỳ thời điểm nào. Ký hiệu: X → Y Lưu ý: Có thể không có t1[X] = t2[X] nhưng vẫn tồn tại phụ thuộc hàm. Yếu tố: tại bất kỳ thời điểm nào. 3.2. Phụ thuộc hàm. b. Hệ tiên đề Amstrong và bổ đề Hệ tiên đề Phản xạ (reflexivity): nếu Y  X  U thì X → Y Tăng trưởng (augmentation): nếu X → Y, Z  U thì XZ → YZ Bắc cầu (transitivity): nếu X → Y, Y → Z thì X → Z Bổ đề nếu X → Y, X → Z thì X → YZ nếu X → Y, WY → Z thì XW → Z nếu X → Y, Z  Y thì X → Z 3.2. Phụ thuộc hàm. c. Khái niệm bao đóng Bao đóng của tập phụ thuộc hàm F+ Tập hợp tất cả các phụ thuộc hàm được suy ra từ F Tập phụ thuộc hàm F tối thiểu Nếu không tồn tại một phụ thuộc hàm X → Y Є F sao cho: F \ {X → Y} tương đương với F Cách tìm: vế phải của các phụ thuộc hàm chỉ để 1 thuộc tính vế trái của các phụ thuộc hàm không bỏ được thuộc tính nào không có phụ thuộc hàm nào bỏ được Bao đóng của tập các thuộc tính X+ Tập hợp tất cả các các thuộc tính phụ thuộc hàm vào X X+ = {A | A là thuộc tính sao cho X → A Є F+} 3.2. Phụ thuộc hàm. d. Phụ thuộc hàm đầy đủ Định nghĩa Tập thuộc tính Y được gọi là phụ thuộc hàm đầy đủ vào tập thuộc tính X nếu nó là phụ thuộc hàm vào X và không phụ thuộc hàm vào bất kỳ một tập con nào của các thuộc tính của X. Lưu ý Sau đây chúng ta sẽ nói "phụ thuộc hàm" với ý nghĩa phụ thuộc hàm đẩy đủ trừ khi có giải thích tường minh . 3.3. Các mức chuẩn hóa. a. Chưa chuẩn hóa Ví dụ Mức 1NF Định nghĩa Quan hệ R được gọi là ở dạng chuẩn thứ nhất (1NF) nếu và chỉ nếu tất cả các miền đều chỉ chứa các giá trị nguyên tố. 3.3. Các mức chuẩn hóa. b. Mức 2NF Định nghĩa Quan hệ R được gọi là ở dạng chuẩn thứ hai (2NF) nếu và chỉ nếu nó ở dạng chuẩn thứ nhất và mọi thuộc tính không khoá đều phụ thuộc hàm đầy đủ vào khoá chính. Một thuộc tính được gọi là thuộc tính không khoá nếu nó không tham dự vào thành phần của khoá chính hoặc khóa ứng cử. ý nghĩa Giảm vấn đề dư thừa và không nhất quán của dữ liệu. 3.3. Các mức chuẩn hóa. Nhận xét Nếu mức 1NF có khóa là khoá đơn: 1NF => 2NF Nếu mức 1NF không có thuộc tính không khóa: 1NF => 2NF Chuyển từ 1NF sang 2NF: phép tách sơ đồ quan hệ Thay thế các quan hệ mức 1NF bằng tập các quan hệ ở mức 2NF thông qua các ánh xạ Các vấn đề cần giải quyết khi thực hiện phép tách Bảo toàn thông tin khi chuyển đổi. Bảo toàn tập phụ thuộc hàm. Ví dụ 3.3. Các mức chuẩn hóa. Các vấn đề còn tồn tại với mức 2NF Phụ thuộc hàm bắc cầu vẫn tồn tại và tạo ra sự dư thừa dữ liệu. Ví dụ: giả sử City → Status (Status phụ thuộc hàm gián tiếp vào khoá S#) hoặc ví dụ quan hệ (S#, ITEM, PRICE) có S# là khoá và ITEM → PRICE Các phụ thuộc hàm bắc cầu này gây ra những khó khăn khi thực hiện các phép toán: Insert Delete Update 3.3. Các mức chuẩn hóa. c. Mức 3NF Định nghĩa Quan hệ R được gọi là ở dạng chuẩn thứ ba (3NF) nếu và chỉ nếu nó ở dạng chuẩn thứ 2 (2NF) và mọi thuộc tính không khoá đều không phụ thuộc hàm bắc cầu vào khoá chính thông qua các thuộc tính không khoá. Y gọi là phụ thuộc hàm bắc cầu vào X thông qua Z nếu Y phụ thuộc hàm vào Z (ZY) và Z lại phụ thuộc hàm vào X (XZ) (với điều kiện X không phụ thuộc hàm vào Z hoặc Y). ý nghĩa Làm biến mất các phụ thuộc hàm bắc cầu của các thuộc tính không khoá. Giảm vấn đề dư thừa và không nhất quán của dữ liệu. 3.3. Các mức chuẩn hóa. Cách nhận biết mức 3NF Quan hệ R mức 1NF là 3NF nếu mọi phụ thuộc hàm tối thiểu XA (A là thuộc tính đơn, A ∉ X) đều có dạng: hoặc X là khoá hoặc A là thuộc tính khoá Chuyển sang 3NF: phép tách sơ đồ quan hệ Thay thế các quan hệ mức 2NF bằng tập các quan hệ ở mức 3NF thông qua các ánh xạ Các vấn đề cần giải quyết khi thực hiện phép tách Bảo toàn thông tin khi chuyển đổi. Bảo toàn tập phụ thuộc hàm. Ví dụ Định lý: quan hệ mức 1NF luôn có thể tách thành các sơ đồ quan hệ con mức 3NF mà vẫn bảo toàn thông tin. 3.3. Các mức chuẩn hóa. Lưu ý: mức độ chuẩn hoá đối với một lược đồ quan hệ đã cho được xác định bởi ngữ nghĩa (semantic) chứ không phải bởi các giá trị đã có mặt trong quan hệ tương ứng tại một thời điểm cụ thể nào đó phải biết ý nghĩa của dữ liệu rồi mới có thể đưa ra nhận định hiện tại lược đồ tương ứng của quan hệ đó ở dạng chuẩn nào HQTCSDL không thể khẳng định rằng một lược đồ quan hệ đã ở dạng chuẩn tốt nhất (3NF chẳng hạn) nếu như chưa nhận đầy đủ thông tin về các phụ thuộc dữ liệu tương ứng 3.3. Các mức chuẩn hóa. Các vấn đề còn tồn tại với mức 3NF Phụ thuộc hàm bắc cầu của các thuộc tính khoá vẫn có thể tồn tại và tạo ra sự dư thừa dữ liệu. Ví dụ: 3.3. Các mức chuẩn hóa. d. Mức BCNF (Boyce – Codd Normal Form) Định nghĩa Một thuộc tính (có thể là thuộc tính ghép) được gọi là thuộc tính quyết định (determinant) nếu một thuộc tính khác nào đó là phụ thuộc hàm đầy đủ vào nó. Quan hệ đã được chuẩn hoá R được gọi là ở dạng chuẩn BCNF nếu mọi thuộc tính quyết định đều là khoá ứng cử (candidate key). Nhận xét Boyce và Codd xem xét các phụ thuộc hàm của cả các khoá ứng cử trong quan hệ. Đối với quan hệ chỉ có một khoá ứng cử thì các định nghĩa 3NF và BCNF là tương đương. BCNF không nêu lên điều kiện đầu tiên quan hệ đã cho phải ở dạng chuẩn 3NF và sau đó mới thoả mãn thêm điều kiện nữa. Như vậy: cần lưu ý là định nghĩa BCNF không hoàn toàn tương đương với định nghĩa 3NF. định nghĩa 3NF không hoàn toàn phù hợp với trường hợp của một quan hệ có hai khoá ứng cử phủ nhau như sẽ xem xét sau này. Hai khoá ứng cử là tập phủ nếu mỗi khoá gồm hơn một thuộc tính và có thuộc tính chung Tuy nhiên, điều sau đây vẫn còn đúng: Bất kỳ một quan hệ nào không ở dạng chuẩn 3NF (hay BCNF) đều có thể được tách thành một tập tương đương ở dạng chuẩn 3NF (hay BCNF) Nếu quan hệ ở mức BCNF thì cũng đã đạt mức 3NF. 3.3. Các mức chuẩn hóa. Cách nhận biết mức BCNF Quan hệ R mức 1NF là BCNF nếu mọi phụ thuộc hàm tối thiểu XA (A là thuộc tính đơn, A ∉ X) đều có dạng X là khoá. Là 1NF và không có bất cứ một phụ thuộc hàm bắc cầu nào. 3.3. Các mức chuẩn hóa. Xét các trường hợp cụ thể Trường hợp 1: Đối với quan hệ chỉ có một khoá ứng cử thì các định nghĩa 3NF và BCNF là tương đương Trường hợp 2: Quan hệ là 3NF và BCNF vì có hai khoá ứng cử không phủ nhau (non-overlapping) Ví dụ Xét ví dụ trong đó quan hệ S là 3NF và cũng là BCNF vì có hai khoá ứng cử không phủ nhau: S(S#, SNAME, STATUS, CITY) 3.3. Các mức chuẩn hóa. Xét các trường hợp cụ thể Trường hợp 3: Quan hệ là 3NF nhưng không là BCNF vì khoá ứng cử là tập phủ Ví dụ : Xét quan hệ SJT với các thuộc tính S (Student), J (Subject), T (Teacher) ý nghĩa của một bộ trong quan hệ SJT là một sinh viên được chỉ định được học một môn được chỉ định là do một giáo viên được chỉ định dạy Mỗi môn học cho mỗi sinh viên học môn đó chỉ do một giáo viên dạy Mỗi giáo viên chỉ dạy một môn học Mỗi môn học có thể do một vài giáo viên dạy Hình 3.11. Bảng dữ liệu mẫu cho quan hệ SJT 3.3. Các mức chuẩn hóa. Xét các trường hợp cụ thể Trường hợp 4: Quan hệ là 3NF và cũng là BCNF mặc dù có khoá ứng cử là tập phủ Ví dụ: quan hệ EXAM với các thuộc tính S (Student), J (Subject), P (Position) ý nghĩa của một bộ của quan hệ EXAM là một sinh viên được chỉ định đã thi một môn học được chỉ định sẽ đạt được một vị trí đã chỉ định trong danh sách lớp Với mục đích của bài toán, đưa ra một giả thiết không thể có hai sinh viên cùng nhận một vị trí trong một môn học nào đó RELATION EXAM (S, J, P) (S, J)  P (J, P)  S KEY (S, J) UNIQUE (J, P) 3.5. Kết luận. Các bước đưa về dạng chuẩn 3NF/BCNF. Buớc 1: Chuyển quan hệ chưa chuẩn hóa thành 1 tập quan hệ tương đương ở dạng 1NF. 2 phương p