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

Tài liệu bài giảng môn học Hệ quản trị cơ sở dữ liệu (tên tiếng Anh: Database Management Systems, mã học phần: CO3021) được biên soạn bởi TS. Võ Thị Ngọc Châu (chauvtn@hcmut.vn), thuộc Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – Đại học Quốc gia TP.HCM (áp dụng cho Chương trình đào tạo ngành Khoa học Máy tính trong Học kỳ 1 năm học 2020–2021).

Trong chương trình đào tạo kỹ sư và cử nhân ngành Khoa học Máy tính, môn học CO3021 thuộc khối kiến thức chuyên ngành cốt lõi, tiếp nối các học phần cơ bản về cơ sở dữ liệu quan hệ và cấu trúc dữ liệu. Mục tiêu học tập chính của học phần là cung cấp các nguyên lý, cơ chế hoạt động bên trong của hệ quản trị cơ sở dữ liệu (DBMS Internals), bao gồm: cấu trúc lưu trữ vật lý trên đĩa, các giải thuật chỉ mục, cơ chế xử lý và tối ưu hóa truy vấn SQL, lý thuyết giao tác, kiểm soát tương tranh và các kỹ thuật phục hồi dữ liệu khi có sự cố.

Giáo trình được cấu trúc thành 7 chương nối tiếp nhau theo tiến trình từ tầng vật lý đến tầng xử lý logic và quản trị hệ thống. Cách tiếp cận của tài liệu dựa trên việc phân tích chi tiết quy trình xử lý truy vấn: từ các giai đoạn phân tích cú pháp (parsing), kiểm tra ngữ nghĩa (validation), biểu diễn trung gian bằng cây truy vấn (Query Tree) hoặc đồ thị truy vấn (Query Graph), cho đến việc lập mô hình đánh giá chi phí tính toán I/O (I/O Cost Estimation) và lựa chọn thuật toán thực thi vật lý tối ưu.

Điểm đặc thù của giáo trình là sự kết hợp chặt chẽ giữa mô hình đại số quan hệ mở rộng và việc tính toán định lượng chi phí truy cập khối đĩa (block accesses) đối với từng thuật toán cụ thể (External Sorting, Nested-Loop Join, Sort-Merge Join, Index Scan), giúp người học hiểu rõ bản chất kỹ thuật của các bộ tối ưu hóa truy vấn (Query Optimizer).

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

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

Đề cương tổng thể của môn học CO3021 bao gồm 7 chương học thuật:

  • Chapter 1: Overall Introduction to Database Management Systems (Tổng quan về hệ quản trị cơ sở dữ liệu): Giới thiệu kiến trúc tổng thể, các thành phần chính và chức năng cốt lõi của DBMS.
  • Chapter 2: Disk Storage and Basic File Structures (Lưu trữ đĩa và cấu trúc tập tin cơ bản): Trình bày về phần cứng lưu trữ, định dạng bản ghi, tổ chức khối (blocks) và các cấu trúc tệp dữ liệu nguyên thủy.
  • Chapter 3: Indexing Structures for Files (Cấu trúc chỉ mục cho tập tin): Phân tích các dạng chỉ mục chính (Primary Index), chỉ mục gom cụm (Clustering Index), chỉ mục phụ (Secondary Index), cấu trúc cây B/B+ Tree và kỹ thuật băm (Hashing).
  • Chapter 4: Query Processing and Optimization (Xử lý và tối ưu hóa truy vấn): Trình bày các thuật toán chuyển dịch câu lệnh SQL sang đại số quan hệ, thuật toán sắp xếp ngoài (External Sorting), các phương pháp thực thi phép chọn (SELECT), phép kết nối (JOIN), phép chiếu (PROJECT), phép tập hợp (SET), các toán tử gom nhóm/hàm gộp, kỹ thuật đường ống (Pipelining), tối ưu hóa dựa trên luật heuristics, ước lượng chi phí/độ chọn lọc (Cost/Selectivity Estimation), tối ưu hóa ngữ nghĩa và tổng quan bộ tối ưu hóa trong hệ quản trị Oracle.
  • Chapter 5: Introduction to Transaction Processing Concepts and Theory (Khái niệm và lý thuyết xử lý giao tác): Giới thiệu các thuộc tính ACID, lịch trình thực thi (schedules) và lý thuyết về khả năng khả tuần tự hóa (serializability).
  • Chapter 6: Concurrency Control Techniques (Kỹ thuật kiểm soát tương tranh): Phân tích các giao thức khóa (Locking protocols), Two-Phase Locking (2PL), kỹ thuật gán nhãn thời gian (Timestamp Ordering) và điều khiển tương tranh đa phiên bản (MVCC).
  • Chapter 7: Database Recovery Techniques (Kỹ thuật phục hồi cơ sở dữ liệu): Cơ chế ghi nhật ký (Write-Ahead Logging - WAL), kỹ thuật Checkpoint và các thuật toán khôi phục dữ liệu sau sự cố hệ thống.
