Bài giảng Cơ sở dữ liệu - Chương 4: Đại số quan hệ và phép tính quan hệ

điều kiện
• Chứa các mệnh đề có dạng
- Ai Bj.
+ Ai là thuộc tính của R.
+ Bj là thuộc tính của S.
+ Miền xác định Ai ≡ Miền xác định Bj.
• Toán tử so sánh: =, , ≥, ≠.
• Các mệnh đề được nối bởi toán tử logic: ∧.
12ββ
5αβ
5βα
1αα
CBAR
12β
4α
1α
FES R A=E ∧ C<F S
β
α
E
125αβ
41αα
FCBA
12
Phép kết bằng
ƒ Tất cả các toán tử so sánh trong biểu thức điều kiện đều là
=.
ƒ Trong mỗi bộ luôn có một hoặc nhiều cặp thuộc tính có giá
trị giống nhau.
12ββ
5αβ
5βα
1αα
CBAR
12β
4α
1α
FES R A=E ∧ C=F S
β
α
E
1212ββ
11αα
FCBA
Phép kết tự nhiên
ƒ Là phép kết bằng và các cặp thuộc tính trong các mệnh đề
phải cùng tên và cùng miền xác định.
ƒ Nếu các cặp thuộc tính không cùng tên thì phải thực hiện 
phép toán đổi tên trước khi kết.
• R(A, B, C) và S(E, F), muốn kết tự nhiên trên 2 cặp thuộc tính (A, E) 
và (C, F).
- R (ρ(A, C)(S)).
12ββ
5αβ
5βα
1αα
CBAR
12β
4α
1α
CAS R S
12ββ
1αα
CBA
13
Phép chia (1)
ƒ Để rút trích các bộ của một quan hệ liên quan với 
tất cả các bộ của quan hệ còn lại.
ƒ Cho 2 quan hệ R(Z) và S(X)
• Z tập hợp các thuộc tính của quan hệ R.
• X tập hợp các thuộc tính của quan hệ S.
• X ⊆ Z.
• R chia S là quan hệ T(Y) với Y = Z – X.
- T(Y) = {t | t ∈ πY(R) ∧ ∀ u ∈ S ⇒ (t, u) ∈ R}.
ƒ Cú pháp
• R ÷ S
Phép chia (2)
1013ββ
5223αβ
101023ββ
2723αβ
1
7
2
7
D
212ββ
212βα
51αα
21αα
ECBAR
3ββ
23ββ
23αβ
12ββ
12βα
1αα
CBA
2
7
D
5
2
ES
πA,B,C(R)
23αβ
1αα
CBAR ÷ S
14
Một số ví dụ
ƒ Cho biết tên, địa chỉ của các nhân viên của phòng Nghiên 
cứu.
• Q1 ← σTenPB = ‘Nghien cuu’(PHONGBAN)
Q2 ← Q1 * NHANVIEN
Q ← πHo, Ten, DChi(Q2)
ƒ Cho biết tên các nhân viên tham gia tất cả các dự án do 
phòng số 5 điều phối.
• Q1 ← πMaDA(σPhongQL = 5(DUAN))
Q2 ← πMaNV, MaDA(THAMGIA)
Q3 ← Q2 ÷ Q1
Q ← πHo, Ten(Q3 * NHANVIEN)
Các phép toán khác
ƒ Để biểu diễn các truy vấn mà không thể thực hiện 
với các phép toán đại số quan hệ cơ sở
• Các truy vấn mang tính chất thông kê đơn giản trên một 
tập hợp các giá trị hoặc các nhóm tập hợp giá trị dữ liệu.
• Các truy vấn dùng để tạo các báo cáo.
ƒ Gồm
• Hàm tập hợp (Aggregate Function).
• Phép gom nhóm các bộ dữ liệu (Grouping).
• Phép kết mở rộng (Outer Join).
15
Hàm tập hợp và gom nhóm (1)
ƒ Để thực hiện các truy vấn thống kê đơn giản trên tập hợp các giá trị số
• SUM - Tính tổng của các giá trị trong tập hợp.
• AVG - Tính giá trị trung bình của các giá trị trong tập hợp.
• MAX, MIN - Tìm giá trị lớn nhất, nhỏ nhất của các giá trị trong tập hợp.
ƒ Để đếm số bộ của một quan hệ hoặc số các giá trị của một thuộc tính.
• COUNT
ƒ Để gom nhóm các bộ của một quan hệ theo các thuộc tính rồi áp dụng 
các hàm tập hợp.
ƒ Cú pháp
• ℱ(R)
• là danh sách các thuộc tính thuộc R.
• là danh sách các cặp (hàm tập hợp, thuộc tính) áp dụng trên các 
nhóm.
Hàm tập hợp và gom nhóm (2)
1020ββ
312ββ
85βα
71αα
DCBAR
1632ββ
55βα
11αα
FEBAS
1220β
15α
MIN_CMAX_CA
74
AVG_DCOUNT_C
ρS(A, B, E, F)(A, BℱSUM(C), AVG(C)(R))
AℱMAX(C), MIN(C)(R)
ℱCOUNT(C), AVG(D)(R)
16
Phép kết mở rộng (1)
ƒ Để giữ lại tất cả các bộ trong một quan hệ bất chấp 
chúng có được liên kết với các bộ trong quan hệ
còn lại hay không nhằm tránh mất thông tin hoặc 
tạo các báo cáo.
ƒ Có 3 dạng
• Mở rộng trái (Left Outer Join)
- R S.
• Mở rộng phải (Right Outer Join)
- R S.
• Mở rộng hai phía (Full Outer Join)
- R S.
Phép kết mở rộng trái
ƒ Giữ lại tất cả các bộ của quan hệ ở bên trái phép toán kết 
mà không liên kết được với bộ nào của quan hệ bên phải.
23ββ
12ββ
5βα
1αα
CBAR
1023
312
72
71
EDS 10235βα
10231αα
3121αα
nullnull23ββ
23
12
2
D
1012ββ
35βα
71αα
ECBA
R C<D S
17
Phép kết mở rộng phải
ƒ Giữ lại tất cả các bộ của quan hệ ở bên phải phép toán kết 
mà không liên kết được với bộ nào của quan hệ bên trái.
23ββ
12ββ
5βα
1αα
CBAR
1023
312
72
71
EDS
R C>D S
31223ββ
7223ββ
7123ββ
7212ββ
23
1
2
1
D
10nullnullnull
712ββ
75βα
75βα
ECBA
Phép kết mở rộng hai phía
ƒ Giữ lại tất cả các bộ của từng quan hệ ở hai bên phép toán 
kết mà không liên kết được với bộ nào của quan hệ còn lại.
23ββ
12ββ
5βα
1αα
CBAR
1023
312
72
71
EDS
R C=D S
72nullnullnull
nullnull5βα
102323ββ
12
1
D
312ββ
71αα
ECBA
18
Một số ví dụ
ƒ Với mỗi phòng ban cho biết mã số, tổng số nhân viên và
mức lương trung bình.
• ρ(MaPB, SoNV, LuongTB)(MaPBℱCOUNT(MaNV), AVG(Luong) (NHANVIEN))
ƒ Với mỗi nhân viên cho biết họ, tên và tên phòng nếu họ là 
trưởng phòng.
• Q1 ← NHANVIEN MaNV = TrPhong PHONGBAN
Q ← πHo, Ten, TenPB(Q1)
Phép tính quan hệ (1)
ƒ Một số khái niệm logic toán học
• Mệnh đề
- Các khẳng định có giá trị chân lý xác định.
• Vị từ
- Là một khẳng định P(x, y, ...) với x, y, ... là các biến trên các miền xác 
định A, B, ...
+ P(x, y, ...) không là mệnh đề.
+ Thay x, y, ... bằng các giá trị cụ thể ta được một mệnh đề.
- x, y, ... là các biến tự do.
• Lượng từ
- Mệnh đề “∀x ∈ A, P(x)” và “∃x ∈ A, P(x)” là các lượng từ hóa của vị từ
P(x).
+ ∀ là lượng từ phổ dụng.
+ ∃ là lượng từ tồn tại.
- x không còn là biến tự do, nó bị buộc bởi các lượng từ ∀ hay ∃.
19
Phép tính quan hệ (2)
ƒ Tổng quan
• Ngôn ngữ hình thức của mô hình quan hệ.
• Chỉ quan tâm đến nội dung dữ liệu cần truy vấn.
• Ngôn ngữ phi thủ tục.
• Dựa trên logic toán học.
ƒ Chia làm 2 dạng
• Phép tính quan hệ biến bộ.
• Phép tính quan hệ biến miền (miền xác định).
Biến bộ và quan hệ miền giá trị
ƒ Biến bộ (Tuple Variable)
• Biến biến thiên trên một quan hệ R xác định.
ƒ R được gọi là quan hệ miền giá trị của biến bộ
(Range Relation).
ƒ Phép tính quan hệ biến bộ đơn giản
• {t | P(t)}.
- t là biến bộ.
- P(t) là vị từ hoặc công thức.
ƒ Ví dụ
• {t | t ∈ NHANVIEN ∧ t.Luong > 50000}.
• {t.Ho, t.Ten | NHANVIEN(t) ∧ t.Luong > 50000}
20
Biểu thức và công thức (1)
ƒ Biểu thức tổng quát của phép tính quan hệ biến bộ
• {t1.Aj, t2.Ak, ..., tn.Am | P(t1, t2, ..., tn, ..., tn+m)}
- t1, ..., tn+m là các biến bộ.
- Ai là thuộc tính của quan hệ miền giá trị ứng với biến bộ ti.
ƒ Công thức nguyên tử
• Thuộc một trong 3 dạng sau
- t ∈ R hoặc R(t)
- ti.A tj.B.
- ti.A c.
• Có chân trị ĐÚNG hoặc SAI.
t ∈ NHANVIEN hoặc NHANVIEN(t)
t.MaNV = s.MaNV
t.Luong > 50000
Biểu thức và công thức (2)
ƒ P được xây dựng từ các 
công thức nguyên tử liên 
kết với nhau bởi các phép 
toán logic ∧, ∨, ¬ theo các 
luật sau
1. Công thức nguyên tử là
công thức.
2. F là công thức thì ¬F cũng là
công thức.
F, G là công thức thì F ∧ G, 
F ∨ G cũng là công thức
3. F là công thức thì (∀t)(F) 
cũng là công thức.
4. F là công thức thì (∃t)(F) 
cũng là công thức.
ƒ Biến bộ tự do và bị buộc
• F là nguyên tử
- Biến bộ là tự do.
• (∀t)(F), (∃t)(F)
- Biến bộ là bị buộc.
• ¬F, F ∧ G, F ∨ G
- Biến bộ là tự do hoặc bị
buộc.
- Biến bộ có thể là tự do trong 
F và bị buộc trong G.
ƒ Ví dụ
•
•
F1: NHANVIEN(d)
F2: (∀d)(d.MaGSat = 
‘123456789’)
21
Biến đổi giữa hai lượng từ
ƒ Quy tắc biến đổi
• (∀) thay bằng ¬(∃), và ngược lại.
• ∧ thay bằng ∨, và ngược lại.
• ¬P thay bằng P, và ngược lại.
ƒ Một số biến đổi thường gặp
• (∀x)(P(x)) ⇔
• (∃x)(P(x)) ⇔
• (∀x)(P(x) ∧ Q(x)) ⇔
• (∀x)(P(x) ∨ Q(x)) ⇔ ¬(∃x)(¬(P(x)) ∧ ¬(Q(x)))
• (∃x)(P(x) ∧ Q(x)) ⇔ ¬(∀x)(¬(P(x)) ∨ ¬(Q(x)))
• (∃x)(P(x) ∨ Q(x)) ⇔ ¬(∀x)(¬(P(x)) ∧ ¬(Q(x)))
¬(∃x)(¬(P(x)))
¬(∀x)(¬(P(x)))
¬(∃x)(¬(P(x)) ∨ ¬(Q(x)))
Truy vấn dùng lượng từ tồn tại (1)
ƒ Tìm tên và địa chỉ của các nhân viên phòng Nghiên 
cứu.
•
• {e.Ten, e.DChi | NHANVIEN(e) ∧ F}
- F = (∃d)(PHONGBAN(d) ∧ F1)
- F1 = (d.TenPB = ‘Nghiên cứu’ ∧ d.MaPB = e.MaPB)
{e.Ten, e.DChi | NHANVIEN(e) ∧ (∃d)(PHONGBAN(d) ∧
d.TenPB = ‘Nghiên cứu’ ∧ d.MaPB = e.MaPB)}
I ( ) ( )( ( ) 
22
Truy vấn dùng lượng từ tồn tại (2)
ƒ Với mỗi dự án triển khai tại Thủ Đức, cho biết mã 
dự án, mã phòng quản lý dự án và họ tên người 
trưởng phòng.
•
ƒ Nhận xét
• Trong một truy vấn có thể có nhiều biến bộ tự do.
{p.MaDA, p.Phong, e.Ho, e.Ten | DUAN(p) ∧
NHANVIEN(e) ∧ p.Diadiem = ‘Thủ Đức’ ∧
(∃d)(PHONGBAN(d) ∧ d.MaPB = p.Phong ∧ d.TrPhg = 
e.MaNV)}
( ) 
Truy vấn dùng lượng từ tồn tại (3)
ƒ Với mỗi nhân viên, cho biết họ tên của nhân viên 
và họ tên của người quản lý nhân viên đó.
•
ƒ Nhận xét
• Một vài biến bộ trong cùng một truy vấn có thể có cùng 
quan hệ miền giá trị.
{e.Ho, e.Ten, s.Ho, s.Ten | NHANVIEN(e) ∧
NHANVIEN(s) ∧ e.MaGSat = s.MaNV }
I ( ) 
23
Truy vấn dùng lượng từ tồn tại (4)
ƒ Tìm các nhân viên tham gia các dự án do phòng số 
5 điều phối.
• {e | NHANVIEN(e) ∧ (∃x)(∃w)(DUAN(x) ∧ THAMGIA(w) ∧
x.Phong = 5 ∧ x.MaDA = w.MaDA ∧ x.MaNV = w.MaNV)}
Truy vấn sử dụng lượng từ phổ dụng
ƒ Tìm các nhân viên tham gia tất cả các dự án do 
phòng số 5 điều phối.
• {e | NHANVIEN(e) ∧ ((∀x)(¬(DUAN(x)) ∨ ¬(x.MaDA = 5) 
∨ ((∃w)(THAMGIA(w) ∧ w.MaNV = e.MaNV ∧ x.MaDA = 
w.MaDA))))}
• {e | NHANVIEN(e) ∧ F}
- F = (∀x)(¬(DUAN(x)) ∨ F1)
- F1 = ¬(x.MaDA=5) ∨ F2
- F2 = (∃w)(THAMGIA(w) ∧ w.MaNV=e.MaNV ∧ x.MaDA=w.MaDA)
• {e | NHANVIEN(e) ∧ (¬(∃x)(DUAN(x) ∧ x.MaDA = 5 ∧
(¬(∃w)(THAMGIA(w) ∧ w.MaNV = e.MaNV ∧ x.MaDA = 
w.MaDA))))}
24
Biểu thức an toàn
ƒ Xét biểu thức
• {t | ¬(NHANVIEN(t))}
• Nhận xét
- Kết quả của biểu thức không
là một số hữu hạn các bộ.
- Biểu thức là không an toàn.
ƒ Biểu thức an toàn là biểu 
thức có một số hữu hạn 
các bộ trong kết quả.
ƒ Định nghĩa hình thức
• Miền xác định của biểu thức 
là tập hợp gồm
- Các hằng xuất hiện trong P.
- Giá trị thuộc tính của các bộ
của các quan hệ xuất hiện 
trong P.
• Ví dụ
- {t | R(t) ∧ t.A = 5}
- Mxđ = {5, 1, 7, 23, 10}
• Biểu thức là an toàn nếu mọi 
giá trị trong kết quả thuộc 
miền xác định của biểu thức.
1023
71
BAR
Phép tính quan hệ biến miền
ƒ Biểu thức tổng quát của phép tính quan hệ biến 
miền
• {x1, x2, ..., xn | P(x1, x2, ..., xn, ..., xn+m)}
- x1, ..., xn+m là các biến miền.
ƒ Công thức nguyên tử
• Thuộc một trong 3 dạng sau
- ∈ R hoặc R(x1, ..., xj)
- xi xj.
- xi c.
• Có chân trị ĐÚNG hoặc SAI.
ƒ Các khái niệm khác tương tự biến bộ.