Kiến Trúc Tham Chiếu Của Cơ Sở Dữ Liệu Phân Tán [3]

Lược đồ tổng thể

Lược đồ phân đoạn

Lược đồ định

Lược đồ ánh xạ địa phương 1

Lược đồ ánh xạ địa phương 2

Các trạm khác

Hệ quản trị cơ sở dữ liệu của trạm 1

Hệ quản trị cơ sở dữ liệu của trạm 2

Cơ sở dữ liệu địa phương của trạm 1

Có thể bạn quan tâm!

Xem toàn bộ 103 trang tài liệu này.

Cơ sở dữ liệu địa phương của trạm 2

Lược đồ độc lập trạm

Hình 1.1: Kiến trúc tham chiếu của cơ sở dữ liệu phân tán[3]

1.4. Các kỹ thuật xây dựng cơ sở dữ liệu phân tán

- Kỹ thuật phân tách dữ liệu từ một cơ sở dữ liệu để lưu trữ trên các trạm khác nhau được gọi là phân mảnh.

- Sử dụng bản sao cho phép cùng một dữ liệu có thể được lưu trữ trên nhiều hơn một trạm.

- Quá trình định vị các phân mảnh dữ liệu hoặc định vị các bản sao phân mảnh lưu trữ dữ liệu trên các trạm khác nhau.

1.4.1. Phân mảnh

Sự phân mảnh là chia dữ liệu trong các bảng dữ liệu thành các bộ hoặc các bảng dữ liệu con. Có ba kiểu phân mảnh một quan hệ tổng thể: Phân mảnh ngang, phân mảnh dọc và phân mảnh hỗn hợp.

Một sự phân mảnh là đúng đắn nếu thoả mãn ba điều kiện sau:

- Điều kiện không mất thông tin: Tất cả dữ liệu của quan hệ tổng thể phải đựơc ánh xạ tới các mảnh, có nghĩa mỗi phần tử dữ liệu thuộc quan hệ tổng thể phải thuộc một hay nhiều mảnh của nó.

- Điều kiện xây dựng lại: Luôn có thể xây dựng lại được quan hệ tổng thể từ các mảnh đã có.

- Điều kiện rời nhau (chỉ áp dụng cho phân mảnh ngang): Để tối thiểu hoá sự lặp lại của dữ liệu.

1.4.1.1. Phân mảnh ngang

Phân mảnh ngang là sự phân chia một quan hệ thành các tập con các bộ, mỗi tập con được xác định bởi phép chọn với tân từ p trên quan hệ tổng thể R: Ri = pi, với pi là tân từ của Ri. Để có thể khôi phục được R ta dùng phép hợp các quan hệ R = R1  R2 ... Rn.

Ví dụ 1.1: Xét quan hệ tổng thể

DAILY (SHDL, DCDL,THPHO)

Trong đó có các thuộc tính: SHDL: Số hiệu đại lý DCDL: Địa chỉ đại lý THPHO: Thành phố

Ta tách quan hệ DAILY thành hai quan hệ DAILY1 và DAILY2 thuộc hai chi nhánh „HN‟ và „HCM‟. Ta có phân đoạn ngang:

DAILY1 = THPHO=”HN” DAILY DAILY2 = THPHO=”HCM” DAILY

Thoả mãn:

- Điều kiện xây dựng lại: DAILY = DAILY1  DAILY2

- Điều kiện rời nhau thoả mãn vì: DAILY1  DAILY2 = 

Tổng quát:

- Điều kiện không mất thông tin nếu tập các tân từ của tất cả các đoạn phải

đầy đủ.

- Điều kiện xây dựng lại luôn luôn thoả mãn với phép hợp.

- Điều kiện rời nhau đòi hỏi các tân từ phải loại trừ nhau.

1.4.1.2. Phân mảnh ngang dẫn tiếp

Phân mảnh ngang dẫn tiếp là sự phân chia một quan hệ ban đầu thành các quan hệ thứ hai khác mà các quan hệ đó liên hệ với quan hệ ban đầu bằng một khoá ngoài. Điều này như là liên hệ dữ liệu giữa quan hệ ban đầu và quan hệ thứ hai được phân đoạn trong cùng một cách.

Ví dụ 1.2: Xét quan hệ tổng thể

CUNGCAP(SHDL, SHSP, SHCHINHANH, SOLUONG)

Trong đó có các thuộc tính:

SHDL: Số hiệu đại lý SHSP: Số hiệu sản phẩm

SHCHINHANH: Số hiệu chi nhánh SOLUONG: Số lượng

Phân đoạn ngang dẫn tiếp của quan hệ CUNGCAP được thực hiện như sau: CUNGCAP1 = CUNGCAP ⋉SHDL= SHDL DAILY1

CUNGCAP2 = CUNGCAP ⋉ SHDL = SHDL DAILY2

Việc bố trí trên cùng một trạm của mỗi cặp đoạn (DAILY1, CUNGCAP1) và (DAILY2, CUNGCAP2) cho phép cải tiến hiệu năng của phép kết nối các quan hệ NHACUNGCAP và CUNGCAP vì có thể thực hiện song song bởi hai phép kết nối (DAILY1⋈ CUNGCAP1) và (DAILY2⋈ CUNGCAP2).

- Điều kiện không mất thông tin của phân đoạn trên đòi hỏi không có SHDL nào trong quan hệ CUNGCAP mà lại không chứa trong quan hệ DAILY. Ở đây có ràng buộc toàn vẹn tham chiếu.

s  CUNGCAP => phải  pDAILY mà p.SHDL= s. SHDL p.SHDL  DAILY1 qua ⋉ => s  CUNGCAP1 hoặc p.SHNCC  DAILY2 qua ⋉ => s  CUNGCAP2

=> Thoả mãn điều kiện không mất thông tin

- Điều kiện xây dựng lại: CUNGCAP = CUNGCAP1  CUNGCAP2

- Điều kiện rời nhau: Ta chứng minh: CUNGCAP1  CUNGCAP2 = 

Giả sử: p  CUNGCAP1 & CUNGCAP2

=> p1  NCC1 p.SHDL = p1.SHDL

=> p2  NCC2 p.SHDL = p2.SHDL

Mâu thuẫn vì SHDL là khoá của DAILY

1.4.1.3. Phân mảnh dọc

Phân mảnh dọc là sự chia một quan hệ thành tập con các bộ, mỗi tập được xác định bởi một phép chiếu được áp dụng cho quan hệ: Ri = ПATTRi R, trong đó ATTRi là tập con các thuộc tính của R.

Tiêu chuẩn cho sự phân mảnh dọc là đúng đắn:

- Điều kiện đầy đủ: Nếu một thuộc tính xuất hiện trong một quan hệ tổng thể thì nó cũng phải xuất hiện trong một mảnh dọc nào đó.

- Điều kiện xây dựng lại: Cần phải thêm vào mỗi mảnh khoá chính, do đó việc xây dựng lại được nhờ vào phép kết nối các mảnh dọc theo các thuộc tính chung.

- Điều kiện rời nhau: Ít nhất khoá phải được lặp lại trên tất cả các mảnh để cho phép xây dựng lại, nên ở đây không thể xem là rời nhau hoàn toàn được.

Ví dụ 1.3: Xét quan hệ tổng thể

NHANVIEN(SHNV, TEN, LUONG, THUE, SHQL, SHPHONG)

Trong đó có các thuộc tính: SHNV: Số hiệu nhân viên TEN: Tên nhân viên LUONG: Mức lương THUE: Thuế

SHQL: Số hiệu quản lý

SHPHONG: Số hiệu phòng

Ta tách quan hệ NHANVIEN thành hai quan hệ NV1 và NV2 NV1 = П SHNV, TEN, SHQL, SHPHONG NHANVIEN NV2 = ПSHNV, TEN, LUONG, THUE NHANVIEN