+-------------------------------------------------------------------------+
|                  Chương trình môn học DBMS (CO3021)                     |
+-------------------------------------------------------------------------+
| [Tầng lưu trữ & Chỉ mục]   -> Chapter 2: Disk Storage & File Structures |
|                               Chapter 3: Indexing Structures            |
|                                                                         |
| [Tầng xử lý & Tối ưu hóa]  -> Chapter 4: Query Processing & Optimization|
|                                                                         |
| [Tầng giao tác & Tin cậy]  -> Chapter 5: Transaction Concepts & Theory  |
|                               Chapter 6: Concurrency Control            |
|                               Chapter 7: Database Recovery              |
+-------------------------------------------------------------------------+

Tiến trình nội dung đi từ cấu trúc dữ liệu lưu trữ vật lý cấp thấp ở các Chương 2 và 3, làm nền tảng cho việc phân tích các thuật toán thực thi truy vấn ở Chương 4, sau đó mở rộng sang các cơ chế bảo đảm tính toàn vẹn và nhất quán của dữ liệu đa người dùng ở Chương 5, 6 và 7.

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

Nội dung trọng tâm ở phần xử lý truy vấn thiết lập các nền tảng lý thuyết và mô hình tính toán bao gồm:

  • Quy trình 5 bước xử lý truy vấn cấp cao:
    1. Scanner: Quét và nhận diện các từ khóa SQL, tên bảng, tên thuộc tính (tokens).
    2. Parser: Kiểm tra cú pháp truy vấn theo các quy tắc ngữ pháp của ngôn ngữ SQL.
    3. Validator: Xác thực ngữ nghĩa của các thuộc tính và quan hệ dựa trên lược đồ cơ sở dữ liệu (System Catalog).
    4. Query Optimizer & Code Generator: Chuyển đổi biểu diễn trung gian (Query Tree hoặc Query Graph) thành kế hoạch thực thi tối ưu (Execution Plan) và sinh mã thực thi.
    5. Runtime Database Processor: Thực thi mã kế hoạch truy vấn để truy xuất dữ liệu từ các khối đĩa và trả kết quả.
  • Mô hình biểu diễn trung gian: Khái niệm Query Block (khối truy vấn cơ bản chứa cấu trúc SELECT-FROM-WHERE, kèm GROUP BY và HAVING); chuyển đổi câu truy vấn lồng nhau thành các Query Block độc lập; cấu trúc Query Tree (quan hệ là nút lá, toán tử đại số quan hệ là nút nội) và Query Graph (nút quan hệ hình tròn đơn, nút hằng số hình tròn đôi, cạnh biểu diễn điều kiện chọn/nối).
  • Mô hình chi phí thuật toán External Sorting: Áp dụng chiến lược Sort-Merge trên tập tin lớn không vừa bộ nhớ chính với các tham số: số khối tệp $b$, dung lượng bộ đệm $n_B$ khối, số đoạn con ban đầu $n_R = \lceil b / n_B \rceil$, bậc trộn $d_M = \min(n_B - 1, n_R)$, số lượt trộn $n_P = \lceil \log_{d_M}(n_R) \rceil$. Tổng chi phí đọc/ghi khối đĩa được mô hình hóa bằng công thức: $$\text{Cost} = 2b + 2b \cdot \log_{d_M}(n_R)$$
  • Các thuật toán thực thi phép chọn (SELECT - S1 đến S10): Tìm kiếm tuyến tính (Linear search - S1), tìm kiếm nhị phân (Binary search - S2), sử dụng Primary Index/Hash Key cho khóa đơn (S3), sử dụng Primary Index cho điều kiện khoảng (S4), sử dụng Clustering Index (S5), sử dụng Secondary B+-Tree Index (S6), Bitmap Index và Functional Index (S7), truy vấn kết hợp điều kiện AND (Conjunctive - S8/S9/S10), và truy vấn chứa điều kiện OR (Disjunctive - yêu cầu quét tuyến tính hoặc hợp các danh sách con trỏ bản ghi).
  • Các thuật toán thực thi phép nối (JOIN - J1 đến J4):
    • Nested-loop join (J1): Phân tích vòng lặp lồng nhau giữa quan hệ ngoài (Outer loop) và quan hệ trong (Inner loop).
    • Single-loop join (J2): Sử dụng cấu trúc chỉ mục/băm trên bảng trong để truy xuất trực tiếp các bản ghi khớp giá trị.
    • Sort-merge join (J3): Quét đồng thời hai con trỏ trên các bảng đã được sắp xếp vật lý theo thuộc tính nối.
    • Hash join (J4): Băm và phân đoạn dữ liệu vào bộ nhớ đệm.

