Đại số quan hệ

Đại số quan hệ (relational algebra) dùng phổ biến trong lý thuyết cơ sở dữ liệu quan hệ là một bộ các toán tử và các quy tắc tương ứng có thể được sử dụng để thao tác trên các toán học (relation) và tạo ra kết quả là một quan hệ khác. Trước đây, đại số quan hệ ít được quan tâm cho đến khi Edgar F. Codd đưa ra mô hình dữ liệu quan hệ (relational model) vào năm 1970. Từ đó đến nay, đại số quan hệ được xem là nền tảng cho các ngôn ngữ truy vấn cơ sở dữ liệu.

Dựa trên lý thuyết tập hợp

Các phép toán dựa trên lý thuyết tập hợp thực hiện trên 2 quan hệ R và S bao gồm:

  • Phép hợp (hội): $ R \cup S $
  • Phép giao: R \cap S $
  • Phép trừ: R \ S

Để thực hiện các phép toán này, 2 quan hệ R và S phải khả hợp. Điều kiện để 2 quan hệ khả hợp bao gồm:

  • 2 quan hệ R và S phải có 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

Kết quả của các phép toán này là 1 quan hệ có cùng thuộc tính với các quan hệ ban đầu

Rút trích 1 phần quan hệ

Phép chọn

Phép chọn (selection): trích ra các bộ (dòng) từ quan hệ R. Các bộ được trích phải thỏa mãn điều kiện p.

  • Ký hiệu: $\sigma_p(R)$
  • Định nghĩa: $\sigma_p(R) = \{t|t \in R, p(t)\}$. Trong đó p(t) thỏa mãn điều kiện t.
  • Kết quả: trả về một quan hệ, có cùng các thuộc tính với quan hệ R.
  • Phép chọn có tính giao hoán.

Ví dụ: Cho quan hệ “SINH_VIÊN” với dữ liệu:

Mã số sinh viên Họ tên Ngày sinh Giới tính
NV01 Nguyễn Bảo Anh 25/05/2000 Nữ
NV02 Trần Mạnh Dũng 21/08/2000 Nam
NV03 Võ Văn Hoàng 14/02/2000 Nam
  • Câu hỏi: Cho biết các sinh viên ‘Nam’.
  • Cách biểu diễn: $\sigma_{(giới\_tính=’Nam’)}(SINH\_VIÊN)$
  • Kết quả của phép chọn:
Mã số sinh viên Họ tên Ngày sinh Giới tính
NV02 Trần Mạnh Dũng 21/08/2000 Nam
NV03 Võ Văn Hoàng 14/02/2000 Nam

Phép chiếu

Phép chiếu (project): sử dụng để trích chọn giá trị của một vài thuộc tính của quan hệ R.

  • Ký hiệu: $\Pi_{A_1, A_2,\dots,A_k}(R)$. Trong đó $A_i$ là tên các thuộc tính được chiếu.
  • Kết quả: trả về một quan hệ có k thuộc tính theo thứ tự.
  • Phép chiếu không có tính giao hoán

Ví dụ: Với quan hệ đã cho phía trên, cho biết họ tên và giới tính của các bạn sinh viên.

  • Cách biểu diễn: $\Pi_{họ\_tên, giới\_tính}(SINH\_VIÊN)$
  • Kết quả:

Kết hợp các quan hệ

Tích Descartes

  • Kí hiệu: $R \times S$
  • Định nghĩa: $R \times S = \{t_rt_s | t_r \in R \land t_s \in S\}$. Nếu R có n bộ và S có m bộ thì kết quả là n*m bộ.
  • Phép tích thường dùng kết hợp với các phép chọn để kết hợp các bộ có liên quan từ hai quan hệ.

Ví dụ: Chúng ta có 2 quan hệ SINH_VIÊN và MÔN HỌC. Chúng ta sẽ có tất cả các trường hợp sinh viên đăng ký môn học (giả sử không có điều kiện nào ràng buộc).

Tên MH
CSDL
Lập trình cơ bản

Tất cả các trường hợp xảy ra là kết quả của phép tích Descartes giữa 2 quan hệ SINH_VIÊN và MÔN_HỌC.

Mã số sinh viên Họ tên Ngày sinh Giới tính Tên MH
NV01 Nguyễn Bảo Anh 25/05/2000 Nữ CSDL
NV02 Trần Mạnh Dũng 21/08/2000 Nam CSDL
NV03 Võ Văn Hoàng 14/02/2000 Nam CSDL
NV01 Nguyễn Bảo Anh 25/05/2000 Nữ Lập trình cơ bản
NV02 Trần Mạnh Dũng 21/08/2000 Nam Lập trình cơ bản
NV03 Võ Văn Hoàng 14/02/2000 Nam Lập trình cơ bản

Phép kết

Phép kết (theta-join $\theta$): tương tự như phép tích Descartes kết hợp với phép chọn. Điều kiện chọn gọi là điều kiện kết.

  • Kí hiệu: $R \bowtie_p S$. Trong đó R, S là các quan hệ, p là điều kiện kết.

Phép kết bằng, kết tự nhiên

Nếu phép kết $\theta$ là phép so sánh bằng (=), thì phép kết đó được gọi là phép kết bằng (equi-join)

  • Ký hiệu $PHÒNG\_BAN \bowtie_{trưởng\_phòng=mã\_nv} NHÂN\_VIÊN$
  • Nếu điều kieejn của equi-join là các thuộc tính giống nhau (cùng tên gọi) ở 2 quan hệ, thì phép kết này được gọi là phép kết tự nhiên (natural-join). Khi đó, kết quả sẽ bỏ bớt 1 thuộc tính (thuộc tính kết sẽ bị trùng). Ký hiệu: $SINH\_VIÊN \bowtie_{mã\_sv} ĐIỂM$

Phép kết ngoài (Outer Join)

Trong một số trường hợp, chúng ta cần mở rộng phép kết để tránh mất thông tin. Ví dụ: tra cứu điểm thi của sinh viên. Với phép kết bình thường, chỉ những sinh viên có thông tin trong cả quan hệ SINH_VIÊN và ĐIỂM mới có ở kết quả. Tuy nhiên, trong một vài trường hợp, chúng ta cần thu về thông tin của cả sinh viên chưa có điểm.

Để thực hiện phép kết ngoài, ban đầu chúng ta sẽ thực hiện phép kết và sau đó thêm vào kết quả của phép kết các bộ của quan hệ mà không phụ hợp với các bộ trong quan hệ kia.

Có 3 loại kết ngoài:

  • Left outer join
  • Right outer join
  • Full outer join