Bài giảng Cơ sở dữ liệu - Bài 9: Ngôn ngữ tân từ - Vũ Văn Định

BÀI 9. NGÔN NGỮ TÂN TỪ
I. Logic toán và ứng dụng của nó vào CSDL.
 ĐN1 : Biểu thức logic là một phát biểu mà giá
trị của nó có thể đúng hoặc sai. Biểu thức logic có
giá trị luôn luôn đúng ( hoặc sai ) được gọi là
hằng đúng hoặc hàng sai. 
1. Một số khái niệm :
- Hàm: là một ánh xạ từ một miền giá trị vào tập
hợp gồm hai giá trị hoặc đúng hoặc sai, thường kí
hiệu là f,g,h
- Tân từ : Là một biểu thức được xây dựng dựa
trên các biểu thức logic, thường kí hiệu P,Q,R
- Các phép toán logic : phủ định (¬ ), kéo theo
(=>), nối liền (), nối rời ( v )
- Các lượng từ : với mọi () và tồn tại ()
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
- ĐN2 : Tân từ một ngôi được định nghĩa
trên 1 tập X và một biến x có giá trị
chạy trên các phần tử của X. 
Với mỗi giá trị của x, tân từ P(x) là một
mệnh đề logic, tức là nó có giá trị hoặc
là đúng hoặc là sai.
VD: X là một tập hợp những người có tên
như sau : 
X={ Hoa , Lan, Tuấn, Dũng, T.Anh,}
Với tân từ NỮ (x) được xác dịnh như : “ x 
là người nữ”. Khi đó mệnh đề : 
NỮ ( Hoa) : cho kết quả là đúng.
NỮ ( Tuấn ) : Cho kết quả là sai .
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
ĐN3: Tân từ n ngôi được định nghĩa
trên các tập X1, X2,Xn và n biến
x1, x2, , xn lấy giá trị trên các tập
Xi tương ứng. Với mỗi ai Xi, xi = ai
, tân từ n ngôi là một mệnh đề.
Kí hiệu : P ( x1, x2, , xn)
VD: CHA ( x1, x2 ) : “ x1 là cha của
x2”
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
- ĐN4: Từ đựợc định nghĩa một cách truy hồi như
sau :
i. Từ là một hằng hay một biến
ii. f (t1,t2,,tn) là một hàm n ngôi thì f là một từ.
- ĐN5: Công thức : 
i. Công thức nguyên tố là một tân từ n ngôi
P(t1,t2,.., tn) , trong đó t1, t2,.., tn là các từ.
ii. Nếu F1, F2, .. ,Fn là các công thức thì các biểu
thức sau: F1 v F2 , F1  F2 , F1 => f2, ¬ F1 
cũng là các công thức.
iii. Nếu F1 là công thức thì x: F1, x: F1 cũng là
các công thức.
iv. Nếu F1 là công thức thì ( F1) cũng là công thức.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
- ĐN6:
- Một công thức được gọi là “đóng”
nếu mọi biến của nó đều có kèm với
lượng từ.
- Một công thức được gọi là “mở” nếu
tồn tại một biến không có kèm với
lượng từ. Biến này gọi là biến tự do. 
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
2. Diễn giải và mô hình.
a. Diễn giải của một công thức:
- Một diễn giải của một CT gồm 4 phần
: 
* Miền giá trị của các biến công thức, 
KH là tập M.
* Việc sử dụng công thức: hằng , hàm
, tân từ. 
* Ý nghĩa của công thức
* Xác định một quan hệ n ngôi trên
tập Mn
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
VD: Cho M = {Tùng, Minh , Hưng, Long, Đoàn, 
Tuấn} và một CT C có dạng như sau : 
x  y (z (P(x,y) v P(y,z) => Q (x,z) )
Tập diễn giải của công thức có thể là :
- M : miền giá trị của các biến x, y, z
- Các tân từ : P: CHA ; Q: ONG
- Ý nghĩa : 
* CHA (x, y): x có cha là y
* ONG (x, y): x có ông là y.
- Các quan hệ 2 ngôi trên M2 :
CHA = {(Tùng, Minh), (Long, Đoàn), (Đoàn, 
Tuấn),(Minh, Long)}
ONG = {(Tùng, Long ), (Minh, Đoàn), (Long, 
Tuấn) }
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
II. Ứng dụng logic toán trong CSDL
1. Dẫn nhập
CSDL : mô hình hoá thông tin gồm các sự kiện đựơc
liên kết hay biểu diễn một tình trạng của thế giới
thực.
Chú ý : 
i. Câu hỏi đóng tương ứng với CT đóng. Câu trả
lời là có hiệu lực đúng hoặc sai.
VD: Tùng có cha là Minh? CHA ( Tùng, Minh)?
Con của Long là ai? x CON (Minh, x) ?
ii. Câu hỏi mở tương ứng với một CT mở.
VD: Cha của Long là ai ? CHA(Long, x ) ?
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
2. Ngôn ngữ tân từ có biến là bộ -n
Một câu hỏi trong ngôn ngữ tân từ có biến là bộ -n thoả
các quy tắc sau :
a. Biến: là một bộ của quan hệ
b. Từ : là hằng, biến, hay biểu thức có dạng s[c] trong
đó : s là biến, c là tập các thuộc tính ( gọi là từ
chiếu)
c. Các biểu thức: 
- R s : với R là một quan hệ; s là biến bộ-n được
gọi là từ
- t1  a, t1  t2: ở đây, t1, t2 là các từ chiếu,  là
toán tử so sánh, a là một hằng.
ĐN7: Một câu hỏi trong ngôn ngữ tân từ có biến là bộ -n 
đựơc biểu diễn như sau :
{ s | F }
Trong đó s là biến bộ-n, F là một công thức chỉ có
một biến tự do là s.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
2. Ngôn ngữ tân từ có biến là miền giá trị
Một câu hỏi trong ngôn ngữ tân từ có biến là bộ -n thoả
các quy tắc sau :
a. Từ : là hằng hoặc biến.
b. Công thức nguyên tố:
i. Q (t1, t2,..,tn) : với Q là một quan hệ; ti là
các từ
ii. t1  a1, t2  a2: ở đây, ti là các từ , là phép
toán
c. Trong 1 CSDL, câu hỏi bằng ngôn ngữ tân từ có dạng
:
{ ( x1, x2,, xk) | F ( x1, x2, , xk) }
Ở đây xi (i= 1,2,..,k) là các biến tự do của F và F 
không có biến tự do nào khác.
Câu trả lời là tập các bộ giá trị (x1, x2, .., xk ) mà
khi thay vào F thì F là đúng.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
VD: Xét cơ sở dữ liệu Thực tập gồm 3 quan hệ sau
đây:
SV( SV#, HT, NS, QUE, HL)
DT(DT#, TDT, CN, KP)
SD(SV#, DT#, NTT, KM, KQ)
Q1: Cho danh sách các sinh viên có quê Hà Nội và có
điểm học lực >=8.0?
- Diễn tả bằng ngôn ngữ tân từ có biến là bộ như
sau:
{ r[HT] | SV r  r[QUE=‘Hà Nội’]  r[HL]>=8.0}
Và bằng ngôn ngữ tân từ có biến là miền giá trị như
sau: 
{n | x y z ( SV (n, x, y, ‘Hà Nội’, z)  z 
>=8.0)}
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Q2: Cho biết tên các sinh viên nam
quê Hải Phòng có điểm học lực >8?
- Diễn tả bằng ngôn ngữ tân từ có biến
là bộ như sau:
{ r[HT] | SV r  r[GT]=‘Nam’ 
r[QUE] = ‘Hải Phòng’  r[HL]>=8}
- Và bằng ngôn ngữ tân từ có biến là
miền giá trị như sau: 
{n | x t z ( SV (n, x, y, 
‘Nam’,’Hải Phòng’, z)  z > 8}
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Q3: Cho danh sách các sinh viên có
điểm thực tập =10?
- Diễn tả bằng ngôn ngữ tân từ có
biến là bộ như sau:
{ r[HT] | p ( SV q  SD p 
q[SV#]=pSV[#]  p[KQ]=9.0}
- Và bằng ngôn ngữ tân từ có biến là
miền giá trị như sau: 
{y | z t w a b c ( SV (x, y, 
z, t, w)  SD(x, a, b, c, 10)}
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
BTVN: Cho quan hệ Thực tập như trên, hãy viết
các câu truy vấn sau bằng ngôn ngữ tân từ
có biến là bộ -n và có biến là miền giá trị ? 
1. Cho thông tin về những sinh viên sinh
trước năm 1985 có quê ở Hà Nội?
2. Cho biết các địa điểm thực tập xa trường
(KM >100) của đề tài số 5?
3. Cho biết mã của những đề tài có kinh phí
lớn hơn 1 triệu và nhỏ hơn 2 triệu?
4. Cho biết mã của sinh viên dưới 20 tuổi, 
thực tập khá ( có điểm kết quả thực tập
>=6.5)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Bài 9. Tối ưu hoá câu hỏi
Nói chung, các ngôn ngữ bậc cao ( ngôn ngữ
con dữ liệu ) đòi hỏi thực hiện trong máy đều rất tốn
kém thời gian. Do vậy, trước khi thực hiện các câu
hỏi thuộc các ngôn ngữ đó cần thiết phải biến đổi
hợp lý để giảm thời gian tính toán. Việc làm đó gọi
là "tối ưu hoá ".
Ví dụ : Thực hiện câu truy vấn : Cho biết các
thông tin cá nhân và việc thực tập của những sinh
viên có điểm thực tập >=8. Ta nên chọn ra những sv
có điểm thực tập >=8 trong quan hệ SD rồi mới đem
kết nối với quan hệ SV để lấy ra nhứng thông tin các
nhân của họ .
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
I. Các chiến lược tối ưu tổng quát
1. Thực hiện phép chọn sớm như có thể
Biến đổi câu hỏi để đưa phép chọn vào thực hiện
trước nhằm làm giảm bớt kích cỡ của kết quả trung gian
và do vậy chi phí phải trả giá cho việc truy nhập bộ nhớ
thứ cấp cũng như lưu trữ của bộ nhớ chính sẽ nhỏ đi.
2. Tổ hợp những phép chọn xác định với phép tích
Đề - Các thành phép kết nối.
Nếu kết quả của tích Đề - Các R x S là đối số của
phép chọn và phép chọn liên quan tới các phép so sánh
giữa các thuộc tính của R và S thì thay phép tích Đề -
Các bằng phép kết nối.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3. Tổ hợp dãy các phép tính một ngôi như các phép
chọn và phép chiếu.
Một dãy các phép một ngôi ( như phép chọn hoặc
phép chiếu) mà kết quả của chúng phụ thuộc vào các
bộ của một quan hệ độc lập thì có thể nhóm các phép
đó lại.
4. Tìm các biểu thức con chung trong một biểu thức
Nếu kết quả của một biểu thức con chung ( biểu
thức xuất hiện hơn một lần) là một quan hệ không lớn
và nó có thể được đọc từ bộ nhớ thứ cấp với ít thời
gian hơn thì nên tính toán trước biểu thức đó chỉ một
lần.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
5. Xử lý các tệp trước
Đối với các tệp số, có hai vấn đề quan trọng cần được
xử lý trước là sắp xếp trước các tệp và thiết lập các tệp
chỉ số.
6. Đánh giá trước khi thực hiện tính toán .
Cần tính toán chi phí thực hiện các phép tính để có
được trình tự thực hiện các phép tính một cách tốt nhất. 
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
II. Biểu thức tương đương
Hai biểu thức E1 và E2 gọi là tương đương ( viết tắt
là ( E1  E 2 ) nếu chúng biểu diễn cùng một ánh xạ, 
nghĩa là nếu thay thế cùng các quan hệ cho tên các lược đồ
tương ứng ở hai biểu thức cho ra cùng một kết quả.
III. Các quy tắc liên quan tới phép kết nối và
phép tích Đề- Các
L1. Quy tắc giao hoán của phép kết nối và phép
tích Đề-Các
Nếu E1 và E2 là hai biểu thức quan hệ, F là điều
kiện trên các thuộc tính của E1 và E2 thì : 
E1  E2  E2  E1 
E1 * E2  E2 * E1
E1 x E2  E2 x E1
F F
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
L2. Quy tắc kết hợp của phép kết nối và
phép tích Đề- Các
Nếu E1, E2 và E3 là các biểu thức quan hệ, F1, F2 
là điều kiện thì : 
(E1  E2 )  E3  E1  (E2  E3 )
(E1 * E2) * E3  E1 *( E2 * E3 )
(E1 x E2) x E3  E1 x ( E2 x E3 ) 
F1 F2 F1 F2
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí