Trước tiên, chúng ta sẽ xét hai loại phân mảnh này một cách riêng biệt và sau đó xét sự phân mảnh phức tạp hơn có thể có được bằng cách áp dụng sự kết hợp của hai loại này.
Trong tất cả các loại phân mảnh, một mảnh có thể được xác định bởi một biểu thức trong một ngôn ngữ CSDL quan hệ (ở đây, chúng ta sẽ dùng đại số quan hệ) mà các quan hệ toàn cục là toán hạng và tạo ra kết quả là một mảnh. Ví dụ, nếu một quan hệ toàn cục NV chứa dữ liệu của các nhân viên, một mảnh chỉ chứa dữ liệu của các nhân viên có chức vụ là “Trưởng phòng” có thể được xác định rò bằng một phép chọn (selection opration) trên quan hệ toàn cục CV= “Trưởng phòng” (NV) ).
Trong chuẩn hoá dữ liệu, chúng ta có một số quy tắc để đảm bảo tính nhất quán
của CSDL. Lưu ý quan trọng là việc phân mảnh dữ liệu nhằm để phân tán dữ liệu (đặc biệt là phân mảnh dọc) tương tự với việc chuẩn hóa các quan hệ. Do đó, chúng ta có thể định nghĩa các quy tắc phân mảnh tương tự như các nguyên lý chuẩn hoá dữ liệu. Phân mảnh dữ liệu phải thoả mãn ba quy tắc sau đây để đảm bảo CSDL không bị thay đổi ngữ nghĩa trong quá trình phân mảnh. Các quy tắc này được gọi là điều kiện đúng đắn (correctness condition).
2.1.1. Điều kiện đúng đắn để phân mảnh dữ liệu
1) Điều kiện đầy đủ (completnees condition)
Nếu một quan hệ R được phân rã thành các mảnh R1, R2, …, Rn , mỗi mục dữ liệu (data item) có thể được tìm thấy trong một hoặc nhiều mảnh Ri. Đặc tính này giống với đặc tính phân rã bảo toàn nội dung (lossless decompostion) của chuẩn hoá dữ liệu và cũng quan trọng trong việc phân mảnh, bởi nó bảo đảm dữ liệu trong một quan hệ toàn cục được ánh xạ vào trong các mảnh mà không bị mất.
- Mục dữ liệu (item data) trong:
+ phân mảnh ngang là một bộ (tuple)
+ phân mảnh dọc là một thuộc tính (property)
- Điều kiện:
+ Phân mảnh ngang:
u R, i[1 , n ]: u Ri
+ Phân mảnh dọc:
A Attr(R), i [1,n]: AAttr(Ri) với Attr(R) là tập thuộc tính của R.
2) Điều kiện tái tạo (recontruction condition)
Nếu một quan hệ R được phân rã thành các mảnh R1, R2, …, Rn, luôn luôn có thể xác định một phép toán quan hệ sao cho:
R = Ri , Ri FR
Phép toán sẽ khác nhau đối với mỗi loại phân mảnh khác nhau; tuy nhiên, điều quan trọng là nó phải được xác định. Trong trường hợp phân mảnh ngang, phép toán
là phép hợp ( ), trong trường hợp phân mảnh dọc, phép toán ( ) là phép kết nối ( ).
- Phân mảnh ngang:
R = R1 R2 … Rn
- Phân mảnh dọc:
R = R1 R2 …Rn
Tính tái tạo (reconstructability) của quan hệ từ các mảnh của nó bảo đảm các ràng buộc về phụ thuộc dữ liệu sẽ được bảo toàn. Trong thực tế, chỉ có các mảnh được chứa trong CSDL phân tán, và quan hệ toàn cục phải được tạo lại thông qua phép toán này, nếu cần.
3) Điều kiện tách biệt (disjointness condition)
Nếu một quan hệ R được phân mảnh ngang thành các mảnh R1, R2,…, Rn và 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). Điều kiện này bảo đảm các mảnh ngang là tách biệt nhau. tức là:
i k và i , k [1,n]: Ri Rk = .
Nếu quan hệ R được phân mảnh dọc, thông thường các thuộc tính khoá chính đều có trong tất cả các mảnh của nó; điều kiện này thường bị vi phạm. Điều kiện tách biệt bảo đảm việc nhân bản dữ liệu có thể được điều khiển một cách tường minh ở mức định vị (allocation level).
2.1.2. Phân mảnh ngang
1) 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ột mảnh ngang (horizontal fragment).
Rò ràng, điều này là có ích trong các CSDL phân tán, mỗi tập hợp con có thể chứa các dữ liệu có các tính chất chung.
- Cách biểu diễn phân mảnh ngang chính:
F (R)
trong đó: F là điều kiện chọn
R là quan hệ toàn cục
- Vị từ:
+ Ta gọi điều kiện chọn trong phép chọn là vị từ (predicate)
+ Ta gọi vị từ được xác định trong phép chọn để xác định một mảnh là vị từ định tính (qualification)
+ Quy ước: qi=Fi
Ví dụ 2.1: Xét hệ thống quản lý dự án của một công ty phát triển phần mềm trong ví dụ 1.5. Giả sử công ty có văn phòng ở Nam Định, Hà Nội.
DA
MADA | TENDA | NS | VT | |
u1 | D1 | Xây dựng phần mềm quản lý lương | 20000 | Nam Định |
u2 | D2 | Thiết kế trang Web bán hàng | 12000 | Hà Nội |
u3 | D3 | Nâng cấp hệ thống mạng | 28000 | Hà Nội |
u4 | D4 | Xây dựng phần mềm quản lý điểm | 25000 | Nam Định |
u5 | D5 | Xây dựng hệ thống quản lý tài chính | 30000 | Hà Nội |
Có thể bạn quan tâm!
-
Một Kiến Trúc Tham Chiếu Dùng Cho Các Csdl Phân Tán -
Các Kiểu Kiến Trúc Tham Chiếu Hệ Quản Trị Csdl Phân Tán -
Các Thành Phần Của Một Hệ Quản Trị Csdl Phân Tán. -
Cây Phân Mảnh Dẫn Xuất Của Hệ Thống Quản Lý Dự Án -
Cơ sơ dữ liệu phân tán - 9 -
Tính Trong Suốt Phân Mảnh Dùng Cho Các Ứng Dụng Chỉ Đọc
Xem toàn bộ 312 trang tài liệu này.
a) Với ứng dụng 1, phân mảnh ngang chính quan hệ toàn cục DA được xác định như sau:
DA 1=VT = “Nam Định” (DA)
DA 2=VT = “Hà Nội” (DA)
Do đó, các vị từ định tính là:
q1: VT = “Nam Định” q2: VT = “Hà Nội”
Kết quả của các mảnh:
DA1
TENDA | NS | VT | |
D1 | Xây dựng phần mềm quản lý lương | 20000 | Nam Định |
D4 | Xây dựng phần mềm quản lý điểm | 25000 | Nam Định |
DA2
TENDA | NS | VT | |
D2 | Thiết kế trang Web bán hàng | 12000 | Hà Nội |
D3 | Nâng cấp hệ thống mạng | 28000 | Hà Nội |
D5 | Xây dựng hệ thống quản lý tài chính | 30000 | Hà Nội |
Xét điều kiện đúng đắn để phân mảnh ngang chính:
- Điều kiện đầy đủ
+ u1 DA: u1 DA1
+ u2 DA: u2 DA2
+ u3 DA: u3 DA2
+ u4 DA: u4 DA1
+ u5 DA: u5 DA2
Do đó điều kiện đầy đủ được đảm bảo
- Điều kiện tái tạo
DA = DA1 DA2
Do đó điều kiện tái tạo được đảm bảo
- Điều kiện tách biệt DA1 DA2 =
Do đó điều kiện tách biệt được đảm bảo
b) Với ứng dụng 1 và ứng dụng 2, phân mảnh ngang chính quan hệ toàn cục DA được xác định như sau:
DA1=(VT = “Nam Định”) (NS >20000) (DA)
DA2=(VT = “Nam Định”) (NS ≤ 20000) (DA) DA3=(VT = “Hà Nội”) (NS >20000) (DA) DA4=(VT = “Hà Nội”) (NS ≤ 20000) (DA)
Do đó, các vị từ định tính là:
q1: VT = “Nam Định” NS >20000
q2: VT = “Nam Định” NS ≤ 20000 q3: VT = “Hà Nội” NS >20000
q4: VT = “Hà Nội” NS ≤ 20000
Kết quả của các mảnh:
DA1
TENDA | NS | VT | |
D4 | Xây dựng phần mềm quản lý điểm | 25000 | Nam Định |
DA2
TENDA | NS | VT | |
D1 | Xây dựng phần mềm quản lý lương | 20000 | Nam Định |
DA3
TENDA | NS | VT | |
D3 | Nâng cấp hệ thống mạng | 28000 | Hà Nội |
D5 | Xây dựng hệ thống quản lý tài chính | 30000 | Hà Nội |
DA4
TENDA | NS | VT | |
D2 | Thiết kế trang Web bán hàng | 12000 | Hà Nội |
Xét điều kiện đúng đắn để phân mảnh ngang chính:
- Điều kiện đầy đủ
+ u1 DA: u1 DA2
+ u2 DA: u2 DA4
+ u3 DA: u3 DA3
+ u4 DA: u4 DA1
+ u5 DA: u5 DA3
Do đó điều kiện đầy đủ được đảm bảo
- Điều kiện tái tạo
DA = DA 1 DA 2 DA 3 DA 4
Do đó điều kiện tái tạo được đảm báo
- Điều kiện tách biệt
+ DA1 DA2 = DA2 DA3 =
+ DA1 DA3 = DA2 DA4 =
+ DA1 DA4 = DA3 DA4 =
Do đó điều kiện tách biệt được đảm bảo
Ví dụ 2.2: Xét hệ thống quản lý dự án của một công ty phát triển phần mềm trong ví dụ 1.5. Giả sử công ty có văn phòng ở Nam Định, Hà Nội, Cần Thơ.
DA
MADA | TENDA | NS | VT | |
u1 | D1 | Xây dựng phần mềm quản lý lương | 20000 | Nam Định |
u2 | D2 | Thiết kế trang Web bán hàng | 12000 | Hà Nội |
u3 | D3 | Nâng cấp hệ thống mạng | 28000 | Hà Nội |
u4 | D4 | Xây dựng phần mềm quản lý điểm | 25000 | Nam Định |
u5 | D5 | Xây dựng hệ thống quản lý tài chính | 30000 | Hà Nội |
u6 | D6 | Phát triển hệ thống tín dụng | 10000 | Cần Thơ |
Giả sử quan hệ toàn cục DA được phân mảnh chính như sau:
DA 1=VT = “Cần Thơ” (DA) DA 2=VT = “Hà Nội” (DA)
Do đó, các vị từ định tính là:
q1: VT = “Cần Thơ” q2: VT = “Hà Nội”
Kết quả của các mảnh:
DA1
TENDA | NS | VT | |
D6 | Phát triển hệ thống tín dụng | 10000 | Cần Thơ |
DA2
TENDA | NS | VT | |
D2 | Thiết kế trang Web bán hàng | 12000 | Hà Nội |
D3 | Nâng cấp hệ thống mạng | 28000 | Hà Nội |
D5 | Xây dựng hệ thống quản lý tài chính | 30000 | Hà Nội |
Điều kiện đầy đủ bị vi phạm vì u1 DA nhưng u1 DA1, u1 DA2. Do đó, điều kiện đúng đắn để phân mảnh ngang chính không thỏa mãn.
Ta có thể tổng quát hoá từ ví dụ trên như sau:
- Để thoả mãn điều kiện đầy đủ thì tập hợp các vị từ định tính của tất cả các mảnh phải là đầy đủ, ít nhất là đối với tập hợp các giá trị cho phép.
- Điều kiện tái tạo luôn luôn được thoả mãn thông qua phép hợp.
- Để thoả mãn điều kiện tách biệt thì các vị từ định tính phải loại trừ nhau (mutual exclusive).
2) Phân mảnh ngang dẫn xuất
Phân mảnh ngang dẫn xuất (devired 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ủ).
- Cách xác định một mảnh: Dùng một phép nửa kết nối (semi-join operation) R A BS (=Attr(R)(RA BS))
Trong đó:
+ R là quan hệ toàn cục được phân mảnh ngang dẫn xuất theo quan hệ toàn cục S
+ AR, BS là hai thuộc tính có thể so sánh được với nhau bởi phép
+ ={=, , , , , }
- Vị từ định tính của mảnh ngang dẫn xuất bao gồm:
+ Điều kiện kết nối
+ Vị từ định tính của mảnh ngang chủ tương ứng
Khi một mối quan hệ toàn cục R được phân mảnh ngang dẫn xuất, các vị từ định tính của các mảnh của nó không thể biểu hiện bằng các vị từ chỉ sử dụng các thuộc tính của R; hơn nữa, điều kiện để một bộ t thuộc về một mảnh cho trước Ri của R là phải tồn tại một bộ t‟ (trong đó một mảnh Si‟ nào đó của S) sao cho t và t‟ thoả mãn điều kiện của phép nửa kết nối của phân mảnh ngang dẫn xuất.
Ví dụ 2.3: Xét hệ thống quản lý dự án của một công ty phát triển phần mềm trong ví dụ 1.5. Giả sử công ty có văn phòng ở Nam Định, Hà Nội.
Giả sử quan hệ toàn cục DA được phân mảnh ngang chính như trong ví dụ 2.1. Giả sử quan hệ toàn cục HS có các bộ như sau:
HS
MANV | MADA | NV | TG | |
u1 | A1 | D1 | Quản lý | 12 |
u2 | A2 | D1 | Phân tích | 34 |
u3 | A2 | D2 | Phân tích | 6 |
u4 | A3 | D3 | Kỹ thuật | 12 |
u5 | A3 | D4 | Lập trình | 10 |
u6 | A4 | D2 | Quản lý | 6 |
u7 | A5 | D2 | Quản lý | 20 |
u8 | A6 | D4 | Kỹ thuật | 36 |
u9 | A7 | D3 | Quản lý | 48 |
u10 | A8 | D5 | Lập trình | 15 |
a) Với ứng dụng 1, phân mảnh ngang chính dẫn xuất quan hệ HS được xác định như sau:
HS1= HS
HS2= HS
Do đó, các vị từ định tính là:
HS.MaDA= DA.MaDADA1 HS.MaDA= DA.MaDADA2
q1: VT = “Nam Định” HS.MaDA= DA.MaDA q2: VT = “Hà Nội” HS.MaDA= DA.MaDA
Kết quả của các mảnh ngang dẫn xuất:
HS1
MADA | NV | TG | |
A1 | D1 | Quản lý | 12 |
A2 | D1 | Phân tích | 34 |
A3 | D4 | Lập trình | 10 |
A6 | D4 | Kỹ thuật | 36 |
HS2
MADA | NV | TG | |
A2 | D2 | Phân tích | 6 |
A3 | D3 | Kỹ thuật | 12 |
A4 | D2 | Quản lý | 6 |
A5 | D2 | Quản lý | 20 |
A7 | D3 | Quản lý | 48 |
A8 | D5 | Lập trình | 15 |
Xét điều kiện đúng đắn để phân mảnh ngang dẫn xuất:
- Điều kiện đầy đủ
+ u1 HS: u1 HS1 u6 HS: u6 HS2
+ u2 HS: u2 HS1 u7 HS: u7HS2
+ u3 HS: u3 HS2 u8 HS: u8 HS1
+ u4 HS: u4 HS2 u9 HS: u9 HS2
+ u5 HS: u5 HS1 u10 HS: u10 HS2
Do đó điều kiện đầy đủ được đảm bảo
- Điều kiện tái tạo
HS = HS1 HS2
Do đó điều kiện tái tạo được đảm bảo
- Điều kiện tách biệt HS1 HS2 =
Do đó điều kiện tách biệt được đảm bảo
b) Với ứng dụng 1 và ứng dụng 2, phân mảnh ngang chính dẫn xuất quan hệ HS được xác định như sau:
HS1= HS
HS2= HS HS3= HS HS4= HS
Do đó, các vị từ định tính là:
HS.MaDA= DA.MaDADA1 HS.MaDA= DA.MaDADA2 HS.MaDA= DA.MaDADA3 HS.MaDA= DA.MaDADA4
q1: VT = “Nam Định” NS >20000 HS.MaDA= DA.MaDA q2: VT = “Nam Định” NS ≤ 20000 HS.MaDA= DA.MaDA q3: VT = “Hà Nội” NS >20000 HS.MaDA= DA.MaDA
q4: VT = “Hà Nội” NS ≤ 20000 HS.MaDA= DA.MaDA
Kết quả của các mảnh ngang dẫn xuất: