TRƯỜNG ĐẠI HỌC HÀNG HẢI
KHOA CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
CƠ SỞ DỮ LIỆU NÂNG CAO
Biên soạn: Th.S Nguyễn Trung Đức
Hải Phòng – 2008

1
BỘ GIAO THÔNG VẬN TẢI
TRƯỜNG ĐẠI HỌC HÀNG HẢI
BỘ MÔN: HỆ THỐNG THÔNG TIN
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
CƠ SỞ DỮ LIỆU NÂNG CAO
TÊN HỌC PHẦN : CƠ SỞ DỮ LIỆU NÂNG CAO
MÃ HỌC PHẦN : 17406
TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY
DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN
HẢI PHÒNG - 2008

2
Tên học phần: Cơ sở dữ liệu nâng cao Loại học phần: 2
Bộ môn phụ trách giảng dạy: Hệ thống Thông tin Khoa phụ trách: CNTT.
Mã học phần: 17406 Tổng số TC: 2
TS tiết
Lý thuyết
Thực hành/Xemina
Tự học
Bài tập lớn
Đồ án môn học
45

Chương 2. Mô hình mạng, mô hình phân cấp
3
3
2.1. Mô hình mạng
2.1.1. Giới thiệu
2.1.2. Các khái niệm
2.2. Mô hình phân cấp
2.2.1. Giới thiệu
2.2.2. Các khái niệm
Chương 3. Thiết kế cơ sở dữ liệu khái niệm
3
3
3.1. Giới thiệu
3.2. Trừu tượng hoá trong thiết kế CSDL
3.3. Các thuộc tính tương xứng giữa các lớp
3.4. Các mô hình dữ liệu
3.5. Mô hình thực thể quan hệ
Chương 4. Điều khiển khai thác tương tranh
3
3
4.1. Giới thiệu
4.2. Một số khái niệm
4.3. Đặc tính của khai thác không xung đột
4.3.1. Một số khái niệm
4.3.2. Khai thác có thứ tự
4.3.3. Đồ thị về thứ tự thực hiện các giao tác
Chương 5. An toàn dữ liệu và xử lý sai sót
3
3
5.1. An toàn trong CSDL

5
6
1
7.1. Giới thiệu về hướng đối tượng
7.1.1. Các khái niệm hướng đối tượng
7.1.2. Mô hình hoá việc phân tích hướng đối tượng
7.1.3. Mô hình hóa dữ liệu
7.2. Nguyên tác của các mô hình hướng đối tượng
7.2.1. Mô hình hoá các đối tượng
7.2.2. Phương pháp
7.2.3. Xác định dạng dữ liệu
7.2.4. Các liên kết thừa kế giữa các lớp
7.2.5. Đa cấu và sự áp đặt
7.2.6. Xác định tập các đối tượng
7.2.7. Khía cạnh động
7.2.8. Lược đồ CSDL hướng đối tượng
7.3. Tính bền vững các các đối tượng
7.3.1. CSDL hướng đối tượng
7.3.2. Quản lý tính bền vững
7.3.3. Kế thừa tính bền vững
7.3.4. Tính bền vững do tham chiếu
7.3.5. Tích hợp với ngôn ngữ lập trình
7.4. Đại số với các đối tượng phức tạp
7.4.1. Mở rộng đại số quan hệ theo đường dẫn và các
phương pháp
7.4.2. Các phép toán đại số
7.4.3. Các phép toán nhóm
7.4.4. Đồ thị các phép toán
Chương 8. Cơ sở dữ liệu phân tán
15

Trưởng Bộ môn

5
MỤC LỤC
Chương 1. Hệ quản trị cơ sở dữ liệu 7
1.1. Quan niệm về CSDL 7
1.2. Các khả năng của một hệ quản trị cơ sở dữ liệu. 7
Chương 2. Cơ sở dữ liệu hướng đối tượng 9
2.1. Nhu cầu về hệ thống cơ sở dữ liệu hướng đối tượng 9
2.1.1. Các đối tượng phức tạp 9
2.1.2. Quản lý các tri thức 9
2.1.3. Quản trị các dữ liệu phân tán 10
2.1.4. Nhu cầu về hệ thống cơ sở dữ liệu hướng đối tượng 10
2.2. Khái niệm về hướng đối tượng 11
2.2.1. Đối tượng 12
2.2.2. Lớp đối tượng 12
2.2.3. Cá thể 13
2.2.4. Kế thừa 13
2.3. Cơ sở dữ liệu hướng đối tượng 13
2.4. Thiết kế cơ sở dữ liệu hướng đối tượng 14
2.4.1. Phân lớp 14
2.4.2. Tổng quát hóa và đặc biệt hóa 14
2.4.3. Gộp 15
2.5. Xây dựng cơ sở dữ liệu hướng đối tượng 15
Chương 3. Cơ sở dữ liệu phân tán 17
3.1. Các phương pháp phân tán dữ liệu 17
3.1.1. Khái niệm về phân tán dữ liệu 17
3.1.1.1. Các lý do phân mảnh 17
3.1.1.2. Các kiểu phân mảnh 17
3.1.1.3. Mức độ phân mảnh 19