Thuộc tính TEN lặp lại ở cả hai mảnh, khi xây dựng lại quan hệ NHANVIEN thông qua phép chiếu, thuộc tính này sẽ bị khử.

NHANVIEN = NV1⋈ SHNV=SHNV П SHNV, LUONG, THUE NV2

1.4.1.4. Phân mảnh hỗn hợp

Là sự kết hợp cả phân mảnh dọc và phân mảnh ngang.

Ví dụ 1.4: Xét quan hệ tổng thể

NHANVIEN(SHNV, TEN,LUONG, THUE, SHQL, SHPHONG)

Tách quan hệ NHANVIEN thành các quan hệ NV1, NV2, NV3, NV4 NV1 = SHPHONG ≤ 10  SHNV, TEN, SHQL, SHPHONG NHANVIEN

NV2 = 10 < SHPHONG ≤ 20  SHNV, TEN, SHQL, SHPHONG NHANVIEN NV3 = SHPHONG >20  SHNV, TEN, SHQL, SHPHONG NHANVIEN NV4 =  SHNV, TEN, LUONG, THUE NHANVIEN

NHÂN VIÊN

Phân tách dọc

Phân tách ngang

NV1

NV2

NV3

Hình 1.2: Cây phân tách của quan hệ

Xây dựng lại quan hệ NHANVIEN ta thực hiện như sau:

NHANVIEN =  (NV1, NV2, NV3) ⋈ SHNV=SHNV  SHNV, LUONG, THUE NV4

Sự phân mảnh hỗn hợp có thể biểu diễn dưới dạng cây phân mảnh. Trong cây phân mảnh, nút gốc tương ứng quan hệ tổng thể, các nút ở giữa tương ứng với

các kết quả trung gian của thể hiện định nghĩa phân mảnh. Ví dụ, hình 1.2 thể hiện cây phân mảnh của quan hệ NHANVIEN. Nút gốc (quan hệ NHANVIEN) được phân mảnh dọc thành hai phần: một phần tương ứng với một nút lá của cây (NV4), phần còn lại được phân mảnh ngang, do vậy sinh ra ba nút lá khác, tương ứng với ba phân mảnh: NV1, NV2, NV3.

1.4.2 Nhân bản dữ liệu

Các chiến lược nhân bản dữ liệu:

1. Nhân bản dữ liệu đầy đủ: Toàn bộ cơ sở dữ liệu sẽ được tạo trên tất cả mỗi trạm.

Ưu điểm: Điều này sẽ cải thiện tính sẵn sàng cao nhất vì nếu sự cố trên trạm này thì vẫn có dữ liệu trên trạm khác và cải thiện hiệu năng lấy dữ liệu trên mạng cho các truy vấn toàn bộ vì dữ liệu sẽ được lấy từ các trạm cục bộ.

Nhược điểm: Các thao tác cập nhập dữ liệu rất chậm vì phải copy, đồng bộ dữ liệu cho mọi trạm. Kỹ thuật điều khiển tương tranh và phục hồi sẽ phức tạp hơn.

2. Không có nhân bản dữ liệu: Mỗi phân mảnh chỉ được lưu trữ trên một trạm, phương án này còn được gọi là định vị không dư thừa dữ liệu. Trong trường hợp này các phân đoạn phải tách rời nhau để tránh lặp bản ghi giống nhau cho các phân đoạn ngang và phân đoạn hỗn hợp.

3. Nhân bản dữ liệu từng phần: Một vài phân mảnh có thể được tạo bản sao và có thể một số phân mảnh sẽ không có bản sao. Việc tạo bản sao này rất có tác dụng cho các nhân viên làm việc di động, tại các nơi xa trung tâm dữ liệu, có thể tạo ra bản sao dữ liệu trên laptop của mình và theo chu kỳ đồng bộ dữ liệu với cơ sở dữ liệu server.

1.4.3 Định vị dữ liệu

Là quá trình gán từng phân đoạn, từng bản sao của phân đoạn cho một trạm cụ thể trong hệ thống phân tán. Việc chọn trạm nào và số bản sao phụ thuộc vào yêu cầu hiệu năng và mục tiêu sẵn sàng của hệ thống với các loại giao tác trên các

