Bài giảng - Bài 6: Ngôn ngữ tân từ

Bài 6: Ngôn ng tân t

ữ

ừ

Khoa HTTT - Đ i h c CNTT

ạ ọ

N i dung

ộ

i c a m t công th c ứ ng giá công th c ứ

i thi u 1. Gi ệ ớ 2. Cú pháp 3. Các đ nh nghĩa ị 4. Di n gi ễ ả ủ 5. Quy t c l ắ ượ 6. Ngôn ng tân t ữ 7. Ngôn ng tân t ữ

ừ ừ

có bi n là n b ộ ế có bi n là mi n giá tr ề ế

ị

2 Khoa HTTT - Đ i h c CNTT ạ ọ

1. Gi

ớ

i thi u ệ

ứ

ữ

ừ

 Ngôn ng tân t ị

ượ ộ ố

ữ ư

ể

ư ế

là ngôn ng truy v n hình th c do Codd ấ c Lacroit, Proix và Ullman phát đ ngh (1972-1973) đ ề tri n, cài đ t trong m t s ngôn ng nh QBE, ALPHA.. ặ ể  Đ c đi m: ặ  Ngôn ng phi th t c ủ ụ ữ  Rút trích cái gì ch không ph i rút trích nh th nào ứ ng v i đ i s quan h ng đ  Kh năng di n đ t t ệ ạ ươ

 Có hai lo iạ :

 Có bi n là n b ộ ế  Có bi n là mi n giá tr ị ề ế

ớ ạ ố ả ươ ễ ả

3 Khoa HTTT - Đ i h c CNTT ạ ọ

2. Cú pháp

: x,y,z,t,s… : a,b,c,…

 ( ) : bi u th c trong ngo c ặ ứ ể  Bi nế : dùng ch th cu i b ký t ở ố ộ  H ngằ : dùng ch th đ u b ký t ộ  Hàm: là m t ánh x t ề ự ự ị

ng dùng ch th ậ ng ng ữ ườ ng ữ ườ ở ầ m t mi n giá tr vào t p h p g m 2 ạ ừ ộ ữ ườ ườ ợ ồ gi a b ở ữ ộ ặ

ộ giá tr : đúng ho c sai. Th ký t

ứ ượ ể

ữ ứ ự ở ữ ộ

c xây d ng d a trên bi u ể ự P,Q,R… gi a b ký t ự (cid:216) ), kéo theo ((cid:222) ), và ((cid:217) ), ị : h,g,f,… ự  Tân từ: là m t bi u th c đ ộ th c logic. Dùng ch in hoa  Các phép toán logic: ph đ nh ( ủ ị

 Các l ng t i ( ho c (ặ (cid:218) ). ượ ọ " ừ: v i m i (

), t n t ớ Khoa HTTT - Đ i h c CNTT 4 ồ ạ $ ) ạ ọ

3. Các đ nh nghĩa (1)

ị

1 ngôi

ị  Tân t

ừ c đ nh nghĩa trên t p X và bi n x có giá tr ị ế ậ

1 ngôi đ ch y trên các ph n t c a X.

 Đ nh nghĩa 1: Tân t ừ ượ ị ầ ử ủ

P(x) là m t m nh đ logic, t c là ừ ỗ ứ ệ ề ộ ạ ớ

 V i m i giá tr c a x, tân t ặ ị

 Ví dụ

ộ

ế

ừ

N (x) đ

ệ ượ

i nườ ữ”. Khi đó ả

ừ Ữ ề Ữ

x là ng ế

 P(x), x là bi n ch y trên X, là m t tân t ạ  P(gt), gt˛ X là m t m nh đ , X = {Nguyen Van A, Tran Thi B} ề ộ c xác đ nh: “  V i tân t ị ớ  M nh đ N (Nguyen Van A): cho k t qu Sai ệ  N (Tran Thi B): cho k t qu Đúng ế Ữ

ả

ị ủ nó có giá tr đúng (Đ) ho c sai (S)

5 Khoa HTTT - Đ i h c CNTT ạ ọ

3. Các đ nh nghĩa (2)

ị

n ngôi

ị  Tân t

n ngôi đ ừ

ậ ậ ị

 Đ nh nghĩa 2: Tân t ừ 1, X2, …, Xn và c đ nh nghĩa trên các t p X ượ ị ng ng. i t n bi n xế 1, x2, …, xn l y giá tr trên các t p X ươ ứ ấ n ngôi là m t m nh đ . ề ộ

 V i m i giá tr a ỗ i

 Ký hi u: P(x ệ

1, x2, …, xn)  Ví d : ụ CHA(x1,x2): “x1 là CHA c a xủ 2”  Chú ý:

t ph i là r i nhau

ế

ấ

ả

ờ

n-1 ngôi

ừ

 Các Xi không nh t thi  V i xớ i=ai, P(x1, x2, …, ai, …, xn) là tân t

ệ ớ ị ˛ Xi, xi=ai.Tân t ừ

6 Khoa HTTT - Đ i h c CNTT ạ ọ

3. Các đ nh nghĩa (3)

ị

 Đ nh nghĩa 3: T

ừ

ố

(cid:216) F1

 N u Fế  N u Fế

" ứ ộ ứ ể F1=>F2, :F1, $ x:F1 cũng là các công th cứ

ị  T là m t h ng hay là m t bi n ừ ế ộ ằ ộ  N u f(t 1, t2, …, tn) là hàm n ngôi thì f là m t tộ ừ ế  Đ nh nghĩa 4: Công th c ị ứ  Công th c nguyên t : P(t 1, t2, …, tn), ti là các từ ứ 1, F2 là các công th c thì các bi u th c sau cũng là các  N u Fế ứ (cid:217) F2, (cid:218) F2, công th c: F F1 ứ 1 1 là m t công th c thì 1 là công th c thì (F ứ

1) cũng là m t công th c ứ ộ

7 Khoa HTTT - Đ i h c CNTT ạ ọ

3. Các đ nh nghĩa (4)

ị

 Đ nh nghĩa 4:

ị  Công th c ứ đóng là công th c n u m i bi n đ u có kèm

ế ề ọ

ng t v i l ớ ượ ừ ẳ

i 1 bi n không kèm ứ ế . (kh ng đ nh Đ, S) ị  Công th c ứ mở là công th c t n t ứ ồ ạ ế

ng t . (tìm ki m thông tin) ừ ế

l ượ  Ví d : ụ  C1:" x$

đóng vì các bi n x,y,z,t đ u có kèm l ng t ,$ ề ừ "

t" y(P(x,y,a)(cid:222) ế t (P(x,y,a)(cid:222) ứ

 C2:" x $ ế

vì bi n y không có l ng t ,$ $ z(Q(y,z,t)(cid:217) R(x,t)) là công th c ứ ượ $ z(Q(y,z,t)(cid:217) R(x,t)) là công th c m ở ượ ừ "

8 Khoa HTTT - Đ i h c CNTT ạ ọ

4. Di n gi ễ

i c a m t công ộ ả ủ th cứ

ồ

ầ

G m 4 ph n:  Mi n giá tr c a các bi n c a công th c (ký

ứ

ế ủ

ị ủ hi u là t p M)

ậ

(ý nghĩa tân

ừ

 S d ng các h ng, các tân t c quan h n ngôi) ệ

ằ ượ

ề ệ ử ụ , xác đ nh đ ị ừ  Ý nghĩa c a công th c ứ ủ  Xác đ nh 1 quan h n ngôi trên t p M ệ

ậ

ị

9 Khoa HTTT - Đ i h c CNTT ạ ọ

5. Quy t c l

ắ ượ

ng giá công th c ứ

 L

b c n: P(x

ừ ậ

1,x2,…xn) và liên

: xét tân t k t v i quan h R, n ngôi.

ng giá tân t ừ ệ

ượ ế ớ

dùng b ng chân tr ả

ị

ượ

ứ $ x F(x) là đúng

(a1,a2,…,an) ˛ R (a1,a2,…,an) ˇ R ,(cid:222)

 L

ượ

˛ M/F(ai):Đ

: x là bi n, ế " x F(x): Đ v i ớ " ˛ M Khoa HTTT - Đ i h c CNTT 10

˛ M (cid:218) F(ai), ai

ạ ọ P(a1,a2,…,an): Đ (cid:219) P(a1,a2,…,an): S (cid:219)  Các phép toán (cid:217) ,(cid:218) ,(cid:216) ừ $  L : g i x là bi n. Công th c ng t ế ọ ˛ M/F(ai):Đ khi có ít nh t m t a ộ i ấ M={a1,a2,…,an} ” ừ " ng t M={a1,a2,…,an} ” (cid:217) F(ai), ai

6. Ngôn ng tân t

ữ

ừ

có bi n là n b ế

ộ

6.1 Qui t cắ 6.2 Đ nh nghĩa ị 6.3 Công th c an toàn 6.4 Bi u di n các phép toán

ứ ễ

ể

11 Khoa HTTT - Đ i h c CNTT ạ ọ

6.1 Quy t c (1)

ắ

ộ ủ ế

1. Bi n là 1 b c a quan h ệ 2. T : h ng, bi n ho c bi u th c có d ng s[C], s: ể

ặ

ạ

ệ ượ

ứ ủ

ậ chi u. ế

ừ

ế ừ ằ bi n, C: t p các thu c tính c a quan h đ ộ ế g i là t ọ 3. Công th c: ứ

 Rs (R là quan h , s là bi n) đ

ệ ừ . Mi n giá ề



ế ế

q q ừ

q t2 ở là toán t chi u, còn a là m t ộ c g i là công th c đây t ử c g i là t ượ ọ ủ ế ượ ọ ứ

tr s đ nh nghĩa mi n bi n thiên c a s. ề ị ẽ ị 1,t2 là các t a , t1 t1 h ng, ằ so sánh d nguyên tố

12 Khoa HTTT - Đ i h c CNTT ạ ọ

6.1 Quy t c (2)

ắ

ứ

ố là m t công th c ứ ộ (cid:222) F2, (cid:217) F2, F1 (cid:218) F2, F1

4. M t ộ công th c nguyên t 5. F1 và F2 là công th c: Fứ (cid:216) F1 là công th cứ

6. F là công th c , s là bi n

ứ

ế $ sF, " sF là công

th cứ

7. F là công th c, (F) là công th c ứ

ứ

13 Khoa HTTT - Đ i h c CNTT ạ ọ

6.2 Đ nh nghĩa

ị

có bi n

ộ

ừ

ỏ ộ ượ

ế ữ c bi u di n nh sau: {s | F} . ư ứ

ộ

 M t câu h i trong ngôn ng tân t là n b đ ễ ể Trong đó s là bi n n b , F là m t công th c ộ ế ch có m t bi n t do là s. ế ự ộ

ỉ

 Ví dụ: BIENGIOI(nuoc,tinhtp). Phép toán

ệ

ể

có bi n

ỏ

c chuy n ừ

ế

quan h BIENGIOI[nuoc] đ ượ thành câu h i trong ngôn ng tân t ữ là b : {s[nuoc] BIENGIOI s}

ộ

14 Khoa HTTT - Đ i h c CNTT ạ ọ

6.3 Công th c an toàn

ứ

ề ả

n u nó tho mãn 3 đi u ki n sau: ệ ế ầ ủ ọ

ầ ử ủ

DOM

(

)

(

˛ ﬁ

F là công th c an toàn: ứ i) N u s là b n th a: F(s) là đúng thì m i thành ph n c a s ỏ ộ ế c a DOM(F): là ph n t sF Đúng :

ii) F’ là công th c con c a F:

˛ ﬁ $ ủ Đúng ứ sF s DOM F )'(

DOM

F )'(

sFs ,' :'

ˇ ﬁ " iii) sFs ,' :' Đúng

15 Khoa HTTT - Đ i h c CNTT ạ ọ

ể

ễ

6.4 Bi u di n các phép toán (1)

 1. Phép h iộ

1, Q2

ệ ứ ứ

 Q1,Q2 là các quan h n chi u ề  F1, F2 là các công th c ng v i Q ớ  Công th c c a Q= Q 1 (cid:218) F2s  Fs=F1s  2. Phép trừ

1, Q2

ứ ủ ¨ Q2

ệ ứ ứ 1-Q2

 Q1,Q2 là các quan h n chi u ề  F1, F2 là các công th c ng v i Q ớ  Công th c c a Q= Q ứ ủ F2s  Fs=F1