3.3.2. Mô hình giao dịch đơn giản 33
3.3.2.1. Ý nghĩa của giao dịch – hàm đặc trưng 33
3.3.2.2. Kiểm tra tính khả tuần tự bằng đồ thị có hướng 35
3.3.3. Nghi thức khóa 2 pha 35
3.3.4. Mô hình khóa đọc và khóa ghi 36
3.3.4.1. Ý nghĩa của giao dịch với khóa đọc và khóa ghi 36
3.3.4.2. Đồ thị tuần tự hóa trong các giao dịch Rlock và Wlock 36
Chương 4. Hệ trợ giúp ra quyết định 38
4.1. Giới thiệu về hệ trợ giúp ra quyết định 38
4.2. Thiết kế cơ sở dữ liệu cho hệ trợ giúp ra quyết định 39
4.2.1. Thiết kế logic 39
4.2.2. Thiết kế vật lý 40
4.3. Kho dữ liệu và kho dữ liệu chuyên đề 40
4.3.1. Kho dữ liệu 41
4.3.2. Kho dữ liệu chuyên đề. 41
4.3.3. Các lược đồ về chiều 42
4.4. Xử lý phân tích trực tuyến 43
4.4.1. Giới thiệu 43
4.4.2. Bảng chéo 43
4.4.3. Cơ sở dữ liệu nhiều chiều 44
4.5. Khai phá dữ liệu 44

7
Chương 1. Hệ quản trị cơ sở dữ liệu
1.1. Quan niệm về Cơ sở dữ liệu
Cơ sở dữ liệu (CSDL) là gì?
Định nghĩa: Một cơ sở dữ liệu (Database) là một tập hợp có cấu trúc các dữ liệu tác nghiệp được
lưu trữ lại và được các hệ ứng dụng cụ thể sử dụng.
Ngày nay CSDL tồn tại trong hầu hết các ứng dụng, ví dụ:
- Ứng dụng quản lý kho hàng;

- Đảm bảo tính độc lập dữ liệu hay sự bất biến của các chương trình ứng dụng đối với các thay
đổi về cấu trúc trong mô hình dữ liệu.
- Hỗ trợ các ngôn ngữ cấp cao nhất định cho phép người sử dụng định nghĩa cấu trúc của dữ
liệu, truy nhập dữ liệu và thao tác dữ liệu.
- Quản trị giao dịch, có nghĩa là khả năng cung cấp các truy cập đồng thời, đúng đắn đối với
CSDL từ nhiều người sử dụng tại cùng một thời điểm.
- Điều khiển truy cập, có nghĩa là khả năng hạn chế truy nhập đến dữ liệu bởi những người sử
dụng không được cấp phép và khả năng kiểm tra tính đúng đắn của dữ liệu.
- Phục hồi dữ liệu, có nghĩa là khả năng phụ hồi, không làm mất mát dữ liệu đối với các lỗi của
hệ thống.

9
Chương 2. Cơ sở dữ liệu hướng đối tượng
2.1. Nhu cầu về hệ thống CSDL hướng đối tượng
Nhìn chung hệ quản trị CSDL quan hệ được sử dụng nhiều nhưng chưa đáp ứng được hết các
yêu cầu của thực thế. Bên cạnh mô hình quan hệ, mô hình mạng và phân cấp vẫn tồn tại. Một số
hạn chế của hệ quản trị CSDL quan hệ.
2.1.1. Các đối tượng phức tạp
Một cách hình thức, một đối tượng nhằm xác định một cấu trúc phức tạp. Ví dụ: Các đối tượng
có cấu trúc phức tạp thường thấy là một siêu văn bản, một lược đồ, bức ảnh hay chương trình. Sự
phức tạp của các đối tượng này thể hiện qua: - Cấu trúc của đối tượng; - Mô hình hóa các đối tượng;
- Ngôn ngữ hỏi trên các đối tượng.
Bình thường, CSDL quan hệ xử lý các loại dữ liệu quen thuộc như số, chữ, ngày tháng, logic.
Với các loại dữ liệu này, chưa thể thể hiện các loại dữ liệu định tính hay một danh sách.
Chính vì vậy người ta đòi hỏi mô hình hóa các đối tượng phức tạp và xử lý chúng trong hệ quản
trị nhờ ngôn ngữ chương trình. Các đối tượng phức tạp được coi như các kí tự, các dữ liệu phức.
Trong chương trình, chúng được mô tả theo các kiểu đặc biệt. Giải pháp này đụng chạm đến các
khái niệm cũng quan trọng khác là hiện tượng dư thừa mã khi mô tả các đối tượng phức tạp trong
chương trình ứng dụng, đụng chạm đến sự phụ thuộc chương trình/dữ liệu. Như vậy việc xử lý các
dữ liệu phức, có kích thước lớn theo giải pháp đó là không hiệu quả.

