Ngôn ngữ tân từ (tiếp theo)
x là biến lấy giá trị trên miền thuộc tính của các quan hệ. Quy tắc định nghĩa công thức : Từ : là hằng hoặc biến Công thức nguyên tố: ( i ) Q (t 1 , t 2 , … t n ) t i là các từ, Q là ...
x là biến lấy giá trị trên miền thuộc tính của các quan hệ.
Quy tắc định nghĩa công thức:
Từ: là hằng hoặc biến
Công thức nguyên tố:
(i) Q (t1, t2, … tn ) ti là các từ, Q là một quan hệ.
(ii) t1 q a1, t2 q a2, … ở đây ti là các từ và q là phép toán.
Công thức nguyên tố là một công thức.
F1, F2 là các công thức thì F1 F2 và F1 F2 cũng là các công thức.
F là một công thức và t là một biến tự do thì " t F và $ t F cũng là các công thức.
F là công thức thi ( F ) cũng là một công thức.
Trong một 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.
Công thức F là an toàn nếu nó thỏa các điều kiện sau:
F ( x1, x2, … xn ) là Đúng Þ xi Ỵ DOM (F) với i = 1, 2, …, n.
Công thức con $ u F ‘ (u) nếu u thỏa F ‘ (u) là Sai
thì Þ u Ỵ DOM (F ‘).
Ví dụ 7.3.1:
Cho một CSDL gồm các quan hệ sau:
VẬN_CHUYỂN (Khách_Hàng, Giá_Trị, Ga_Đến, #Toa, Mặt_Hàng, Khối_Lượng, N_Dỡ_Hàng)
TÀU (#Tàu, #Toa )
TOA (#Toa, Loại_Toa, TL_Rỗng, Khả_Năng_Chứa, Tình_Trạng, Ga)
HÀNG (Ga_Gốc, Ga_Đích, GA_TT, #T_Đường)
TUYẾN_ĐƯỜNG ( #T_Đường, Hàng, Ga)
LỊCH_TRÌNH (#Tàu, #T_Đường, Ngày)
Câu hỏi 1: Cho danh sách các loại toa "Frigo" đang sẵn sàng ở ga "Tour" và có khả năng chứa trên 10 toa ?
Câu hỏi trên có thể được biểu diễn bằng ngôn ngữ đại số quan hệ như sau:
(TOA : (Loại_Toa = "Frigo" Khả_Năng_Chứa > 10 Ga = "Tour" Tình_Trạng = "Td" ) [#Toa],
Diễn tả bằng ngôn ngữ tân từ có biến là bộ như sau:
{ r [#Toa] | TOA r r[Loại_Toa] = "Frigo" r[Khả_Năng_Chứa] > 10 r[Ga] = "Tour" r[Tình_Trạng] = "Td" }
Và bằng ngôn ngữ tân từ có biến là miền giá trị như sau:
{ n | $ x $ c ( TOA (n, "Frigo", x, c, "Td", "Tour") c > 10) }
Câu hỏi 2: Cho danh sách các loại toa của tàu số 4002 ?
Câu hỏi được biểu diễn bằng ngôn ngữ đại số quan hệ:
(((TÀU : #Tàu = 4002) [ #Toa] ) * TOA) [ Loại_Toa]
Bằng ngôn ngữ tân từ có biến là bộ giá trị :
{ r [Loại_Toa] | $ p (TOA r TÀU p r [#Toa] = p[ #Toa] p[ #Tàu] = 4002 }
Bằng ngôn ngữ tân từ có biến là miền giá trị chúng ta có công thức sau:
{ t | $ u $ p $ c $ e $ g (TÀU (w, 4002) TOA (w, t, p, c, e, g)) }
Câu hỏi 3: Cho danh sách các con đường đi qua ga "Tour" ?
Câu hỏi được biểu diễn bằng ngôn ngữ đại số quan hệ:
R1 ¬ TUYẾN_ĐƯỜNG * ( #Tuyến_đường1 = #Tuyến_đường2)
Tuyến_đường2:
R2 ¬ (R1 : (Ga = "Tour" Hạng1 < Hạng2) [ #Tuyến_đường1]
Bằng ngôn ngữ tân từ có biến là bộ giá trị :
{ r [ #Tuyến_Đường] | TUYẾN_ĐƯỜNG r $ p (TUYẾN_ĐƯỜNG p r [#Tuyến_Đường] = p[ #Tuyến_Đường] r[ Hạng] < p[ Hạng] r[Ga] = "Tour" }
Bằng ngôn ngữ tân từ có biến là miền giá trị chúng ta có công thức sau:
{ l | $ r1 $ r2 $ g (TUYẾN_ĐƯỜNG (l, r1, "Tour") TUYẾN_ĐƯỜNG (l, r2, g) (r2 > r1)) }
Câu hỏi 4: Cho danh sách các ga mà toa tàu đi từ "Anger" đến "Bezier" ?
Chúng ta cần một lược đồ – công thức sau:
x := { g | $ lHẠNG ("Anger", "Bezier", g, l) }
Output (x)
While x "Bezier"
X := { g | $ lHẠNG ("Anger", "Bezier", g, l) }
Output (x)
End.
Tính tương đương: Một câu hỏi được biểu diễn bằng một trong 3 ngôn ngữ thao tác CSDL: ngôn ngữ đại số quan hệ, ngôn ngữ tân từ có biến là bộ, ngôn ngữ tân từ có biến là miền giá trị là tương đương nhau:
Quy trình chứng minh như trên.
Một số định lý:
Định lý 7.1:
Nếu B là một biểu thức trong ngôn ngữ đại số quan hệ thì tồn tại 1 biểu thức an toàn trong ngôn ngữ tân từ có biến là n-bộ tương đương với biểu thức B.
Chứng minh: (Bằng phương pháp quy nạp theo số phép toán hiện diện trong B).
Trường hợp B không có phép toán:
B là một bảng các hằng { t1, t2, … , tn } hoặc B là một quan hệ.
Nếu B là một quan hệ Q, thì chúng ta có biểu thức an toàn có dạng { t | Q }.
Nếu B là một bảng hằng { t1, t2, … , tn }, thì chúng ta có công thức : B’ = { t | t = t1 t = t2 t = t3 … t = tn }.
Trong đó ti là dạng viết tắt của t1 = ti1, t2 = ti2, …, tk = tik; ở đây tj là thành phần thứ j của bộ t.
Vì t1, t2, … , tn là các bộ hoặc các hằng nên miền giá trị MGT(B) = { t1, t2, … , tn } và DOM (B’) = { t1, t2, … , tn }; hay công thức : { t | t = t1 t = t2 t = t3 … t = tn } là tương đương với biểu thức B đã cho.
Trường hợp B có chứa phép toán.
Giả sử B có dạng B = B1 q B2.
B1, B2 là các biểu thức quan hệ và q là phép toán quan hệ có số phép toán ít hơn B. Chúng ta cần tìm C, biểu thức an toàn tương đương với B.
Các phép toán quan hệ được xét là: Hợp ( - Union), Hiệu ( -Minus), Chiếu ([ ] - Project), Tích Đề các (x - Cartesian) và Chọn ( :() - Selection).
Phân tích phép toán:
Trường hợp 1: Phép Hợp ( - Union). Nếu B = B1 B2 thì ta có:
B1 º { t | C1(t) }
B2 º { t | C2(t) }
C1(t) và C2(t) là các công thức an toàn.
Xét công thức C(t) = C1(t) C2(t). Chúng ta cần chứng minh C(t) là công thức an toàn. Xét công thức trong ngôn ngữ tân từ B’ = { t | C(t) } với C(t) là công thức an toàn, tức là với mọi t là n-bộ t Ỵ DOM(B’) để C(t) là đúng. Khi đó B tương đương với B’, ký hiệu: B º B’.
Nhận xét: DOM(C1) DOM(C2) Í DOM(C).
Xét điều kiện 1 của định nghĩa công thức an toàn:
Nếu t0 thỏa C(t) = C1(t) C2(t) thì:
Hoặc t0 thỏa C1(t) Þ t0 Ỵ DOM(C1), bởi vì C1 là công thức an toàn;
Hoặc t0 thỏa C2(t) Þ t0 Ỵ DOM(C2), bởi vì C2 là công thức an toàn.
Þ Như vậy điều kiện 1 là thỏa.
Xét điều kiện 2 & 3:
Nếu có công thức $ u F(u) hoặc " u F(u) là các công thức con của C thì chúng nằm gọn trong C1 hoặc C2.
Do C1 và C2 là các công thức an toàn nên các công thức con cũng thỏa các điều kiện an toàn.
Do u0 thỏa $ u F(u) Þ u0 Ỵ DOM(F).
Do u0 thỏa " u F(u) Þ u0 Ỵ DOM(F).
Bởi vì C(t) = C1(t) C2(t), do đó B º B’ theo định nghĩa của phép hợp ( ).
Trường hợp 2: Phép Hiệu (-Minus). Nếu B = B1 - B2 thì ta có:
B’ º { t | C1(t) C2(t) }
C(t) = C1(t) C2(t).
Xét điều kiện 1 của định nghĩa công thức an toàn:
(** Lưu ý: DOM(C) = DOM(C1) DOM(C2)).
Nếu t0 thỏa C(t) Þ t0 Ỵ DOM(C1) Í DOM(C)
Nghĩa là với t là một n-bộ thỏa C(t) thì t thuộc vào miền giá trị của công thức C(t). Điều kiện 1 thỏa.
Điều kiện 2:
Nếu có công thức $ u F(u) là công thức con của C thì :
$ u F(u) là công thức con C1. C1 là an toàn nên u0 thỏa F(u0) là đúng Þ u0 Ỵ DOM(F). Và
$ u F(u) là công thức con C2. C2 là an toàn nên u0 thỏa F(u0) là sai Þ u0 Ỵ DOM( F). Hay u0 thỏa F(u0) là đúng Þ u0 Ỵ DOM(F).
Vậy điều kiện 2 thỏa mãn.
Điều kiện 3: (hoàn toàn tương tự như trên)
Nếu có công thức " u F(u) là công thức con của C thì :
" u F(u) là công thức con C1. C1 là an toàn nên u0 thỏa F(u0) là đúng Þ u0 Ỵ DOM(F). Và
" u F(u) là công thức con C2. C2 là an toàn nên u0 thỏa F(u0) là sai Þ u0 Ỵ DOM( F). Hay u0 thỏa F(u0) là đúng Þ u0 Ỵ DOM(F).
Vậy điều kiện 3 thỏa mãn.
Trường hợp 3: Phép chiếu ([ ] - Project)
Biểu thức quan hệ có dạng: B = B1[X]. Ở đây, X là tập các thuộc tính.
B1 có biểu thức tương đương là B’ = { t | C1(t) } và C1(t) là một công thức an toàn.
Xét B’ = { u | $ t (C(t) Ç u = t[X] }
A là tập các hằng và các giá trị của thuộc tính X của các quan hệ có mặt trong biểu thức đại số quan hệ B1. Khi đó:
DOM (C1) = MGT(X) A.
Đặt E = MGT(X) - A. Þ
DOM(C) = DOM(C1) - E.
Về điều kiện 1:
u0 thỏa C, $ t0 (C1(t0) u = t0[X] là đúng. Þ C1(t0) : là đúng.
C1 là an toàn Þ t0 Ỵ DOM(C1).
t0j = u0j, thành phần thứ j của t0 và u0.
u0j X Þ u0j Ỵ DOM(C1) - E, hay u0 Ỵ DOM(C1)
Như vậy C là công thức an toàn.
Điều kiện 2 & 3:
$ u F(u) hoặc " u F(u) là các công thức con của C. Suy ra chúng là các công thức con của C1.
Như vậy C(t) là công thức an toàn và chúng ta có: B º B’.
Trường hợp 4: Phép tích Đề các ( x - Cartesian).
Biểu thức B có dạng B = B1 x B2.
B1 có công thức an toàn C1 tương đương và
B2 có công thức an toàn C2 tương đương.
Chúng ta xây dựng biểu thức trong ngôn ngữ tân từ có biến bộ-n như sau:
B’ = { u | $ t $ v (C1(t) C2(v) u[X] = tu[Y] = v }
Ở đây X và Y là tập các thuộc tính của B1 và B2. Chúng ta cần chứng minh công thức là an toàn
Þ B º B’.
Xét điều kiện 1:
u0 thỏa C. Þ
u0 [X] = t0 thỏa C1, C1 là công thức an toàn Þ t0 Ỵ DOM(C1).
u0 [Y] = v0 thỏa C2, C2 là công thức an toàn Þ v0 Ỵ DOM(C2).
Þ u0 Ỵ DOM(C1) DOM(C2) Í DOM (C) Þ Điều kiện 1 thỏa.
Điều kiện 2& 3: (không có)
Trường hợp 5: Đối với phép chọn ( :() - Selection)
Biểu thức trong ngôn ngữ đại số quan hệ có dạng:
B = B1 : (E)
(phép chọn theo điều kiện E). B1 có biểu thức an toàn là C1. Biểu thức trong ngôn ngữ tân từ có biến bộ-n là:
B’ = { t | C1(t) E’ }
Ở đây E’ được suy từ E bằng cách lấy các toán hạng biểu diễn bởi thuộc tính X là t[X].
C(t) = C1(t) E’. Cần chứng minh C là một công thức an toàn.
DOM(C) = DOM(C1) Tập hằng (E’).
t0 thỏa C1 là đúng Þ t0 Ỵ DOM(C1).
Þ điều kiện 1 làthỏa.
Điều kiện 2 &3 (không có) Như vậy C(t) = C1(t) E’ là một công thức an toàn. Ta có B º B’.
Kết luận: Một câu hỏi được biểu diễn bằng ngôn ngữ đại số quan hệ luôn luôn tìm được biểu thức tương đương với nó biểu diễn bằng ngôn ngữ tân từ có biến là bộ-n.
Ví dụ 7.3.1:
Cho 2 quan hệ R(A,B) và S(C,D).
Biểu thức trong ngôn ngữ đại số quan hệ là:
((R x S) : (B = C)) [A,B,D].
Biểu diễn trong ngôn ngữ tân từ có biến là bộ-n:
Với R x S:
{ t | $ u $ v (R u S v (t[A] = u[A]) (t[B] = u[B]) t[C] = v[C]) t[D] = v[D] }
Sâu hơn nữa tới phép chọn (: (B=C)), và rồi phép chiếu :
{ w | $ t ( $ u $ v (R u S v (t[A] = u[A]) (t[B] = u[B]) t[C] = v[C]) t[D] = v[D] ) (t[B] = t[C]) (w[A] = t[A]) (w[C] = t[C]) (w[D] = t[D]) }
Đơn giản biểu thức chúng ta thu được :
{ w | $ u $ v (R u S v (w[A] = u[A]) (w[C] = v[C]) w[D] = v[D] ) (u[B] = v[C]) }
đó là biểu thức tương đương được biểu diễn bằng ngôn ngữ tân từ có biến là bộ-n của biểu thức trong ngôn ngữ đại số quan hệ nêu trên.
Định lý 7.2:
Ứng với mỗi biểu thức an toàn trong ngôn ngữ tân từ có biến là bộ-n ta có một biểu thức an toàn tương đương trong ngôn ngữ tân từ có biến là miền giá trị.
Quá trình biến đổi câu hỏi tron ngôn ngữ tân từ có biến là bộ-n sang câu hỏi tron ngôn ngữ tân từ có biến là miền giá trị:
Cho câu hỏi dạng { t | C(t) }, Ở đây t là một bộ-n có k bậc tự do. t0 phát sinh ra k biến miền giá trị tự do là x1, x2, x3, ..., xk.
Trong công thức C(t), mỗi biểu thức Q t mà Q là một quan hệ, thì được đổi thành Q (x1, x2, x3, ..., xk).
vMỗi biểu thức có sự hiện diện của t[xi] thì được đổi thành xi.
Trong các biểu thức con có dạng $ u G(u) hay " u G(u) được biến đổi như sau:
Biến u được đổi thành y1, y2, …, ym, Ở đây m là bậc của u.
R(u) được đổi thành R (y1, y2, …, ym).
u[yi] được đổi thành yi.
$ u được đổi thành $ y1, $ y2, $ y3 , …, $ ym,
" u được đổi thành " y1, " y2, " y3 , …, " ym,
