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

Tài liệu "Chương 4: Đại số quan hệ" thuộc chuỗi bài giảng môn Cơ sở dữ liệu, do Bộ môn Hệ thống Thông tin – Khoa Công nghệ Thông tin – Trường Đại học Khoa học Tự nhiên biên soạn. Trong chương trình đào tạo bậc đại học các ngành Công nghệ Thông tin, Hệ thống Thông tin và Khoa học Máy tính, môn Cơ sở dữ liệu đóng vai trò là học phần cơ sở ngành bắt buộc, cung cấp nền tảng lý thuyết và kỹ thuật quản trị dữ liệu có cấu trúc.

Mục tiêu học tập chính của chương là trang bị cho người học hiểu biết bản chất toán học của mô hình dữ liệu quan hệ; phân biệt rõ hai nhóm xử lý dữ liệu: xử lý thay đổi dữ liệu (cập nhật: thêm, xóa, sửa) và xử lý không làm thay đổi dữ liệu (rút trích: truy vấn). Qua đó, sinh viên nắm vững nguyên lý vận hành của Ngôn ngữ truy vấn (Query Language – QL), phân biệt ngôn ngữ thủ tục (Đại số quan hệ – Relational Algebra) với ngôn ngữ phi thủ tục (Phép tính quan hệ – Relational Calculus) và ngôn ngữ truy vấn thương mại (SQL).

Cấu trúc bài giảng được triển khai theo hướng diễn dịch logic: từ việc đặt vấn đề qua các thao tác thực tế trên bảng dữ liệu, chuẩn hóa thành khái niệm đại số, định nghĩa hình thức các phép toán tập hợp và phép toán quan hệ chuyên biệt, đến cách thức phối hợp các toán tử để giải quyết các bài toán rút trích dữ liệu phức tạp. Điểm đặc thù của tài liệu là tính trực quan hóa cao, mọi khái niệm toán học trừu tượng đều được minh họa bằng lược đồ và bảng dữ liệu thể hiện cụ thể (như quan hệ KHOA, SINHVIEN, GIAOVIEN, BOMON, DETAI), giúp người học theo dõi rõ ràng sự biến đổi cấu trúc và dữ liệu sau mỗi phép toán.

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

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

Nội dung chương 4 được chia thành 10 chủ đề chính, phản ánh trình tự tiếp cận từ nền tảng toán học đến ứng dụng biểu thức truy vấn:

  1. Tổng quan về xử lý dữ liệu và ngôn ngữ truy vấn: Phân định hai nhóm thao tác: thao tác cập nhật (làm thay đổi dữ liệu) và thao tác truy vấn (rút trích thông tin). Giới thiệu vị trí của Đại số quan hệ (tiếp cận theo quy trình các bước thực hiện) so với Phép tính quan hệ (tiếp cận dựa trên logic khai báo) và SQL.
  2. Khái niệm Đại số và Đại số quan hệ: Thiết lập mối tương quan giữa đại số số học (toán tử $+$, $-$, $*$, $/$; toán hạng là biến số, hằng số) và đại số quan hệ (toán tử là các phép toán quan hệ; toán hạng là các quan hệ, thể hiện quan hệ $t, v$).
  3. Các phép toán tập hợp và Tính khả hợp (Union Compatibility): Trình bày điều kiện để hai quan hệ khả hợp: cùng bậc $n$ ($R(A_1, \dots, A_n)$ và $S(B_1, \dots, B_n)$) và tương thích miền giá trị $\text{DOM}(A_i) = \text{DOM}(B_i)$ với $1 \le i \le n$. Định nghĩa ba phép toán: Phép hội ($r \cup s = {t \mid t \in r \lor t \in s}$), Phép giao ($r \cap s = {t \mid t \in r \land t \in s}$), Phép trừ ($r - s = {t \mid t \in r \land t \notin s}$).
  4. Phép chọn ($\sigma$ - Selection): Phép toán đơn nguyên trích xuất các bộ thỏa mãn biểu thức điều kiện $P$ ($\sigma_P(r)$). Điều kiện $P$ được xây dựng từ các phép so sánh ($=, \ne, <, \le, >, \ge$) và liên kết logic ($\land, \lor, \neg$).
  5. Phép chiếu ($\Pi$ - Projection) và Phép chiếu tổng quát: Trích xuất tập thuộc tính xác định $\Pi_{A_1, \dots, A_k}(r)$, loại bỏ các bộ trùng lặp. Mở rộng phép chiếu tổng quát cho phép đưa vào các biểu thức số học (ví dụ: tính lương mới $\text{LUONG} \times 1.1$).
  6. Phép tích Cartesian ($\times$ - Cartesian Product): Kết hợp từng bộ của quan hệ $r$ với tất cả các bộ của quan hệ $s$, tạo ra quan hệ mới có bậc bằng tổng bậc của $r$ và $s$.
  7. Phép kết (Join): Các dạng phép kết dữ liệu gồm Kết tự nhiên (Natural join), Kết có điều kiện tổng quát (Theta join) và Kết bằng (Equi join).
  8. Phép chia ($\div$): Phép toán phục vụ các truy vấn mang ý nghĩa "với mọi" / "tất cả".
  9. Các phép toán bổ sung: Các phép toán mở rộng nhằm tối ưu biểu thức truy vấn.
  10. Các thao tác cập nhật trên quan hệ: Nguyên lý hình thức cho các thao tác chèn (insert), xóa (delete) và hiệu chỉnh (modify/update).

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