cần giới thiệu loại dữ liệu đặc biệt là tri thức trong cả các chức năng quản trị và ngôn ngữ người sử
dụng. Khi đưa tri thức vào ngôn ngữ hỏi dữ liệu hay ngôn ngữ chương trình người ta cần giải quyết:
- Tri thức được mã hóa trong chương trình ứng dụng thường hay mắc nhược điểm là mô tả dữ
liệu trùng lặp.
- Việc quản lý mối liên hệ giữa những người sử dụng có dùng tri thức khó có thể tốt như việc
quản lý trong trường hợp chỉ sử dụng các dữ liệu định lượng.
- Việc suy luận với khối lượng lớn các thông tin như các sự kiện và tri thức trong hệ quản trị
CSDL có thể nặng nề, dẫn đến việc làm mất tính hiệu quả của toàn bộ hệ thống.
2.1.3. Quản trị các dữ liệu phân tán
Một hệ quản trị CSDL thông thường được tổ chức như một phần mềm cổ điển và được cài đặt
trên một máy tính tập trung. Hiện nay môi trường tin học phục vụ các công tác đa dạng với các đối
tượng phức tạp hơn, khiến người ta phải dùng đến hệ thống không tập trung và xử lý song song.
Như vậy cần có công cụ khác là hệ quản trị CSDL phân tán.
Hệ phân tán tạo lập do việc tập hợp các máy nối nhau theo mạng truyền thông dùng cho một
công việc tổng thể và được quản lý trên địa bàn rộng lớn. Yêu cầu đặt ra ở đây là quản trị và xử lý
những dữ liệu phân tán tại các máy độc lập. Các trạm độc lập ấy đã có các hệ quản trị, nhưng không
hoàn toàn giống nhau.
Để khai thác dữ liệu theo hệ thống quản trị CSDL phân tán, người ta không thể không thay đổi
hệ quản trị cũ. Ít ra cũng phải mở rộng hệ quản trị CSDL tập trung. Hệ thống phân tán cũng đòi hỏi
các chức năng xử lý song song.
Các hệ thống với các chức năng xử lý song song được thiết lập để khai thác các khả năng xử lý
song song của máy đa bộ xử lý. Đi đôi với các thiết bị cho phép xử lý dữ liệu một cách song song,
cũng có các ngôn ngữ bậc cao cho phép mô tả dữ liệu phân tán và mô tả song song các chức năng
xử lý.
Nhược điểm của các hệ quản trị CSDL thế hệ hai đòi hỏi đưa ra các hệ thống tiên tiến. Đó là các
CSDL hướng đối tượng, CSDL suy diễn và CSDL phân tán.
2.1.4. Nhu cầu về hệ thống CSDL hướng đối tượng
Các thí dụ về CSDL thường lấy từ lĩnh vực xử lý dữ liệu truyền thống. Một ứng dụng xử lý dữ
liệu có đặc trưng là dùng các tệp dữ liệu, xử lý dữ liệu tệp để đáp ứng các yêu cầu. Các công nghệ
CSDL quan hệ, mạng hay phân cấp đều thể hiện các tiếp cận khác nhau nhằm tích hợp các tệp dữ

Để thấy quan điểm về hướng đối tượng, hãy xét một vật trong thế giới thực là chiếc ghế. Ghế là
một phần tử, hay là một thể hiện của lớp rộng hơn gọi là đồ đạc. Một tập các thuộc tính liên kết với
đối tượng trong lớp đồ đạc, chẳng hạn giá thành, kích thước, trọng lượng, vị trí và mầu sắc. Những
điều này được áp dụng mỗi khi người ta nói về cái bàn hay cái ghế, tủ…. Bởi vì ghế là thành viên
của lớp đồ đạc, nó thừa kế tất cả các thuộc tính đã xác định cho lớp.
Mỗi đối tượng trong lớp đồ đạc có thể được xử lý theo nhiều cách. Mỗi phép xử lý này sẽ thay
đổi một hay nhiều thuộc tính của đối tượng và chúng được gọi là dịch vụ hay phương pháp trên đối
tượng.
Các đối tượng sẽ bao bọc:
- Dữ liệu thông qua giá trị thuộc tính.
- Các phép toán như các hoạt động có tác dụng thay đổi giá trị thuộc tính.
- Các đối tượng khác, như là các đối tượng phức tạp.
- Các hằng số, như các giá trị mặc định.
- Các thông tin liên quan.

12
Việc bao bọc thông tin của các đối tượng có nghĩa là tất cả thông tin này được thu gọn lại
dưới một tên và có thể được dùng như một đặc tả hay một thành phần chương trình.
2.2.1. Đối tượng
Khái niệm về đối tượng là khái niệm sinh ra từ việc nhận thức thế giới thực. Một đối tượng có
các đặc tính sau:
- Mang tên duy nhất, không thay đổi.
- Thuộc về một lớp.
- Có thể gửi các thông báo đến các đối tượng khác.
- Có trạng thái riêng.
Định nghĩa 2.1. Đối tượng là một thực thể có vai trò xác định rõ ràng trong lĩnh vực ứng dụng,
có trạng thái, hành vi và được xác định tên.
Ví dụ về các đối tượng thuộc lớp Người. Chúng liên lạc với nhau thông qua thông báo. Thông
báo là dạng các thao tác áp dụng lên đối tượng. Thao tác trong môi trường hướng đối tượng được
gọi là phương pháp. Chẳng hạn phương pháp kết hôn tác động lên đối tượng để biết đối tượng này

người ta có thể cài đặt che giấu các giá trị, ngay cả các liên kết cũng bị che giấu, cũng như không
thấy được các thông báo. Việc bảo vệ thông tin làm việc bên trong cùng với các giá trị đối tượng
trước các sử dụng thông thường này được gọi là che dấu thông tin.
Một khái niệm quan trọng trọng trong OOP là bao bọc, có nghĩa mọi vấn đề về đối tượng đều
được nhận biết thông qua định nghĩa lớp đối tượng. Người ta truy cập khái niệm nhờ giao diện lớp
và xác định các hành vi thông qua việc xác định lớp.
Định nghĩa 2.8. Sơ đồ đối tượng là đồ thị gồm các thể hiện của đối tượng, tương thích với sơ đồ
lớp.
Định nghĩa 2.9. Bao gói, hay bao bọc là kĩ thuật che giấu, làm ẩn những chi tiết về cài đặt bên
trong của đối tượng đối với các truy cập từ bên ngoài.
2.2.3. Cá thể
Cá thể hóa là quá trình khẳng định sự tồn tại của các đối tượng trong môi trường hướng đối
tượng, bằng việc xác định lớp của chúng. Mỗi đối tượng là một cá thể của lớp; thường được dùng
với thuật ngữ thể hiện của lớp.
2.2.4. Kế thừa
Khái niệm kế thừa là khái niệm quan trọng trong tiếp cận hướng đối tượng. Người ta thường
dụng thuật ngữ này khi chỉ định lớp đối tượng này tiếp thụ, thừa kế các thuộc tính của lớp đối tượng
khác. Tuy nhiên mỗi lớp con có thể mạng một số thuộc tính hay phương pháp riêng.
Định nghĩa 2.l0. Kế thừa là tính chất cho phép các lớp con kế thừa những thuộc tính, phép toán
của lớp cha.
Việc kế thừa nhiều lần xẩy ra khi một lớp kế thừa từ nhiều lớp.
2.3. CSDL hướng đối tượng
Dù có nhiều ngôn ngữ hướng đối tượng, đa số CSDL hướng đối tượng dựa trên C++. Lựa chọn
này là do tính hiệu quả và thông dụng của C++.
Thực tế CSDL hướng đối tượng có các ưu điểm:
- Cho phép xét các liên kết đối tượng dưới dạng các phép lưu trữ với các đối tượng.
- Các đối tượng được phép dùng chung cho nhiều người sử dụng.
- Khả năng phát triển kho tri thức bằng cách thêm các đối tượng mới và các phép xử lý kèm
theo.
- Phát triển hệ quản trị CSDL dựa trên việc xử lý các đối tượng phức tạp, thiết kế giao diện

2.4.1. Phân lớp
Quá trình phân lớp liên quan đến việc định tên đối tượng với các thuộc tính, hành vi tương tự
nhau và nhóm các đối tượng vào cùng một lớp. Theo thí dụ về sơ đồ người ta xác định sơ đồ với các
thuộc tính tên, ngày tạo, hình vẽ. Các phép toán chung là lưu trữ tìm kiếm, vẽ.
Trong đoạn chương trình trên, danh sách các trường và các kiểu dữ liệu đơn giản dùng cho các
sơ đồ được liệt kê trong mục thuộc tính. Tiếp theo là các phương thức, có tên và các tham số. Có
một số phương thức như tạo mới, xóa… áp dụng cho tất cả các đối tượng trong CSDL.
Tất cả các định nghĩa về giao diện lớp đối tượng cần có phép toán tạo mới và hủy bỏ đối tượng.
Quá trình phân lớp sẽ tạo ra lớp của các đối tượng có các thuộc tính, phương thức chung, và một vài
đối tượng có thuộc tính và phương thức riêng. Lúc đó người ta cần đến khái niệm tổng quát hóa và
chuyên biệt hóa.
2.4.2. Tổng quát hóa và đặc biệt hóa
Tổng quát hóa là quá trình xác định lớp đối tượng mang các thuộc tính tương tự và theo sự
tương tự này người ta có thể trừu tượng hóa để được lớp cao hơn, hay lớp cha. Chẳng hạn ban đầu
người ta xác định lớp hình tam giác, hình vuông, hình chữ nhật, và hình tròn rồi trừu tượng hóa
thành lớp cao hơn về sơ đồ, gồm các thuộc tính chung của tất cả các sơ đồ.
Định nghĩa 2.11. Lớp trừu tượng là lớp không có thể hiện trực tiếp, nhưng các thành phân sau
nó có thể có thể hiện trực tiếp.
Định nghĩa 2.12. Lớp cụ thể là lớp có thể có các thể hiện trực tiếp.

15
Chuyên biệt hóa là quá trịnh ngược lại với tổng quát hóa. Bắt đầu từ lớp sơ đồ, người ta có thể
xác định lớp con để phân biệt các loại sơ đồ khác nhau; mỗi lớp con chia sẻ thuộc tính và phương
thức chung trong lớp sơ đồ nhưng có các thuộc tính và phương thức dùng riêng.
Người ta dùng cây phân cấp để thể hiện quá trình tổng quát hóa. Phân cấp nả rất có ý nghĩa
trong hệ thống hướng đối tượng, để chỉ ra dãy các thừa kế. Khi mô tả các lớp, người ta cần chỉ ra sự
tham gia của lớp vào dãy kế thừa này.
Hai định nghĩa lớp đối tượng này đều tham chiếu đến lớp đối tượng cha bằng câu lệnh kế thừa.
Lớp tam giác thừa kế tất cả các thuộc tính và phương thức của sơ đồ. Các thuộc tính bổ sung cũng
được mô tả ngay. Phương thức tạo mới được mô tả lại, tính đến các đặc trưng riêng của hình tam

- Chi phí nhỏ nhất: Hàm chi phí gồm có chi phí lưu mỗi mảnh F
i
tại vị trí S
j
, chi phí vấn tin F
i
tại vị trí S
j
, chi phí cập nhật F
i
tại tất cả mọi vị trí chứa nó và chi phí truyền dữ liệu. Vì thế bài toán
cấp phát cố gắng tìm một lược đồ cấp phát với hàm chi phí tổ hợp thấp nhất.
- Hiệu quả: Chiến lược cấp phát được thiết kế nhằm duy trì một hiệu quả lớn nhất đó là hạ thấp
thời gian đáp ứng và tăng tối đa lưu lượng hệ thống tại mỗi vị trí.
Nói chung bài toán cấp phát tổng quát là bài toán phức tạp, vì thế các nghiên cứu đều tập trung
tìm ra các giải thuật heuristic tốt để có thể có được các lời giải tối ưu. Để phân biệt bài toán cấp
phát tập tin truyền thống với cấp phát mảnh trong các thiết kế CSDL phân tán, chúng ta gọi bài toán
thứ nhất là bài toán cấp phát tập tin, và bài toán sau là bài toán cấp phát CSDL.
Hiện không có một mô hình heuristic tổng quát nào nhận một tập các mảnh và sinh ra một chiến
lược cấp phát gần tối ưu ứng với các loại ràng buộc. Các mô hình đã được phát triển chỉ mới đưa ra
một số giả thiết đơn giản hóa và dễ áp dụng cho một số cách đặt vấn đề cụ thể.
Thông tin cho cấp phát:
Thông tin về CSDL:
Để thực hiện phân mảnh ngang, chúng ta đã định nghĩa độ tuyển hội sơ cấp. Bây giờ chúng ta
cần mở rộng định nghĩa đó cho các mảnh và định nghĩa độ tuyển của một mảnh F
j
ứng với câu vấn
tin q
i
. Đây là số lượng các bộ của F

trong mỗi lần chạy của nó – ký hiệu là RR
ij
. Và
tương ứng là các truy xuất cập nhật – ký hiệu là UR
ij
.
Chúng ta định nghĩa hai ma trận UM và RM với các phần tử tương ứng u
ij
và r
ij
được đặc tả như
sau
- u
ij
= 1 nếu vấn tin q
i
có cập nhật mảnh F
j
, ngược lại sẽ bằng 0
- r
ij
= 1 nếu vần tin q
i
cần đọc mảnh F
j
, ngược lại sẽ băng 0.
Một vectơ O gồm các giá trị 0(i) cũng được định nghĩa, với 0(i) đặc tả vị trí đưa ra câu vấn tin
q
i
. Cuối cúng để định nghĩa ràng buộc thời gian đáp ứng, thời gian đáp ứng tối đa được phép của

