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.

Nội dung chính

Tổng quan về giáo trình

Tài liệu học tập Cơ sở dữ liệu do Khoa Công nghệ Thông tin – Trường Đại học Kinh tế Kỹ thuật Công nghiệp (UNETI) biên soạn là học liệu chuyên ngành dành cho chương trình đào tạo đại học khối ngành Công nghệ Thông tin. Trong khung chương trình, học phần đóng vai trò cầu nối giữa các môn học nền tảng toán học (như Toán rời rạc, Logic toán) và các môn học ứng dụng chuyên sâu về phát triển phần mềm, quản trị hệ thống thông tin.

Mục tiêu học tập của tài liệu tập trung vào việc cung cấp hệ thống lý thuyết về mô hình cơ sở dữ liệu quan hệ do E.F. Codd đề xuất, trọng tâm là lý thuyết thiết kế lược đồ quan hệ và các kỹ thuật xử lý, tối ưu hóa câu hỏi truy vấn. Kết quả học tập kỳ vọng bao gồm:

• Khả năng phân tích và biểu diễn các ràng buộc toàn vẹn dữ liệu thông qua phụ thuộc hàm (FD).
• Vận dụng hệ tiên đề Armstrong để chứng minh, tính bao đóng và xác định phủ tối thiểu.
• Thực hiện thuật toán tìm tất cả các khóa và áp dụng các phép chuẩn hóa dữ liệu từ dạng chuẩn 1 (1NF) đến Boyce-Codd (BCNF).
• Chuyển đổi và tối ưu hóa biểu thức đại số quan hệ nhằm giảm thiểu chi phí bộ nhớ và thời gian thực thi trong hệ quản trị cơ sở dữ liệu (DBMS).

Tài liệu được cấu trúc theo phương pháp hình thức toán học chặt chẽ, kết hợp tuần tự từ định nghĩa, định lý, chứng minh đến thuật toán giải thuật và ví dụ minh họa từng bước. Điểm đặc trưng trong cách tiếp cận của tài liệu là sự chuẩn hóa các quy trình kỹ thuật thành các bước giải thuật rõ ràng (thuật toán tìm khóa, thuật toán kiểm tra mất mát thông tin qua ma trận bảng, thuật toán tổng hợp 3NF), giúp người học có thể triển khai thực hành và tự động hóa quy trình phân tích thiết kế dữ liệu.

---

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Trích đoạn tài liệu tập trung vào hai khối kiến thức trọng tâm thuộc Chương 3 và Chương 4:

