Ôn Tập Môn CSDL Phân Tán

ĐỀ CƯƠNG ÔN TẬP MÔN CƠ SỞ DỮ LIỆU PHÂN TÁN
1. Các định nghĩa cơ sở dữ liệu phân tán. Các khía cạnh quan trọng trong từng định nghĩa?
2. Mô hình cơ sở dữ liệu phân tán trên một mạng phân tán địa lý. Mô hình CSDL phân tán trên một mạng cục bộ. Mô hình một
hệ thống đa xử lý?
3. Các đặc điểm của CSDL phân tán so với CSDL tập trung. Điều khiển tập trung, độc lập dữ liệu, dư thừa dữ liệu, tính riêng
biệt và bảo mật?
4. Các đặc điểm của CSDL phân tán so với CSDL tập trung. Các cấu trúc vật lý phức tạp và truy xuất hiệu quả, tính tòan vẹn,
phục hồi, điều khiển đồng thời?
5. Các nguyên nhân chính dẫn đến việc sử dụng CSDL phân tán?
6. Các hệ quản trị CSDL phân tán. Các hình thức thực hiện truy vấn từ xa?
7. Kiến trúc tham khảo dùng cho các CSDL phân tán?
8. Các đặc điểm của kiến trúc tham khảo dùng cho các CSDL phân tán?
9. Đặc điểm của hệ song song và hệ phân tán, điểm tương đồng và điểm khác biệt?
10. Kiến trúc cơ sở dữ liệu. Share nothing?
11. Kiến trúc cơ sở dữ liệu. Share disk?
12. Kiến trúc cơ sở dữ liệu. Hybrid?
13. Kiến trúc cơ sở dữ liệu. Datacycle?
14. Kiến trúc cơ sở dữ liệu. Client Server?
15. Những vấn đề cần quan tâm khi lựa chọn kiến trúc cơ sở dữ liệu?
16. Các loại phân mảnh dữ liệu. Các điều kiện đúng đắn khi phân mảnh dữ liệu?
17. Tính trong suốt phân mảnh cho các ứng dụng chỉ đọc?
18. Tính trong suốt phân mảnh cho các ứng dụng cập nhật?
19. Các tác vụ cơ bản truy xuất CSDL phân tán?
20. Các ràng buộc tòan vẹn trong CSDL phân tán?
21. Thiết kế CSDL phân tán. Các vấn đề cần quan tâm?
22. Thiêt kế CSDL phân tán. Các cách tiếp cận trong thiết kế?
23. Các kỹ thuật phân vùng ngang thường sử dụng?
24. Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang. Các yêu cầu thông tin?
25. Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang chính. Các định nghĩa?
26. Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang chính. Giải thuật COM_MIN?
27. Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang chính. Giải thuật PHORIZONTAL?
28. Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang dẫn xuất? Đồ thị kết? Phân loại?
29. Thiết kế phân mảnh CSDL phân tán. Phân mảnh dọc. Các yêu cầu thông tin?
30. Thiết kế phân mảnh CSDL phân tán. Phân mảnh dọc. Giải thuật gom tụ?
31. Thiết kế phân mảnh CSDL phân tán. Phân mảnh dọc. Giải thuật phân tách?
32. Thiết kế phân mảnh CSDL phân tán. Phân mảnh hỗn hợp?
33. Các vấn đề tối ưu cần quan tâm trong hệ cơ sở dữ liệu phân tán?
34. Cách tính các chi phí trong hệ cơ sở dữ liệu phân tán?
35. Xử lý truy vấn. Các vấn đề cần quan tâm?
36. Biến đổi truy vấn tòan cục thành truy vấn phân mảnh. Biểu thức chuẩn tắc của truy vấn phân mảnh?
37. Biến đổi truy vấn tòan cục thành truy vấn phân mảnh. Các phép biến đổi tương đương đại số quan hệ định tính? Các quy tắc?
38. Biến đổi truy vấn tòan cục thành truy vấn phân mảnh. Các tiêu chuẩn dùng chung để đơn giản hóa các biểu thức trên lược đồ
phân mảnh và tập trung.
39. Biến đổi truy vấn tòan cục thành truy vấn phân mảnh. Tối ưu hóa các phép kết giữa các quan hệ được phân mảnh ngang.
40. Biến đổi truy vấn tòan cục thành truy vấn phân mảnh. Sử dụng phép suy diễn cho các phép đơn giản hóa. Đơn giản hóa quan
hệ phân mảnh dọc. Chương trình nửa kết.
41. Biến đổi truy vấn tòan cục thành truy vấn phân mảnh. Gom nhóm phân tán và định trị hàm kết hợp. Mở rộng đại số quan hệ.
Các đặc tính của phép gom nhóm.
42. Quy tình tối ưu hóa?

1/
Định nghĩa 1
 CSDL phân tán là sự tập hợp dữ liệu mà về mặt luận lý chúng thuộc cùng một hệ thống nhưng đặt ở nhiều nơi của 1 mạng máy tính
 Sự phân tán dữ liệu (Data distribution): dữ liệu phải được phân tán ở nhiều nơi
 Sự tương quan luận lý (Logical correlation): Dữ liệu của các nơi được dùng chung để giải quyết một vấn đề.

Định nghĩa 2
CSDL phân tán là sự tập hợp dữ liệu được phân tán trên các máy tính khác nhau của một mạng máy tính. Mỗi nơi của mạng máy tính có khả năng xử lý tự trị và có thể thực hiện các ứng dụng cục bộ. Mỗi một nơi cũng tham gia thực hiện ít nhất một ứng dụng toàn cục, mà nơi này yêu cầu truy xuất dữ liệu ở nhiều nơi thông qua hệ thống mạng.
 Sự phân tán dữ liệu: Dữ liệu phải được phân tán nhiều nơi
 Ứng dụng cục bộ (Local application): Ứng dụng được chạy hòan thành tại một nơi và chỉ sử dụng dữ liệu cục bộ tại nơi này
 Ứng dụng toàn cục (Global application) hay Ứng dụng phân tán (Distributed application): Ứng dụng được chạy hoàn thành và sử dụng dữ liệu của ít nhất hai nơi
2/
CSDLPT trên một mạng phân tán địa lý


CSDLPT trên một mạng cục bộ (LAN)

CSDLPT trên một hệ thống đa xử lý

3/
Điều khiển tập trung
Trong CSDL phân tán việc điều khiển dữ liệu tập trung ít được tập trung đến hơn, nó còn tùy thộc vào cấu trúc của CSDL.
Ở CSDL phân tán việc điều khiển sẽ dựa vào việc điều khiển các mảnh dữ liệu thông qua việc quản lý CSDL cục bộ( do Người quản trị CSDL cục bộ thực hiện) và quản lý CSDL toàn cục ( do Người quản trị CSDL toàn cục thực hiện), tại mỗi địa phương mà csdl đang ở đó sẽ mang Tính tự trị vị trí / địa phương tức tại đó họ có thể tự quản lý cơ sở dữ liệu của mình mà không phụ thuộc.
Độc lập dữ liệu
Trong CSDL phân tán có một khái niệm mới về Độc lập dữ liệu đó là Tính trong suốt dữ liệu (Data transparency)
Trong suốt phân mảnh: Không nhìn thấy các mảnh; nhìn thấy các quan hệ toàn cục; lược đồ toàn cục
Trong suốt vị trí: Không nhìn thấy quan hệ cục bộ, thấy các mảnh; lược đồ phân mảnh
Trong suốt nhân bản: Nhìn thấy các mảnh; không thấy nhân bản các mảnh
Trong suốt ánh xạ cục bộ: Nhìn thấy quan hệ cục bộ; không nhìn thấy CSDL vật lý
Trong suốt phân tán (Distribution transparency): Gồm 4 trong suốt trên

Giảm dư thừa dữ liệu
Giảm dư thừa dữ liệu trong csdl phân tán là phức tạp hơn so với csdl cục bộ vì tính chất phấn tán của cơ sở dữ liệu sẽ dẫn đến:
Hoạt động của các chương trình ứng dụng có thể bị tăng lên khi dữ liệu được sao lại tất cả các vị trí, nơi trình ứng dụng cần nó.
Khi cập nhật thông tin hay một mẫu tinh thì phải cập nhật trên tất cả các site để đảm bảo tính nhất quán của dữ liệu.
Tính riêng biệt và tính bảo mật
- Trong CSDL phân tán với một mức độ tự trị rất cao của các địa phương, người chủ dữ liệu địa phương cảm giác được bảo vệ tốt hơn vì họ có thể tự chủ thực hiện bảo vệ thay vì phụ thuộc vào người quản trị CSDL trung tâm.
- Vấn đề bảo mật là bản chất trong hệ phân tán nói chung, vì các mạng truyền thông diện rộng cho phép nhiều người cập nhật và khai thác dữ liệu nên cần được bảo vệ.
4/
Các cấu trúc vật lý phức tạp và truy xuất hiệu quả : Cấu trúc vật lý phức tạp của csdl phân tán nên để truy xuất hiệu quả ta cần thực hiện tối ưu hóa:
 Tối ưu hóa toàn cục (glocal optimization)
 Tối ưu hóa cục bộ (local optimization)
Tính toàn vẹn (Integrity) :
Dữ liệu phấn tán là một thể thống nhất nhưng được phấn bố đến các địa phương chí vì vậy khi thực hiện cập nhật dữ liệu phải đảm bảo dữ liệu sẽ được cập nhật do việc truy vấn phải thông qua internet nên cần đảm bảo truy vấn được thực hiện toàn vẹn
Giao tác (transaction)
Giao tác - Đơn vị thực hiện nguyên tố .Một chuỗi các tác vụ mà tất cả được thực hiện hay đều không được thực hiện

Điều khiển đồng thời:
Truy suất dữ liệu và cập nhật một cách đổng bộ trên tất cả các mảnh chứa dữ liệu của csdl
5/
Nguyên nhân sử dụng CSDLPT
 Thực tế tổ chức và kinh tế - Không tập trung tại một nơi mà phấn bố trên nhiều vùng địa lý khác nhau
 Các CSDL hiện tại cần kết nối với nhau: Nhiều CSDL đã tồn tại trong 1 công ty và cần được thực hiện nhiều ứng dụng toàn cục
 Sự lớn mạnh tăng: Có thêm các đơn vị tổ chức độc lập
 Giảm chi phí truyền thông: Nhiều ứng dụng cục bộ làm giảm chi phí truyền thông so với CSDL tập trung
 Hiệu suất: Cơ chế song song hóa; Phân mảnh theo ứng dụng, cực đại hóa tính cục bộ ứng dụng
 Độ tin cậy và tính sẵn sàng: Dư thừa dữ liệu; Cần đảm bảo tính tin cậy của dữ liệu
6/
Các thành phần DDBMS
Truyền thông dữ liệu:Nhận yêu cầu truy xuất dữ liệu của ứng dụng chạy tại thiết bị đầu cuối Trả kết quả về cho ứng dụng
Quản trị CSDL:Quản lý CSDL Thực hiện các yêu cầu của ứng dụng: Xử lý dữ liệu (data proccessing)
Từ điển dữ liệu :Lưu trữ thông tin về các đối tượng trong CSDL. Lưu trữ thông tin về sự phân tán dữ liệu các nơi
CSDL phân tán: Liên lạc giữa các nơi gửi yêu cầu và nhận kết quả

Các loại truy xuất cơ sở dữ liệu phân tán từ xa:
Truy xuất từ xa thông qua tác vụ cơ bản DDBMS

Truy xuất từ xa thông qua chương trình phụ trợ

7/

Lược đồ toàn cục:Xác định tất cả các dữ liệu sẽ được lưu trữ trong CSDLPT cũng như các dữ liệu không được phân tán ở các trạm trong hệ thống
Lược đồ phân đoạn :Mỗi quan hệ tổng thể có thể chia thành một vài phần không giao nhau gọi là phân đoạn. Sơ đồ phân đoạn mô tả các ánh xạ giữa các quan hệ tổng thể và các đoạn được định nghĩa trong sơ đồ phân đoạn

Lược đồ định vị: Sơ đồ định vị xác định đoạn dữ liệu nào được định vị tại trạm nào trên mạng
8/
-Chia sẽ tài nguyên
-Tính mở
-Khả năng sử lý song song
-Khả năng mở rộng hệ thống
-Khả năng thứ lỗi(phục hồi khi có sự cố và hoạt đông liên tục)
-Tin cậy và nhất quán
9/
Tương đồng là phần chia dữ liệu để xử lý.
Tăng khả năng xử lý dữ liệu
Mang Tính trong suốt dữ.
Parallel:
-Fast interconnect(truy cập nhanh)
– Homogeneous software(đồng nhất về phần mềm)
– High performance is goal(thời gian thực hi nhanh)
– Transparency is goal(tính trong suốt dữ liệu)
Distributed:
– Geographically distributed(Phân bố trên nhiều vùng ịa lý)
– Data sharing is goal (may run intoheterogeneity, autonomy)(dữ liệu được chia sẽ có thể chạy tự trị và đa dạng trên nhiều vung khác nhau)
– Disconnected operation possible(vẫn hoạt động được khi mất kết nối)



10/Shared Nothing

Cấu trúc gồm nhiều node mỗi node sở hữu hệ thống phần cứng riêng của nó như là:proccessor riêng, bộ nhớ riêng,I/O device riêng,...Những node này liên kết với nhau qua hệ thống mạng LAN hay WAN
Ứng dụng:
-Ứng dung phổ biến nhất hiện nay là data warehousing
-Ứng dụng trong phát triển wed
-Ứng dụng cho các hệ thống phân bố rộng trên các vùng địa lý khác nhau

Ưu:
-mang tính dàn trãi(triển khai trên nhiều vung địa lý)
-dễ quản lý và bảo dưỡng(mỗi node có một nhiệm vụ riêng)
-dễ dàng triển khai
Khuyết:
-Chậm trong vấn đề truyền tải dữ liệu của các node
-Cần thời gian lâu hơn để thực hiện truy vấn giũa các node không được ghép đôi lại với nhau đối với các truy vấn cần lượng dữ liệu lớn.
11/Shared Disk

12/Hybrid



13/

14/Client và Server:
Client/Server
 Server – điều khiển, lưu trữ CSDL, xử lý các truy vấn và quản lý việc khai thác tài nguyên trên mạng của các WS (Clients).
 Client – Khai thác tài nguyên qua Server(thuật ngữ client để chỉ người dùng)
Với cấu trúc client –server ta có thể phân chia nhiệm vụ cần thực hiện cho client hoăc server





15/
• Reliability(tính bền vững và độ tinh cậy của cấu trúc)
• Scalability(tính dàng trải có thể mở rộng và phát triển rộng khấp)
• Geographic distribution of data(có tể phân bố dữ liệu trên nhiều vùng địa lý,triển khai được trên các vùng cách xa nhau)
• Data “clusters”(có gom nhóm dữ liệu hay không(mặt vật lý(cluster là dạng index trên ý thức vật lý )))
• Performance(khả năng thể hiện của cấu trúc)
• Cost(chi phí)
-CPU:thời gian thực hiện truy suất
-I/O:xuất nhập dữ liệu(memory,disk,..)
-Truyền tải dữ liệu trên hệ thống mạng(đây là đặt điểm quan trong của việc chọn một cấu trúc cho việc sử dung csdl phân tán)
16/
Các loại phân manh
Phân mảnh ngang (Horizontal fragmentation – HF)
Phân mảnh ngang một quan hệ tổng thể n-bộ R là tách R thành các quan hệ con R1, R2, ..., Rk sao cho quan hệ R có thể được khôi phục lại từ các quan hệ con này bằng phép hợp: R = R1 È R2 È ... È Rk
-Phân mảnh ngang chính (primary HF) - Một quan hệ được thực hiện dựa trên các vị từ được định nghĩa trên quan hệ đó
-Phân mảnh ngang dẫn xuất (derived HF) - một quan hệ được thực hiện dựa trên các vị từ được định nghĩa trên quan hệ khác
Phân mảnh dọc (Vertical fragmentation – VF)
Phân mảnh dọc một quan hệ tổng thể n-bộ R là tách R thành các quan hệ con n-bộ R1, R2, ..., Rk sao cho quan hệ R có thể được khôi phục lại từ các quan hệ con này bằng phép nối R = R1 R2 ..., Rk
Phân mảnh hỗn hợp
Kết hợp cả phân mảnh ngang và phân mảnh dọc
Các yêu cầu phân mảnh dữ liệu:
Điều kiện đầy đủ (Completeness condition): Mỗi mục dữ liệu trong R phải có trong một hoặc nhiều mảnh Ri .Tức trong HF, các mẫu tin bất kì phải thuộc về 1 mãnh đã được phân ra.đối với VF thì một thuộc tính của R phải thuộc về 1 mãnh nào đó được phân ra.
Điều kiện tái tạo – Reconstruction condition:Từ các mảnh con có thể thực hiện được các phép toán nào đó mà kết quả của phép toán đó sẽ là quan hệ chưa phân mảnh ban đầu.
 Phân mảnh ngang:
 Phân mảnh dọc:
Điều kiện tách biệt (Disjointness condition):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 (i # k).Đối với phân mảnh ngang mục dữ liệu di là mẫu tin ,còn phân mảnh dọc là thuộc tính.
17/
18/
19/
20/
21/
Cần quan tâm đến
-Nơi chạy ứng dụng;
-Tần suất chạy ứng dụng
-Số lượng, loại và sự phân tán của các truy xuất
22/
23/
-Round robin(Chia vong)
-Hash partitioning(chia theo ham bam)
- Range partitioning(chia theo vung)

1. Các định nghĩa cơ sở dữ liệu phân tán. Các khía cạnh quan trọng trong từng định nghĩa?
CSDL phân tán là tập hợp dữ liệu logic thuộc về cùng một hệ thống nhưng trải rộng ra nhiều điểm trên mạng máy tính.
Hai vấn đề quan trọng:
- Sự phân tán dữ liệu (data distribution): dữ liệu phải được phân tán ở nhiều nơi.
- Sự tương quan luận lý (logical correlation): dữ liệu của các nơi được sử dụng chung để cùng giải quyết một vấn đề.

Ứng dụng cục bộ (local application): ứng dụng được chạy hoàn thành tại một nơi và chỉ sử dụng dữ liệu cục bộ của nơi này.
Ứng dụng toàn cục (hoặc ứng dụng phân tán) (global application / distributed application): ứng dụng được chạy hoàn thành và sử dụng dữ liệu của ít nhất hai nơi.
3. Các đặc điểm của CSDL phân tán so với CSDL tập trung. Điều khiển tập trung, độc lập dữ liệu, dư thừa dữ liệu, tính riêng biệt và bảo mật?
Đặc điểm của CSDL phân tán:
- Đáp ứng nhanh hầu hết các ứng dụng dữ liệu tại các trạm.
- Tăng cường các đơn thể ứng dụng và CSDL mà không làm cản trở người sử dụng hiện tại.
- Kiểm soát dữ liệu địa phương theo hướng hoàn thiện sự tích hợp và quản trị dữ liệu từ xa.
- Tăng cường khả năng của hệ thống lien quan đến sự dư thừa dữ liệu.
a) Điều khiển tập trung: CSDL phân tán được được điều khiển với cấu trúc phân lớp dựa vào một hệ quản trị CSDL toàn cục (có trách nhiệm trên toàn bộ CSDL phân tán) và hệ quản trị CSDL địa phương (có trách nhiệm với CSDL địa phương riêng).
b) Độc lập dữ liệu: Các chương trình không bị ảnh hưởng bởi sự thay đổi trong cấu trúc vật lý của dữ liệu. Với CSDL phân tán, có một khía cạnh mới được thêm vào trong ý niệm độc lập dữ liệu là ’trong suốt phân tán’. Với ‘trong suốt phân tán’ chúng ta có thể hiểu là các chương trình ứng dụng có thể sử dụng CSDL như là nó không được tổ chức phân tán. Vì thế sự chính xác của chương trình không bị ảnh hưởng bởi việc dich chuyển dữ liệu từ trạm này đến trạm khác. Tuy nhiên, tốc độ thực hiện của chúng bị ảnh hưởng.
c) Giảm dư thừa dữ liệu: lý do để giảm dư thừa dữ liệu:
- Sự không tương thích giữa nhiều bản sao của cùng một tập dữ liệu.
- Tiết kiệm không gian lưu trữ bằng cách loại bỏ các dư thừa. Việc giảm dư thừa dữ liệu cũng có thể đạt được băng cách chia sẻ dữ liệu, cho phép nhiều ứng dụng truy cập cùng các bản tin và bản ghi.
- Hoạt động của các chương trình ứng dụng có thể bị tăng lên khi dữ liệu được sao lại tất cả các vị trí, nơi trình ứng dụng cần nó.
- Tính thường trực của hệ thống sẽ tăng lên, bởi vì khi có lỗi xảy ra ở trạm nào đó, sẽ không dừng việc thực hiện các ứng dụng của trạm khác nếu dữ liệu đã được sao chép lại.
d) Biệt lập và bảo mật: hai khía cạnh cần được xem xét:
- Trong CSDL phân tán với một mức độ tự trị rất cao của các địa phương, người chủ dữ liệu địa phương cảm giác được bảo vệ tốt hơn vì họ có thể tự chủ thực hiện bảo vệ thay vì phụ thuộc vào người quản trị CSDL trung tâm.
- Vấn đề bảo mật là bản chất trong hệ phân tán nói chung, vì các mạng truyền thông diện rộng cho phép nhiều người cập nhật và khai thác dữ liệu nên cần được bảo vệ.
2. 5. Các nguyên nhân chính dẫn đến việc sử dụng CSDL phân tán?

- Tổ chức và kinh tế - Không tập trung.
- Các CSDL hiện tại cần kết nối với nhau: Nhiều CSDL đã tồn tại trong 1 công ty và cần được thực hiện nhiều ứng dụng toàn cục. //truy xuat du lieu o nhieu noi
- Sự lớn mạnh tăng: Có thêm các đơn vị tổ chức độc lập.
- Giảm chi phí truyền thông: Nhiều ứng dụng cục bộ làm giảm chi phí truyền thông so với CSDL tập trung.
- Hiệu suất: Cơ chế song song hóa; Phân mảnh theo ứng dụng, cực đại hóa tính cục bộ ứng dụng.
- Độ tin cậy và tính sẵn sàng: Dư thừa dữ liệu; Cần đảm bảo tính tin cậy của dữ liệu.
3. 7. Kiến trúc tham khảo dùng cho các CSDL phân tán?
Lược đồ toàn cục - Global Schema
- Xác định tất cả các dữ liệu sẽ được lưu trữ trong CSDLPT cũng như các dữ liệu không được phân tán ở các trạm trong hệ thống
- Global schema được định nghĩa theo cách như trong CSDL tập trung
- Trong mô hình quan hệ, global schema bao gồm định nghĩa của tập các quan hệ tổng thể (Globle relation)
Lược đồ phân đoạn - Fragment Schema
- Mỗi quan hệ tổng thể có thể chia thành một vài phần không giao nhau gọi là phân đoạn (fragment)
- Có nhiều cách khác nhau để thực hiện việc phân chia fragments
- Sơ đồ phân đoạn mô tả các ánh xạ giữa các quan hệ tổng thể và các đoạn được định nghĩa trong sơ đồ phân đoạn
- Các đoạn được mô tả bằng tên của quan hệ tổng thể cùng với chỉ mục đoạn. Chẳng hạn, Ri được hiểu là đoạn thứ i của quan hệ R
Lược đồ định vị - Allocation schema
- Các đoạn là các phần logic của một quan hệ tổng thể được định vị vật lý trên một hay nhiều trạm
- Sơ đồ định vị xác định đoạn dữ liệu nào được định vị tại trạm nào trên mạng
- Tất cả các đoạn được liên kết với cùng một quan hệ tổng thể R và được định vị tại cùng một trạm j cấu thành ảnh vật lý quan hệ tổng thể R tại trạm j
- Do đó ta có thể ánh xạ một-một giữa một ảnh vật lý và một cặp (quan hệ tổng thể, trạm)
- Các ảnh vật lý có thể chỉ ra bằng tên của một quan hệ tổng thể và một chỉ mục trạm
- Ký hiệu Ri để chỉ đoạn thứ i của quan hệ tổng thể R
- Ký hiệu Rj để chỉ ảnh vật lý của quan hệ tổng thể R tại trạm j
- Tương tự như vậy, bản sao của đoạn i thuộc quan hệ R tại trạm j được ký hiệu là Rij

Các đọan và hình ảnh tổng thể của 1 QH tổng thể

Các yếu tố suy ra từ kiểu kiến trúc trên
- Tách rời khái niệm phân đoạn dữ liệu với khái niệm định vị dữ liệu
- Biết được dữ liệu dư thừa
- Độc lập với các DBMS địa phương
- Ba yếu tố này tương ứng với ba mức trong suốt tương ứng
Trong suốt phân mảnh (phân đọan)
- Fragmentation transparency
- Lược đồ toàn cục (global schema)
- Quan hệ toàn cục
Cơ sở dữ liệu phân tán trong suốt hoàn toàn. Làm việc trên CSDLPT hoàn toàn giống như làm việc với cơ sở dữ liệu tập trung.
Trong suốt vị trí (định vị dữ liệu)
- Location transparency
- Lược đồ phân mảnh (fragmentation schema)
- Mảnh (fragment)
Làm việc ở lược đồ phân đoạn. Ứng dụng phải xác định truy nhập vào phân đoạn nào của CSDLPT. Có thể cùng một lúc truy nhập vào nhiều phân đoạn của CSDLPT để tận dụng khả năng song song của CSDLPT
Trong suốt ánh xạ cục bộ (địa phương)
- Local mapping transparency
- Lược đồ định vị (allocation schema)
- Quan hệ cục bộ (local relation)
Làm việc ở lược đồ định vị. Các ứng dụng phải xác định truy nhập vào phân đoạn nào và phân đoạn đó được đặt tại vị trí nào trong hệ cơ sở dữ liệu phân tán. Nhìn thấy quan hệ cục bộ, ko nhìn thấy CSDL vật lý.
Trong suốt ánh xạ cục bộ (địa phương)
- Ứng dụng tham chiếu đến các đối tượng có các tên độc lập từ các hệ thống cục bộ địa phương.
- Ứng dụng được cài đặt trên một hệ thống không đồng nhất nhưng được sử dụng như một hệ thống đồng nhất.


Trong suốt nhân bản
- Replication transparency
- Bản nhân (replica)
- Độc lập với các DBMS địa phương
Không trong suốt
- No transparency
- Lược đồ ánh xạ cục bộ (local mapping schema)
Do tính không đồng nhất của Hệ CSDLPT các ứng dụng thông thường phải xây dựng các hàm và cài đặt các hàm phụ trợ này tại các địa phương. Sau đó, chương trình ứng dụng sẽ kích hoạt các hàm phụ trợ này từ xa thông qua mạng để thay thế cho việc chạy các lệnh SQL trên từng hệ quản trị cơ sở dữ liệu địa phương.
4. 36.Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Biểu thức chuẩn tắc của truy vấn phân mảnh?
• Thay thế các quan hệ toàn cục xuất hiện trong biểu thức bởi đại số quan hệ tái tạo các quan hệ toàn cục từ các mảnh.
• Sử dụng tính phân phối của phép chọn và phép chiếu đối với phép hợp và phép kết để phân phối xử lý đến các phân đoạn.

37. Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Các phép biến đổi tương đương đại số quan hệ định tính? Các qui tắc?

*Các phép biến đổi tương đương:
2 quan hệ R_1 và R_2 là tương đương nếu các bộ của chúng biểu diễn cùng ánh xạ từ các tên thuộc tính vào các giá trị, ngay cả khi thứ tự của các thuộc tính là khác nhau.
2 biểu thức đại số quan hệ E_1 và E_2 là tương đương, ký hiệu là E_1↔E_2 hoặc E_1≡E_2 nếu thay thế cùng các quan hệ cho các tên giống nhau trong 2 biểu thức, thì chũng có kết quả tương đương.
*Các qui tắc:
Ký hiệu 1 quan hệ định tính là 1 cặp [R:q_R], trong đó R là 1 quan hệ được gọi là thân (body) của quan hệ định tính và q_R là 1 vị từ được gọi là vị từ định tính của quan hệ định tính.
Qui tắc 1
σ_F [R:q_R] ⟹ [σ_F R: F & q_R]
Thực hiện phép chọn trên 1 quan hệ định tính, ta được quan hệ định tính có vị từ định tính là giao của vị từ định tính ban đầu và điều kiện chọn.
Qui tắc 2
π_A [R:q_R] ⟹ [π_A R:q_R]
Thực hiện phép chiếu trên 1 quan hệ định tính, được 1 quan hệ có vị từ định tính chính là vị từ định tính ban đầu.
Qui tắc 3
[R:q_R] × [S:q_S] ⟹[R × S : q_R & q_S]
Tích Decac của 2 quan hệ là quan hệ mới có vị từ định tính là giao của 2 quan hệ đầu.
Qui tắc 4
[R:q_R] - [S:q_S] ⟹[R - S : q_R]
Phép trừ giữa 2 quan hệ được 1 quan hệ mới có vị từ định tính là vị từ của quan hệ bị trừ.
Qui tắc 5
[R:q_R] ∪ [S:q_S] ⟹[R ∪ S : q_R OR q_S]
Hợp của 2 quan hệ là quan hệ mới có vị từ định tính là hợp của các vị từ.
Qui tắc 6
[R:q_R] ►◄〖_F〗 [S:q_S] ⟹[R►◄〖_F〗S : q_R & q_S & F]
Phép kết của 2 quan hệ là 1 quan hệ có vị từ định tính là giao của 2 vị từ định tính ban đầu và điều kiện kết.
Qui tắc 7
[R:q_R] ►<_F [S:q_S] ⟹[R►<_FS: q_R & q_S & F]
Phép kết trái của 2 quan hệ là 1 quan hệ có vị từ định tính là giao của 2 vị từ định tính ban đầu và điều kiện kết.
5. Mô hình client-server
Mô hình client-server là một mô hình nổi tiếng trong mạng máy tính, được áp dụng rất rộng rãi và là mô hình của mọi trang web hiện có. Ý tưởng của mô hình này là máy con (đóng vài trò là máy khách) gửi một yêu cầu (request) để máy chủ (đóng vai trò người cung ứng dịch vụ), máy chủ sẽ xử lý và trả kết quả về cho máy khách. Các chương trình server này chấp nhận tất cả các yêu cầu hợp lệ đến từ mọi nơi trên mạng, sau đó nó thi hành dịch vụ và trả kết quả về máy yêu cầu. Một chương trình được coi là client khi nó gửi các yêu cầu tới máy có chương trình server và chờ đợi câu trả lời từ server.
Ưu và nhược điểm chính: Có thể nói rằng với mô hình client/server thì mọi thứ dường như đều nằm trên bàn của người sử dụng, nó có thể truy cập dữ liệu từ xa (bao gồm các công việc như gửi và nhận file, tìm kiếm thông tin, ...) với nhiều dịch vụ đa dạng mà mô hình cũ không thể làm được. Mô hình client/server cung cấp một nền tảng lý tưởng cho phép tích hợp các kỹ thuật hiện đại như mô hình thiết kế hướng đối tượng, hệ chuyên gia, hệ thông tin địa lý (GIS) ... Một trong những vấn đề nảy sinh trong mô hình này đó là tính an toàn và bảo mật thông tin trên mạng. Do phải trao đổi dữ liệu giữa 2 máy ở 2 khu vực khác nhau cho nên dễ dàng xảy ra hiện tượng thông tin truyền trên mạng bị lộ

Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Biểu thức chuẩn tắc của truy vấn phân mảnh?
Thay thế các quan hệ toàn cục xuất hiện trong biểu thức bởi đại số quan hệ tái tạo các quan hệ toàn cục từ các mảnh.
Sử dụng tính phân phối của phép chọn và phép chiếu đối với phép hợp và phép kết để phân phối xử lý đến các phân đoạn.

Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Các phép biến đổi tương đương đại số quan hệ định tính? Các qui tắc?
Các phép biến đổi tương đương:
2 quan hệ R_1 và R_2 là tương đương nếu các bộ của chúng biểu diễn cùng ánh xạ từ các tên thuộc tính vào các giá trị, ngay cả khi thứ tự của các thuộc tính là khác nhau.
2 biểu thức đại số quan hệ E_1 và E_2 là tương đương, ký hiệu là E_1E_2 hoặc E_1≡E_2 nếu thay thế cùng các quan hệ cho các tên giống nhau trong 2 biểu thức, thì chũng có kết quả tương đương.
Các qui tắc:

Quan hệ định tính (Qualified relation) là 1 quan hệ được mở rộng bởi 1 vị từ định tính.
Ký hiệu 1 quan hệ định tính là 1 cặp [R:q_R], trong đó R là 1 quan hệ được gọi là thân (body) của quan hệ định tính và q_R là 1 vị từ được gọi là vị từ định tính của quan hệ định tính.


Qui tắc 1
σ_F[R:q_R] ⟹ [σ_F R: F &q_R]
Thực hiện phép chọn trên 1 quan hệ định tính, ta được quan hệ định tính có vị từ định tính là giao của vị từ định tính ban đầu và điều kiện chọn.
Qui tắc 2
π_A[R:q_R] ⟹ [π_AR:q_R]
Thực hiện phép chiếu trên 1 quan hệ định tính, được 1 quan hệ có vị từ định tính chính là vị từ định tính ban đầu.
Qui tắc 3
[R:q_R] × [S:q_S]⟹[R×S : q_R&q_S]
Tích Decac của 2 quan hệ là quan hệ mới có vị từ định tính là giao của 2 quan hệ đầu.
Qui tắc 4
[R:q_R] - [S:q_S] ⟹[R - S : q_R]
Phép trừ giữa 2 quan hệ được 1 quan hệ mới có vị từ định tính là vị từ của quan hệ bị trừ.
Qui tắc 5
[R:q_R] ∪[S:q_S] ⟹[R ∪ S : q_R OR q_S]
Hợp của 2 quan hệ là quan hệ mới có vị từ định tính là hợp của các vị từ.
Qui tắc 6
[R:q_R] ►◄_F[S:q_S] ⟹[R►◄_FS : q_R&q_S& F]
Phép kết của 2 quan hệ là 1 quan hệ có vị từ định tính là giao của 2 vị từ định tính ban đầu và điều kiện kết.
Qui tắc 7
[R:q_R] ►<_F[S:q_S] ⟹[R►<_FS: q_R&q_S& F]
Phép kết trái của 2 quan hệ là 1 quan hệ có vị từ định tính là giao của 2 vị từ định tính ban đầu và điều kiện kết.

Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Các tiêu chuẩn dùng chung để đơn giản hóa các biểu thức trên lược đồ phân mảnh và tập trung.
Chuyển cây truy vấn thành biểu thức đại số quan hệ
Chuyển thành 1 biểu thức tương đương hiệu quả hơn sử dụng Heuristic
Các luật biến đổi Heuristic:
Thực hiện phép chọn càng sớm càng tốt
Thay thế phép tích Decarte bằng phép kết
Nếu có nhiều phép kết, thực hiện phép kết có điều kiện khắt khe trước
Dùng phép chiếu để loại những thuộc tính không cần thiết trước
(theo Slide csdl1 )

Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Tối ưu hóa các phép kết giữa các quan hệ được phân mảnh ngang.
Dùng tiêu chuẩn 4:
Sử dụng đại số quan hệ định tính để định trị vị từ định tính các toán hạng của nó. Thay thế các cây con, bao gồm phép kết và các toán hạng bởi quan hệ rỗng nếu vị từ định tính của kết quả phép kết bị mâu thuẫn
Giải pháp 1: nếu có nhiều mảnh được ghép với nhau.
R►◄_FS = (U_i R_i)►◄_F(U_j S_j)
Giải pháp 2: nếu có 1 số cặp mảnh được ghép với nhau
R►◄_FS = U_ij (R_i►◄_F S_j)

Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Sử dụng phép suy diễn cho các phép đơn giản hóa. Đơn giản hóa quan hệ phân mảnh dọc. Chương trình nửa kết.
Sử dụng phép suy diễn cho các phép đơn giản hóa
Mục đích:
Mâu thuẫn giữa các điều kiện chọn của các truy vấn và các vị từ định tính của các mảnh.
Bộ cứng minh định lí (theorem prover)???
Ví dụ:
Xét truy vấn Q1- Cho biết mã của các nàh cung cấp có đơn hàng cung cấp ở phía Bắc.
Cây toán tử của Q1
Giả sử: (1) Phía Bắc chỉ bao gồm các phòng ban có mã từ 1 đến 10.
(2) Tất cả các đơn hàng của các phòng ban có mã từ 1 đến 10 đều gửi đến các nhà cung cấp ở San Francisco
Từ (1), có thể viết các điều suy diễn như sau:
Area = ‘NORTH’⟹not (10 < deptnum ≤ 20)
Area = ‘NORTH’⟹not (deptnum>20)
Area = ‘NORTH’⟹deptnum≤10
Từ (2): deptnum ≤10⟹not (snum= supplier.snum and supplier.city = ‘LA’)



Đơn giản hóa quan hệ phân mảnh dọc
Mục đích:
Xác định 1 tập con bao gồm các mảnh đủ để trả lời truy vấn, sau đó loại bỏ tất cả các mảnh khác từ biểu thức truy vấn và các phép kết được dùng trong phép biến đổi ngược của lược đồ phân mảnh ngược của lược đồ phân mảnh để tái tạo các quan hệ toàn cục.
Ví dụ:
Truy vấn Q_5, hãy cho biết tên và tiền lương của các nhân viên:
Q_5: π_(name,sal)emp


Chương trình nửa kết.
Mục đích:
1 phép kết có thể được thực hiện bởi 1 chương trình nửa kết (semi-join program) trong đó có phép nửa kết.
Ví dụ:
Xét phép kết bằng (equi-join) R ►◄_(A=B)S,trong đó A và B là các thuộc tính (hoặc tập các thuộc tính) của R và S, chương trình nửa kết ứng với phép kết này là:
S►◄_(A=B)(R►<_(A=B) π_(S.B))