trạm. Đối với hệ yêu cầu tính sẵn sàng cao, mọi giao dịch thao tác lấy dữ liệu, giao dịch cập nhật chỉ làm tại một trạm thì nên tổ chức tạo bản sao đầy đủ. Nếu các giao dịch thường cập nhật một phần dữ liệu tại một trạm thì các phân đoạn cho phần dữ liệu đó nên được định vị trên trạm đó.

1.5. Kết luận chương

Cơ sở dữ liệu phân tán rất quan trọng vì nhiều lý do khác nhau, nó có thể được cài đặt trên các mạng máy tính diện rộng và các mạng cục bộ nhỏ. Có hai lý do về tổ chức và kỹ thuật đối với sự phát triển cơ sở dữ liệu phân tán đó là: Cơ sở dữ liệu phân tán được xây dựng để khắc phục các thiếu sót của cơ sở dữ liệu tập trung và nó phù hợp hơn trong cấu trúc phân quyền của nhiều tổ chức. Kỹ thuật cơ sở dữ liệu phân tán được mở rộng và phát triển từ kỹ thuật của cơ sở dữ liệu truyền thống. Trong môi trường mới này, một số vấn đề kỹ thuật đòi hỏi các giải pháp khác, và một số giải pháp hoàn toàn mới.

Tính trong suốt phân tán cung cấp sự độc lập của các chương trình khỏi sự phân tán của cơ sở dữ liệu. Các mức trong suốt phân tán khác nhau có thể được cung cấp bởi một hệ quản trị cơ sở dữ liệu phân tán; Tại mỗi mức, tính trong suốt làm cho người lập trình ứng dụng không biết được sự phân tán dữ liệu.

CHƯƠNG 2. TỐI ƯU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU PHÂN TÁN

2.1. Vấn đề tối ưu hóa xử lý truy vấn

Chức năng chính của bộ xử lý truy vấn là chuyển đổi một truy vấn mức cao (phép tính quan hệ) sang một truy vấn tương đương (đại số quan hệ). Quá trình chuyển đổi cùng cho một kết quả như nhau [5].

Có nhiều giải pháp chuyển đổi, mỗi giải pháp khác nhau có thể tiêu thụ tài nguyên của mạng máy tính khác nhau. Vì vậy, cần phải lựa chọn một giải pháp khi thực hiện sao cho tiêu thụ tài nguyên là tối thiểu.

Có hai phương pháp tối ưu cơ bản: Phương pháp biến đổi một câu truy vấn mức cao thành câu truy vấn tương đương ở mức thấp hơn dưới dạng biểu thức đại số quan hệ và phương pháp chọn lựa trong số các câu truy vấn dạng biểu thức đại số quan hệ tương đương một biểu thức có chi phí thời gian thực hiện và chi phí sử dụng tài nguyên là ít nhất.

Ví dụ 2.1: Xét các quan hệ sau: NV (MNV, TênNV, Chức vụ)

PC (MNV, MDA, Nhiệm vụ, Thời gian) Và một câu truy vấn đơn giản sau:

“Cho biết tên của các nhân viên hiện đang quản lý một dự án”

Biểu thức truy vấn bằng phép tính quan hệ theo cú pháp của SQL là: SELECT TênNV

FROM NV, PC

WHERE NV.MNV=PC.MNV

AND Nhiệmvụ=”Quảnlý”

Câu truy vấn trên được biểu diễn dưới dạng biểu thức đại số quan hệ như sau:

TênNV (Nhiệmvụ=”Quảnlý” NV.MNV=PC.MNV(NV x PC))

Phép toán trên được chuyển đổi tương đương cho cùng một kết quả nhưng có chi phí thời gian và sử dụng tài nguyên ít hơn (do tránh sử dụng tích Descartes):

TênNV (NV MNV (Nhiệmvụ=”Quảnlý” (PC)))