Kỹ năng phát triển

Thông qua các nội dung được giảng dạy, người học hình thành các kỹ năng:

  • Kỹ năng phân tích và ánh xạ: Khả năng chuyển đổi biểu thức SQL phức tạp sang mô hình toán học tương đương của đại số quan hệ mở rộng (Extended Relational Algebra) có chứa các toán tử gom nhóm $\Im$ và hàm gộp (MAX, MIN, COUNT, SUM).
  • Kỹ năng tính toán và ước lượng chi phí I/O: Khả năng áp dụng các công thức giải tích để tính chính xác số lần truy cập khối đĩa (Block Accesses) của từng phương án thực thi dựa trên kích thước bảng ($b$), kích thước bản ghi, và số lượng khối đệm bộ nhớ khả dụng ($n_B$).
  • Kỹ năng phân tích chiến lược truy vấn: Đánh giá việc lựa chọn thứ tự quan hệ trong phép nối (đặt bảng có số khối nhỏ hơn ở vòng lặp ngoài Outer loop để giảm số lần đọc lại dữ liệu bảng trong), lựa chọn loại chỉ mục phù hợp (B+-Tree, Bitmap, Functional Index) cho các biểu thức điều kiện cụ thể.

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

Tài liệu thể hiện phương pháp sư phạm tiếp cận theo hướng kỹ thuật giải thuật và phân tích định lượng (Quantitative Analysis). Giảng viên sử dụng các mô hình cơ sở dữ liệu mẫu cụ thể để minh họa từng bước vận hành của giải thuật.

Lược đồ cơ sở dữ liệu mẫu và các truy vấn chuẩn

Tài liệu sử dụng hệ thống bảng chuẩn quản lý nhân sự làm case study xuyên suốt:

  • EMPLOYEE (Ssn, Fname, Minit, Lname, Bdate, Address, Sex, Salary, Super_ssn, Dno)
  • DEPARTMENT (Dname, Dnumber, Mgr_ssn, Mgr_start_date)
  • WORKS_ON (Essn, Pno, Hours)

Dựa trên lược đồ này, các dạng toán tử được thiết kế qua chuỗi bài tập truy vấn mẫu:

  • $\text{OP1: } \sigma_{SSN='123456789'}(EMPLOYEE)$ (Phép chọn trên khóa chính).
  • $\text{OP2: } \sigma_{DNUMBER > 5}(DEPARTMENT)$ (Phép chọn điều kiện khoảng).
  • $\text{OP4: } \sigma_{DNO=5 \land SALARY > 30000 \land SEX='F'}(EMPLOYEE)$ (Điều kiện hội AND).
  • $\text{OP4': } \sigma_{DNO=5 \lor SALARY > 30000 \lor SEX='F'}(EMPLOYEE)$ (Điều kiện tuyển OR).
  • $\text{OP7: } \sigma_{((Salary \cdot Commission_pct) + Salary) > 5000}(EMPLOYEE)$ (Phép chọn trên biểu thức hàm, minh họa cho Functional Index).
  • $\text{OP8: } EMPLOYEE \bowtie_{DNO=DNUMBER} DEPARTMENT$ (Phép kết nối hai bảng).
        [Mô hình tính toán chi phí Nested-Loop Join (OP8)]
-----------------------------------------------------------------
  Tham số:
    - Bảng EMPLOYEE (bE): 2.000 khối
    - Bảng DEPARTMENT (bD): 10 khối
    - Bộ đệm bộ nhớ (nB): 7 khối
  
  Trường hợp 1: EMPLOYEE làm vòng lặp ngoài (Outer Loop)
    Chi phí = bE + (bD * bE) / (nB - 2)
            = 2.000 + 10 * (2.000 / 5) = 6.000 lần truy cập khối

  Trường hợp 2: DEPARTMENT làm vòng lặp ngoài (Outer Loop)
    Chi phí = bD + (bE * bD) / (nB - 2)
            = 10 + 2.000 * (10 / 5) = 4.010 lần truy cập khối
-----------------------------------------------------------------
  => Kết luận giải thuật: Bảng có kích thước nhỏ hơn đặt ở vòng
     lặp ngoài cho chi phí I/O thấp hơn rõ rệt (4.010 < 6.000).

Phương pháp trực quan hóa giải thuật

Giáo trình sử dụng các bảng mô phỏng từng bước (Trace-step execution) cho thuật toán Sort-Merge Join ($T \leftarrow R \bowtie_{A=B} S$). Trạng thái của hai con trỏ bản ghi $i$ (trên quan hệ $R$) và $j$ (trên quan hệ $S$) được biểu diễn chi tiết qua từng chu kỳ so sánh:

  • Khi $R(i)[A] > S(j)[B]$: Tăng chỉ số $j \leftarrow j + 1$.
  • Khi $R(i)[A] < S(j)[B]$: Tăng chỉ số $i \leftarrow i + 1$.
  • Khi $R(i)[A] = S(j)[B]$: Xuất bộ bản ghi kết hợp $\langle R(i), S(j) \rangle$, đồng thời duyệt và xuất tất cả các bản ghi trùng lặp liên tiếp của cả hai quan hệ trước khi tiếp tục tăng $i$ và $j$.

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

Nội dung bài giảng tổng hợp kiến thức từ các tài liệu chuẩn quốc tế hàng đầu về hệ cơ sở dữ liệu:

  1. R. Elmasri & S. B. Navathe, Fundamentals of Database Systems (Phiên bản thứ 6 - 2011 và phiên bản thứ 7 - 2016, Nhà xuất bản Pearson/Addison-Wesley).
  2. J. Widom et al., Database System Implementation (Prentice-Hall, 2000) và Database Systems: The Complete Book (Prentice-Hall, 2002).
  3. A. Silberschatz, H. F. Korth, S. Sudarshan, Database System Concepts (Phiên bản thứ 3, McGraw-Hill, 1999).

Sự tích hợp giữa các nguồn tài liệu này thể hiện ở các khía cạnh:

  • Cập nhật các kỹ thuật chỉ mục hiện đại: Bên cạnh các cấu trúc truyền thống (B-Tree, Hashing), giáo trình đưa vào phân tích cơ chế hoạt động của Bitmap Index (sử dụng phép toán logic bit OR/AND trên các vector bit để tăng tốc truy vấn tập hợp) và Functional Index (ví dụ lệnh CREATE INDEX income_ix ON EMPLOYEE (Salary + (Salary*Commission_pct)); trong hệ thống quản trị hiện đại).
  • Liên hệ hệ thống thương mại thực tế: Nội dung học phần có mục chuyên đề phân tích tổng quan cơ chế tối ưu hóa truy vấn của hệ quản trị cơ sở dữ liệu thương mại Oracle (Overview of Query Optimization in Oracle), giúp sinh viên đối chiếu giữa mô hình lý thuyết giải thuật và cơ chế thực tế trong các hệ thống DBMS công nghiệp.
  • Mở rộng kỹ thuật tối ưu hóa ngữ nghĩa: Trình bày phương pháp Semantic Query Optimization, sử dụng các ràng buộc toàn vẹn và quy tắc ngữ nghĩa đã được định nghĩa trong schema để loại bỏ các phép toán dư thừa mà không cần truy cập dữ liệu vật lý.

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

  • Sinh viên đại học: Giáo trình phục vụ trực tiếp cho sinh viên năm thứ 3 và năm thứ 4 chuyên ngành Khoa học Máy tính, Kỹ thuật Máy tính và Công nghệ Thông tin tại Trường Đại học Bách Khoa – ĐHQG-HCM đang theo học học phần CO3021.
  • Yêu cầu kiến thức tiên quyết (Prerequisites):
    • Kiến thức về mô hình dữ liệu quan hệ, đại số quan hệ căn bản và ngôn ngữ lập trình truy vấn SQL.
    • Kiến thức về Cấu trúc dữ liệu và Giải thuật (các thuật toán tìm kiếm nhị phân, sắp xếp, cấu trúc cây và giải thuật băm).
    • Kiến thức nền tảng về Kiến trúc máy tính và Hệ điều hành (cơ chế phân trang, quản lý bộ nhớ đệm buffer pool, cấu trúc sector/block trên ổ đĩa vật lý).
  • Giảng viên và nhà nghiên cứu: Có thể sử dụng tài liệu làm khung đề cương chi tiết, bài giảng tham chiếu chuẩn cho việc giảng dạy các học phần chuyên sâu về Database Internals hoặc xây dựng các hệ thống lưu trữ dữ liệu quy mô lớn.
  • Kỹ sư phần mềm và Quản trị viên cơ sở dữ liệu (DBA): Sử dụng làm tài liệu tham cứu kỹ thuật để hiểu rõ cơ chế vận hành của Query Optimizer, từ đó phân tích kế hoạch thực thi (Execution Plan), thiết kế chỉ mục phù hợp và tối ưu hóa hiệu năng câu lệnh SQL phức tạp.

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

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

Giáo trình được thiết kế cho sinh viên đại học ngành Khoa học Máy tính, Kỹ thuật Phần mềm và Kỹ thuật Máy tính cần học chuyên sâu về cơ chế vận hành bên trong của hệ quản trị cơ sở dữ liệu, cũng như các kỹ sư phần mềm muốn nắm vững nguyên lý hoạt động của bộ tối ưu hóa truy vấn.

2. Cần trang bị những kiến thức nền nào trước khi học?

Người học cần hoàn thành học phần cơ sở dữ liệu cơ bản (sử dụng thành thạo SQL và hiểu mô hình quan hệ), học phần Cấu trúc dữ liệu và Giải thuật (hiểu về cây tìm kiếm, thuật toán sắp xếp ngoài, giải thuật băm), cùng kiến thức cơ bản về quản lý tệp và bộ đệm trong Hệ điều hành.

3. Điểm khác biệt của giáo trình này so với các tài liệu nhập môn cơ sở dữ liệu là gì?

Các tài liệu nhập môn tập trung vào việc thiết kế lược đồ quan hệ, chuẩn hóa dữ liệu (1NF, 2NF, 3NF, BCNF) và cách viết câu lệnh SQL phía người dùng. Ngược lại, giáo trình CO3021 tập trung hoàn toàn vào tầng lõi hệ thống (DBMS Internals): cách parser phân tích câu lệnh, thuật toán thực thi đại số quan hệ ở mức khối đĩa vật lý, mô hình toán học tính toán chi phí I/O, và cơ chế kiểm soát giao tác, phục hồi dữ liệu.

4. Phương pháp tự học giáo trình này như thế nào để đạt hiệu quả cao?

Người học nên tự diễn giải từng bước các câu truy vấn mẫu (OP1 đến OP9) thành biểu diễn Query Tree/Graph, sau đó tự tính toán chi phí I/O khối đĩa bằng các công thức giải tích cho từng trường hợp bộ đệm ($n_B$) khác nhau. Ngoài ra, việc đọc đối chiếu với các chương tương ứng trong sách giáo khoa của tác giả Elmasri & Navathe (Chương 18-19) sẽ giúp củng cố toàn diện phần giải thuật.

5. Có tài liệu học thuật nào được sử dụng bổ trợ trực tiếp cùng giáo trình?

Tài liệu được xây dựng trực tiếp dựa trên các giáo trình chuẩn quốc tế gồm: Fundamentals of Database Systems (R. Elmasri & S. B. Navathe, bản in lần 6 và 7), Database System Implementation / Database Systems: The Complete Book (J. Widom et al.), và Database System Concepts (A. Silberschatz, H. F. Korth, S. Sudarshan).

Kết luận

Bài giảng môn học Hệ quản trị cơ sở dữ liệu (CO3021) do TS. Võ Thị Ngọc Châu biên soạn cung cấp hệ thống kiến thức toàn diện và chính xác về các cơ chế nội tại của một DBMS quan hệ. Giá trị cốt lõi của tài liệu nằm ở việc mô hình hóa toán học các quy trình xử lý truy vấn, phân tích chi tiết các thuật toán vật lý từ mức truy cập khối đĩa đến việc xây dựng cây thực thi tối ưu.

Lộ trình học tập được thiết kế mạch lạc: người học nghiên cứu cấu trúc lưu trữ và chỉ mục ở các Chương 2 và 3; nắm vững giải thuật thực thi, sắp xếp ngoài và tối ưu hóa ở Chương 4; sau đó hoàn thiện kiến thức quản trị hệ thống với các kỹ thuật giao tác, kiểm soát tương tranh và phục hồi dữ liệu ở các Chương 5, 6 và 7. Các nội dung tham khảo bổ sung từ các công trình của Elmasri, Navathe, Widom và Sudarshan cung cấp đầy đủ cơ sở học thuật cho việc nghiên cứu chuyên sâu về công nghệ cơ sở dữ liệu.