Thiết Kế Phân Mảnh Cơ Sở Dữ Liệu

- Các bước thực hiện:

+ Thiết kế phân mảnh

+ Thiết kế định vị

e) Thiết kế vật lý (physical design)

- Đầu vào:

+ Các lược đồ khái niệm cục bộ

+ Thông tin kiểu truy xuất các mảnh trong các lược đồ

- Đầu ra: Lược đồ vật lý

- Các bước thực hiện: Ánh xạ các lược đồ khái niệm cục bộ vào các thiết bị lưu trữ vật lý (physical storage device) có sẵn tại các nơi tương ứng

f) Giai đoạn theo dòi và kiểm tra

- Đầu vào: Lược đồ vật lý

- Đầu ra:

+ Một số dạng phản hồi

+ Yêu cầu quay trở lại một trong các bước trước các giai đoạn thiết kế

- Các bước thực hiện:

+ Giám sát cách thực hiện CSDL

+ Giám sát tính thích hợp của các khung nhìn của người sử dụng

Cách tiếp cận từ trên xuống là cách thường dùng nhất đối với các hệ thống được xây dựng từ đầu, bởi vì nó cho phép thực hiện thiết kế một cách hợp lý. Do đó, cách tiếp cận này sẽ được đề cập đến trong phần còn lại của chương này. Tuy nhiên, chúng ta sẽ không bàn đến các kỹ thuật có thể được sử dụng trong việc thiết kế lược đồ toàn cục và lược đồ vật lý, bởi vì chúng không phải được dùng riêng cho CSDL phân tán.

2) Chiến lược thiết kế từ dưới lên (Bottom - up)

Khi CSDL phân tán được phát triển từ sự kết hợp của các CSDL hiện tại, thì không cần thiết phải sử dụng cách tiếp cận từ trên xuống. Trong thực tế, trong trường hợp này, lược đồ toàn cục thường được tạo ra từ sự kết hợp các mô tả dữ liệu hiện tại. Cũng có thể sử dụng một lược đồ chuyển đổi khác nhau cho từng cặp CSDL hiện tại và khi đó không có khái niệm lược đồ toàn cục. Tuy nhiên, điều này sẽ làm cho các hệ thống khác với kiến trúc tham chiếu của chúng ta.

Khi các CSDL hiện tại được kết hợp lại, chúng ta có thể sử dụng cách tiếp cận từ dưới lên (bottom - up - approach) để thiết kế phân tán dữ liệu. Cách tiếp cận này dựa trên sự tích hợp của các lược đồ hiện tại thành một lược đồ toàn cục. Bằng cách tích hợp, chúng ta muốn hợp nhất các định nghĩa dữ liệu chung và giải quyết các mâu thuẫn giữa các biểu diễn khác nhau cho cùng một dữ liệu.

Lưu ý rằng, bản thân cách tiếp cận từ dưới lên không dễ dàng được áp dụng cho các quan hệ được phân mảnh ngang. Trong thực tế, các mảnh ngang của cùng một

quan hệ toàn cục phải có cùng một lược đồ quan hệ, đặc điểm này dễ dàng được áp dụng trong thiết kế từ trên xuống, trong khi đó khó phát hiện ra đặc điểm này trong các CSDL được thiết kế một cách độc lập rồi sau đó tích hợp lại. Vì các mảnh ngang có một đặc điểm thích hợp và có ích cho một CSDL phân tán, quá trình tích hợp nên biến đổi các định nghĩa của các quan hệ cục bộ sao cho chúng có thể được xem là các mảnh ngang của một quan hệ toàn cục chung.

Khi các CSDL hiện tại được kết hợp thành một CSDL phân tán, có thể chúng sử dụng các hệ thống DBMS khác nhau. Như chúng ta đã bàn ngắn gọn trong chương 1 và chương 2, một hệ thống không đồng nhất làm tăng độ phức tạp của việc tích hợp dữ liệu và cần phải có sự chuyển đổi giữa các biểu diễn khác nhau. Trong trường hợp này, có thể có sự chuyển đổi một–một giữa từng cặp DBMS khác nhau. Tuy nhiên, cách tiếp cận được sử dụng chủ yếu trong các nguyên mẫu của các hệ thống không đồng nhất là chọn ra một ô hình dữ liệu chung, và sau đó chuyển đổi tất cả các lược đồ khác nhau của các DMBS phức tạp thành một dạng biểu diễn duy nhất này.

Tóm lại, thiết kế từ dưới lên của một CSDL phân tán đòi hỏi:

- Chọn một mô hình cơ sở dữ liệu chung để mô tả lược đồ toàn cục của CSDL.

- Chuyển đổi mỗi lược đồ cục bộ thành mô hình dữ liệu chung.

- Tích hợp các lược đồ cục bộ thành một lược đồ toàn cục chung.

Do đó, cách tiếp cận từ dưới lên đòi hỏi phải giải quyết ba vấn đề mà không phải của riêng CSDL phân tán, mà chúng cũng có trong các hệ thống tập trung. Vì thế thiết kế từ dưới lên không được giải quyết trong chương này.

3.1.4. Các yêu cầu thông tin

Một khía cạnh của thiết kế phân tán là có quá nhiều yếu tố trong thiết kế tối ưu. 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 và các đặc tính của các hệ thống máy tính ở mỗi nơi, tất cả đều ảnh hưởng đến các quyết định phân tán. Điều này làm cho việc phát biểu vấn đề phân tán rất phức tạp.

Thông tin dùng để thiết kế phân tán có thể được chia thành bốn loại:

- 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

Hai loại sau hoàn toàn có tính chất định hướng và được sử dụng trong các mô hình định vị hơn là trong các giải thuật phân mảnh. ở đây, chúng ta không xét chúng một cách chi tiết. Thay vào đó, các yêu cầu thông tin chi tiết của các giải thuật phân mảnh và định vị sẽ được bàn đến trong các phần tương ứng của chúng.

3.2. Thiết kế phân mảnh cơ sở dữ liệu

Thiết kế phân mảnh là vấn đề đầu tiên phải được giải quyết trong thiết kế phân tán dữ liệu theo cách tiếp cận từ trên xuống. Mục đích của thiết kế phân mảnh là xác định các mảnh không giao nhau mà chúng là các đơn vị phân tán, còn được gọi là đơn vị định vị luận lý (logical unit of allocation), thích hợp cho vấn đề định vị dữ liệu sau này.

Rò ràng, các bộ phận hoặc các thuộc tính của các quan hệ không thể được xem là các đơn vị phân tán riêng biệt, bởi vì các vấn đề ứng dụng sẽ trở nên khó quản lý.

Thiết kế các mảnh bao gồm việc gom nhóm các bộ (trong trường hợp phân mảnh ngang) hoặc các thuộc tính (trong trường hợp phân mảnh dọc) mà chúng có cùng các đặc tính theo quan điểm định vị của chúng. Mỗi nhóm gồm các bộ hoặc các thuộc tính có cùng các đặc tính tạo thành một mảnh.

Ý tưởng cơ bản là nếu bất kỳ hai phần tử nào thuộc cùng một mảnh có cùng các đặc tính theo quan điểm định vị của chúng, thì bất kỳ phương pháp nào dùng để định vị dữ liệu sẽ đặt chúng chung với nhau. Do đó các mảnh có được theo cách này là các đơn vị phân tán thích hợp.

Bây giờ chúng ta sẽ làm rò nghĩa của “cùng các đặc tính” của các phần tử của mảnh.

Ví dụ 3.1: Xét việc xác định các mảnh ngang của quan hệ toàn cục DA(MADA, TENDA, NS, VT) trong ví dụ 1.5.

Giả sử các ứng dụng quan trọng của CSDL phân tán này yêu cầu thông tin về các dự án lấy từ quan hệ DA. Cho mỗi vị trí là một nơi của CSDL phân tán.

Ứng dụng có thể được chạy tại bất kỳ vị trí nào. Tuy nhiên, khi chúng được chạy tại một vị trí cho trước, chúng sẽ tham chiếu đến các bộ của các dự án tại vị trí đó với xác suất cao hơn so với các bộ của vị trí khác. Điều này xảy ra bởi vì các dự án hiện tại được phân tán tại các vị trí, và bởi vì thông tin về các dự án được yêu cầu bởi cùng một vị trí. Do đó, trong trường hợp đơn giản, các mảnh được thiết kế bằng cách tập hợp trong mỗi mảnh gồm các bộ của các dự án có cùng đặc tính theo quan điểm định vị của chúng.

Chúng ta cũng nêu ra một ví dụ đơn giản về phân mảnh dọc quan hệ DA. Giả sử các thuộc tính VT và NS chỉ sử dụng cho các ứng dụng quản trị mà các ứng dụng này luôn luôn sử dụng các thuộc tính này chung với nhau. Do đó, cặp thuộc tính VT và NSd là một mảnh dọc thích hợp.

Lưu ý rằng, nơi gốc của mỗi ứng dụng là thích hợp cho các đặc tính cục bộ để định nghĩa các mảnh tương ứng. Do đó chúng ta xem các ứng dụng được chạy tại các nơi khác nhau như là các ứng dụng khác nhau, ngay cả khi chúng thực hiện cùng một chức năng.

Sau đây, chúng ta xét phân mảnh ngang, phân mảnh dọc và phân mảnh hỗn hợp một cách độc lập nhau. Như chúng ta đã khảo sát, điều phải làm trước tiên về mặt khái niệm là xác định phân mảnh và sau đó định vị các mảnh.