Biến đổi truy vấn toàn cục thành truy vấn phân mảnh. Gom nhóm phân tán và định trị hàm kết hợp. Mở rộng đại số quan hệ. Các đặc tính của phép gom nhóm.
Gom nhóm phân tán và định trị hàm kết hợp.
Tiêu chuẩn 6: Để phân tán việc gom nhóm và định trị hàm kết hợp xuất hiện trong 1 truy vấn toàn cục, các phép hợp (biểu diễn việc tập hợp các mảnh) phải được đẩy lên phía trên phép gom nhóm tương ứng

Mở rộng đại số quan hệ??????
Các đặc tính của phép gom nhóm:
Tính phân phối đối với phép hợp:
Ψ_(G,AF)(R_1ᴜR_2) →(Ψ_(G,AF) R_1)ᴜ(Ψ_(G,AF) R_2)
Điều kiện cần và đủ: mỗi nhóm G_i hoặc được chứa hoặc không được giao nhau với mọi toán hạng R_j∀i,j : (G_i⊆R_j) hoặc (G_i∩R_j=ф)
Mỗi nhóm phải được chứa hoàn toàn trong 1 mảnh.
Thực hiện phép gom nhóm trên các toán hạng của phép hợp và sau đó hợp các kết quả này.

Câu 24:Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang. Các yêu cầu thông tin?
Phân mảnh ngang một quan hệ tổng thể n-bộ R là tác R thành các quan hệ con n-bộ R1, R2, .., Rk sao cho quan hệ R có thể được khôi phục lại từ các quan hệ con này bằng phép hợp R = R1U R2U … U Rk.
Có 2 loại phân mảnh ngang:
Phân mảnh ngang chính: phân mảnh ngang chính của một quan hệ được thực hiện dựa trên các vị từ được định nghĩa trên quan hệ đó.
Phân mảnh ngang dẫn xuất: phân mảnh ngang dẫn xuất của một quan hệ được thực hiện dựa trên các vị từ được định nghĩa trên quan hệ khác.
Các yêu cầu về thông tin:
Các yếu tố trong thiết kế tối ưu ảnh hưởng đến các quyết định phân tán:
Tổ chức luận lý của CSDL
Vị trí của các ứng dụng
Các đặc điểm truy xuất CSDL của các ứng dụng.
Các đặc tính của các hệ thống máy tính tại mỗi nơi
Các loại thông tin để thiết kế phân tán
Thông tin về CSDL
Thông tin về ứng dụng
Thông tin về mạng truyền thông
Thông tin về hệ thống máy tính
Câu 25:Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang chính. Các định nghĩa?
Phân mảnh ngang chính của một quan hệ là phân mảnh ngang trong đó việc phân mảnhđược thực hiện dựa trên các vị từ được định nghĩa trên quan hệ đó.
Mảnh ngang chính được xác định bằng phép chọn trên quan hệ toàn cục.
Ri = σFi(R); 1 ≤ i ≤ n
Filà điều kiện chọn của mảnh Ri
Nếu Fiở dạng chuẩn giao thì nó là một vị từgiao tối thiểu mi
Tính đúng đắn: mỗi bộ của quan hệ toàn cục được đưa vào trong một và chỉ một mảnh.
Xác định phân mảnh ngang chính của một quan hệ toàn cục là xác định một tập các vị từ chọn (selection predicate) đầy đủ vàtách biệt.
Mảnh ngang (horizontal fragment) hoặc mảnh giao tối thiểu (minterm fragment) Ri bao gồm tất cả các bộ của R thỏa mãn vị từ giao tối thiểu mi.
Câu 26:Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang chính. Giải thuật COM_MIN?
(books_136)
Bước 1: Thuật toán tìm tập vị từ đầu đủ và cực tiểu.
Quy tắc cơ bản về DD&CT: Một quan hệ hoặc một mảnh được phân hoạch thành ít nhất hai phần và chúng được truy xuất khác nhau bởi ít nhất một ứng dụng.
Ta gọi fi của PR là mảnh fi được sinh ra từ một vị từ hội sơ cấp trong PR
Thuật toán COM_MIN
Đầu vào: R là quan hệ; PR là tập vị từ đơn giản.
Đầu ra: PR’ là tập vị từ đơn giản và cực tiểu.
Begin
Tìm một vị từ pi∈ PR sao cho pi phân hoạch R theo quy tắc cơ bản DD&CT;
PR’ = {pi};
PR = PR – {pi};
F = {fi} / * fi là mảnh hội sơ cấp sinh ra bởi pi*
Do
Begin
Tìm một pj∈ PR sao chopj phân hoạch mảnh fk của PR’ theo quy tắc cơ bản DD&CT;
PR’ = PR’ U {pj};
PR = PR – {pj};
F = F U {fj}; /* fj sinh bởi pj */
If∃pk∈ PR’ là một vị từ không có lien đới then
Begin
PR’ = PR’ – {pk};
F = F-{fk};
End
End
Until PR’ là đầy đủ
End
Câu 27: Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang chính. Giải thuật PHORIZONTAL?
Thuật toán PHORIZONTAL
Đầu vào: R là một quan hệ
Đầu ra: M là tập các vị từ hội sơ cấp có nghĩa.
Begin
PR’ = COM_MIN(R, PR);
Tính tập M các vị từ hội sơ cấp từ PR’;
Tính tập các I các phép kéo theo giữa các pi∈ PR;
For mỗi mi∈ M do
If mi mẫu thuẫn với I then M = M – {mi};
End

Câu 28: Thiết kế phân mảnh CSDL phân tán. Phân mảnh ngang dẫn xuất? Đồ thị kết? Phân loại?

Thank lớp trưởng nhiều nha!