Bài Tập môn Hệ Thống Phân Tán

Bài Tập môn Hệ Thống Phân Tán

Câu 1: Anh(Chị) hãy giải thích định nghĩa cơ sở dữ liệu phân tán và giải thích định nghĩa?

Định nghĩa CSDL phân tán:

Cơ sở dữ liệu phân tán nói riêng và hệ phân tán nói chung là một lĩnh vực được nghiên cứu từ lâu nhưng gần đây do sự phát triển nhanh chóng của công nghệ truyền tin và sự bành trướng của internet.

Một CSDL phân tán là một tập hợp nhiều CSDL có liên đới logic và được phân bố rải rác trên nhiều máy trong một mạng máy tính

Giải thích định nghĩa:

• Về mặt trực quan thì nghĩa đen của cụm từ cơ sở dữ liệu phân tán chưa 2 cụm từ: cơ sở dữ liệu và phân tán.
• Việc phân tán ở đây chúng ta hiểu là phân tán thông tin và các thông tin đó được lưu trữ trên mạng máy tính
• Tính chất phân tán: Toàn bộ dữ liệu của CSDL phân tán không được lưu trữ ở một nơi mà cư trú trên nhiều máy trạm thuộc mạng máy tính, điều này giúp chúng ta phân biệt CSDL phân tán với CSDL tập trung đơn lẻ.
• Tương quan logic: Toàn bộ dữ liệu của CSDL phân tán có một số thuộc tính ràng buộc chúng với nhau, điều này chúng ta có thể phân biệt một CSDL phân tán với 1 tập hợp CSDL cục bộ hoặc các tệp cư trú tại các vị trí khác nhau trong một mạng máy tính.
• Bản chất kết hợp:CSDL phân tán = CSDL + Mạng máy tính. Nó là sự hợp nhất của hai hướng tiếp cận: quản lý dữ liệu (CSDL) và truyền thông (mạng máy tính).

Câu 2:

I.Giới thiệu Phân mảnh ngang

a. Khái niệm Phân mảnh ngang

Phân mảnh ngang là kỹ thuật chia một quan hệ (bảng) thành nhiều phân mảnh dựa trên các bộ (hàng) của quan hệ đó. Mỗi phân mảnh là một tập con các bộ, nhưng vẫn giữ nguyên cấu trúc thuộc tính (cột). Mục tiêu là phân tán dữ liệu để tối ưu hóa truy vấn và tăng hiệu suất hệ thống phân tán.

b. Lý do phân mảnh

• Các ứng dụng thường chỉ truy xuất một tập con của quan hệ, không phải toàn bộ dữ liệu.
• Việc phân rã một quan hệ thành nhiều mảnh cho phép xử lý song song nhiều giao dịch, giảm thời gian truy vấn.
• Phân mảnh giúp tăng mức độ hoạt động đồng thời và giảm lưu lượng truyền dữ liệu trong hệ thống.

c. Các quy tắc phân mảnh đúng đắn

• Tính đầy đủ (Completeness): Hợp tất cả các phân mảnh phải bằng quan hệ gốc.
• Tính tái thiết được (Reconstruction): Có thể tái tạo quan hệ ban đầu từ các phân mảnh.
• Tính tách biệt (Disjointness): Các phân mảnh không được chồng lấn (mỗi bộ chỉ thuộc một phân mảnh).

d. Các loại phân mảnh

• Phân mảnh ngang nguyên thủy (Primary Horizontal Fragmentation): Dựa trên điều kiện chọn trực tiếp từ quan hệ gốc.
• Phân mảnh ngang dẫn xuất (Derived Horizontal Fragmentation): Dựa trên quan hệ với bảng khác, tức là phân mảnh một quan hệ dựa vào vị trí được định nghĩa trên quan hệ khác.

e. Yêu cầu thông tin của phân mảnh ngang

Để thiết kế phân mảnh tối ưu, cần thu thập thông tin:

• Thông tin về CSDL:

Mục đích: Để biết cấu trúc bảng, dữ liệu, quan hệ giữa các bảng.

Thông tin về CSDL muốn nói đến là lược đồ toàn cục và quan hệ gốc, các quan hệ con. Trong ngữ cảnh này, chúng ta cần biết được các quan hệ sẽ kết lại với nhau bằng phép nối hay bằng phép tính khác. Với mục đích phân mảnh dẫn xuất, các vị từ được định nghĩa trên quan hệ khác, ta thường dùng mô hình thực thể – liên hệ (entity–relationship model), vì trong mô hình này các mối liên hệ được biểu diễn bằng các đường nối có hướng (các cung) giữa các quan hệ có liên hệ với nhau qua một nối.

• Thông tin ứng dụng:

Mục đích: Để hiểu cách truy vấn, tần suất truy cập, điều kiện lọc dữ liệu.