3.3. Thiết kế phân mảnh ngang

3.3.1. Các yêu cầu thông tin của phân mảnh ngang

1) Thông tin về cơ sở dữ liệu

Thông tin về CSDL liên quan đến lược đồ khái niệm toàn cục, chỉ ra mối liên kết giữa các quan hệ.

Mô hình hóa các mối liên kết giữa các quan hệ bằng đồ thị.

Thông tin định lượng cần có về CSDL là số bộ của mỗi quan hệ R, ký hiệu

card(R)

Quy ước:

- Mối liên hệ: biểu diễn bằng cung có hướng

- Mỗi nút là một lược đồ quan hệ: biểu diễn bằng hình chữ nhật

Trong đó:

+ S gọi là quan hệ chủ (owner) - bên một

+ R gọi là quan hệ bộ phận (member) - bên nhiều

+ L gọi là đường liên hệ

Định nghĩa các hàm:

- Owner(tên đường liên hệ): Trả về quan hệ chủ của đường kết nối

- Member(tên đường liên hệ): Trả về quan hệ bộ phận của đường kết nối

Ví dụ 3.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.

Với quan hệ toàn cục DA, HS như sau

Khi đó CARD(DA)=4, CARD(HS)=10, CARD(TL)=4, CARD(NV)=8

Ta thấy rằng:

- Có nhiều nhân viên giữ một chức vụ nên mối liên hệ giữa hai quan hệ TL và NV là một nhiều. Do đó có một đường liên hệ giữa các quan hệ TL và NV.

- Một nhân viên tham gia nhiều dự án và một dự án có nhiều nhân viên tham gia nên mối quan hệ giữa hai quan hệ NV và DA là nhiều-nhiều. Do đó, có hai đường liên hệ từ quan hệ NV và DA đến HS.

Ta có đồ thị biểu diễn mối liên hệ giữa các quan hệ toàn cục như sau:

Từ đồ thị biểu diễn mối liên hệ giữa các quan hệ toàn cục, ta xác định được các loại quan hệ với mỗi đường liên hệ như sau:

- owner ( L1) = NV, member ( L1) = HS

- owner ( L2) = DA, member ( L2) = HS

- owner ( L3) = TL, member ( L3) = NV

Ví dụ 3.3: Xét hệ thống quản lý dự án trong ví dụ 2.13. Với quan hệ toàn cục NV như sau

MANV

HOTEN	LUONG	THUE	MAQL	MAP
NV001	Nguyễn Trâm Anh	100	10	QL1	P1
NV002	Trần Minh Toàn	150	12	QL1	P1
NV003	Minh Mẫn Vương	120	6	QL1	P1
NV004	Hà Thị Kiết	234	62	QL1	P1
NV005	Nguyễn Châu Phong	124	3	QL2	P2
NV006	Lê Hải Anh	234	0	QL2	P2

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

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

MANV

HOTEN	LUONG	THUE	MAQL	MAP
NV007	Lê Mai Hương	612	70	QL2	P2
NV008	Trần Hoàng Phong	435	67	QL3	P3

Khi đó CARD(NV)=8,

Ta thấy rằng:

- Có nhiều nhân viên làm tại mỗi phòng ban và mỗi phòng ban có một người quản lý nên mối liên hệ giữa hai quan hệ PH và NV là một nhiều. Do đó có 2 đường liên hệ giữa các quan hệ PH và NV.

- Một nhà cung cấp cung cấp nhiều mặt hàng và một mặt hàng được cung cấp bởi nhiều nhà cung cấp nên mối quan hệ giữa hai quan hệ NCC và MH là nhiều-nhiều. Do đó, có đường liên hệ từ quan hệ NCC và MH đến KD.

- Một phòng cung cấp nhiều mặt hàng và một mặt hàng được cung cấp bởi nhiều phòng nên mối quan hệ giữa hai quan hệ KD và PH là nhiều-nhiều. Do đó, có đường liên hệ từ quan hệ PH và MH đến KD.

Ta có đồ thị biểu diễn mối liên hệ giữa các quan hệ toàn cục như sau:

Từ đồ thị biểu diễn mối liên hệ giữa các quan hệ toàn cục, ta xác định được các loại quan hệ với mỗi đường liên hệ như sau:

- owner ( L1) = NCC, member ( L1) = KD

- owner ( L2) = MH, member ( L2) = KD

- owner ( L3) = PH, member ( L3) = KD

- owner ( L4) = PH, member ( L4) = NV

- owner ( L5) = PH, member ( L5) = NV

2) Thông tin về ứng dụng

Thông tin về ứng dụng có hai loại

- Thông tin định tính: Dùng để phân mảnh