- Các mảnh sẽ được cấp phát trên mạng như thế nào?
- Những thông tin nào sẽ cần thiết cho việc phân mảnh và cấp phát?
3.1.1.1. Các lý do phân mảnh
Trước tiên việc phân tán dữ liệu được thực hiện trên cơ sở cấp phát các tập tin cho các nút trên
một mạng máy tính. Các nút mạng thường nằm ở các vị trí địa lý khác nhau trải rộng trên một diện
tích lớn. Do vậy để tối ưu việc khai thác thông tin thì dữ liệu không thể để tập trung mà phải phân
tán trên các nút của mạng.
Hơn nữa một quan hệ không phải là một đơn vị truy xuất dữ liệu tốt nhất. Ví dụ như, nếu ứng
dụng được thực hiện trên một bộ phận nhỏ các dữ liệu của quan hệ mà quan hệ đó nằm tại các vị trí
khác nhau thì có thể gây ra những truy xuất thừa và hơn thế việc nhân bản các quan hệ làm tốn
không gian bộ nhớ. Do vậy phân rã một quan hệ thành nhiều mảnh, mỗi mảnh được xử lý như một
đơn vị sẽ cho phép thực hiện nhiều giao dịch đồng thời. Một câu truy vấn ban đầu có thể được chia
ra thành một tập các truy vấn con, các truy vấn này có thể được thực hiện song song trên các mảnh
sẽ giúp cải thiện tốc độ hoạt động của hệ thống.
Tuy nhiên chúng ta cũng sẽ gặp những rắc rối của việc phân mảnh, ví dụ nếu các ứng dụng có
những xung đột sẽ ngăn cản hoặc gây khó khăn cho việc truy xuất dữ liệu. Phân rã các mảnh nói
chung làm tăng chi phí trong việc truy xuất dữ liệu. Một vấn đề nữa liên quan đến việc kiểm soát
ngữ nghĩa và tính toàn vẹn dữ liệu.
3.1.1.2. Các kiểu phân mảnh
Thể hiện của các quan hệ chính là các bảng, vì thế vấn đề là tìm những cách khác nhau để chia
một bảng thành nhiều bảng nhỏ hơn. Rõ ràng có hai phương pháp khác nhau: Chia bảng theo chiều
dọc và chia bảng theo chiều ngang. Chia dọc ta được các quan hệ con mà mỗi quan hệ chứa một tập
con các thuộc tính của quan hệ gốc – gọi là phân mảnh dọc. Chia ngang một quan hệ ta được các
quan hệ con mà mỗi quan hệ chứa một số bộ của quan hệ gốc - gọi là phân mảnh ngang.

18
Ngoài ra còn có một khả năng hỗn hợp, đó là phân mảnh kết hợp cách phân mảnh ngang và
dọc. Tất nhiên quá trình phân mảnh gắn liến với vấn đề cấp phát và bài toán cụ thể.
Ví dụ 3.1.
Trong ví dụ này chúng ta sử dụng một CSDL của một công ty máy tính thực hiện các dự án

Minh Tài
Ks Máy
E2
P2
Phân tích
6
E4
Dương Hà
Lập trình viên
E3
P3
Tư vấn
10
E5
Minh Hoa
Phân tích hệ thống
E3
P4
Kỹ sư
48
E6
Văn Hiền
Ks Điện
E4
P2
Lập trình viên
18
E7
Hoài Nam
Ks Máy

Hà Nội
Ks Điện
4000
P2
CSDL
135000
Hải Phòng
Phân tích hệ thống
10000
P3
CAD/CAM
250000
Hà Nội
Ks Máy
3500
P4
Bảo Trì
310000
Quảng Ninh
Lập trình viên
4100
Người ta có thể chia ngang quan hệ DuAn Thành các quan hệ con DuAn1, DuAn2. DuAn1 chứa
những thông tin về các dự án có ngân sách dưới 200000$, còn DuAn2 lưu các thông tin về các dự
án có ngân sách trên 200000$.
Hình 3.2. Phân mảnh ngang quan hệ DuAn
DuAn1
MaDuAn
Ten
KinhPhi
Vitri

KinhPhi
MaDuAn
Ten
Vitri
P1
150000
P1
Trang thiết bị
Hà Nội
P2
135000
P2
CSDL
Hải Phòng
P3
250000
P3
CAD/CAM
Hà Nội
P4
310000
P4
Bảo Trì
Quảng Ninh
3.1.1.3. Mức độ phân mảnh
Phân mảnh CSDL đến mức độ nào là một quyết định rất quan trong có ảnh hưởng đến hiệu năng
thực hiện vấn tin. Mức độ phân mảnh có thể là từ thái cực không phân mảnh nào đến thái cực phân
mảnh thành từng bộ hoặc từng thuộc tính. Tuy nhiên nếu phân mảnh quá nhỏ sẽ có những tác động
không tốt đến hoạt động khai thác CSDL. Vậy cần phải định ra được một mức độ phân mảnh thích
hợp. Mức độ này sẽ tùy thuộc vào từng CSDL và các ứng dụng CSDL cụ thể.

,…, R
N
và mục
dữ liệu t
i
nằm trong mảnh r
i
, thì nó sẽ không nằm trong các mảnh R
k
với k  j. Tiêu chuẩn này đảm
bảo rằng các mảnh ngang sẽ tách biệt với nhau. Nếu quan hệ được phân mảnh dọc, các thuộc tính
khóa chính phải được lặp lại trong mỗi mảnh. Vì thế trong trường hợp phân mảnh dọc, tính tách biệt
chỉ được định nghĩa trên các trường không phải là khóa chính của một quan hệ.
3.1.1.5. Các kiểu cấp phát
Giả sử CSDL đã được phân mảnh hợp lý và cần quyết định cấp phát các mảnh cho các vị trí trên
mạng. Khi dữ liệu được cấp phát, nó có thể được nhân bản hoặc duy trì một bản duy nhất.
Lý do cần phải nhân bản là nhằm đảm bảo độ tin cậy và hiệu quả cho các câu vấn tin chỉ đọc.
Nếu có nhiều bản sao của một mục dữ liệu thì chúng ta vẫn có cơ hội truy xuất được dữ liệu đố
ngay cả khi hệ thống xẩy ra sự cố. Hơn nữa các câu vấn tin chỉ đọc truy xuất đến cùng một mục dữ
liệu có thể cho thực hiện song song bởi vì các bản sao có mặt tại nhiều vị trí. Ngược lại câu vấn tin
cập nhật có thể gây ra nhiều rắc rối bởi vì hệ thống phải bảo đảm rằng tất cả các bản sao phải được
cập nhật chính xác. Vì vậy quyết định nhân bản cần được cân nhắc và phụ thuộc vào tỷ lệ giữa các
câu vấn tin chỉ đọc và câu vấn tin cập nhật. Quyết định này có ảnh hưởng đến tất cả các thuộc toán
của hệ quản trị CSDL phân tán và các chức năng kiểm soát khác.
3.1.1.6. Các yêu cầu thông tin
Một điều cần lưu ý trong việc thiết kế phân tán là quá nhiều yếu tố có ảnh hưởng đến một thiết
kế tối ưu. Tổ chức logic của CSDL, vị trí các ứng dụng, đặc tính truy xuất của các ứng dụng đến

