Tài liệu học tập CSDL: Lý thuyết thiết kế, Phụ thuộc hàm, Chuẩn hóa (UNETI)

Tài liệu học tập cơ sở dữ liệu phần 2 dành cho sinh viên trường Đại học Kinh tế Kỹ thuật Công nghiệp. Nâng cao kiến thức chuyên sâu về CSDL, chuẩn bị vững chắc

• Trường học: Trường Đại học Kinh tế Kỹ thuật Công nghiệp
• Chuyên ngành: Công nghệ Thông tin
• Đề tài: Lý thuyết thiết kế cơ sở dữ liệu: Phụ thuộc hàm và chuẩn hóa
• Loại tài liệu: Tài liệu học tập

Tóm tắt

I. Tổng quan về lý thuyết phụ thuộc hàm và chuẩn hóa CSDL

Lý thuyết thiết kế cơ sở dữ liệu quan hệ do E.F. Codd đề xuất là nền tảng quan trọng trong lĩnh vực công nghệ thông tin. Phụ thuộc hàm (FD) là khái niệm cốt lõi, mô tả mối quan hệ giữa các thuộc tính trong lược đồ quan hệ. Phụ thuộc hàm X → Y tồn tại khi giá trị của tập thuộc tính X xác định duy nhất giá trị của tập thuộc tính Y. Ví dụ, trong quan hệ nhà cung ứng S, thuộc tính S# xác định SNAME, STATUS và CITY. Hệ tiên đề Armstrong cung cấp ba quy tắc cơ bản: phản xạ, tăng trưởng và bù. Các quy tắc này cho phép suy diễn tất cả phụ thuộc hàm từ một tập phụ thuộc hàm đã cho. Chuẩn hóa là quá trình phân tích và tái cấu trúc lược đồ quan hệ. Mục tiêu là loại bỏ trùng lặp dữ liệu và các bất thường tiềm ẩn. Quá trình này sử dụng các dạng chuẩn: 1NF, 2NF, 3NF và BCNF.

1.1. Định nghĩa phụ thuộc hàm cơ bản

Phụ thuộc hàm là mối quan hệ ràng buộc giữa hai tập thuộc tính trong lược đồ quan hệ R(U). Cho X và Y là tập con của U, ký hiệu X → Y nghĩa là mỗi giá trị của X tương ứng với đúng một giá trị của Y. Cần phân biệt phụ thuộc hàm đầy đủ và phụ thuộc hàm bộ phận. FD đầy đủ là khi loại bỏ bất kỳ thuộc tính nào khỏi X thì FD không còn đúng. FD bộ phận là khi có thể bỏ một thuộc tính khỏi X mà FD vẫn giữ nguyên.

1.2. Vai trò của lý thuyết chuẩn hóa trong thiết kế CSDL

Chuẩn hóa giúp xây dựng cơ sở dữ liệu có cấu trúc rõ ràng và logic. Quá trình này giảm thiểu sự trùng lặp thông tin giữa các bảng. Đồng thời ngăn chặn các bất thường khi cập nhật, xóa hoặc chèn dữ liệu. Các dạng chuẩn được xây dựng theo cấp độ tăng dần. Mỗi cấp độ giải quyết một loại vấn đề cụ thể. Từ 1NF đảm bảo giá trị nguyên tử đến BCNF xử lý mọi phụ thuộc hàm không tầm thường.

II. Phân tích vấn đề trùng lặp và bất thường dữ liệu trong lược đồ quan hệ

Thiết kế lược đồ quan hệ không đúng cách dẫn đến nhiều vấn đề nghiêm trọng. Trùng lặp dữ liệu là vấn đề phổ biến nhất. Cùng một thông tin được lưu trữ ở nhiều vị trí khác nhau trong cơ sở dữ liệu. Bất thường cập nhật xảy ra khi thay đổi thông tin ở một chỗ nhưng quên cập nhật ở chỗ khác. Dữ liệu trở nên không nhất quán giữa các bảng. Bất thường xóa là khi xóa một bản ghi dẫn đến mất mát thông tin quan trọng. Ví dụ, xóa nhà cung ứng có thể mất thông tin về sản phẩm mà họ cung cấp. Bất thường chèn xuất hiện khi không thể thêm dữ liệu mới do thiếu thông tin liên quan. Các vấn đề này xuất phát từ phụ thuộc hàm không đầy đủ và phụ thuộc hàm bắc cầu. Chúng làm tăng kích thước cơ sở dữ liệu và giảm hiệu suất truy vấn đáng kể.