- Thông tin định lượng: Dùng để cấp phát

a) Thông tin định tính

Thông tin định tính cơ bản bao gồm các vị từ được sử dụng trong các truy vấn của người sử dụng.

Chỉ phân tích các ứng dụng quan trọng để xác định xác định các vị từ.

Định nghĩa

Cho quan hệ R(A1, A2, A3,…, An) với Ai là một thuộc tính có miền trị Di. Giả sử cần phân mảnh ngang quan hệ R.

- Vị từ đơn giản

Một vị từ đơn giản (simple predicate) pj được định nghĩa trên R có dạng: pj: Ai  Value

Trong đó

+  là một trong các phép so sánh, {=, , <, ≤, >, ≥}

+ Value được chọn từ miền của Ai, Value  Di

- Tập các vị từ đơn giản: Tập hợp các vị từ đơn giản được định nghĩa trên quan hệ R được kí hiệu là Pr bao gồm các vị từ đơn giản pj , 1≤ j ≤ m

Pr={p1, p2,…,pm }

- Một vị từ giao tối thiểu (minterm predicate) mj đối với một tập hợp các vị từ đơn giản Pr={p1, p2,…,pm } là một tổ hợp giao của tất cả các vị từ xuất hiện trong Pr, các vị từ này ở dạng thông thường hoặc ở dạng phủ định, để sao cho mj không bị mâu thuẫn.

Tức là:

mj = p*

, 1≤ i ≤ m

i i i i j

với p* = p hoặc p* = p và m  false

- Tập hợp các vị từ giao tối thiểu: Tập hợp các vị từ giao tối thiểu được ký hiệu M bao gồm các vị từ giao tối thiểu mk, 1≤ k≤ z

M= {m1, m2, …, mz}

Chú ý:

- Đối với vị từ đẳng thức (equality predicate), phủ định của đẳng thức Attribute = Value là Attribute  Value

- Đối với các vị từ bất đẳng thức (inequality predicate), phủ định là phần bù. Phần bù của Attribute ≤ Value là Attribute >Value.

Ngoài các vấn đề lý thuyết về phép lấy bù trong các tập hợp vô hạn, cũng có một vấn đề là có thể khó xác định được phần bù.

Ví dụ 3.4: Nếu hai vị từ đơn giản có dạng Lower_bound ≤Attribute và Attribute≤Upper_bound thì phần bù của chúng là (Lower_bound ≤ Attribute) và

(Attribute ≤ Upper_bound).

Tuy nhiên, hai vị từ trên có thể được viết Lower_bound ≤ Attribute ≤ Upper_bound với phần bù là ( Lower_bound ≤ Attribute ≤ Upper_bound) thì không thể dễ xác định. Do đó nghiên cứu trong lĩnh vực này chỉ xét các vị từ đẳng thức đơn giản.

b) Thông tin định lượng

Theo những thông tin định lượng về các ứng dụng của người sử dụng, cần có hai tập hợp dữ liệu:

- Độ chọn giao tối thiểu (minterm selectivity): là số bộ của quan hệ sẽ được truy xuất bởi một truy vấn tương ứng với một vị từ giao tối thiểu cho trước.

Ký hiệu độ chọn của vị từ giao tối thiểu mj là Sel(mj)

Như vậy, Sel(mj)={số bộ của quan hệ được truy xuất theo mj}

- Tần số truy xuất (access frequency): Là tần số của các ứng dụng truy xuất dữ liệu. Cho Q={q1, q2,…, qq} là tập hợp các truy vấn

Kí hiệu tần số truy xuất của truy vấn qi trong một khoảng thời gian cho trước là

Acc(qi)

Kí hiệu tần số truy xuất của vị từ giao tối thiểu mj là Acc(mj) .

Ví dụ 3.5: Xét hệ thống quản lý dự án trong 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, mỗi nơi đều thực hiện một số dự án và hệ thống có các ứng dụng sau:

- Ứng dụng 1: Truy xuất DA theo vị trí là “Hà Nội”

- Ứng dụng 2: Truy xuất các bộ của DA có ngân sách lớn hơn 20000 Quan hệ toàn cục dự án

MADA

TENDA	NS	VT
D1	Xây dựng phần mềm quản lý lương	20000	Nam Định
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
D4	Xây dựng phần mềm quản lý điểm	25000	Nam Định
D5	Xây dựng hệ thống quản lý tài chính	30000	Hà Nội

Với ứng dụng 1 và ứng dụng 2, ta có:

- Các vị từ đơn giản được định nghĩa trên quan hệ DA: p1: VT=‟Hà Nội‟

p2: NS>20000

- Tập vị từ đơn giản: PDA={p1, p2}.

- Các vị từ giao tối thiểu được định nghĩa dựa trên các vị từ đơn giản