20
CSDL, và các đặc tính của hệ thống máy tính tại mỗi vị trí đều có ảnh hưởng đến các quyết định

i
 <giá trị>
Trong đó   {=, <, <=, >=, >, <>}, A
i
là một thuộc tính, <giá trị>  dom(A
i
).
Như vậy cho trước một lược đồ R, nếu các miền giá trị dom(A
i
) là hữu hạn chúng ta có thể xác
định được tập tất cả các vị từ đơn giản trên R.
Ví dụ: Với hình 3.1. các vị từ đơn giản của quan hệ DuAn:
P1: Ten = “Bảo trì”
P2: KinhPhi <= 200000
Trong các bài toán thức tế các câu vấn tin thường chứa nhiều vị từ phức tạp hơn, là tổ hợp của
các vị từ đơn giản. Ví dụ vị từ hội sơ cấp của các vị từ đơn giản. Bởi một biểu thức boolean luôn có
thê biến đổi được thành dạng chuẩn hội cho nên chúng ta sử dụng hội sơ cấp để biểu diễn các vị từ
phức tạp.
Cho lược đồ quan hệ R(U), U = A
1
, A
2
,…, A
N
trong đó mỗi A
i
là một thuộc tính có miền giá trị
dom(A
i
). Pr = {p

Theo những thông tin định tính về các ứng dụng chúng ta cần biết hai tập dữ liệu:

37
Bây giờ ta giả sử rằng T
4
là một giao dịch nhận khóa đọc A trước khi T
1
khóa ghi A. Nếu T
1
xuất hiện trước T
4
trong lịch biểu tuần tự thì T
4
đọc một giá trị của A có chứa hàm f, còn trong lịch
biểu S, giá trị được đọc bởi T
4
không chứa f. Vì vậy, T
4
phải thực hiện trước T
1
trong một lịch biểu
tuần tự tương đương với S. Suy luận duy nhất không thê thực hiện được là nếu trong S hai giao dịch
cùng nhần khóa đọc một mục A theo một thứ tự nào đó thì những giao dịch này phải xuất hiện theo
thứ tự đó trong một lịch biểu tuần tự. Đúng ra thứ tự tương đối này là của các khóa đọc không tạo ra
sẹ khác biệt nào trên các giá trị được tạo ra bởi các giao dịch thực hiện đồng thời.
Thuật toán 3.4. Kiểm tra tính khả tuần tự của các lịch biểu với các khóa đọc/ghi.
Vào: Một lịch biểu S cho một tập các giao dịch T
1
, T
2

Nếu G có chu trình thi S là bất khả tuần tự, ngược lại thì một sắp xếp topo của G là thứ tự tuần
tự cho các giao dịch này.

22
0. Gọi F tập các mảnh hội sơ cấp
Pr’ = , F = 
1. p  Pr, nếu p phân hoạch R theo quy tắc 1
- Pr’ = Pr’  {p}
- Pr = Pr – {p}
- F = F  {f} với f là một mảnh hội sơ cấp theo p
2. p  Pr nếu p phân hoạch một mảnh f  F theo quy tắc 1
- Pr’ = Pr’  {p}
- Pr = Pr – {p}
- F = F  {f} với f là một mảnh hội sơ cấp theo p
Lặp lại bước 2 cho đến khi nào không p  Pr’ phân hoạch một mảnh f  F
3. p  Pr’ nếu p’ mà p tương đương với p’
- Pr’ = Pr’ – {p}
- F = F – {f} với f là một mảnh hội sơ cấp theo p
Sau bước 3 Pr’ là tập vị từ đầy đủ và tối thiểu cần tìm.
Bước tiếp theo của thiết kế phân mảnh ngang nguyên thủy là suy dẫn ra tập các vị từ hội sơ cấp
có thể được định nghĩa trên các vị từ trong tập Pr’. Các vị từ hội sơ cấp này xác định các mảnh cho
bước cấp phát.
Bước cuối của quá trình thiết kế là loại bỏ một số mảnh vô nghĩa. Điều này được thực hiện bằng
cách xác định những vị từ mâu thuẫn với tập các phép kéo theo I. Chẳng hạn, nếu Pr’ = (P1, P2),
trong đó
P1: A = giá trị 1
P2: A = giá trị 2
Và miền biến thiên của A là {giá trị 1, giá trị 2} rõ ràng I chứa hai phép kéo theo với khẳng
định:
i1: (A = giá trị 1)   (A = giá trị 2)

theo phép toán chọn trên quan hệ chủ nhân của đường nối đó. Như thế nếu cho trước một liên kết L,
trong đó owner(L) = S và member(L) = R, các mảnh ngang dẫn xuất của R được định nghĩa là:
R
i
= R S
i
, 1  i  k
Trong đó k là số lượng các mảnh được định nghĩa trên R, và S
i
= S(E
i
), với E
i
là công thức định
nghĩa phân mảnh ngang nguyên thủy S
i
.
Ví dụ: Xét liên kết giữa bảng Luong và NhanVien. Chúng ta có thể nhóm các nhân viên thành
hai nhóm tùy theo lương. Giả sử nhóm có lượng từ 4000$ trở xuống và nhóm lương trên 4000$. Hai
mảnh NhanVien1 và NhanVien2 được định nghĩa như sau:
NhanVien1 = NhanVien Luong1
NhanVien2 = NhanVien Luong2
Trong đó
Luong1 = Luong(Luong  4000)
Luong2 = Luong(Luong > 4000)
Kết quả thu được như sau:
NhanVien1
NhanVien2
MaNV
Ten

từ nối giữa quan hệ chủ và quan hệ thành viên (chẳng hạn NhanVien.ChucVu = Luong.ChucVu).
Cũng có một vấn đề phức tạp phải chú ý, trong lược đồ CSDL chúng ta hay gặp nhiều đường nối
đến một quan hệ R. Như thế có thể có nhiều cách phân mảnh ngang dẫn xuất cho R. Quyết định
chọn cách phân mảnh nào cần dựa trên hai tiêu chuẩn sau:
1. Phân mảnh có đặc tính nối tốt hơn;
2. Phân mảnh được sử dụng trong nhiều ứng dụng hơn.

24
3.1.2.4. Kiểm tra tính đúng đắn của phân mảnh ngang
1. Tính đầy đủ
Tính đầy đủ của một phân mảnh ngang nguyên thủy dựa vào các vị từ chọn được dùng. Với
điều kiện các vị từ chọn là đầy đủ, phân mảnh thu được cung được bảo đảm là đầy đủ, bởi vì cơ sở
của thuật toán phân mảnh là một tập các vị từ cực tiểu và đầy đủ. Tính đầy đủ sẽ được bảo đảm với
điều kiện là không có sai sót xẩy ra khi định nghĩa tập vị từ đầy đủ và cực tiểu Pr. Tính đầy đủ của
phân mảnh ngang dẫn xuất có hơi khác. Khó khăn là do vị từ định nghĩa phân mảnh có liên quan
đến hai quan hệ.
Gọi R là quan hệ thành viên của một liên kết mà chủ là quan hệ S được phân mảnh thành F
s
=
{S
1
, S
2
,…, S
N
}. A là thuộc tính nối giữa R và S. Vậy đối với mỗi bộ t của R, phải có một bộ t’ sao
cho t.A = t’.A
Quy tắc này được gọi là ràng buộc toàn vẹn hay toàn vẹn tham chiếu, bảo đảm mọi bộ trong các
mảnh của quan hệ thành viên đều nằm trong quan hệ chủ.
2. Tính tái thiết được

các quan hệ nhỏ hơn để nhiều ứng dụng có thể chỉ chạy trên một quan hệ. Trong ngữ cảnh này, một
phân mảnh tối ưu là một phân mảnh sinh ra một lược đồ phân mảnh cho phép giảm đến tối da thời
gian thực thi các ứng dụng chạy trên các mảnh đó.
Phân mảnh dọc đã được nghiên cứu trong ngữ cảnh của các hệ CSDL tập trung. Lý do chính là
sử dụng nó làm một công cụ thiết kế cho phép các vấn tin làm việc trên các quan hệ nhỏ hơn vì thế
giảm bớt số truy xuất và tiết kiệm bộ nhớ. Một trong số các phương pháp phân mảnh dọc đã nghiên
cứu trong mô hình CSDL quan hệ là việc chuẩn hóa các quan hệ về các dạng chuẩn cấp cao.
Bên cạnh phương pháp chuẩn hóa các quan hệ còn có những phương pháp khác và chúng
thường gắn với mục tiêu của bài toán.
3.1.4. Cấp phát.
Bài toán cấp phát:
Giả sử rằng có một tập các mảnh F = {F
1
, F
2
,…, F
N
} và một mạng máy tính bao gồm các vị trị S
= {S
1
, S
2
,…, S
M
} trên đó có một tập các ứng dụng dạng Q = {q
1
, q
2
,…, q
k