Chương học xây dựng các nguyên lý cốt lõi của lý thuyết cơ sở dữ liệu quan hệ:

  • Tính đóng (Closure Property): Đầu vào của một phép toán là một hoặc nhiều quan hệ, kết quả trả về luôn là một quan hệ mới. Đặc tính này cho phép lồng ghép liên tiếp các phép toán để tạo thành một chuỗi biểu thức đại số quan hệ.
  • Tính khả hợp: Ràng buộc chặt chẽ về mặt toán học trước khi thực hiện các thao tác tập hợp ($\cup, \cap, -$), đảm bảo tính nhất quán về cấu trúc và ngữ nghĩa dữ liệu giữa hai quan hệ.
  • Tính chất đại số: Xác lập các quy tắc biến đổi tương đương như tính giao hoán ($r \cup s = s \cup r$, $r \cap s = s \cap r$, $\sigma_{p_1}(\sigma_{p_2}(r)) = \sigma_{p_2}(\sigma_{p_1}(r))$) và tính kết hợp ($r \cup (s \cup t) = (r \cup s) \cup t$), làm nền tảng cho việc tối ưu hóa câu truy vấn.

Kỹ năng phát triển

  • Kỹ năng phân tích câu truy vấn: Nhận diện bảng dữ liệu nguồn, xác định điều kiện chọn lọc bộ (mệnh đề $\sigma$) và các trường dữ liệu cần trích xuất (danh sách thuộc tính $\Pi$).
  • Kỹ năng thiết lập biểu thức hình thức: Chuyển đổi yêu cầu ngôn ngữ tự nhiên thành biểu thức đại số quan hệ nhiều bước, sử dụng đúng thứ tự ưu tiên của các toán tử.
  • Kỹ năng xử lý dữ liệu quan hệ đa bảng: Sử dụng phối hợp tích Cartesian và phép chọn hoặc các biến thể của phép kết để liên kết các bảng thông qua quan hệ khóa ngoài (ví dụ: liên kết BOMON.TRUONGBM với GIAOVIEN.MAGV).

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

Phương pháp tiếp cận sư phạm

Tài liệu áp dụng phương pháp tiếp cận từ trực quan đến trừu tượng (inductive-deductive learning):

  1. Khởi động bài toán thực tế: Trình bày bảng dữ liệu KHOA với các thao tác cụ thể như chuyển đổi phòng làm việc của khoa CNTT sang phòng B12, hoặc trích xuất tên các khoa thành lập từ năm 1980.
  2. Trừu tượng hóa toán học: Quy đổi các bài toán trên về cấu trúc tập hợp, toán tử và toán hạng.
  3. Hình thức hóa định nghĩa: Đưa ra ký hiệu toán học chính xác ($\sigma, \Pi, \times, \cup, \cap, -$) cùng các điều kiện biên (bậc của quan hệ, miền giá trị).
  4. Kiểm chứng qua ví dụ mẫu: Cung cấp các bước thực thi chi tiết, minh họa rõ bảng trung gian và bảng kết quả cuối cùng.

Hệ thống bài tập và nghiên cứu tình huống

Tài liệu sử dụng một hệ thống cơ sở dữ liệu quản lý trường học và đề tài nghiên cứu khoa học làm trường hợp nghiên cứu xuyên suốt:

  • KHOA(MAKHOA, TENKHOA, NAMTL, PHONG, DIENTHOAI, TRUONGKHOA, NGAYNHANCHUC)
  • GIAOVIEN(MAGV, HOTEN, NGSINH, MABM, PHAI, LUONG, DIACHI)
  • SINHVIEN(TENSV, NGSINH, PHAI, DIACHI)
  • BOMON(MABM, TENBM, PHONG, TRUONGBM, NGAYNHANCHUC)
  • DETAI(MADT, TENDT, MACD, GVCNNDT)
  • CONGVIEC(..., NGAYBD, ...)
  • CHUDE(MACD, TENCD)
  • TG_DETAI(MAGV, MADT, ...)