2.1. Bất thường dữ liệu do thiết kế lược đồ kém

Trùng lặp dữ liệu gây lãng phí bộ nhớ và tạo ra mâu thuẫn trong hệ thống. Khi cập nhật một giá trị, cần thay đổi ở tất cả các vị trí chứa thông tin đó. Nếu bỏ sót, dữ liệu sẽ không còn chính xác và đáng tin cậy. Bất thường xóa có thể phá vỡ tính toàn vẹn tham chiếu. Một bản ghi bị xóa có thể kéo theo mất mát nhiều thông tin liên quan. Điều này ảnh hưởng nghiêm trọng đến độ tin cậy của hệ thống cơ sở dữ liệu.

2.2. Phụ thuộc hàm bộ phận và phụ thuộc bắc cầu

Phụ thuộc hàm bộ phận xảy ra khi một thuộc tính chỉ phụ thuộc vào một phần của khóa chính. Tình huống này thường gặp trong lược đồ có khóa chính composite. Một phần của khóa xác định thuộc tính không phải khóa. Phụ thuộc bắc cầu là khi thuộc tính A xác định B, B xác định C nhưng C không trực tiếp phụ thuộc A. Chuỗi phụ thuộc này tạo ra dữ liệu dư thừa không cần thiết trong lược đồ quan hệ.

III. Các phương pháp chuẩn hóa lược đồ quan hệ hiệu quả

Chuẩn hóa lược đồ quan hệ là giải pháp hiệu quả cho các vấn đề trùng lặp và bất thường. Quá trình này sử dụng phép tách để chia lược đồ lớn thành các lược đồ con. Mỗi lược đồ con thỏa mãn một dạng chuẩn cụ thể. Dạng chuẩn 1 (1NF) yêu cầu mọi thuộc tính có giá trị nguyên tử. Không tồn tại nhóm lặp lại trong bất kỳ trường nào. Dạng chuẩn 2 (2NF) loại bỏ phụ thuộc hàm bộ phận vào khóa chính. Mọi thuộc tính không khóa phải phụ thuộc đầy đủ vào toàn bộ khóa chính. Dạng chuẩn 3 (3NF) loại bỏ phụ thuộc hàm bắc cầu. Không thuộc tính không khóa nào phụ thuộc vào thuộc tính không khóa khác. BCNF là dạng chuẩn mạnh hơn, yêu cầu mọi determinant đều là siêu khóa. Quá trình chuẩn hóa cần cân bằng giữa tính chuẩn tắc và hiệu suất hệ thống.

3.1. Quy trình chuẩn hóa từng bước từ 1NF đến BCNF

Bước đầu tiên là xác định tất cả phụ thuộc hàm trong lược đồ quan hệ. Sử dụng hệ tiên đề Armstrong để tính bao đóng của tập phụ thuộc hàm. Xác định khóa chính và khóa ứng viên của lược đồ. Tiếp theo, kiểm tra lược đồ có thỏa mãn dạng chuẩn mục tiêu hay không. Nếu vi phạm, thực hiện phép tách không mất mát. Lược đồ được chia thành hai hoặc nhiều lược đồ con đạt chuẩn yêu cầu.

3.2. Hệ tiên đề Armstrong và ứng dụng trong suy diễn phụ thuộc hàm

Hệ tiên đề Armstrong bao gồm ba quy tắc: phản xạ, tăng trưởng và bù. Quy tắc phản xạ: nếu Y là tập con của X thì X → Y. Quy tắc tăng trưởng: nếu X → Y thì XZ → YZ. Quy tắc bù: nếu X → Y và X → Z thì X → YZ. Từ ba quy tắc cơ bản, có thể suy diễn tất cả phụ thuộc hàm logic. Bao đóng F+ chứa toàn bộ phụ thuộc hàm suy diễn từ F.

IV. Kết luận và ứng dụng thực tế của lý thuyết chuẩn hóa CSDL

Lý thuyết phụ thuộc hàm và chuẩn hóa đóng vai trò quan trọng trong thiết kế cơ sở dữ liệu hiện đại. Nền tảng lý thuyết này giúp xây dựng hệ thống dữ liệu chất lượng cao và đáng tin cậy. Kết quả là cơ sở dữ liệu hoạt động ổn định và hiệu quả trong thời gian dài. Ứng dụng thực tế rất đa dạng, từ hệ thống quản lý doanh nghiệp đến thương mại điện tử. Thiết kế chuẩn hóa giúp giảm chi phí bảo trì và nâng cấp hệ thống. Sinh viên ngành công nghệ thông tin cần nắm vững lý thuyết này. Kiến thức về phụ thuộc hàm và dạng chuẩn là nền tảng cho nhiều môn học khác. Thực hành nhiều bài tập giúp hiểu sâu và vận dụng linh hoạt trong các dự án thực tế. Tuy nhiên, đôi khi cần phi chuẩn hóa để tối ưu hiệu suất truy vấn. Quyết định phi chuẩn hóa phải dựa trên phân tích kỹ lưỡng về yêu cầu cụ thể.

