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

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 ()

- Đ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 .

Đ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”

- Đ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.

- Đ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.

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 Mⁿ

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 M²:

CHA = {(Tùng, Minh), (Long, Đoàn), (Đoàn,

Tuấn),(Minh, Long)}

ONG = {(Tùng, Long ), (Minh, Đoàn), (Long,

Tuấn) }

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 ) ?

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.

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ệ; t_ilà

các từ

ii. t1  a1, t2  a2: ở đây, t_ilà 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.

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)}

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}

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)}

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)

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ọ .

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.

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.

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.

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

F

E1 * E2  E2 * E1

E1 x E2  E2 x E1

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 )

F1

F2

F1

(E1 * E2) * E3

 E1 *( E2 * E3 )

(E1 x E2) x E3  E1 x ( E2 x E3 )