Cơ sở dữ liệu - Chương 6: Ngôn ngữ phép tính quan hệ

1NGÔN NGỮ PHÉP TÍNH QUAN HỆ
Chương 6
2
Giới thiệu
z Là ngôn ngữ truy vấn hình thức do Codd 
đề nghị (1972,1973), được Lacroit & 
Piroix (1977), Ullman (1982) phát 
triển, cài đặt trong một số ngôn ngữ 
như QBE, ALPHA,…...
zĐặïc điểm:
– Phi thủ tục
– Dựa trên logic
– Khả năng diễn đạt tương đương với 
ĐSQH
3Giới thiệu
z 2 loại: 
– Ngôn ngữ phép tính quan hệ có biến 
là bộ (gọi tắt là phép tính bộ)
– Ngôn ngữ phép tính quan hệ có biến 
là miền (gọi tắt là phép tính miền)
4
Nội dung
I. Giới thiệu
II. Phép tính quan hệ có biến là bộ
Tuple Relational Calculus – TRC
III. Phép tính quan hệ có biến là miền
Domain Relational Calculus - DRC
5Phép tính quan hệ có biến là bộ
(Tuple Relational Calculus)
6
Biến bộ và quan hệ vùng của biến bộ
z Biến bộ: biến nhận giá trị là một bộ
của quan hệ trong CSDL
z Với mỗi biến bộ t, quan hệ R mà t biến 
thiên trên đó được gọi là quan hệ vùng 
của biến bộ và được chỉ ra bởi kí pháp 
R(t).
7Biểu thức truy vấn phép tính bộ
zMột biểu thức truy vấn phép tính bộ
đơn giản có dạng
{t⏐P(t)}
trong đó: 
t là một biến bộ
P(t) là 1 công thức theo t.
P(t) định trị ĐÚNG hay SAI tùy thuộc 
vào giá trị của t 
8
Ví dụ
z Tìm ngày sinh và địa chỉ của nhân viên 
có tên là "Dinh Ba Tien“
{t.NGSINH, t.DCHI⏐ NHANVIEN(t) 
and t.HONV='Dinh' and 
t.TENLOT='Ba' and t.TENNV='Tien'}
9Ví dụ
z Tìm tất cả các nhân viên có lương trên 
30,000
{t⏐ NHANVIEN(t) and t.LUONG>30000}
Công thức này chỉ định rằng:
t là một biến bộ
quan hệ vùng của biến bộ t là NHANVIEN
Trị của biểu thức truy vấn này là các bộ t 
∈NHANVIEN thỏa t.LUONG>30000
10
Định nghĩa hình thức của phép tính bộ
z Một công thức truy vấn tổng quát có dạng
{t1.A1,t2.A2,…,tn.An⏐P(t1, t2,…,tn,tn+1,…,tn+m)}
trong đó: 
– t1,t2,…tm+n là các biến bộ và không nhất 
thiết phải giống nhau,
– Ai là một thuộc tính của quan hệ vùng của 
biến bộ ti. 
– P là 1 công thức. 
z Một công thức P(t1, t2, ...…, tn, tn+1, ...…, tn+m) 
được hình thành từ các công thức nguyên tố.
11
Công thức nguyên tố
Công thức nguyên tố được định nghĩa:
1. R(t) là công thức nguyên tố
R là một quan hệ và t là một biến bộ
2. ti.A θ tj.B là công thức nguyên tố
θ là phép so sánh (=, ≠,>, ≥, <,≤)
A là thuộc tính cuả quan hệ vùng của biến bộ ti
B là thuộc tính cuả quan hệ vùng của biến bộ tj
3. ti.A θ c hoặc c θ tj.B là các công thức nguên tố
c là trị hằng, θ là 1 phép so sánh (=, ≠,>, ≥, <,≤)
A là thuộc tính cuả quan hệ vùng của biến bộ ti
B là thuộc tính cuả quan hệ vùng của biến bộ tj
12
Công thức nguyên tố
z Ví dụ: dưới đây là các công thức nguyên 
tố:
– NHANVIEN (t) [theo (1)]
– r.MANV = s.MANV [theo (2)]
– t.LUONG > 3000 [theo (3)]
13
Công thức nguyên tố
zMỗi công thức nguyên tố định trị ĐÚNG 
hoặc SAI đối với 1 bộ cụ thể, được gọi là
giá trị chân lý của một công thức nguyên 
tố.
z Với công thức nguyên tố R(t), R là 1 
quan hệ và t là biến bộ trên R
– R(t) định trị ĐÚNG nếu t là một bộ
thuộc R
– R(t) định trị SAI nếu ngược lại 
14
Ví dụ
R A B C
a1 b1 c1
a2 b2 c2
Giả sử có 2 bộ
t1= 
t2=
⇒ R(t1) định trị ĐÚNG, 
R(t2) định trị SAI
Với các công thức nguyên tố dạng (2), 
(3), định trị tùy thuộc vào ý nghĩa của 
phép thay thế giá trị thật sự của bộ vào 
vị trí biến bộ.
15
Công thức
Công thức được ĐN:
1. Mọi công thức nguyên tố là công thức.
2. Nếu F1 và F2 là các công thức thì (F1 and 
F2), (F1 or F2), not(F1), not (F2) là công thức 
Giá trị chân lý của các công thức trên được 
ĐN:
– (F1 and F2) chỉ ĐÚNG nếu cả F1 lẫn F2 
đều ĐÚNG.
– (F1 or F2) chỉ SAI nếu cả F1 lẫn F2 đều 
SAI
– not(F1) là ĐÚNG nếu F1 là SAI, 
not(F1) là SAI nếu F1 là ĐÚNG.
– not(F2) là ĐÚNG nếu F2 là SAI, 
not(F2) là SAI nếu F2 là ĐÚNG.
16
Công thức
3. Nếu F là 1 công thức thì (∀t)(F) là một 
công thức. 
(∀t)(F) định trị ĐÚNG nếu F ĐÚNG với 
mọi bộ t, SAI nếu ít nhất một bộ SAI.
4. Nếu F là 1 công thức thì (∃t)(F) là một 
công thức. 
(∃t)(F) định trị SAI nếu F SAI với mọi 
bộ t, ĐÚNG nếu ít nhất một bộ ĐÚNG.
5. Nếu F là công thức thì (F) là công 
thức.
17
Biến tự do & Biến kết buộc
zNếu F là một công thức nguyên tố thì
mọi biến bộ t trong F đều là biến tự do.
z Tất cả các biến bộ tự do t trong F được 
xem là biến kết buộc trong công thức 
F'=(∃t)(F) hoặc F'=(∀t)(F).
zĐối với công thức F= F1 and F2 , F=F1 
or F2, F=not(F1) hoặc F=not(F2). Xuất 
hiện của biến t trong F là tự do hay kết 
buộc là hoàn toàn phụ thuộc vào việc 
nó là tự do hay kết buộc trong F1, F2.
18
Biến tự do & Biến kết buộc
z Biến tự do trong một công thức ⇔
biến toàn cục trong một chương trình 
(biểu diễn kết quả công thức - What).
z Biến kết buộc trong một công thức ⇔
biến cục bộ trong một chương trình 
(biểu diễn kiểm tra công thức –
Yes/No).
19
Ví dụ
z Tìm tên và địa chỉ của các nhân viên 
phòng "Nghien cuu“
z { t.HONV, t.TENNV, t.DCHI⏐
NHANVIEN(t) and (∃d)(PHONGBAN(d) 
and d.TENPHG='Nghien cuu' and 
d.MAPHG=t.SOPHG)}
20
Ví dụ
z Với mọi đề án ở "Ha Noi", liệt kê các mã số đề
án (MADA), mã số phòng ban chủ trì đề án 
(MAPHG), họ tên trưởng phòng (TENNV, 
HONV) cũng như địa chỉ (DCHI) và ngày sinh 
(NGSINH) của người ấy.
{p.MADA, p.PHONG. m.TENNV,m.HONV, 
m.NGSINH, m.DCHI ⏐ DEAN(p) and NHANVIEN(m) and p.DDIEM_DA='Ha Noi' and 
((∀d) (PHONGBAN(d) and p.PHONG=d.MAPHG and d.TPHG=m.MANV))}
p,m : biến tự do, d:biến kết buộc
21
Ví dụ
z Tìm họ tên của từng nhân viên và
người phụ trách trực tiếp nhân viên đó.
{e.HONV, e.TENNV, s.HONV, s.TENNV ⏐
NHANVIEN(e) and NHANVIEN(s) and 
e.MA_NQL = s.MANV}
22
Ví dụ
z Tìm họ tên các nhân viên làm việc cho 
các đề án mà phòng mã số 5 chủ trì.
{e.HONV, e.TENNV ⏐ NHANVIEN(e) and 
((∃ x)(∃ w) (DEAN(x) and 
PHANCONG(w) and x. PHONG=5 and 
w.MA_NVIEN=e.MANV and 
x.MADA=w.SODA))}
23
Một số biến đổi lượng từ
1. (∀ x)(P(x))≡ not (∃x)(not(P(x)))
2. (x)(P(x)) ≡ not(∀ x)(not (P(x)).
3. (∀ x)(P(x) and Q(x))≡ not (∃ x)(not(P(x)) or not (Q(x))).
4. (∀ x)(P(x) or Q(x))≡ not (∃ x)(not(P(x)) and not (Q(x))).
5. (∃ x)(P(x) or Q(x)) ≡ not(∀ x)(not(P(x)) and not (Q(x))).
6. (∃ x)(P(x) and Q(x)) ≡ not(∀ x)(not(P(x)) or not (Q(x))).
7. (∀ x)(P(x)) ⇒(∃ x)(P(x))
8. not(∃ x)(P(x)) ⇒ not(∀ x)(P(x))
Tuy nhiên, khẳng định sau SAI:
not(∀ x)(P(x)) ⇒ not(∃ x)(P(x))
24
Công thức an toàn
Xem câu truy vấn:
{t ⏐ not(NHANVIEN(t) )}
⇒ ý nghĩa: cho biết những nhân viên 
không có trong bảng NHANVIEN
⇒ câu truy vấn không xác định 
⇒ not(NHANVIEN(t)) là công thức 
không an toàn.
25
Ví dụ
zDanh sách những nhân viên (TENNV, 
HONV) không có thân nhân nào.
{ e.HONV, e.TENNV ⏐ NHANVIEN(e) 
and (not(∃d)( THANNHAN(d) and 
e.MANV=d.MA_NVIEN))}
{e.TENNV, e.HONV⏐ NHANVIEN(e) and 
(∀d)(not(THANNHAN(d) 
or ((∃d)(THANNHAN(d) and 
not(e.MANV=d.MA_NVIEN)))))}
26
Phép tính quan hệ có biến là miền
(Domain Relational Calculus- DRC)
27
Khái niệm
z Biến miền là biến nhận giá trị từ một miền 
giá trị của một thuộc tính.
z Một biểu thức truy vấn phép tính miền có
dạng
{x1,x2,…,xn⏐P(x1,x2,…,xn,xn+1,…, xn+m)}
hoặc
{x1x2… xn⏐P(x1,x2,…,xn,xn+1,…,xn+m)}
Trong đó x1,x2, …, xn, xn+1, …, xn+m là các 
biến miền và không nhất thiết phải khác 
nhau, nhận giá trị từ các MGT của các thuộc 
tính và P là công thức theo x1, ...…, xn.
28
Công thức
Một công thức được hình thành từ các công 
thức nguyên tố.
Công thức nguyên tố được ĐN
(i) R(x1,x2, ...…, xj) là một công thức nguyên tố.
Trong đó R là một quan hệ bậc j. 
Mỗi xi, 1≤ i ≤ n, là một biến miền. Công 
thức này ngụ ý rằng (x1,x2,…,xj) là một bộ
của quan hệ R
(ii) xi θ xj là công thức nguyên tố, xi và xj là các 
biến miền, c là một hằng trị, θ là 1 phép so 
sánh (=,≠,>,≥,<,≤).
29
Công thức
(iii) xi θ c hoặc c θ xj công thức nguyên tố, xi 
và xj là các biến miền, c là một hằng trị, θ là 1 
phép so sánh (=,≠,>,≥,<,≤).
Một công thức nguyên tố định trị ĐÚNG, hoặc 
SAI với một tập giá trị cụ thể tương ứng với 
các biến miền, được gọi là giá trị chân lý của 
một công thức nguyên tố.
Các ĐN về công thức dựa trên công thức 
nguyên tố, các ĐN về biến kết buộc và biến tự
do, các lượng từ trong trường hợp phép tính 
miền cũng tương tự như phép tính bộ.
30
Ví dụ
{uv⏐ (∃ q) (∃ r) (∃ s) 
(NHANVIEN(qrstuvwxyz) and q='Dinh' 
and r='Ba' and s='Tien')}
{uv⏐ (NHANVIEN('Dinh', 'Ba', 
'Tien',t,u,v,w,x,y,z)} 
31
Ví dụ
{qsv ⏐(∃z) (NHANVIEN(qrstuvwxyz) 
and (∃ l)(∃ m)(PHONGBAN(lmno) and 
l='Nghien cuu' and m=z)) }
{iksuv ⏐(∃ j)(DEAN(hijk) and (∃ t) 
(NHANVIEN(qrstuvwxyz) and 
(∃m)(∃n) (PHONGBAN(lmno) and k=m 
and n=t and j='Ha Noi')))}
32
Tài liệu tham khảo
1. Mai Văn Cường, Phạm Nguyễn Cương, Bài 
giảng Ngôn ngữ phép tính quan hệ.
2. Ramez Elmasri and Shamkant B. Navathe, 
Fundamentals of Database Systems, 
Chapter 6. Fourth Edition, Addison-Wesley, 
2004. ISBN 0-321-12226-7.
3. R. Ramakrishnan and J. Gehrke, Database 
Management Systems, Chapter4 -
Relational Algebra and Calculus, 
McGrawHill, 2nd Edition.
33
HẾT.