Phép toán quan hệ

Chia sẻ: Vu Thai Hoc | Ngày: | Loại File: PPT | Số trang:24

1
326
lượt xem
95
download

Phép toán quan hệ

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ngôn ngữ hình thức cho mô hình quan hệ - Ngôn ngữ SQL thuận tiện cho tính toán.

Chủ đề:
Lưu

Nội dung Text: Phép toán quan hệ

  1. Phép toán quan hệ  1 / 24
  2. Ngôn ngữ hình thức cho mô hình quan hệ   Ngôn ngữ SQL thuận tiện cho  tính toán  Các ngôn ngữ theo tính toán quan  hệ thuận tiện cho mô tả. Lớp  ngôn ngữ này chịu ảnh hưởng của  ngôn ngữ SQL 2 / 24
  3. Phép toán quan hệ   Phép toán có • biến, hằng   • Phép toán so sánh  (,=,≥ ,≠ .≤ ),  • Liên kết logic  ( ∧ )  ,∨ • Lượng tử (∃ ,∀)  Có hai loại ngôn ngữ    • Tính toán quan hệ trên bộ (Tuple relational calculus TRC) : Các  biến theo các bộ dữ liệu.  Đại diện là QUEL. • Phép toán quan hệ trên miền (Domain relational calculus DRC).  Các biến theo các phần tử của miền dữ liệu. Đại diện là QBE. • Cả hai TRC và  DRC là phần con đơn giản của logic vị từ bậc  một. 3 / 24
  4. Phép toán quan hệ trên bộ (TRC)  Biến bộ : biến nhận các bộ của lược đồ quan hệ như  là giá trị.  Câu hỏi có dạng  {T| p(T )} T = biến bộ p(T) = công thức mô tả T  Kết quả là tập các bộ t mà p(t) thỏa mãn, khi  T=t   Công thức P(T) được viết theo logic vị từ bậc nhất. 4 / 24
  5. Thí dụ : tìm thủy thủ có tần suất trên 7 S ∈ a r Sr tin >     |S S ilo s∧ . a g 7       Biến S gắn với một bộ trong quan hệ Sailors 5 / 24
  6. Công thức TRC  Công thức :  Công thức nguyên tử R ∈ Rel,    R.a op S.b,   R.a op hằng,   hằng op R.a  Xác định đệ qui  ¬p,   p∧ p∨ p⇒q , trong đó p,  q,  q,  q là công thức  ∃ R(p(R)), trong đó R là biến bộ ∀R(p(R)), trong đó R là biến bộ  Terms 6 / 24
  7. Ngữ nghĩa của các câu hỏi TRC  F  là  công thức nguyên tử  R ∈ Rel, và R  được gán với bộ trong thể  hiện của quan hệ Rel  {S|S∈Sailors}  F  là công thức so sánh  R.a op S.b, R.a op hằng, hay hằng  op R.a, và các bộ gắn với  R và S  có các trường tên là  R.a và   S.b,  thỏa mãn so sánh true.  F  là công thức  ¬p, và  p không đúng; công thức p ∧ q, và cả  p và  q đều  true;  công thức p ∨ q, và một trong hai là  true;  công thức p ⇒ q, và q là  true khi mà  p là  true.  F là công thức có dạng  ∃ R(p( R )), và có sự gán các bộ cho biến tự  do trongb  p ( R ), bao gồm biến R làm cho công thức p( R )  true;  F là công thức có dạng  ∀R (p ( R )), và có sự gán các bộ cho biến  tự do trongb  p ( R ), bao gồm biến R làm cho công thức p( R )  true không liên quan đến bộ nào được gán cho R. 7 / 24
  8. Thí dụ về TRC Reserves Sailors sid sname rating age sid bid day 22 dustin 7 45.0 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 58 rusty 10 35.0 8 / 24
  9. Tìm tên và tuổi của thủy thủ có tần suất trên 7 { P | ∃ S ∈  Sailors (S.rating > 7 ∧ P.name = S.sname ∧ P.age = S.age)} P là biến bộ có hai trường name và age. - Hai trường là trường duy nhất trong P - P khi liên quan đến bất kì quan hệ nào Sailors sid sname rating age name age 22 dustin 7 45.0 Lubber 55.0 31 lubber 8 55.5 rusty 35.0 58 rusty 10 35.0 9 / 24
  10. Tìm tên thủy thủ phục vụ tàu 103 { P | ∃ S ∈ Sailors  ∃ R ∈ Reserves  (R.sid = S.sid ∧ R.bid = 103 ∧ P.sname = S.sname)} Tìm tất cả các thủy thủ có bộ trong quan hệ Reserves, có cùng giá trị  trong trường SID, mà bid =103 { S | ∃ S ∈ Sailors ∧∃ R ∈ Reserves (R.sid = S.sid ∧    R.bid = 103)} Vậy thì, các bộ kết quả trông ra sao, về dòng, cột. Có gì khác nhau  không ? 10 / 24
  11. Tìm tên thủy thủ đã từng phục vụ tàu đỏ { P | ∃ S ∈ Sailors  ∃ R ∈ Reserves ∃ B ∈ Boats (R.sid = S.sid ∧ B.bid = R.bid ∧ B.color ='red' ∧ P.sname = S.sname)} Tìm tất cả các bộ sailor S mà có bộ R trong Reserves và B trong quan hệ  Boats, để R.sid = S.sid ∧ B.bid = R.bid ∧ B.color ='red' { P | ∃ S ∈ Sailors  ∃ R ∈ Reserves  (R.sid = S.sid ∧ P.sname = S.sname ∧   ∃ B ∈ Boats(B.bid = R.bid ∧  B.color ='red'))} 11 / 24
  12. Tìm thủy thủ phục vụ tất cả các tàu { P | ∃ S ∈ Sailors  ∀B ∈ Boats (∃ R ∈ Reserves (S.sid = R.sid ∧ R.bid = B.bid ∧ P.sname = S.sname))} Tìm thủy thủ S mà tx các tàu B có trong bộ Reserves cho thấy : thủy thủ  S đã phục vụ tàu B. ρ (Tempsids, (π Re serves) / (π Boats)) sid, bid bid π sname (Tempsids  Sailors)  12 / 24
  13. Tìm các thủy thủ đã trên tàu đỏ { P | ∃ S ∈ Sailors ∧∀B ∈ Boats   (B.color = 'red'  ⇒ (∃ R ∈ Reserves (S.sid = R.sid ∧ R.bid = B.bid))} Thể hiện theo đại số quan hệ : ρ (Tempsids, (π Re serves) / (π Boats)) sid, bid bid π sname (Tempsids  Sailors)  13 / 24
  14. Tìm thủy thủ phục vụ tất cả các tàu đỏ  về logic    p ⇒ q  tương đương  ¬p∨q   { P | ∃ S ∈ Sailors ∧∀B ∈ Boats   (B.color = 'red'  ⇒ (∃ R ∈ Reserves (S.sid = R.sid ∧ R.bid = B.bid))}   được viết lại như : { P | ∃ S ∈ Sailors ∧∀B ∈ Boats   (B.color ≠ 'red' ∨ ∃ R ∈ Reserves (S.sid = R.sid ∧  (  R.bid = B.bid))}  để hạn chế các tàu đỏ 14 / 24
  15. Phép toán quan hệ trên miền  Câu hỏi có dạng       x1, x2,..., xn | p x1, x2,..., xn           Kết quả  là tất cả các bộ                             xn x1, x2,..., Để cho công thức là đúng p x1, x2,..., xn           15 / 24
  16. Công thức DRC  Công thức nguyên tử   ∈ Rel , trong đó Rel là quan hệ có n biến    X op Y    X op hằng số  op  là một trong các phép so sánh (,=,≥ ,≠ .≤ ),   Xác định đệ qui   ¬p,   p∧ p∨ p⇒q , trong đó  p, q  là  q,  q,  công thức ∃ X(p(X)), trong đó  X là biến miền ∀X(p(X)), trong đó X là biến miền 16 / 24
  17. Biến tự do và biến ràng buộc  ∃X ∀X Việc sử dụng lượng tử         và         trong công thức được  gọi là ràng buộc X ( bind X).  Biến không bị buộc là biến tự do.   Xét lại định nghĩa về câu hỏi             x1, x2,..., xn | p x1, x2,..., xn           y Điều hạn chế quan trọng là các biến x1, ..., xn bên  trái dấu  `|’ cần là biến tự do duy nhất trong công  thức p(...). 17 / 24
  18. Tìm thủy thủ tần suất trên 7 Sailors I, N,T, A | I, N,T, A ∈ Sailors ∧ T > 7   sid sname rating age   22 dustin 7 45.0     31 lubber 8 55.5   58 rusty 10 35.0                                      I, N,T, A ∈ Sailors biến miền dữ liệu I, N, T và  A là bị buộc vào các  trường của các bộ Sailors.  Mỗi bộ                    thỏa mãn T>7 có trong kết quả. I, N,T, A  Có thể thay đổi   Tìm thủy thủ trên 18 tuổi và tần suất trên 9, tên là Joe 18 / 24
  19. Tìm thủy thủ có suất > 7 đã trên tàu 103     I, N,T, A | I, N,T, A ∈Sailors ∧ T > 7 ∧  ∃ Ir, Br, D Ir, Br, D ∈ Re serves ∧ Ir = I ∧ Br = 103              Sailors Reserves Boats sid sname rating age sid bid day bid bname color 22 dustin 7 45.0 101 interlake red 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 103 marine green 58 rusty 10 35.0  Đã dùng                              thay cho   ∃ Ir ( ∃ Br ( ∃ D ( . ..) ) ) ∃ Ir, Br, D ( . . .)  Lưu ý rằng việc dùng ∃  để tìm bộ trong Reserves được  nối với Sailors {| ∈Sailors ∧ T>7  ∧  Ir,Br,D    ∃ ( ∈ Reserves ∧  Ir =I )} 19 / 24
  20. Tìm thủu thủ suất > 7 đã trên tàu đỏ     I, N,T, A | I, N,T, A ∈Sailors ∧ T >7 ∧  ∃ Ir, Br, D Ir, Br, D ∈Re serves ∧ Ir = I ∧     ∃ B, BN,C B, BN,C ∈Boats ∧ B = Br ∧ C =' red'                Sailors Reserves Boats sid sname rating age sid bid day bid bname color 22 dustin 7 45.0 101 interlake red 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 103 marine green 58 rusty 10 35.0  Lưu ý cách dùng ngoặc để chỉ phạm vi của lượng từ  Có thể viết lại, với RED là hằng BN = red 20 / 24
Đồng bộ tài khoản