Để phân tán ngoài thông tin định lượng Card (R) ta còn cần thông tin định tính cơ bản gồm các vị từ được dùng trong các câu vấn tin. Lượng thông tin này phụ thuộc bài toán cụ thể.

Nếu không thể phân tích được hết tất cả các ứng dụng để xác định những vị từ này thì ít nhất cũng phải nghiên cứu được các ứng dụng “quan trọng” nhất.

Vậy chúng ta xác định các vị từ đơn giản (simple predicate). Cho quan hệ R (A₁, A₂, …, Aₙ), trong đó Aᵢ là một thuộc tính được định nghĩa trên một miền biến thiên D(Aᵢ) hay Dᵢ.

Một vị từ đơn giản P được định nghĩa trên R có dạng:

P: Aᵢ θ Value

Trong đó θ ∈ {=, ≠, <, ≤, >, ≥} và value được chọn từ miền biến thiên của Aᵢ (value ∈ Dᵢ).

Như vậy, cho trước lược đồ R, các miền trị Dᵢ, chúng ta có thể xác định được tập tất cả các vị từ đơn giản Pᵣ trên R.

Vậy Pᵣ = {P: Aᵢ θ Value}. Tuy nhiên trong thực tế ta chỉ cần những tập con thực sự của Pᵣ.

Cho một tập Pᵣ = {pᵢ₁, pᵢ₂, …, pᵢₘ} là các vị từ đơn giản trên quan hệ Rᵢ, tập các vị từ hội sơ cấp Mᵢ = {m₁, m₂, …, m_z} được định nghĩa là:

Mᵢ = {mⱼ | mⱼ = ∧ pᵢₖ* với 1 ≤ k ≤ m, 1 ≤ j ≤ z}

Trong đó pᵢₖ* = pᵢₖ hoặc pᵢₖ* = ¬pᵢₖ. Vi thế mỗi vị từ đơn giản có thể xuất hiện trong vị từ hội sơ cấp dưới dạng tự nhiên hoặc dạng phủ định.

f. Ví dụ minh họa

Giả sử có bảng SinhVien gồm các thông tin: MaSV, HoTen, NgaySinh, Khoa, DiemTB.

Bảng này chứa dữ liệu của sinh viên toàn trường.

Để tối ưu truy vấn theo khoa, ta thực hiện phân mảnh ngang dựa trên thuộc tính Khoa:

• SinhVien_CNTT: chứa các sinh viên thuộc khoa Công nghệ thông tin.
• SinhVien_KinhTe: chứa các sinh viên thuộc khoa Kinh tế.
• SinhVien_XayDung: chứa các sinh viên thuộc khoa Xây dựng.

Mỗi phân mảnh giữ nguyên cấu trúc cột nhưng chỉ chứa các bộ thỏa điều kiện Khoa = ....

Nhờ vậy:

• Khi ứng dụng khoa CNTT truy vấn, chỉ cần truy xuất phân mảnh SinhVien_CNTT, không phải toàn bộ bảng.
• Giảm chi phí truyền dữ liệu và tăng tốc độ xử lý.

II.Bài tập

Xét quan hệ Duan (MaDA, TenDA, Ngansach, Diadiem) gồm các dữ liệu sau:

a) Vị từ đơn giản có thể định nghĩa trên quan hệ Duan:

Theo TenDA:

• p1: TenDA = “Thiết bị đo đạc”
• p2: TenDA = “Xây dựng nhà”
• p3: TenDA = “Chăn nuôi”
• p4: TenDA = “Khai thác”
• p5: TenDA = “Trồng trọt”

Theo ngân sách:

• p6: Ngansach <= 30000
• p7: Ngansach ∧>30000

b) Các vị từ hội sơ cấp có thể định nghĩa được trên quan hệ Duan:

• m1: TenDA= “Thiết bị đo đạc” ∧ Ngansach > 30000
• m2: TenDA= ¬( “Thiết bị đo đạc”) ∧ Ngansach > 30000
• m3: TenDA= “Thiết bị đo đạc” ∧ Ngansach <= 30000
• m4: TenDA= ¬( “Thiết bị đo đạc”) ∧ Ngansach <= 30000
  
• m5: TenDA= “Xây dựng nhà” ∧ Ngansach > 30000
• m6: TenDA= ¬( “Xây dựng nhà”) ∧ Ngansach > 30000
• m7: TenDA= “Xây dựng nhà” ∧ Ngansach <= 30000
• m8: TenDA= ¬( “Xây dựng nhà”) ∧ Ngansach <= 30000
• m9: TenDA= “Chăn nuôi” ∧ Ngansach > 30000
• m10: TenDA= ¬( “Chăn nuôi”) ∧ Ngansach > 30000
• m11: TenDA= “Chăn nuôi” ∧ Ngansach <= 30000
• m12: TenDA= ¬( “Chăn nuôi”) ∧ Ngansach <= 30000
  
