›
›

Bài giảng Cơ sở dữ liệu phân tán - Chương 3: Các mức trong suốt phân tán - Nguyễn Trung Trực

pdf 41 trang ngocly 2730
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cơ sở dữ liệu phân tán - Chương 3: Các mức trong suốt phân tán - Nguyễn Trung Trực", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_co_so_du_lieu_phan_tan_chuong_3_cac_muc_trong_suot.pdf

Nội dung text: Bài giảng Cơ sở dữ liệu phân tán - Chương 3: Các mức trong suốt phân tán - Nguyễn Trung Trực

  1. Chương 3 Các mức trong suốt phân tán Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 1
  2. Nội dung ™ Kiến trúc tham khảo của CSDL phân tán. ™ Các loại phân mảnh dữ liệu. ™ Các điều kiện đúng đắn để phân mảnh dữ liệu. ™ Phân mảnh ngang chính. ™ Phân mảnh ngang dẫn xuất. ™ Phân mảnh dọc. ™ Phân mảnh hỗn hợp. ™ Tính trong suốt phân tán dùng cho ứng dụng chỉ đọc. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 2
  3. Nội dung ™ Tính trong suốt phân tán dùng cho ứng dụng cập nhật. ™ Các tác vụ cơ bản truy xuất CSDL phân tán. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 3
  4. Kiến trúc tham khảo của CSDL phân tán Lược đồ toàn cục Các lược đồ Lược đồ phân mảnh độc lập nơi Lược đồ định vị Lược đồ ánh xạ cục bộ 1 Lược đồ ánh xạ cục bộ 2 (Các nơi khác) DBMS của nơi 1 DBMS của nơi 2 CSDL cục bộ 1 CSDL cục bộ 2 Hình 3.1. Kiến trúc tham khảo dùng cho các CSDL phân tán. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 4
  5. Kiến trúc tham khảo của CSDL phân tán ™ Trong suốt phân mảnh f fragmentation transparency f Lược đồ toàn cục (global schema) f Quan hệ toàn cục (global relation) ™ Trong suốt vị trí f location transparency f Lược đồ phân mảnh (fragmentation schema) f Mảnh (fragment) ™ Trong suốt nhân bản f replication transparency f Bản nhân (replica) Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 5
  6. Kiến trúc tham khảo của CSDL phân tán ™ Trong suốt ánh xạ cục bộ f local mapping transparency f Lược đồ định vị (allocation schema) f Quan hệ cục bộ (local relation) ™ Không trong suốt f No transparentcy f Lược đồ ánh xạ cục bộ (local mapping schema) Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 6
  7. Kiến trúc tham khảo của CSDL phân tán R R1 R1 Nơi 1 R2 R2 Nơi 2 R3 R 4 R3 Nơi 3 Quan hệ toàn cụcMảnh Hình ảnh vật lý Hình 3.2. Các mảnh và các hình ảnh vật lý của một quan hệ toàn cục. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 7
  8. Các loại phân mảnh dữ liệu ™ Phân mảnh ngang f horizontal fragmentation f Phân mảnh ngang chính (primary horizontal fragmentation) f Phân mảnh ngang dẫn xuất (derived horizontal fragmentation) Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 8
  9. Các loại phân mảnh dữ liệu R R1 R2 Phân mảnh ngang chính S R R1 R2 Phân mảnh ngang chính Phân mảnh ngang dẫn xuất Hình 3.3. Các loại phân mảnh ngang. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 9
  10. Các loại phân mảnh dữ liệu ™ Phân mảnh dọc f vertical fragmentation f Phân mảnh dọc gom tụ (vertical clustering fragmentation) y Phân mảnh dư thừa (redundant fragmentation) y Phân mảnh không dư thừa (non-redundant fragmentation) f Phân mảnh dọc tách biệt (vertical partitioning fragmentation) Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 10
  11. Các loại phân mảnh dữ liệu RR K K ∪ X Phân mảnh gom tụ không dư thừa Phân mảnh gom tụ có dư thừa R Phân mảnh dọc tách biệt Hình 3.4. Các loại phân mảnh dọc. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 11
  12. Các loại phân mảnh dữ liệu ™ Phân mảnh hỗn hợp f mixed fragmentation f Kết hợp giữa phân mảnh ngang và phân mảnh dọc. RR Hình 3.5. Phân mảnh hỗn hợp. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 12
  13. Các điều kiện đúng đắn ™ Quan hệ R được phân rã thành các mảnh R1, R2, , Rn ™ Điều kiện đầy đủ f completeness condition f Mỗi mục dữ liệu trong R phải có trong một hoặc nhiều mảnh Ri f Phân mảnh ngang: ∀u ∈ R, ∃ i ∈ [1, n]: u ∈ Ri f Phân mảnh dọc: ∀A ∈ Attr(R), ∃ i ∈ [1, n]: A ∈ Attr(Ri) Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 13
  14. Các điều kiện đúng đắn ™ Điều kiện tái tạo f reconstruction condition f Luôn luôn có thể xác định một phép toán quan hệ ∇ sao cho: R = ∇ Ri, ∀ Ri ∈ FR với FR = {R1, R2, , Rn} f Phân mảnh ngang: R = R1 ∪ R2 ∪ ∪ Rn f Phân mảnh dọc: R = R1 > < Rn Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 14
  15. Các điều kiện đúng đắn ™ Điều kiện tách biệt f disjointness condition f Nếu mục dữ liệu di có trong Ri thì nó không có trong bất kỳ mảnh Rk khác (k ≠ i). f Phân mảnh ngang: ∀ i ≠ k và i, k ∈ [1, n]: Ri ∩ Rk = ∅ hoặc ∀ u ∈ Ri, ∀ i ≠ k và i, k ∈ [1, n]: u ∉ Rk Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 15
  16. Phân mảnh ngang chính ™ Phân mảnh ngang chính (primary horizontal fragmentation) là sự phân chia các bộ của một quan hệ toàn cục thành các tập hợp con dựa vào các thuộc tính của quan hệ này, mỗi tập hợp con được gọi là mảnh ngang (horizontal fragment). ™ Mỗi mảnh ngang được tạo bởi một phép chọn trên quan hệ toàn cục. ™ Vị từ định tính (qualification) của mảnh ngang. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 16
  17. Phân mảnh ngang chính ™ Ví dụ f Quan hệ toàn cục: supplier (snum, name, city) f Các mảnh ngang: supplier1 = σ city = ‘SF’ supplier supplier2 = σ city = ‘LA’ supplier f Các vị từ định tính: q1: city = ‘SF’ q2: city = ‘LA’ f Xét các điều kiện đúng đắn Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 17
  18. Phân mảnh ngang chính ™ Điều kiện đầy đủ: tập hợp các vị từ định tính của tất cả các mảnh ngang phải đầy đủ. ™ Điều kiện tái tạo: phép hợp. ™ Điều kiện tách biệt: các vị từ định tính phải loại trừ nhau. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 18
  19. Phân mảnh ngang dẫn xuất ™ Phân mảnh ngang dẫn xuất (derived horizontal fragmentation) là sự phân chia các bộ của một quan hệ toàn cục thành các tập hợp con, được gọi là các mảnh ngang, dựa vào phân mảnh ngang của một quan hệ khác (được gọi là quan hệ chủ). ™ Vị từ định tính của mảnh ngang dẫn xuất bao gồm điều kiện kết và vị từ định tính của mảnh ngang chủ tương ứng. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 19
  20. Phân mảnh ngang dẫn xuất ™ Ví dụ f Quan hệ toàn cục: supply (snum, pnum, deptnum, quan) f Các mảnh ngang dẫn xuất: supply1 = supply > < snum = snum supplier2 f Các vị từ định tính: q1: supply.snum = supplier.snum AND supplier.city = ‘SF’ q2: supply.snum = supplier.snum AND supplier.city = ‘LA’ f Xét các điều kiện đúng đắn Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 20
  21. Phân mảnh ngang dẫn xuất S R T P Hình 3.6. Cây phân mảnh ngang dẫn xuất. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 21
  22. Phân mảnh dọc ™ Phân mảnh dọc (vertical fragmentation) là sự phân chia tập thuộc tính của một quan hệ toàn cục thành các tập thuộc tính con; các mảnh dọc (vertical fragment) có được bằng cách chiếu quan hệ toàn cục trên mỗi tập thuộc tính con. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 22
  23. Phân mảnh dọc ™ Ví dụ f Quan hệ toàn cục: emp (empnum, name, sal, tax, mgrnum, deptnum) f Phân mảnh dọc không dư thừa: emp1 = Π empnum, name, mgrnum, deptnum emp emp2 = Π empnum, sal, tax emp emp = emp1 > < empnum = empnum Π empnum, sal, tax emp2 Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 23
  24. Phân mảnh hỗn hợp ™ Một mảnh ngang được phân mảnh dọc. ™ Một mảnh dọc được phân mảnh ngang. ™ Ví dụ f Quan hệ toàn cục: emp (empnum, name, sal, tax, mgrnum, deptnum) f Phân mảnh hỗn hợp: emp1 = σ deptnum ≤ 10 Π empnum, name, mgrnum, deptnum emp emp2 = σ 10 20 Π empnum, name, mgrnum, deptnum emp emp4 = Π empnum, name, sal, tax emp emp = (emp1 ∪ emp2 ∪ emp3) >< empnum = empnum Π empnum, sal, tax emp4 Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 24
  25. Phân mảnh hỗn hợp emp {empnum, name, mgrnum, deptnum} {empnum, name, sal, tax} v h emp4 deptnum ≤ 10 deptnum > 20 emp1 emp2 emp3 deptnum > 10 and deptnum ≤ 20 Hình 3.7. Cây phân mảnh của quan hệ EMP. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 25
  26. Example.DDB ™ Lược đồ toàn cục: emp (empnum, name, sal, tax, mgrnum, deptnum) dept (deptnum, name, area, mgrnum) supplier (snum, name, city) supply (snum, pnum, deptnum, quan) ™ Lược đồ phân mảnh: emp1 = σ deptnum ≤ 10 Π empnum, name, mgrnum, deptnum emp emp2 = σ 10 20 Π empnum, name, mgrnum, deptnum emp emp4 = Π empnum, name, sal, tax emp Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 26
  27. Example.DDB ™ Lược đồ phân mảnh: dept1 = σ deptnum ≤ 10 dept dept2 = σ 10 20 dept supplier1 = σ city = ‘SF’ supplier supplier2 = σ city = ‘LA’ supplier supply1 = supply > < snum = snum supplier2 Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 27
  28. Tính trong suốt phân tán dùng cho ứng dụng chỉ đọc ™ Ví dụ 1 f Cho biết tên của nhà cung cấp có mã được nhập từ thiết bị đầu cuối. f Mức 1 – Trong suốt phân mảnh read (terminal, $snum); select name into $name from supplier where snum = $snum; if #FOUND then write (terminal, $name) else write (terminal, ‘Not found’); Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 28
  29. Tính trong suốt phân tán dùng cho ứng dụng chỉ đọc f Mức 2 – Trong suốt vị trí read (terminal, $snum); select name into $name from supplier1 where snum = $snum; if not #FOUND then select name into $name from supplier2 where snum = $snum; if #FOUND then write (terminal, $name) else write (terminal,’Not found’); Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 29
  30. Tính trong suốt phân tán dùng cho ứng dụng chỉ đọc f Trường hợp dữ liệu nhập có liên quan đến vị từ định tính của mảnh read (terminal, $snum); read (terminal, $city); case $city of ‘SF’: select name into $name from supplier1 where snum = $snum; ‘LA’:select name into $name from supplier2 where snum = $snum; end; if #FOUND then write (terminal, $name) else write (terminal, ‘Not found’); Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 30
  31. Tính trong suốt phân tán dùng cho ứng dụng chỉ đọc ™ Ví dụ 2 f Cho biết tên của nhà cung cấp mà họ cung cấp mặt hàng có mã được nhập từ thiết bị đầu cuối. f Giả sử một mặt hàng chỉ được cung cấp bởi một nhà cung cấp. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 31
  32. Tính trong suốt phân tán dùng cho ứng dụng chỉ đọc f Mức 1 – Trong suốt phân mảnh read (terminal, $pnum); select name into $name from supplier, supply where supplier.snum = supply.snum and supply.pnum = $pnum; if #FOUND then write (terminal, $name) else write (terminal, ‘Not found’); Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 32
  33. Tính trong suốt phân tán dùng cho ứng dụng chỉ đọc f Mức 2 – Trong suốt vị trí read (terminal, $pnum); select name into $name from supplier1, supply1 where supplier1.snum = supply1.snum and supply1.pnum = $pnum; if not #FOUND then select name into $name from supplier2, supply2 where supplier2.snum = supply2.snum and supply2.pnum = $pnum; if #FOUND then write (terminal, $name) else write (terminal, ‘Not found’); Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 33
  34. Tính trong suốt phân tán dùng cho ứng dụng cập nhật ™ Cập nhật dữ liệu (thêm, sửa, xóa) phải bảo đảm các ràng buộc toàn vẹn về khóa chính, khóa ngoại, phụ thuộc hàm, ràng buộc nghiệp vụ ™ Qui tắc read-one write-all. ™ Qui tắc owner – member. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 34
  35. Tính trong suốt phân tán dùng cho ứng dụng cập nhật ™ Sửa dữ liệu trong CSDL phân tán f Mục dữ liệu bị sửa không có trong vị từ định tính. f Mục dữ liệu bị sửa có trong vị từ định tính và giá trị của vị từ định tính không bị thay đổi khi thay thế dữ liệu cũ và dữ liệu mới. f Mục dữ liệu bị sửa có trong vị từ định tính và giá trị của vị từ định tính bị thay đổi khi thay thế dữ liệu cũ và dữ liệu mới. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 35
  36. Tính trong suốt phân tán dùng cho ứng dụng cập nhật ™ Ví dụ f Sửa dữ liệu của nhân viên có mã 100: mã phòng 3 thành mã phòng 15. f Các mảnh: emp1 được đặt tại nơi 1 và 5. emp2 được đặt tại nơi 2 và 6. emp3 được đặt tại nơi 3 và 7. emp4 được đặt tại nơi 4 và 8. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 36
  37. Tính trong suốt phân tán dùng cho ứng dụng cập nhật emp h v v emp1 emp2 emp3 emp4 emp1 = Π empnum, name, sal, tax σ deptnum 10 emp emp4 = Π empnum, sal, tax, mgrnum σ deptnum > 10 emp Hình 3.9. Cây phân mảnh của quan hệ EMP. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 37
  38. Tính trong suốt phân tán dùng cho ứng dụng cập nhật emp1 emp2 empnum name sal tax empnum mgrnum deptnum 100 smith 10000 1000 100 20 3 Trước cập nhật Sau cập nhật emp3 emp4 empnum name deptnum empnum sal tax mgrnum 100 smith 15 100 10000 1000 20 Hình 3.10. Ứng dụng cập nhật. Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 38
  39. Tính trong suốt phân tán dùng cho ứng dụng cập nhật f Mức 1 – Trong suốt phân mảnh update emp set deptnum = 15 where empnum = 100; Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 39
  40. Tính trong suốt phân tán dùng cho ứng dụng cập nhật f Mức 2 – Trong suốt vị trí select name, sal, tax into $name, $sal, $tax from emp1 where empnum = 100; if #FOUND then begin select mgrnum into $mgrnum from emp2 where empnum = 100; insert into emp3 (empnum, name, deptnum) values (100, $name, 15); Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 40
  41. Tính trong suốt phân tán dùng cho ứng dụng cập nhật insert into emp4 (empnum, sal, tax,mgrnum) values (100, $sal, $tax, $mgrnum); delete from emp1 where empnum = 100; delete from emp2 where empnum = 100 end; Chương 3. Các mức trong suốt phân tán 2006 Nguyễn Trung Trực - Khoa CNTT 41