thienthannho_vn2009
New Member
Download miễn phí Bài giảng Ngôn ngữ tân từ
Một câu hỏi trong ngôn ngữ tân từ có biến là
n bộ được biểu diễn như sau: {s | F} . 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
quan hệ BIENGIOI[nuoc] được chuyển
thành câu hỏi trong ngôn ngữ tân từ có biến
là bộ: {s[nuoc] BIENGIOI s}
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Khoa HTTT - Đại họcCNTT 1
Bài 6: Ngôn ngữ tân từ
Khoa HTTT - Đại học CNTT 2
Nội dung
1. Giới thiệu
2. Cú pháp
3. Các định nghĩa
4. Diễn giải của một công thức
5. Quy tắc lượng giá công thức
6. Ngôn ngữ tân từ có biến là n bộ
7. Ngôn ngữ tân từ có biến là miền giá trị
Khoa HTTT - Đại học CNTT 3
1. Giới thiệu
Ngôn ngữ tân từ là ngôn ngữ truy vấn hình thức do Codd
đề nghị (1972-1973) được Lacroit, Proix và Ullman phát
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
Khả năng diễn đạt tương đương với đại số quan hệ
Có hai loại:
Có biến là n bộ
Có biến là miền giá trị
Khoa HTTT - Đại học CNTT 4
2. Cú pháp
( ) : biểu thức trong ngoặc
Biến: dùng chữ thường ở cuối bộ ký tự: x,y,z,t,s…
Hằng: dùng chữ thường ở đầu bộ ký tự: a,b,c,…
Hàm: là một ánh xạ từ một miền giá trị vào tập hợp gồm 2
giá trị: đúng hay sai. Thường dùng chữ thường ở giữa bộ
ký tự: h,g,f,…
Tân từ: là một biểu thức được xây dựng dựa trên biểu thức
logic. Dùng chữ in hoa ở giữa bộ ký tự P,Q,R…
Các phép toán logic: phủ định (¬), kéo theo (⇒), và (∧),
hay (∨).
Các lượng từ: với mọi (∀), tồn tại (∃)
Khoa HTTT - Đại học CNTT 5
3. Các định nghĩa (1)
Định nghĩa 1: Tân từ 1 ngôi
Tân từ 1 ngôi được định nghĩa trên tập X và 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ị đúng (Đ) hay sai (S)
Ví dụ
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}
Với tân từ NỮ(x) được xác định: “x là người nữ”. Khi đó
Mệnh đề NỮ(Nguyen Van A): cho kết quả Sai
NỮ(Tran Thi B): cho kết quả Đúng
Khoa HTTT - Đại học CNTT 6
3. Các định nghĩa (2)
Định nghĩa 2: Tân từ n ngôi
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 giá trị ai∈Xi, xi=ai.Tân từ n ngôi là một mệnh đề.
Ký hiệu: P(x1, x2, …, xn)
Ví dụ: CHA(x1,x2): “x1 là CHA của x2”
Chú ý:
Các Xi không nhất thiết phải là rời nhau
Với xi=ai, P(x1, x2, …, ai, …, xn) là tân từ n-1 ngôi
Khoa HTTT - Đại học CNTT 7
3. Các định nghĩa (3)
Định nghĩa 3: Từ
Từ là một hằng hay là một biến
Nếu f(t1, 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(t1, t2, …, tn), ti là các từ
Nếu F1, F2 là các công thức thì các biểu thức sau cũng là các
công thức: F1∨F2, F1∧F2, F1=>F2, ¬F1
Nếu F1 là một công thức thì ∀:F1, ∃x:F1 cũng là các công thức
Nếu F1 là công thức thì (F1) cũng là một công thức
Khoa HTTT - Đại học CNTT 8
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
với lượng từ. (khẳng định Đ, S)
Công thức mở là công thức tồn tại 1 biến không kèm
lượng từ. (tìm kiếm thông tin)
Ví dụ:
C1:∀x∃t∀y(P(x,y,a)⇒ ∃z(Q(y,z,t)∧R(x,t)) là công thức
đóng vì các biến x,y,z,t đều có kèm lượng từ ∀,∃
C2:∀x ∃t (P(x,y,a)⇒ ∃z(Q(y,z,t)∧R(x,t)) là công thức mở
vì biến y không có lượng từ ∀,∃
Khoa HTTT - Đại học CNTT 9
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)
Sử dụng các hằng, các tân từ (ý nghĩa tân từ,
xác định được quan hệ n ngôi)
Ý nghĩa của công thức
Xác định 1 quan hệ n ngôi trên tập Mn
Khoa HTTT - Đại học CNTT 10
5. Quy tắc lượng giá công thức
Lượng giá tân từ: xét tân từ bậc n: P(x1,x2,…xn) và liên
kết với quan hệ R, n ngôi.
P(a1,a2,…,an): Đ ⇔ (a1,a2,…,an) ∈R
P(a1,a2,…,an): S ⇔ (a1,a2,…,an) ∉R
Các phép toán ∧,∨,¬,⇒ dùng bảng chân trị
Lượng từ ∃: gọi x là biến. Công thức ∃x F(x) là đúng
khi có ít nhất một ai∈M/F(ai):Đ
M={a1,a2,…,an} ≡∨F(ai), ai∈M
Lượng từ ∀: x là biến, ∀x F(x): Đ với ∀ ai∈M/F(ai):Đ
M={a1,a2,…,an} ≡∧F(ai), ai∈M
Khoa HTTT - Đại học CNTT 11
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
Khoa HTTT - Đại học CNTT 12
6.1 Quy tắc (1)
1. Biến là 1 bộ của quan hệ
2. Từ: hằng, biến hay biểu thức có dạng s[C], s:
biến, C: tập các thuộc tính của quan hệ được gọi
là từ chiếu.
3. Công thức:
Rs (R là quan hệ, s là biến) được gọi là từ. Miền giá trị
sẽ định nghĩa miền biến thiên của s.
t1θ a , t1θ t2 ở đây t1,t2 là các từ chiếu, còn a là một
hằng, θ là toán tử so sánh dược gọi là công thức
nguyên tố
Khoa HTTT - Đại học CNTT 13
6.1 Quy tắc (2)
4. Một công thức nguyên tố là một công thức
5. F1 và F2 là công thức: F1∨F2, F1∧F2,
F1⇒F2, ¬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
Khoa HTTT - Đại học CNTT 14
6.2 Định nghĩa
Một câu hỏi trong ngôn ngữ tân từ có biến là
n bộ được biểu diễn như sau: {s | F} . 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
quan hệ BIENGIOI[nuoc] được chuyển
thành câu hỏi trong ngôn ngữ tân từ có biến
là bộ: {s[nuoc] BIENGIOI s}
Khoa HTTT - Đại học CNTT 15
F là công thức an toàn: nếu nó thoả mãn 3 điều kiện sau:
i) Nếu s là bộ n thỏa: F(s) là đúng thì mọi thành phần của s
là phần tử của DOM(F):
ii) F’ là công thức con của F:
iii)
6.3 Công thức an toàn
)()
FDOMsĐúngsF ∈→)'
',' FDOMsĐúngsFssF ∈→∃)'
',' FDOMsĐúngsFssF ∉→∀Khoa HTTT - Đại học CNTT 16
6.4 Biểu diễn các phép toán (1)
1. Phép hội
Q1,Q2 là các quan hệ n chiều
F1, F2 là các công thức ứng với Q1, Q2
Công thức của Q= Q1∪Q2
Fs=F1s∨F2s
2. Phép trừ
Q1,Q2 là các quan hệ n chiều
F1, F2 là các công thức ứng với Q1, Q2
Công thức của Q= Q1-Q2
Fs=F1∧¬F2s
Khoa HTTT - Đại học CNTT 17
6.4 Biểu diễn các phép toán (2)
3. Phép tích
Q1(x1,…,xm), Q2(y1,…,yn)
F1, F2 là các công thức ứng với Q1, Q2
Công thức của Q= Q1 x Q2
Fs: s(x1,…,xm, y1,…,yn)
Fs=(∃v) (∃ p) (F1v ∧ F2p ∧
s1=v1 ∧ …sm=vm ∧ sm+1=p1 ∧ … sm+n=pn)
Khoa HTTT - Đại học CNTT 18
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 Q1
Công thức của Q= Q1 [xi1, xi2,…,xik]
Fs=(∃v) (F1v ∧ s1=vi1 ∧s2=vi2 ∧… sk=vik)
5. Phép chọn
Q1 là quan hệ n chiều, F1 là công thức ứng với Q1
Công thức Q=Q1:điều kiện ĐK (ĐK:xiθxj hay xiθa)
Fs=F1s ∧ si θ sj hay F1s ∧ si θ a (1≤i, j ≤ n, i≠j)
Khoa HTTT - Đại học CNTT 19
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
Khoa HTTT - Đại học CNTT 20
7.1 Quy tắc
1. Từ: là hằng hay biến
2. Công thức nguyên tố
Q(t1,t2,…,tn): ti là các từ, Q là quan hệ
tiθ tj ,tiθ a với ti là từ, a là một hằng, θ là phép toán
3. Một công thức nguyên tố ...