1. Chương 3: Lý thuyết thiết kế cơ sở dữ liệu (Trang 121 – 156)

   • Phụ thuộc hàm (Functional Dependency - FD): Định nghĩa toán học về phụ thuộc hàm trên lược đồ quan hệ $R(U)$, trong đó $X \to Y$ xác định rằng với mọi cặp bộ $t_1, t_2 \in R$, nếu $t_1[X] = t_2[X]$ thì $t_1[Y] = t_2[Y]$. Phân biệt phụ thuộc hàm đầy đủ và phụ thuộc hàm bộ phận thông qua ví dụ quan hệ cung ứng $S(S#, STATUS, CITY)$, $P(P#, PNAME, COLOR, WEIGHT, CITY)$, $SP(S#, P#, QTY)$.
   • Hệ tiên đề Armstrong (Armstrong, 1974): Trình bày 3 tiên đề chính gồm Tiên đề Phản xạ ($Y \subseteq X \implies X \to Y$), Tiên đề Tăng trưởng ($Z \subseteq U, X \to Y \implies XZ \to YZ$), và Tiên đề Bắc cầu ($X \to Y \land Y \to Z \implies X \to Z$). Các hệ quả được chứng minh hình thức gồm Luật hợp ($X \to Y, X \to Z \implies X \to YZ$), Luật tựa bắc cầu ($X \to Y, WY \to Z \implies WX \to Z$), và Luật tách ($X \to Y, Z \subseteq Y \implies X \to Z$).
   • Bao đóng và Phủ tối thiểu: Định nghĩa bao đóng tập phụ thuộc hàm $F^+$ và bao đóng tập thuộc tính $X^+$. Cung cấp thuật toán lặp xác định $X^+$. Trình bày thuật toán tìm phủ tối thiểu qua 3 bước: (1) Đưa vế phải về dạng nguyên tố một thuộc tính, (2) Loại bỏ phụ thuộc hàm dư thừa, (3) Loại bỏ thuộc tính dư thừa ở vế trái.
   • Xác định khóa của lược đồ quan hệ: Phân rã tập thuộc tính thành tập nguồn ($TN$ - thuộc tính chỉ xuất hiện ở vế trái hoặc không xuất hiện trong $F$) và tập trung gian ($TG$ - thuộc tính xuất hiện ở cả hai vế). Quy trình sinh siêu khóa và tối thiểu hóa để tìm toàn bộ khóa của lược đồ $R(U)$.
   • Phép tách - kết nối không mất mát thông tin (Lossless Join Decomposition): Khái niệm phép tách $\rho = (R_1, \dots, R_k)$ và điều kiện kết nối tự nhiên $r = \Pi_{R_1}(r) \bowtie \dots \bowtie \Pi_{R_k}(r)$. Cung cấp thuật toán kiểm tra mất mát thông tin thông qua bảng ma trận kích thước $k \times n$ với các ký hiệu $a_j$ và $b_{ij}$. Định lý kiểm tra phép tách 2 lược đồ $(R_1, R_2)$ dựa trên điều kiện $R_1 \cap R_2 \to R_1 - R_2$ hoặc $R_1 \cap R_2 \to R_2 - R_1$.
   • Các dạng chuẩn (Normal Forms) và phương pháp chuẩn hóa: Định nghĩa 1NF (miền giá trị nguyên tố), 2NF (không chứa phụ thuộc bộ phận vào khóa chính), 3NF (không chứa phụ thuộc bắc cầu vào khóa chính), và BCNF (mọi vế trái của phụ thuộc hàm không tầm thường đều là siêu khóa). Trình bày hai phương pháp chuẩn hóa: Chuẩn hóa bằng phép tách không mất mát thông tin và chuẩn hóa bằng phép tổng hợp (Synthesis algorithm).

2. Chương 4: Tối ưu hóa câu hỏi truy vấn (Trang 156 – 170)

   • Đại số quan hệ và cây truy vấn: Ngôn ngữ con dữ liệu, biểu thức quan hệ tương đương $E_1 \cong E_2$, và mô hình biểu diễn truy vấn bằng cây đại số quan hệ.
   • Nguyên tắc tối ưu hóa truy vấn: Ưu tiên chuyển các phép chọn ($\sigma$) và phép chiếu ($\pi$) xuống vị trí sớm nhất trong cây đại số để thu hẹp kích thước quan hệ trung gian trước khi thực hiện phép tích Đề-các ($\times$) hoặc phép kết nối tự nhiên ($\bowtie$).
   • Ví dụ cơ sở dữ liệu quản lý mạng cáp: Mô hình gồm $TUYEN(TC#, TC, DAI)$, $CAP(MC#, MC, GIA, NSX)$, $L_DAT(TC#, MC#, SL, NG)$ minh họa quá trình giảm chi phí tính toán khi thay thế phép nối tích Đề-các toàn phần bằng việc chọn lọc điều kiện ($NSX = \text{'Việt Nam'}$, $DAI > 50\text{ km}$) tại các nút lá.
   • Tối ưu hóa bằng khung nhìn cụ thể hóa (Materialized Views): Kỹ thuật lưu trữ kết quả tính toán trung gian, cơ chế cập nhật tăng cường khi có phép chèn ($I_R$) hoặc xóa ($D_R$), và phương pháp xử lý các phép toán khối (COUNT, SUM, AVG, MIN, MAX), phép giao, hợp, hiệu.

Kiến thức nền tảng được xây dựng

• Nền tảng toán học quan hệ: Dựa trên mô hình quan hệ hình thức của E.F. Codd và lý thuyết suy diễn logic của W.W. Armstrong (1974), thiết lập cơ sở chứng minh tính đúng đắn và tính đầy đủ của các luật biến đổi dữ liệu.
• Nguyên lý bảo toàn thông tin và bảo toàn phụ thuộc hàm: Cung cấp tiêu chuẩn toán học để đánh giá tính toàn vẹn của cấu trúc dữ liệu sau khi phân rã, tránh hiện tượng sinh các bộ dữ liệu giả mạo (spurious tuples).
• Lý thuyết tối ưu hóa chi phí: Xây dựng mô hình ước lượng chi phí thực thi dựa trên lực lượng (cardinality) và bậc (degree) của các quan hệ trung gian trong cây đại số.

Kỹ năng phát triển

• Kỹ năng phân tích logic: Khả năng suy diễn các phụ thuộc hàm dẫn xuất, tính toán tập bao đóng thuộc tính và chứng minh các định lý trong hệ tiên đề Armstrong.
• Kỹ năng thiết kế và chuẩn hóa cấu trúc: Khả năng phát hiện các dị thường thêm, xóa, sửa (insert, delete, update anomalies) trong lược đồ quan hệ chưa chuẩn; thực hiện quy trình chuẩn hóa lược đồ về dạng 3NF và BCNF bằng phương pháp giải thuật.
• Kỹ năng tối ưu hóa truy vấn: Kỹ năng phân tích cú pháp biểu thức truy vấn, xây dựng cây đại số quan hệ ban đầu, áp dụng các luật biến đổi tương đương để tái cấu trúc cây truy vấn nhằm đạt hiệu năng tối ưu.

---

Phương pháp giảng dạy và học tập

Giáo trình triển khai phương pháp tiếp cận diễn dịch chuẩn mực của các tài liệu khoa học máy tính:

1. Quy trình giải thuật hóa (Algorithmic approach): Các khái niệm lý thuyết trừu tượng đều được gắn liền với các thuật toán có đầu vào (Input), đầu ra (Output) và các bước thực thi (Method) rõ ràng. Điển hình như thuật toán tìm bao đóng $X^+$, thuật toán kiểm tra phép tách bằng bảng ma trận $a_{j}/b_{ij}$, thuật toán phân rã BCNF lặp, và thuật toán tổng hợp 3NF từ phủ không dư thừa.
2. Hệ thống bài tập đánh giá đa dạng:
   • 25 câu hỏi trắc nghiệm khách quan (Trang 147 – 154): Bao quát toàn bộ khái niệm từ định nghĩa phụ thuộc hàm, các tiên đề Armstrong (tăng trưởng, phản xạ, bắc cầu), luật suy dẫn (luật hợp, tựa bắc cầu, luật tách), định nghĩa các tập thuộc tính nguồn ($TN$), trung gian ($TG$), đích ($TĐ$), và các tiêu chuẩn nhận diện dạng chuẩn 1NF, 2NF, 3NF, BCNF.
   • 14 bài tập thực hành tự luận (Trang 154 – 156): Đòi hỏi người học trực tiếp tính toán chứng minh phụ thuộc hàm thuộc $F^+$, tìm toàn bộ tập khóa của lược đồ quan hệ nhiều thuộc tính, tìm phủ tối thiểu, chuẩn hóa lược đồ về 3NF, và kiểm tra tính không mất mát thông tin của các phép tách lược đồ.
3. Mô hình nghiên cứu tình huống cụ thể (Case studies): Các ví dụ xuyên suốt được xây dựng từ các bài toán thực tế như bài toán phân công giảng dạy $R(C, T, H, R, S, G)$ với các ràng buộc về phòng học, môn học, giảng viên, sinh viên; bài toán cung ứng vật tư $S - P - SP$; bài toán quản lý mạng cáp viễn thông $TUYEN - CAP - L_DAT$.

---

Điểm nổi bật và cập nhật

• Tính chuẩn xác và hình thức hóa cao: Giáo trình thể hiện đầy đủ các bước chứng minh toán học của các định lý nền tảng (chứng minh tính đúng đắn của hệ tiên đề Armstrong A1, A2, A3; chứng minh tính tương đương của phủ tối thiểu; chứng minh tính bảo toàn thông tin của phép tách).
• Tính hệ thống trong xử lý phụ thuộc hàm: Cung cấp phương pháp phân loại thuộc tính ($TN, TG, TĐ$) giúp người học có công cụ mang tính cơ học, chính xác để xác định không gian tìm kiếm khóa mà không bị bỏ sót trường hợp trong các lược đồ phức tạp.
• Tích hợp giữa đại số quan hệ lý thuyết và kỹ thuật hệ quản trị CSDL: Trong Chương 4, giáo trình không dừng lại ở các phép toán trừu tượng mà đối chiếu trực tiếp giữa biểu thức đại số quan hệ, cây đại số quan hệ với câu lệnh truy vấn SQL thực tế (SELECT, WHERE, GROUP BY, CREATE VIEW).
• Phân tích chuyên sâu về khung nhìn cụ thể hóa (Materialized Views): Giáo trình trình bày cơ chế toán học xử lý cập nhật dữ liệu trên View khi có sự thay đổi tại bảng gốc ($R_{new} = R_{old} \cup I_R$ hoặc $R_{new} = R_{old} \setminus D_R$), đồng thời phân tích sự đánh đổi chi phí giữa việc quét trực tiếp trên View cụ thể hóa và việc sử dụng chỉ mục (Index) trên bảng quan hệ thông thường.

---

Đối tượng sử dụng giáo trình

Tài liệu được thiết kế cho các nhóm đối tượng cụ thể trong đào tạo và nghiên cứu:

1. Sinh viên đại học:
   • Dành cho sinh viên chuyên ngành Công nghệ Thông tin, Hệ thống Thông tin, Kỹ thuật Phần mềm, Khoa học Dữ liệu từ năm thứ hai trở đi.
   • Yêu cầu kiến thức tiên quyết: Người học cần nắm vững kiến thức về Toán rời rạc (lý thuyết tập hợp, quan hệ, logic mệnh đề, lý thuyết đồ thị cơ bản) và kiến thức nhập môn lập trình.
2. Giảng viên và cán bộ học thuật:
   • Làm tài liệu giảng dạy chính khóa cho học phần Cơ sở dữ liệu hoặc Lý thuyết cơ sở dữ liệu quan hệ.
   • Sử dụng khung bài tập trắc nghiệm và thực hành phong phú để xây dựng đề thi, bài kiểm tra đánh giá định kỳ và chuẩn đầu ra học phần.
3. Kỹ sư phần mềm và Quản trị viên cơ sở dữ liệu (DBA):
   • Làm tài liệu tham khảo để nắm vững bản chất toán học của việc thiết kế bảng dữ liệu, tránh lỗi dư thừa và bất nhất dữ liệu trong quá trình thiết kế hệ thống.
   • Ứng dụng các quy tắc biến đổi cây truy vấn và kỹ thuật Materialized Views để tối ưu hóa hiệu năng các câu truy vấn phức tạp trên các hệ quản trị CSDL như Oracle, PostgreSQL, SQL Server.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với đối tượng người học nào?

Giáo trình được biên soạn chuyên biệt cho sinh viên đại học khối ngành Công nghệ Thông tin và Kỹ thuật phần mềm đang theo học học phần Cơ sở dữ liệu hoặc Thiết kế CSDL quan hệ.

2. Cần chuẩn bị những kiến thức nền tảng nào trước khi tiếp cận tài liệu?

Người học cần có nền tảng cơ bản về Toán rời rạc (tập hợp, ánh xạ, logic hình thức), cấu trúc dữ liệu cơ bản và khái niệm sơ khởi về mô hình bảng trong cơ sở dữ liệu.

3. Điểm khác biệt trong cách trình bày lý thuyết thiết kế của giáo trình là gì?

Tài liệu quy chuẩn hóa các khái niệm lý thuyết thành các thuật toán từng bước cụ thể (như thuật toán tìm phủ tối thiểu 3 bước, bảng ma trận $a/b$ kiểm tra không mất mát thông tin, thuật toán tách/tổng hợp dạng chuẩn), giúp người học có phương pháp giải bài tập rõ ràng và chính xác.

4. Làm thế nào để tự học và làm chủ các thuật toán chuẩn hóa trong giáo trình?

Người học nên tiếp cận tuần tự theo đúng tiến trình: nắm vững định nghĩa phụ thuộc hàm $\to$ thực hành tính bao đóng $X^+ \to$ tìm phủ tối thiểu $\to$ tìm khóa qua tập nguồn/trung gian $\to$ phân tích dạng chuẩn 1NF, 2NF, 3NF, BCNF $\to$ thực hành giải toàn bộ 14 bài tập tự luận ở cuối chương 3.

5. Giáo trình có hướng dẫn tối ưu hóa câu lệnh SQL thực tế không?

Có. Chương 4 của giáo trình minh họa sự tương đương giữa cây đại số quan hệ và các mệnh đề SQL (SELECT, FROM, WHERE, GROUP BY), đồng thời hướng dẫn phương pháp sử dụng khung nhìn cụ thể hóa (CREATE VIEW) kết hợp chỉ mục (Index) để tối ưu hóa hiệu năng truy xuất.

---

Kết luận

Tài liệu học tập Cơ sở dữ liệu của Khoa Công nghệ Thông tin – Trường Đại học Kinh tế Kỹ thuật Công nghiệp (UNETI) cung cấp hệ thống kiến thức toàn diện, chuẩn xác về lý thuyết thiết kế cơ sở dữ liệu quan hệ và tối ưu hóa truy vấn. Việc kết hợp chặt chẽ giữa hệ thống tiên đề hình thức, các định lý toán học và các thuật toán thiết kế cụ thể tạo nên giá trị học thuật cốt lõi cho học liệu.

Lộ trình học tập đề xuất cho người học là nghiên cứu tuần tự từ lý thuyết phụ thuộc hàm, bao đóng, khóa, chuẩn hóa lược đồ (Chương 3) trước khi chuyển sang các kỹ thuật tối ưu hóa đại số quan hệ và khung nhìn cụ thể hóa (Chương 4). Để củng cố kỹ năng thực hành, người học nên kết hợp lý thuyết trong tài liệu với việc cài đặt thử nghiệm trên các hệ quản trị cơ sở dữ liệu quan hệ tiêu chuẩn.

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.