• m13: TenDA= “Khai thác” ∧ Ngansach > 30000
• m14: TenDA= ¬( “Khai thác”) ∧ Ngansach > 30000
• m15: TenDA= “Khai thác” ∧ Ngansach <= 30000
• m16: TenDA= ¬( “Khai thác”) ∧ Ngansach <= 30000
• m17: TenDA= “Trồng trọt” ∧ Ngansach > 30000
• m18: TenDA= ¬( “Trồng trọt”) ∧ Ngansach > 30000
• m19: TenDA= “Trồng trọt” ∧ Ngansach <= 30000
• m20: TenDA= ¬( “Trồng trọt”) ∧ Ngansach <= 30000

c) Độ tuyến của các hội sơ cấp

Nhóm Thiết bị do đạc:

• m₁: TenDA = "Thiết bị do đạc" ∧ Ngansach > 30000 → Độ tuyến = 1 (P₁ thỏa)
• m₂: TenDA = ¬("Thiết bị do đạc") ∧ Ngansach > 30000 → Độ tuyến = 1 (P₂ thỏa)
• m₃: TenDA = "Thiết bị do đạc" ∧ Ngansach ≤ 30000 → Độ tuyến = 0 (không có)
• m₄: TenDA = ¬("Thiết bị do đạc") ∧ Ngansach ≤ 30000 → Độ tuyến = 3 (P₃, P₄, P₅ thỏa)

Nhóm Xây dựng nhà:

• m₅: TenDA = "Xây dựng nhà" ∧ Ngansach > 30000 → Độ tuyến = 1 (P₂ thỏa)
• m₆: TenDA = ¬("Xây dựng nhà") ∧ Ngansach > 30000 → Độ tuyến = 1 (P₁ thỏa)
• m₇: TenDA = "Xây dựng nhà" ∧ Ngansach ≤ 30000 → Độ tuyến = 0 (không có)
• m₈: TenDA = ¬("Xây dựng nhà") ∧ Ngansach ≤ 30000 → Độ tuyến = 3 (P₃, P₄, P₅ thỏa)

Nhóm Chăn nuôi:

• m₉: TenDA = "Chăn nuôi" ∧ Ngansach > 30000 → Độ tuyến = 0 (không có)
• m₁₀: TenDA = ¬("Chăn nuôi") ∧ Ngansach > 30000 → Độ tuyến = 2 (P₁, P₂ thỏa)
• m₁₁: TenDA = "Chăn nuôi" ∧ Ngansach ≤ 30000 → Độ tuyến = 1 (P₃ thỏa)
• m₁₂: TenDA = ¬("Chăn nuôi") ∧ Ngansach ≤ 30000 → Độ tuyến = 2 (P₄, P₅ thỏa)

Nhóm Khai thác:

• m₁₃: TenDA = "Khai thác" ∧ Ngansach > 30000 → Độ tuyến = 0 (không có)
• m₁₄: TenDA = ¬("Khai thác") ∧ Ngansach > 30000 → Độ tuyến = 2 (P₁, P₂ thỏa)
• m₁₅: TenDA = "Khai thác" ∧ Ngansach ≤ 30000 → Độ tuyến = 1 (P₄ thỏa)
• m₁₆: TenDA = ¬("Khai thác") ∧ Ngansach ≤ 30000 → Độ tuyến = 2 (P₃, P₅ thỏa)

Nhóm Trồng trọt:

• m₁₇: TenDA = "Trồng trọt" ∧ Ngansach > 30000 → Độ tuyến = 0 (không có)
• m₁₈: TenDA = ¬("Trồng trọt") ∧ Ngansach > 30000 → Độ tuyến = 2 (P₁, P₂ thỏa)
• m₁₉: TenDA = "Trồng trọt" ∧ Ngansach ≤ 30000 → Độ tuyến = 1 (P₅ thỏa)
• m₂₀: TenDA = ¬("Trồng trọt") ∧ Ngansach ≤ 30000 → Độ tuyến = 2 (P₃, P₄ thỏa)

d) Phân mảnh ngang cho quan hệ Duan

• F1 = σ TenDA = “Thiết bị đo đạc”∧ Ngansach> 30000 (Duan)

• F2= σ TenDA = “Xây dựng nhà ”∧ Ngansach> 30000 (Duan)

• F3 = σ TenDA = “Chăn nuôi ”∧ Ngansach <= 30000 (Duan)

• F4 = σ TenDA = “Khai thác”∧ Ngansach <= 30000 (Duan)

• F5 = σ TenDA = “Trồng trọt ”∧ Ngansach <= 30000 (Duan)