4.1. Ứng dụng chuẩn hóa trong phát triển phần mềm hiện đại

Trong phát triển phần mềm, chuẩn hóa giúp thiết kế database schema rõ ràng và dễ bảo trì. Các framework ORM hoạt động hiệu quả hơn với lược đồ được chuẩn hóa đúng cách. Việc mở rộng hệ thống trở nên đơn giản hơn khi cấu trúc dữ liệu logic. Các hệ thống NoSQL cũng áp dụng nguyên tắc chuẩn hóa ở mức độ nhất định. Dù mô hình dữ liệu khác nhau, mục tiêu giảm trùng lặp vẫn được duy trì.

4.2. Mối quan hệ giữa lý thuyết và thực hành thiết kế CSDL

Lý thuyết chuẩn hóa cung cấp khung làm việc khoa học cho thiết kế cơ sở dữ liệu. Thực hành giúp hiểu rõ ưu nhược điểm của từng dạng chuẩn trong hoàn cảnh cụ thể. Kết hợp lý thuyết và thực tiễn tạo ra giải pháp tối ưu cho bài toán thiết kế. Bài tập thực tế về phụ thuộc hàm rèn luyện tư duy logic hiệu quả. Xác định khóa, tính bao đóng, kiểm tra dạng chuẩn là kỹ năng cốt lõi cần thành thạo.

Trích đoạn nội dung tài liệu

121 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU CHƯƠNG 3 LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU Mục tiêu: Chương này sẽ trình bày những khái niệm cơ bản nhất về lý thuyết cơ sở dữ liệu quan hệ do E.F Codd đề xuất, đó là các khái niệm về quan hệ, về khóa của lược đồ quan hệ. Những khái niệm này có vai trò quan trọng trong việc thiết kế và cài đặt các hệ cơ sở dữ liệu quan hệ và các hệ quản trị cơ sở dữ liệu. Nội dung của chương bao gồm các phần: Phụ thuộc hàm Bao đóng Phủ tối thiểu Khóa của lược đồ quan hệ Phép tách – kết nối Các dạng chuẩn của lược đồ quan hệ Các phương pháp chuẩn hóa lược đồ quan hệ 3. Phụ thuộc hàm 3.1 Định nghĩa phụ thuộc hàm Cho một quan hệ R xác định trên tập thuộc tính U, kí hiệu là R(U).

X, Y là các tập con của U, ta nói rằng X xác định Y hay Y phụ thuộc hàm vào X, kí hiệu X  Y nếu trên quan hệ R ta có mọi bộ giá trị t1, t2 bất kỳ mà giá trị của tập thuộc tính X trên bộ t1 (kí hiệu t1[X]) bằng giá trị của tập thuộc tính X trên bộ t2 (kí hiệu là t2[X]) thì t1[Y]) = t2[Y]). Phụ thuộc hàm ký hiệu là FD. Cần chú ý rằng chỉ xét các phụ thuộc hàm thỏa mãn cho mọi quan hệ trên lược đồ tương ứng của nó. Không thể xem xét một phụ thuộc hàm thỏa mãn một quan hệ r đặc biệt ( ví dụ quan hệ rỗng) của lược đồ R rồi sau đó qui nạp rằng phụ thuộc hàm đó là thỏa trên R.

KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 122 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU S (S# STATUS CITY) P (P# PNAME COLOR WEIGHT CITY) SP (S# P# QTY) Trong quan hệ S của hàng cung ứng, mỗi một trong số các thuộc tính SNAME, STATUS, CITY đều phụ thuộc hàm vào thuộc tính S#. Mỗi giá trị S# tồn tại vừa đúng một giá trị tương ứng đối với từng thuộc tính SNAME, STATUS, CITY. Khi đó có thể viết: S# → SNAME, S# → STATUS và S# → CITY.2 Phụ thuộc hàm đầy đủ và không đầy đủ  Phụ thuộc hàm (FD) đầy đủ: Một FD X Y là một phụ thuộc hàm đầy đủ nếu loại bỏ bất kỳ thuộc tính A nào ra khỏi X thì FD không còn đúng nữa  Phụ thuộc hàm không đ  ầy đủ (FD bộ phận): Một FD X Y là phụ thuộc hàm bộ phận nếu có thể bỏ đi 1 thuộc tính A  X ra khỏi X mà FD vẫn còn đúng.3 Hệ tiên đề Amstrong Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ R(U) và X→Y là một phụ thuộc hàm, X,Y⊆ U. Nói rằng X→Y được suy diễn logic từ F nếu mối quán hệ r trên R(U) đều thỏa các phụ thuộc hàm của F thì cũng thỏa X→Y.

Chẳng hạn F= {A→B,B→C} thì A→C suy ra từ F. Gọi F+ là bao đóng (closure) 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+ thì F là họ đầy đủ( full family) của các phụ thuộc hàm. Để có thể xác định khóa 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 đề. Tập các quy tắc của hệ tiên đề được Armstrong (1974) đưa ra, thường được gọi là hệ tiên đề Armstrong. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 123 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Gọi R(U) là lược đồ quan hệ với U= {A1, …., An} là tập các thuộc tính. Hệ tiên đề Armstrong bao gồm :  A1(phản xạ): nếu Y⊆X thì X→Y  A2(tăng trưởng):nếu Z⊆U và X→Y thì XZ→YZ trong đó ký hiệu XZ là tập hợp của 2 tập X và Z thay cho ký hiệu X∪Z.

 A3(bắc cầu): nếu X→Y và Y→Z thì X→Z Ví dụ : AB→C, C→A Cần chứng minh rằng BC→ABC Thật vậy từ : 1. BC→ABC ( bắc cầu từ (2) và (4)) Định lý : Hệ tiên đề Armstrong là đúng. Có nghĩa là F là tập các phụ thuộc hàm đúng trên quan hệ r. nếu X→Y là một phụ thuộc hàm được suy diễn từ F nhờ hệ tiên đề Armstrong thì X→Y là đúng trên quan hệ r.

Chứng minh : Lần lượt kiểm tra tính đúng đắn của ba tiên đề A1, A2, A3 A1 : Tiên đề A1 rõ ràng là đúng vì không thể có hai bộ bằng nhau trên X mà lại không bằng nhau trên tập con của nó. A2 : Giả sử rằng quan hệ r thỏa mãn X→Y. Tồn tại hai bột, u ∈r sao cho t[XZ] = u[ZX] mà t[YZ] ≠ u[YZ]. Nhưng vì t[X] = u[X] nên t[Y] ≠ u[Y] là trái với giả thiết X→Y.

KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 124 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU A3 : Cho X→Y và Y→Z đúng trên quan hệ r. Giả sử tồn tại hai bộ t, u∈r sao cho t[Y] = u[Y]. Nhưng lại có t[Y] = u[Y] và t[Z] ≠ u[Z] là trái với giả thiết Y→Z. Suy ra X→Z đúng trên quan hệ r.

Từ hệ tiên đề Armstrong suy ra một số luật sau đây : Định lý : a. Luật hợp: nếu X→Y và X→Z thì X→YZ b. Luật tựa bắc cầu: nếu X→Y và WY→X thì XW→Z c. Luật tách: nếu X→Y và Z⊆Y thì X→Z Chứng minh: a.

Từ X→Y dùng luật tăng trưởng thêm X có X→XY, dùng luật bắc cầu ta có điều phải chứng minh. Từ X→Y, dùng luật tăng trưởng, thêm W có WX→WY. Dùng luật bắc cầu cho WX→WY và Wy→Z suy ra WX→Z. Vì Z⊆Y nên Y→Z theo luật phản xạ.

Dùng luật bắc cầu cho X→Y và Y→Z có X→Z.1 Bao đóng của tập các phụ thuộc hàm Định nghĩa: Cho quan hệ R xác định trên tập thuộc tính U, F là tập các phụ thuộc hàm. Tập hợp tất cả các phụ thuộc hàm được suy diễn logic từ tập F được gọi là bao đóng của F và kí hiệu là F+ Ví dụ: Cho quan hệ R, U ={ A, B, C, D, E, I } F= {AI, ACD, BC, DE} Ta có: 1. AC D (gt) KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 125 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU 4. AB  D (bắc cầu (2) và (3)) CM tương tự có: AC E, AB E Vậy: F+ ={AI, ACD, BC, DE, ABD, ACE, ABE} 3.

Bao đóng của tập các thuộc tính Định nghĩa: Cho quan hệ R xác định trên tập các thuộc tính U, gọi F là tập các phụ thuộc hàm trên tập U, X  U, X+ là bao đóng của X trên tập F được định nghĩa như sau: X+ = { X  A / X  A  F+ } 3. Thuật toán tìm bao đóng  Input: U, F; X, Y, Z  U  Output: X+  Phương pháp: Tính liên tiếp tập các thuộc tính X0, X1, … theo quy tắc:  B1: X0 = X  Bi: Xi+1 = Xi  A Nếu tồn tại phụ thuộc hàm Y  Z thuộc F+ mà A  Z, Y  Xi Do X  U mà U hữu hạn nên i hữu hạn, khi đó X+ = Xi+1 Ví dụ: Cho quan hệ R xác định trên U, với U = { A, B, C, D, E, I}; F= {AI, ACD, BC, DE} Tìm (AC)+ Giải: 1. X2= ACDIE (vì D  E) Vậy: (AC)+ = ACDEI KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 126 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU 3. Phủ tối thiểu Phủ của tập các phụ thuộc hàm : Gọi F và G là các tập của các phụ thuộc hàm.

Nói rằng F, G là tương đương nếu F+ = G+. Nếu F, G là tương đương đôi khi còn nói F phủ G (và G phủ F). Dễ dàng kiểm tra liệu F và G có tương đương với nhau hay không. Phương pháp kiểm tra: Lấy mỗi phụ thuộc hàm Y→Z thuộc F, kiểm tra xem liệu Y→Z có thuộc G+ không ? Dùng thuật toán 3.1 để tính Y+ và kiểm tra liệu Z⊆ Y+ hay không ? Nếu tồn tại một phụ thuộc hàm Y→Z thuộc F mà không phụ thuộc G+ thì chắc chắn F+ ≠ G+.

Nếu mỗi phụ thuộc hàm thuộc F cũng thuộc G+ thì mỗi phụ thuộc hàm V→W thuộc F+ cũng thuộc G+. Để kiểm tra mỗi phụ thuộc G là thuộc F+ quá trình làm hoàn toàn tương tự. Do đó F và G là tương đương khi và chỉ khi mỗi phụ thuộc hàm thuộc F là thuộc G+ và mỗi phụ thuộc hàm thuộc G thuộc F+. Định lý : Mỗi tập các phụ thuộc hàm F đều được phủ bằng tập các phụ thuộc hàm G mà vế phải các phụ thuộc hàm đó bao gồm không quá một thuộc tính.

Chứng minh : Gọi G là tập các phụ thuộc hàm X→A sao cho với X→Y thuộc F thì A∈Y. TừX→Y suy ra X→A. Do vậy G⊆ F+ Ngược lại, có F⊆ G+ vì nếu Y= A1…An thì X→Y được suy ra từ : X→A1, …., X→An nhờ luật hợp. Để có thể phục vụ quá trình thiết kế lược đồ cơ sở dữ liêu, sau đây sẽ đưa ra một số khái niệm: Gọi tập các phụ thuộc hàm F là tối thiểu nếu: a.

Mỗi vế phải của một phụ thuộc hàm thuộc F chỉ có một thuộc tính. Không tồn tại một phụ thuộc hàm X→A thuộc F mà F+ = (F- {X→A}) +. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 127 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU c. Không tồn tại một phụ thuộc hàm X→A thuộc F và một tập hợp con Z của X mà F+= (F- {X→A}∪ {Z→A}) + Thực vậy, điều kiện b đảm bảo cho tập F không có một phụ thuộc hàm nào mà dư thừa, điều kiện C đảm bảo không có thuộc tính nao tham gia phía trái của phụ thuộc hàm là dư thừa.

Vế phải của phụ thuộc hàm ở điều kiện a chỉ có một thuộc tính đảm bảo chắc chắn không có một thuộc tính nào trên vế phải là dư thừa. Định lý Mỗi tập phụ thuộc hàm F đều tương đương với một tập F’ tối thiểu. Chứng minh: Giả sử rằng không vế phải nào của các phụ thuộc hàm của F có nhiều hơn một thuộc tính. Để kiểm tra điều kiện b, xét (X→Y) ∈F.

Nếu (F- {X→Y}) + =F+ thì loại bỏ X→Y khỏi F. Chú ý rằng các phụ thuộc hàm được sắp theo một thứ tự khác nhau thì sẽ cho ra kết quả khác nhau. Ví dụ: Cho tập F gồm: A→B, A→C, B→C, B→A, C→A Có thể loại bỏ F : B→A và A→C hoặc loại bỏ B→C nhưng không thể đồng thời loại bỏ cả ba phụ thuộc hàm.