(cid:217) (cid:216) 16 Khoa HTTT - Đ i h c CNTT ạ ọ

ể

ễ

6.4 Bi u di n các phép toán (2)

 3. Phép tích

ớ

1, Q2

 Q1(x1,…,xm), Q2(y1,…,yn)  F1, F2 là các công th c ng v i Q ứ ứ  Công th c c a Q= Q

ứ ủ

1 x Q2

p) (F1v

Fs: s(x1,…,xm, y1,…,yn) (cid:217) (cid:217) F2p Fs=($ v) ($ s1=v1 (cid:217) …sm=vm (cid:217) sm+1=p1 (cid:217) … sm+n=pn)

17 Khoa HTTT - Đ i h c CNTT ạ ọ

ể

ễ

6.4 Bi u di n các phép toán (3)

 4. Phép chi uế

 Q1(x1,…,xn), F1 là các công th c ng v i Q  Công th c c a Q= Q

1 [xi1, xi2,…,xik]

ứ ứ ớ

(cid:217) s1=vi1 (cid:217) s2=vi2 (cid:217) … sk=vik)

 Q1 là quan h n chi u, F  Công th c Q=Q

ứ ủ Fs=($ v) (F1v  5. Phép ch nọ ệ ề ớ

1:đi u ki n ĐK (ĐK:x

q a) ề

1 là công th c ng v i Q ứ ứ ệ (cid:217) si

a (1£

sj ho c Fặ

q q q xj ho c xặ i n, i„ j) i, j £ Fs=F1s ứ (cid:217) si

18 Khoa HTTT - Đ i h c CNTT ạ ọ

7. Ngôn ng tân t

ữ

ế

ề

có bi n là mi n giá ừ trị

7.1 Quy t cắ 7.2 Bi u di n câu h i ỏ ễ ể 7.3 Công th c an toàn ứ 7.4 Bi u di n các phép toán ễ

ể

19 Khoa HTTT - Đ i h c CNTT ạ ọ

7.1 Quy t cắ

ặ

ừ



1. T : là h ng ho c bi n ế ằ 2. Công th c nguyên t ố ứ  Q(t1,t2,…,tn): ti là các t ừ

q q q tj ,ti ti

3. M t ộ công th c nguyên t 4. F1 và F2 là công th c: Fứ

a v i tớ i là t ứ

(cid:222) F2, (cid:216) F1 là công

th cứ

5. F là công th c , t:bi n t

do,

$ sF," sF cũng công

ế ự

ứ

th cứ

, Q là quan h ệ ừ , a là m t h ng, là phép toán ộ ằ ố là m t công th c ứ ộ (cid:217) F2, F1 (cid:218) F2, F1

6. F là công th c, (F) là công th c ứ ứ ạ ọ

20 Khoa HTTT - Đ i h c CNTT

7.2 Bi u di n câu h i ỏ ễ

ể

{(x1,x2,…,xn) | F(x1,x2,…,xn)}  xi là các bi n t do c a F ế ự ủ  Q= {(x1,x2,…,xn) | F(x1,x2,…,xn)} nên (x1,x2, F(x1,x2,…,xn):Đúng

…,xn)˛ Q (cid:222)

21 Khoa HTTT - Đ i h c CNTT ạ ọ

7.3 Công th c an toàn

ứ

ả ề

n u nó tho mãn 3 đi u ki n sau: ệ ế ầ ủ ọ

= ,...,1,)

DOM

(

x i

˛ ﬁ

ii) F’ là công th c con c a F: F là công th c an toàn: ứ i) N u s là b n th a: F(s) là đúng thì m i thành ph n c a s ỏ ộ ế c a DOM(F): là ph n t ầ ử ủ ( ( xF ,..., :) ) nx Đúng 1 ứ ủ

˛ ﬁ $ xF :' Đúng x DOM F )'(

(

DOM

ˇ $ ﬁ " iii)

DOM

Đúng

)

(

= ,...,1,)( iF

( xF ,..., 1

Đúng :) nx x i Khoa HTTT - Đ i h c CNTT 22

ˇ $ ﬁ