Hệ thống ví dụ được phân loại từ đơn giản đến phức tạp:

  • Ví dụ 1 (Phép chọn và chiếu đơn giản): Cho biết họ tên và mức lương của các giáo viên nữ: $$\Pi_{\text{HOTEN, LUONG}}(\sigma_{\text{PHAI='Nữ'}}(\text{GIAOVIEN}))$$
  • Ví dụ 2 (Kết hợp phép chiếu và phép hội): Cho biết mã số các giáo viên thuộc bộ môn HTTT hoặc có tham gia đề tài mã 001: $$\Pi_{\text{MAGV}}(\sigma_{\text{MABM='HTTT'}}(\text{GIAOVIEN})) \cup \Pi_{\text{MAGV}}(\sigma_{\text{MADT='001'}}(\text{TG_DETAI}))$$
  • Ví dụ 3 (Kết hợp phép chiếu và phép giao): Cho biết mã số các trưởng khoa có chủ nhiệm đề tài: $$\Pi_{\text{TRUONGKHOA}}(\text{KHOA}) \cap \Pi_{\text{GVCNĐT}}(\text{DETAI})$$
  • Ví dụ 4 (Phép chọn với khoảng thời gian): Cho biết tên các công việc bắt đầu trong khoảng từ 01/01/2007 đến 01/08/2007: $$\sigma_{\text{NGAYBĐ} \ge \text{'1/1/2007'} \land \text{NGAYBĐ} \le \text{'1/8/2007'}}(\text{CONGVIEC})$$
  • Ví dụ 5 (Phép chiếu tổng quát có tính toán): Cho biết họ tên giáo viên và lương sau khi tăng 10%: $$\Pi_{\text{HOTEN, LUONG} \times 1.1}(\text{GIAOVIEN})$$
  • Ví dụ 6 (Tích Cartesian phối hợp phép chọn): Tìm thông tin bộ môn cùng thông tin trưởng bộ môn: $$\sigma_{\text{TRUONGBM=MAGV}}(\text{BOMON} \times \text{GIAOVIEN})$$
                      QUY TRÌNH THỰC THI TRUY VẤN

Điểm nổi bật và cấu trúc trình bày

  • Tính chuẩn xác về mô hình toán học: Tài liệu phân định rõ sự khác nhau giữa biến quan hệ, thể hiện của quan hệ (instance), bộ dữ liệu (tuple) và thuộc tính (attribute). Việc đối chiếu song song giữa đại số số học và đại số quan hệ (bảng so sánh ở Slide 8) giúp người học nắm bắt nhanh khái niệm trừu tượng.
  • Làm rõ các tính chất đại số quan trọng: Tài liệu chỉ ra cụ thể:
    • Phép chọn có tính giao hoán: $\sigma_{p_1}(\sigma_{p_2}(r)) = \sigma_{p_2}(\sigma_{p_1}(r)) = \sigma_{p_1 \land p_2}(r)$.
    • Phép chiếu không có tính giao hoán: $\Pi_{X, Y}(r) \ne \Pi_X(\Pi_Y(r))$, và quy tắc rút gọn dãy phép chiếu: $\Pi_{A_1, \dots, A_n}(\Pi_{A_1, \dots, A_m}(r)) = \Pi_{A_1, \dots, A_n}(r)$ (với $n \le m$).
  • Mở rộng biểu thức số học: Đưa khái niệm phép chiếu tổng quát $\Pi_{F_1, \dots, F_n}(E)$ vào bài giảng, chứng minh tính linh hoạt của đại số quan hệ khi xử lý các phép toán tính toán giá trị dẫn xuất ($F_i$ là hàm số học dựa trên hằng số và thuộc tính).
  • Trực quan hóa cấu trúc dữ liệu: Các slide phân tích rõ số hàng (bộ) và số cột (thuộc tính) thay đổi như thế nào qua phép chọn (giảm số bộ, giữ nguyên số cột) và phép chiếu (giảm số cột, có thể giảm số bộ do loại trừ trùng lặp).

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

Đối tượng Mục đích và Phạm vi sử dụng
Sinh viên chuyên ngành CNTT, HTTT, KHMT Sử dụng làm tài liệu học tập chính thức cho học phần Cơ sở dữ liệu; nắm vững bản chất toán học của các phép toán trước khi học ngôn ngữ SQL.
Giảng viên và Trợ giảng Sử dụng làm đề cương bài giảng lý thuyết, khung bài tập trên lớp và định hướng thiết kế đề thi đánh giá năng lực suy luận đại số.
Lập trình viên / Kỹ sư dữ liệu Tài liệu tham khảo để hiểu sâu cơ chế biên dịch và tối ưu hóa câu truy vấn bên dưới các công cụ cơ sở dữ liệu quan hệ (RDBMS Query Optimizer).

Kiến thức tiên quyết

  • Toán rời rạc: Lý thuyết tập hợp cơ bản (hội, giao, hiệu, tích Descartes), logic vị từ và đại số Boolean.
  • Nhập môn lập trình: Tư duy xử lý dữ liệu có cấu trúc, biến, kiểu dữ liệu và toán tử điều kiện.

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

1. Tài liệu này phù hợp với học phần nào trong chương trình đào tạo?

Tài liệu được thiết kế chuyên biệt cho học phần Cơ sở dữ liệu (thường giảng dạy ở học kỳ 3 hoặc 4) thuộc khối kiến thức cơ sở nhóm ngành Công nghệ Thông tin tại Trường Đại học Khoa học Tự nhiên và các trường khối kỹ thuật.

2. Hai quan hệ cần đáp ứng điều kiện gì để thực hiện được các phép toán tập hợp?

Để thực hiện các phép toán tập hợp ($\cup, \cap, -$), hai quan hệ $r(R)$ và $s(S)$ phải thỏa mãn tính khả hợp (Union Compatibility):

  • Lược đồ $R$ và $S$ phải có cùng bậc $n$ (cùng số lượng thuộc tính).
  • Miền giá trị của các thuộc tính tương ứng phải tương thích: $\text{DOM}(A_i) = \text{DOM}(B_i)$ với mọi $1 \le i \le n$.

3. Phép chọn ($\sigma$) và Phép chiếu ($\Pi$) khác nhau như thế nào về mặt cấu trúc kết quả?

  • Phép chọn ($\sigma_P(r)$): Trích xuất theo hàng ngang (lọc các bộ thỏa điều kiện $P$). Kết quả giữ nguyên danh sách thuộc tính ban đầu và số bộ kết quả luôn nhỏ hơn hoặc bằng số bộ của quan hệ gốc ($|KQ| \le |r|$).
  • Phép chiếu ($\Pi_A(r)$): Trích xuất theo cột dọc (lấy một tập con các thuộc tính $A$). Kết quả có số thuộc tính bằng $k$ ($k \le n$) và số bộ cũng có thể giảm nếu xuất hiện các bộ dữ liệu trùng lắp sau khi chiếu.

4. Tại sao cần học Đại số quan hệ khi các hệ quản trị hiện đại đều sử dụng SQL?

Đại số quan hệ là nền tảng toán học của SQL. Hiểu rõ đại số quan hệ giúp người học:

  • Nắm được cách thức bộ tối ưu hóa truy vấn (Query Optimizer) của hệ quản trị cơ sở dữ liệu chuyển đổi một câu lệnh SQL thành cây đại số quan hệ và sắp xếp lại thứ tự các phép toán để giảm chi phí thực thi.
  • Xây dựng tư duy truy vấn chặt chẽ, tối ưu hóa câu lệnh ngay từ khâu thiết kế logic.

5. Thứ tự thực thi giữa phép tích Cartesian và phép chọn có ảnh hưởng gì đến kết quả?

Tích Cartesian ($r \times s$) tạo ra số lượng bộ rất lớn ($|r| \times |s|$). Trong thực tế tính toán, phép chọn với điều kiện liên kết ($\sigma_{\text{khóa ngoại}=\text{khóa chính}}$) thường được đẩy xuống thực hiện đồng thời hoặc kết hợp thành phép kết (Join) để giảm kích thước bảng dữ liệu trung gian, tối ưu hóa bộ nhớ và thời gian tính toán.

Kết luận

Chương 4 "Đại số quan hệ" trong bài giảng Cơ sở dữ liệu của Bộ môn Hệ thống Thông tin – Trường ĐH Khoa học Tự nhiên là tài liệu học thuật chuẩn hóa, trình bày hệ thống toán học hình thức dùng cho việc rút trích và thao tác dữ liệu. Việc làm chủ các phép toán đơn nguyên ($\sigma, \Pi$), phép toán tập hợp ($\cup, \cap, -$) và phép toán kết nối ($\times, \bowtie, \div$) là điều kiện tiên quyết giúp sinh viên nắm vững nguyên lý vận hành của các hệ quản trị cơ sở dữ liệu quan hệ, tạo nền tảng trực tiếp cho các nội dung tiếp theo như Phép tính quan hệ, Ngôn ngữ SQL và Kỹ thuật tối ưu hóa câu truy vấn.