Giáo trình Cơ sở dữ liệu 2
MỤC LỤC
Chương 1. Hệ quản trị cơ sở dữ liệu............................................................................ 3
1.1. Quan niệm về CSDL ........................................................................................ 3
1.2. Các khả năng của một hệ quản trị cơ sở dữ liệu................................................ 3
Chương 2. Cơ sở dữ liệu hướng đối tượng .................................................................. 5
2.1. Nhu cầu về hệ thống cơ sở dữ liệu hướng đối tượng......................................... 5
2.1.1. Các đối tượng phức tạp.............................................................................. 5
2.1.2. Quản lý các tri thức.................................................................................... 6
2.1.3. Quản trị các dữ liệu phân tán ..................................................................... 6
2.1.4. Nhu cầu về hệ thống cơ sở dữ liệu hướng đối tượng .................................. 7
2.2. Khái niệm về hướng đối tượng ......................................................................... 7
2.2.1. Đối tượng .................................................................................................. 8
2.2.2. Lớp đối tượng............................................................................................ 9
2.2.3. Cá thể ........................................................................................................ 9
2.2.4. Kế thừa...................................................................................................... 9
2.3. Cơ sở dữ liệu hướng đối tượng ....................................................................... 10
2.4. Thiết kế cơ sở dữ liệu hướng đối tượng .......................................................... 10
2.4.1. Phân lớp .................................................................................................. 11
2.4.2. Tổng quát hóa và đặc biệt hóa.................................................................. 11
2.4.3. Gộp.......................................................................................................... 12
2.5. Xây dựng cơ sở dữ liệu hướng đối tượng........................................................ 12
Chương 3. Cơ sở dữ liệu phân tán ............................................................................. 14
3.1. Các phương pháp phân tán dữ liệu.................................................................. 14
3.1.1. Khái niệm về phân tán dữ liệu ................................................................. 14
3.1.1.1. Các lý do phân mảnh......................................................................... 14
3.1.1.2. Các kiểu phân mảnh.......................................................................... 14
3.1.1.3. Mức độ phân mảnh ........................................................................... 16
3.1.1.4. Quy tắc phân mảnh đúng đắn............................................................ 16
3.1.1.5. Các kiểu cấp phát.............................................................................. 16
3.1.1.6. Các yêu cầu thông tin........................................................................ 17
3.1.2. Phân mảnh ngang..................................................................................... 17
3.1.2.1. Yêu cầu thông tin của phân mảnh ngang........................................... 17
3.1.2.2. Phân mảnh ngang nguyên thủy.......................................................... 18
3.1.2.3. Phân mảnh ngang dẫn xuất ............................................................... 20
3.1.3. Phân mảnh dọc. ....................................................................................... 22
3.1.4. Cấp phát. ................................................................................................. 22
3.2. Kiểm soát dữ liệu ngữ nghĩa........................................................................... 23
3.2.1. Quản lý khung nhìn ................................................................................. 23
3.2.1.1. Khung nhìn trong quản lý tập trung................................................... 24
3.2.1.2. Cập nhật qua các khung nhìn ............................................................ 24
3.2.1.3. Khung nhìn trong cơ sở dữ liệu phân tán........................................... 25
3.2.2. An toàn dữ liệu........................................................................................ 25
3.2.2.1. Kiểm soát cấp quyền tập trung.......................................................... 25
3.2.2.2. Kiểm soát cấp quyền phân tán........................................................... 26
3.3. Quản lý giao dịch và điểu khiền đồng thời phân tán........................................ 27
3.3.1. Các khái niệm cơ bản về giao dịch........................................................... 27
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.3.1.1. Tính nguyên tử.................................................................................. 27
3.3.1.2. Mục dữ liệu....................................................................................... 28
3.3.1.3. Khóa................................................................................................. 28
3.3.1.4. Kiểm soát hoạt động đồng thời bằng khóa......................................... 28
3.3.1.5. Khóa sống (livelock)......................................................................... 30
3.3.1.6. Khóa “cứng” (deadlock) ................................................................... 30
3.3.1.7. Tính khả tuần tự của lịch biểu........................................................... 31
3.3.1.8. Bộ xếp lịch........................................................................................ 32
3.3.1.9. Nghi thức.......................................................................................... 32
3.3.2. Mô hình giao dịch đơn giản ..................................................................... 32
3.3.2.1. Ý nghĩa của giao dịch – hàm đặc trưng ............................................. 32
3.3.2.2. Kiểm tra tính khả tuần tự bằng đồ thị có hướng................................. 33
3.3.3. Nghi thức khóa 2 pha............................................................................... 34
3.3.4. Mô hình khóa đọc và khóa ghi................................................................. 35
3.3.4.1. Ý nghĩa của giao dịch với khóa đọc và khóa ghi ............................... 35
3.3.4.2. Đồ thị tuần tự hóa trong các giao dịch Rlock và Wlock..................... 35
Chương 4. Hệ trợ giúp ra quyết định......................................................................... 37
4.1. Giới thiệu về hệ trợ giúp ra quyết định ........................................................... 37
4.2. Thiết kế cơ sở dữ liệu cho hệ trợ giúp ra quyết định ....................................... 38
4.2.1. Thiết kế logic........................................................................................... 38
4.2.2. Thiết kế vật lý.......................................................................................... 39
4.3. Kho dữ liệu và kho dữ liệu chuyên đề............................................................. 39
4.3.1. Kho dữ liệu.............................................................................................. 40
4.3.2. Kho dữ liệu chuyên đề............................................................................. 40
4.3.3. Các lược đồ về chiều................................................................................ 41
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 ........................................................................ 43
4.5. Khai phá dữ liệu............................................................................................. 43
PDF created with pdfFactory Pro trial version www.pdffactory.com
Chương 1. Hệ quản trị cơ sở dữ liệu
1.1. Quan niệm về CSDL
Cơ sở dữ liệu là gì?
Một cơ sử dữ liệu có thể định nghĩa như sau: Một cơ sở dữ liệu 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 thông dụng, ví dụ:
- Ứng dụng quản lý kho hàng;
- Hệ thống đặt chỗ máy bay;
- Ứng dụng quản lý nguồn nhân lực…
Hệ quản trị cơ sở dữ liệu là gì?
Chúng ta có thể định nghĩa hệ quản trị cơ sở dữ liệu như sau: Hệ quản trị cơ sở dữ liệu là
một hệ thống phần mềm cho phép tạo lập cơ sở dữ liệu và điều khiển mọi truy nhập đối với cơ
sở dữ liệu đó.
Hệ cơ sở dữ liệu là gì?
Hệ cơ sở dữ liệu là một hệ thống bao gồm 4 thành phần:
- Cơ sở dữ liệu hợp nhất: Cơ sở dữ liệu của hệ có hai tính chất tối thiểu hóa dư thừa và
được chia sẻ.
- Những người sử dụng: Người sử dụng của hệ là bất kỳ một người nào có nhu cầu truy
nhập vào cơ sở dữ liệu, có nghĩa là người sử dụng bao gồm tất cả những người sử dụng cuối,
những người viết chương trình ứng dụng và những người điều khiển toàn bộ hệ thống hay còn
gọi là người quản trị cơ sở dữ liệu.
- Phần mềm quản trị cơ sở dữ liệu.
- Phần cứng của hệ bao gồm các thiết bị nhớ thứ cấp được sử dụng để lưu trữ cơ sở dữ
liệu.
1.2. Các khả năng của một hệ quản trị cơ sở dữ liệu.
Có hai khả năng cho phép phân biệt các hệ quản trị cơ sở dữ liệu với các kiểu hệ thống lập
trình khác:
- Khả năng quản lý dữ liệu tồn tại lâu dài;
- Khả năng truy nhập các khối lượng dữ liệu lớn một cách hiệu quả.
Đặc điểm thứ nhất chỉ ra rằng có một cơ sở dữ liệu tồn tại trong một thời gian dài, nội
dụng của cơ sở dữ liệu này là các dữ liệu mà một hệ quản trị cơ sở dữ liệu truy nhập và quản
lý. Đặc điểm thứ hai phân biệt một hệ quản trị với một hệ thống xử lý tệp cũng quản lý dữ liệu
tồn tại lâu dài nhưng nói chung không cung cấp các truy nhập nhanh chóng đến các bộ phận
dữ liệu tùy ý.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Các khả năng của một hệ quản trị cơ sở dữ liệu hầu hết là cần thiết khi khối lượng dữ liệu
cần lưu trữ là rất lớn, bởi vì các khối lượng dữ liệu nhỏ thì các kỹ thuật truy nhập đơn giản,
chẳng hạn quét tuần tự các dữ liệu là thích hợp.
Khi xem xét hai đặc điểm trên của một hệ quản trị cơ sở dữ liệu là cơ bản, còn một số các
khả năng khác mà có thể thấy trong hầu hết các hệ quản trị cơ sở dữ liệu thương mại, đó là:
- Hỗ trợ ít nhất một mô hình dữ liệu hay một sự trừu tượng toán học mà qua đó người sử
dụng có thể quan sát dữ liệu.
- Đả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 cơ sở dữ liệu 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.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Chương 2. Cơ sở dữ liệu hướng đối tượng
2.1. Nhu cầu về hệ thống cơ sở dữ liệu hướng đối tượng
Nhìn chung hệ quản trị cơ sở dữ liệu 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ị cơ sở dữ liệu quan hệ.
2.1.1. Các đối tượng phức tạp
Một cách phi 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, cơ sở dữ liệu quan hệ xử lý 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ả.
Hơn nữa, do cấu trúc dữ liệu hiện tại là quá đơn giản, không thể dùng cho mô hình hóa
các đối tượng phức tạp, thí dụ đối tượng trong hệ thống phân cấp hay đồ thị.
Ví dụ 2.1. Một đối tượng phức tạp, chẳng hạn trong CAD, thường được phân rã và đặt
trong các quan hệ nhỏ; chính vì vậy mà thông tin ngữ nghĩa sẵn có trong một vấn đề bị chia
nhỏ ra, phân tán dưới dạng các giá trị trong các quan hệ. Điều này khiến người sử dụng phải
nhìn thế giới của bài toán theo cách nhìn của cơ sở dữ liệu quan hệ. Để có thể khôi phục các
ngữ nghĩa ban đầu, không tránh được việc yêu cầu các phép kết nối quan hệ, là phép toán tốn
kém tài nguyên để thực hiện.
Ngoài việc mô hình hóa, việc truy vấn cơ sở dữ liệu thông qua ngôn ngữ cũng cần phải
xem xét. Khó có thể có ngôn ngữ lý tưởng trên các đối tượng phức tạp. Cũng có thể sử dụng
các ngôn ngữ lập trình để giải quyết nhưng sẽ gặp khó khăn về sự khác biệt giữa kiểu dữ liệu
và cách khai thác dữ liệu của ngôn ngữ lập trình và ngôn ngữ cơ sở dữ liệu. Ngôn ngữ truy
vấn cơ sở dữ liệu thì dựa trên cơ sở tập hợp, trong khi ngôn ngữ lập trình dựa trên các thủ tục.
Các ứng dụng về cơ sở dữ liệu được nhìn nhận theo hai khía cạnh:
- Khía cạnh tĩnh: thể hiện qua các dữ liệu.
- Khía cạnh động: thể hiện qua các phép xử lý tác động lên dữ liệu.
Người ta thấy những đối tượng được hệ quản trị cơ sở dữ liệu quan hệ xử lý đặc biệt là dữ
liệu tĩnh. Phần tác động của chúng, tức các hoạt động, được mô tả riêng biệt thông qua các
PDF created with pdfFactory Pro trial version www.pdffactory.com
chương trình ứng dụng tác động lên các dữ liệu. Người tập trình phải biết cấu trúc quan hệ
của các đối tượng, bởi lẽ hệ quản trị cơ sở dữ liệu quan hệ không đáp ứng những nhu cầu về
các đối tượng động.
2.1.2. Quản lý các tri thức
Một quan hệ được tổ chức như một tập các n-bộ, thể hiện những sự kiện. Một hệ quản trị
cơ sở dữ liệu quan hệ cho phép xử lý các sự kiện, các tri thức dưới dạng tổng quát và trừu
tượng.
Người ta sử dụng tri thức này theo hai khía cạnh, ứng với hai cách suy luận:
- Đưa ra sự kiện mới, dựa trên các sự kiện và các tri thức đã biết.
- Sử dụng để trả lời các câu hỏi cần đến suy luận.
Do vậy việc quản lý các tri thức trong cơ sở dữ liệu là nhu cầu thực tế, nhất là đối với các
ứng dụng cần đến các kiến thức chuyên gia.
Hệ quản trị cơ sở dữ liệu sử dụng các điều kiện toàn vẹn. Điều kiện ràng buộc dưới dạng
các tri thức 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ị cơ sở dữ liệu 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ị cơ sở dữ liệu 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ị cơ sở dữ liệu 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 và dụng
cho một công việc tổng thể và được quản lý trên địa bàn rộng về địa lý. 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ị cơ sở dữ liệu 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ị cơ sở dữ liệu 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 ho phép mô tả dữ liệu phân tán và mô tả song song
các chức năng xử lý.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Nhược điểm của các hệ quản trị cơ sở dữ liệu thế hệ hai đòi hỏi đưa ra các hệ thống tiên
tiến. Đó là các cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu suy diễn và cơ sở dữ liệu phân
tán.
2.1.4. Nhu cầu về hệ thống cơ sở dữ liệu hướng đối tượng
Các thí dụ về cơ sở dữ liệu 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ệ cơ sở dữ liệu 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ữ liệu để đáp ứng nhu cầu ứng dụng. Các điểm mạnh của cơ sở
dữ liệu quan hệ đã khiến chúng chiếm ưu thế trên thị trường cơ sở dữ liệu. Tuy nhiên việc
tăng tính khái quát, trừu tượng của các kiểu dữ liệu do máy xử lý lại là điểm yếu của công
nghệ quan hệ. Trước khi đề cập vấn đề hướng đối tượng trong cơ sở dữ liệu, bên cạnh các hạn
chế của cơ sở dữ liệu quan hệ, người ta còn thấy các hạn chế nêu trên về hệ thống cơ sở dữ
liệu nói chung, về phạm vị ngữ nghĩa, về cấu trúc dữ liệu, về tính chủ động và tính toàn vẹn
dữ liệu.
1. Phạm vị ngữ nghĩa: Lý thuyết quan hệ chỉ hỗ trợ một phần các khái niệm ngữ nghĩa.
Nhiều khái niệm về ngữ nghĩa không thể hiện qua mô hình quan hệ được.
2. Cấu trúc dữ liệu: Các hệ thống quan hệ bị hạn chế bớt về cấu trúc dữ liệu. Trong hệ
thống quan hệ các dữ liệu được tổ chức thành bảng gồm các thuộc tính đơn. Nhiều kiểu thông
tin không phù hợp với cách thể hiện này.
3. Tính thụ động của dữ liệu: Trong hệ thống quan hệ, dữ liệu hầu hết là thụ động. Các
chương trình ứng dụng có vai trò kích hoạt các dữ liệu này, để dữ liệu trở nên linh động. Tỏng
mô hình hướng đối tượng, người ta có thể biết được hành vi cũng như cấu trúc dữ liệu.
4. Toàn vẹn ngữ nghĩa: Đảm bảo tính toàn vẹn ngữ nghĩa là có thể giữ được tính bền vững
của ngữ nghĩa cơ sở dữ liệu dưới tác động của các chương trình. Hệ thống quan hệ quản lý
hành vi của dữ liệu theo các chương trình ứng dụng. Cùng một dữ liệu có thể mang các hành
vi khác nhau, nên dữ liệu cần có ý nghĩa khác nhau tùy theo chương trình sử dụng, dễ gây nên
tình trạng vi phạm tính toàn vẹn dữ liệu. Những tình huống kém khả năng như vậy của cơ sở
dữ liệu quan hệ sẽ được cơ sở dữ liệu hướng đối tượng khắc phụ, nhất là đối với các đối tượng
dữ liệu phức tạp và có khối lượng lớn các thông tin ngữ nghĩa. Các lĩnh vực điển hình cần đến
cơ sở dữ liệu hướng đối tượng là:
- Cơ sở dữ liệu đa phương tiện, cần lưu trữ khối lượng lớn các tín hiệu âm thanh, hình ảnh
và văn bản; cần liên kết nhiều kiểu dữ liệu.
- Các hệ thống thông tin địa lý, cần xử lý nhiều loại dữ liệu thống kê, bản đồ; các dữ liệu
được thu thập từ nhiều vùng khác nhau.
- Các cơ sở dữ liệu phục vụ thiết kế gồm các sơ đồ, nhiều thành phần dữ liệu phức tạp liên
kết nhau. Một thiết kế đòi hỏi xử lý qua nhiều giai đoạn, nhiều thế hệ.
2.2. Khái niệm về hướng đối tượng
Để 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
PDF created with pdfFactory Pro trial version www.pdffactory.com
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.
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 kết hôn với ai.
Định nghĩa 2.2. Trạng thái bao gồm tính chất của đối tượng, như là thuộc tính và các mối
quan hệ, và những giá trị gán cho các tính chất đó.
Định nghĩa 2.3. Phép toán là một hàm số hay một dịch vụ mà tất cả các thể hiện của lớp
đều chấp nhận.
Định nghĩa 2.4. Phương pháp là việc thực hiện của một phép toán.
Hành vi và cấu trúc của một đối tượng trong môi trường oop hoàn toàn do lớp đối tượng
xác định. Lớp là khái niệm cơ bản trong tiếp cận hướng đối tượng.
Định nghĩa 2.5. Hành vi là thể hiện cách thức tác động của một một đối tượng.
PDF created with pdfFactory Pro trial version www.pdffactory.com
2.2.2. Lớp đối tượng
Một lớp đối tượng có giao diện và miền riêng. Giao diện của đối tượng là cái mà các đối
tượng khác thấy được. Giao diện lớp đối tượng gồm hai thành phần sau:
1. Thuộc tính của lớp: Trong chừng mực nào đó các thuộc tính của lớp được coi tương
được với các thuộc tính của quan hệ. Đương nhiên thông qua thuộc tính lớp người ta có thể
thể hiện các liên kết giữa các đối tượng, hay trong lớp cũng có thuộc tính ảo, chẳng hạn thuộc
tính tuối có giá trị tùy thuộc vào thuộc tính ngày sinh. Đối với lớp, không có hạn chế gì về
cách thức cấu trúc thuộc tính hay cách liên kết với nhau. Các thuộc tính có thể là đối tượng,
dùng đẻ tạo đối tượng phức tạp hơn. Người ta không xử lý trực tiếp các giá trị thuộc tính của
đối tượng mà xử lý thông qua các phương pháp liên kết với lớp đối tượng.
2. Phương pháp gắn với lớp đối tượng: Các thông báo chuyển đến lớp đối tượng nhờ
phương pháp gắn với lớp đối tượng. Chúng thường có dạng các phép toán, các hàm với các
tham số. Các đối tượng trong một lớp chỉ có thể được truy cập thông qua các phương pháp.
Tại mức giao diện, phần hiện rõ là tên phương pháp và các tham số cần cho phương pháp này.
Định nghĩa 2.6. Lớp đối tượng là tập các đối tượng có chung cấu trúc và hành vi.
Định nghĩa 2.7. Sơ đồ lớp cho biết cấu trúc tĩnh của mô hình hướng đối tượng, đó là các
lớp đối tượng, cấu trúc bên trong của chúng, và mối quan hệ mà chúng tham gia.
Miền riêng của lớp đối tượng là phần xác định lớp, nhưng không hiện ra cho đối tượng
khác thấy. Miền này có thể gồm các thông tin chi tiết về cấu trúc của lớp đối tượng. Trong
chương trình 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.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Đị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. Cơ sở dữ liệu hướng đối tượng
Dù có nhiều ngôn ngữ hướng đối tượng, đa số cơ sở dữ liệu 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ế cơ sở dữ liệu 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ị cơ sở dữ liệu dựa trên việc xử lý các đối tượng phức tạp, thiết kế
giao diện chương trình, mô tả đối tượng động và trừu tượng.
Hệ quản trị cơ sở dữ liệu hướng đối tượng là hệ quản trị cho phép lưu trữ và chia sẻ các
đối tượng với nhiều ứng dụng. Hệ thống hướng đối tượng là sự mở rộng có ý nghĩa của lập
trình hướng đối tượng. Trong môi trường OOP các đối tượng được coi như các biến chương
trình, chỉ tồn tại với vòng đời của chương trình đã tạo ra và sử dụng đối tượng. Còn trong hệ
thống cơ sở dữ liệu hướng đối tượng, các đối tượng là bền vững hơn. Thuật ngữ bền vững
được dùng với nghĩa đối tượng tồn tại không lệ thuộc vào vòng đời của chương trình tạo ra
nó. Chương trình khác có thể truy cập hay hủy bỏ đối tượng này. Hệ thống cơ sở dữ liệu
hướng đối tượng có các nét đặc trưng sau:
- Ngôn ngữ cơ sở dữ liệu có khả năng mô tả lớp đối tượng, tao sinh, lưu trữ và xóa đối
tượng.
- Các đối tượng cho phép chương trình ứng dụng truy cập. Mỗi đối tượng trong kho các
đối tượng có tên duy nhất OID. Khái niệm OID khác với khái niệm khóa chính trong cơ sở dữ
liêu quan hệ. Khóa chính là tập các thuộc tính xác định duy nhất bộ dữ liệu, mang giá trị có
thể thay đổi được. Trong hệ thống hướng đối tượng, OID thường là chuỗi 64, 128bit hoặc cao
hơn và mang giá trị không thay đổi.. Một đối tượng cũng có thể có các thuộc tính mang vai
trò như khóa chính trong cơ sở dữ liệu quan hệ. Điều này hoàn toàn phụ thuộc vào việc xác
định lớp. Việc gán OID hoàn toàn do hệ quản trị cơ sở dữ liệu hướng đối tượng thực hiện.
Kho đối tượng là nơi chứa dữ liệu tạo nên cơ sở dữ liệu hướng đối tượng. Hệ quản trị cơ
sở dữ liệu hướng đối tượng cần có các chức năng cơ bản như hệ quản trị cơ sở dữ liệu bình
thường, như điều khiển tương tranh, an toàn dữ liệu, toàn vẹn dữ liệu… Thực ra, hệ quản trị
cơ sở dữ liệu hướng đối tượng hoạt động như hệ quản trị thường, với sự tham giá của phần
mềm hướng đối tượng để truy cập các đối tượng.
2.4. Thiết kế cơ sở dữ liệu hướng đối tượng
Để xác định rõ việc thực hiện cơ sở dữ liệu hướng đối tượng theo các dạng tiếp cần, trước
hết cần xác định cách thức thiết kế một hệ thống hướng đối tượng.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Một cơ sở dữ liệu hướng đối tượng gồm các đối tượng; tất cả các thứ thuộc về lớp. Để xây
dựng mô hình khái niệm cho cơ sở dữ liệu hướng đối tượng, người ta cần xác định tập các lớp
đối tượng.
Lớp đối tượng được xác định nhờ các thuộc tính và phương thức thức. Người ta cũng phải
xác định sự tương tác giữa các lớp. Khái niệm về lớp cũng tương tự như kiểu dữ liệu đã giới
thiệu trước đây.
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
cơ sở dữ liệu.
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.
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.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Sơ đồ
Hình chữ nhật
Hình tam giác
Hình tròn
Hình vuông
Tam giác đều
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 giác. Phương thức Diện tích cũng là phương thức dùng riêng cho hình tam giác.
Còn lớp đối tượng Hình đều cạnh thì thừa kết tính chất củ lớp Tam giác. Điều này có nghĩa nó
thừa kết các tính chất của lớp tam giác và lớp so đồ. Lớp đối tượng này cũng có thuộc tính
riêng. Người ta mô tả lại các phương thức để phù hợp với loại hình này.
2.4.3. Gộp
Gộp là quá trình liên kết các lớp đối tượng với nhau để tạo lên một lớp gộp. Chẳng hạn cơ
sở dữ liệu ngân hàng gồm khách hàng, tài khoản, chi nhánh và mối quan hệ giữa chúng. Khi
thực hiện cơ sở dữ liệu này theo kĩ thuật quan hệ, người ta tạo các các quan hệ tách biệt đối
với mỗi thực thể và dùng khái niệm khóa ngoài để thể hiện mối quan hệ 1-n. Người ta cũng
dùng quan hệ khác có khóa ngoài để thể hiện quan hệ m-n giữa khách hàng và tài khoản. Để
thiết lập khung nhìn về tất cả thông tin liên quan đến một tài khoản nào đó, người ta cần nối 4
bảng cơ sở.
Trong cơ sở dữ liệu hướng đối tượng người ta giải quyết vấn đề này nhở lớp đối tượng
gộp. Lớp đăng ký được tạo, liên kết các đối tượng kiểu khác hàng, tài khoản, và chi nhánh.
Mỗi đối tượng đăng ký sẽ liên kết một khách hàng với một tài khoản, có thuộc tính đặc biệt
cho biết thời gian thực hiện đăng ký này.
2.5. Xây dựng cơ sở dữ liệu hướng đối tượng
Một số điều liên quan đến lược đồ cơ sở dữ liệu hướng đối tượng xuất hiện khi phân lớp
đối tượng, tổng quát hóa, đặc biệt hóa và gộp. Các vấn đề này xảy ra song song. Người ta
không trình bày quá trình chuyển từ mô hình thực thể E/R sang mô hình hướng đối tượng bởi
lẽ không có điểm tương tự giữa một bên là thực thể và mối quan hệ, một bên là lớp đối tượng.
Hơn nữa, mô hình E/R hầu như hướng dữ liệu chứ không cho biết về hành vi của thực thể khi
dựa vào hạng của quan hệ mà thực thể tham gia.
Việc chuyển hóa mô hình đối tượng ngữ nghĩa sang cơ sở dữ liệu hướng đối tượng được
thực hiện như sau:
- Đối với mỗi đối tượng ngữ nghĩa, người ta tạo một lớp đối tượng.
- Khi có quan hệ cha con giữa hai đối tượng ngữ nghĩa, người ta thực hiện liên kết thừa kế
giữa lớp đối tượng thể hiện kiểu con và lớp đối tượng thể hiện kiểu cha.
PDF created with pdfFactory Pro trial version www.pdffactory.com
- Tiến hành gộp và liên kết các đối tượng ngữ nghĩa về kiểu đối tượng để được các lớp đối
tượng gộp.
- Giữ tính toàn vẹn về hạng giữa các đối tượng ngữ nghĩa, duy trì việc hợp nhóm của các
đối tượng ngữ nghĩa và phân rã kiểu con bằng các phương thức.
Vòng đời phát triển hướng đối tượng gồm ba pha:
- Pha phân tích: người ta phát triển mô hình ứng dụng trên thế giới thực, chỉ ra các thuộc
tính quan trọng. Cần xác định các khái niệm trừu tượng về mô hình xuất phát từ lĩnh vực ứng
dụng và các mô tả về hệ thống. Người ta xác định các hành vi chức năng của hệ thống, độc
lập với môi trường sẽ thực hiện hướng đối tượng.
Pha thiết kế: Cho phép xác định cách thức sẽ thực hiện mô hình phân tích hướng đối
tượng.
Pha thực hiện: Người ta xác định và khảo sát tất cả các kết quả của việc thực hiện thiết kế.
Tất cả các quyết định thiết kế chiến lược, như là cách thức tích hợp hệ quản trị cơ sở dữ liệu,
cách liên lạch giữa các đối tượng, cách xử lý sai sót… đều được triển khai. Tiếp theo người ta
tích hợp các quyết định này vào mô hình thiết kế ban đầu, rồi hình thức hóa mô hình thiết kế
để các đối tượng có thể tương tác với các đối tượng khác theo các kịch bản.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Chương 3. Cơ sở dữ liệu phân tán
Thiết kế hệ thống thông tin có cơ sở dữ liệu phân tán bao gồm:
- Phân tán và chọn những vị trí đặt dữ liệu;
- Các chương trình ứng dụng tại các điểm;
- Thiết kế tổ chức khai thác hệ thống đó trên nền mạng.
3.1. Các phương pháp phân tán dữ liệu
3.1.1. Khái niệm về phân tán dữ liệu
Khi thiết kế các hệ thống cơ sở dữ liệu phân tán người ta thường tập trung xoay quanh các
câu hỏi?
- Tại sao lại cần phải phân mảnh?
- Làm thế nào để thực hiện phân mảnh?
- Phân mảnh nên thực hiện đến mức độ nào?
- Có cách gì kiểm tra tính đúng đắn của việc phân mảnh?
- 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 ứng 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 chi 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
PDF created with pdfFactory Pro trial version www.pdffactory.com
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.
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 phần mềm gồm các quan hệ:
DuAn(MaDuAn, Ten, KinhPhi, ViTri);
NhanVien(MaNV, Ten, ChucVu);
TrachNhiem(MaNV, MaDuAn, TrachNhiem, ThoiGianTG);
Luong(ChucVu, Luong).
Hình 3.1. Dữ liệu của các bảng
NhanVien
Ten
Hoàng Lan
TrachNhiem
MaNV
E1
ChucVu
Ks Điện
MaNV MaDuAn TrachNhiem ThoiGianTG
E1
E2
E2
E3
E3
E4
E5
E6
E7
E8
P1
P1
P2
P3
P4
P2
P2
P4
P3
P3
Quản lý
Phân tích
Phân tích
Tư vấn
12
24
6
10
48
18
24
48
36
40
E2
Đình Vượng Phân tích hệ thống
E3
E4
E5
E6
Minh Tài
Dương Hà
Minh Hoa
Văn Hiền
Hoài Nam
Ks Máy
Lập trình viên
Phân tích hệ thống
Ks Điện
Kỹ sư
Lập trình viên
Quản lý
Quản lý
Kỹ sư
E7
Ks Máy
E8
Vân Dũng Phân tích hệ thống
Quản lý
DuAn
Luong
MaDuAn
Ten
KinhPhi
Vitri
Hà Nội
ChucVu
Ks Điện
Phân tích hệ thống 10000
Ks Máy
Lập trình viên
Luong
4000
P1
P2
P3
P4
Trang thiết bị 150000
Cơ sở dữ liệu 135000 Hải Phòng
CAD/CAM
Bảo Trì
250000
310000 Quảng Ninh
Hà Nội
3500
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
P1
Ten
KinhPhi
Vitri
Hà Nội
Trang thiết bị 150000
P2
Cơ sở dữ liệu 135000 Hải Phòng
DuAn2
MaDuAn
P3
Ten
CAD/CAM
KinhPhi
250000
Vitri
Hà Nội
PDF created with pdfFactory Pro trial version www.pdffactory.com
P4
Bảo Trì
310000 Quảng Ninh
Ngoài ra cũng có thể phân mảnh dọc quan hệ DuAn thành hai quan hệ DuAn3, DuAn4.
DuAn3 chỉ chứa thông tin về ngân sách của các dự án, còn DuAn4 lưu thông tin về tên và vị
trí dự án. Điều cần lưu ý là khóa của quan hệ DuAn phải xuất hiện trong cả hai mảnh.
Hình 3.3. Phân mảnh dọc quan hệ DuAn
DuAn3
DuAn4
Ten
MaDuAn
KinhPhi
150000
135000
250000
310000
MaDuAn
Vitri
Hà Nội
Hải Phòng
Hà Nội
P1
P2
P3
P4
P1
P2
P3
P4
Trang thiết bị
Cơ sở dữ liệu
CAD/CAM
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 cơ sở dữ liệu. 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 cơ sở dữ liệu và
các ứng dụng cơ sở dữ liệu cụ thể.
3.1.1.4. Quy tắc phân mảnh đúng đắn
Chúng ta sẽ phải tuân thủ ba qui tắc trong khi phân mảnh mà chúng sẽ đảm bảo CSDL
không có thay đổi nào về mặt ngữ nghĩa sau khi phân mảnh.
1. Tính đầy đủ: Nếu một quan hệ R được phân mảnh thành các mảnh R1, R2,…, RN thì
mỗi mục dữ liệu có trong R phải có mặt trong một hoặc nhiều mảnh Ri.
2. Tính tái thiết được: Nếu một quan hệ R được phân mảnh thành R1, R2,…, RN thì cần
phải định nghĩa một toán tử tái thiết Θ sao cho:
R = ΘRi, i = 1..N.
Toán tử Θ thay đổi tùy theo từng loại phân mảnh; thông thường khi phân mảnh ngang thì
Θ là phép toán hợp còn phân mảnh dọc là phép toán kết nối.
3. Tính tách biệt: Nếu quan hệ R được phân mảnh ngang thành các mảnh R1, R2,…, RN và
mục dữ liệu ti nằm trong mảnh ri, thì nó sẽ không nằm trong các mảnh Rk 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.
PDF created with pdfFactory Pro trial version www.pdffactory.com
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ị cơ sở dữ liệu 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 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 phân tán.
3.1.2. Phân mảnh ngang
Trong phần ngày chúng ta sẽ bàn đến hai chiến lược phân mảnh:
- Phân mảnh ngang nguyên thủy: Phân mảnh ngang nguyên thủy của một quan hệ được
thực hiện dựa trên các vị từ được định nghĩa trên quan hệ đó.
- Phân mảnh ngang dẫn xuất: Là phân mảnh một quan hệ dựa vào các vị từ được định
nghĩa trên một quan hệ khác.
3.1.2.1. 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ề cơ sở dữ liệu là lược đồ toàn cục và các quan hệ gốc. 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 kết nối hay phép tính khác.
Để thể hiện người ta thường dụng mô hình thực thể để biểu diễn các quan hệ với các mỗi liên
kết giữa chúng.
Thông tin định lượng cần có là lực lượng của mỗi quan hệ R, đó là số bộ có trong R được
ký hiệu là card(R).
2. Thông tin về ứng dụng
Để 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 vào bài toán cụ thể.
Cho lược đồ quan hệ R(U), U = A1, A2,…, AN trong đó mỗi Ai là một thuộc tính có miền
giá trị dom(Ai). Một vị từ đơn giản P được định nghĩa trên R có dạng:
P: Ai θ <giá trị>
Trong đó θ ∈ {=, <, <=, >=, >, <>}, Ai là một thuộc tính, <giá trị> ∈ dom(Ai).
Như vậy cho trước một lược đồ R, nếu các miền giá trị dom(Ai) 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.
PDF created with pdfFactory Pro trial version www.pdffactory.com
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 = A1, A2,…, AN trong đó mỗi Ai là một thuộc tính có miền
giá trị dom(Ai). Pr = {p1, p2,…, pt}. Tập các vị từ hội sơ cấp M = {m1, m2,…, mk} được định
nghĩa như sau:
mi = ∧ p’j với 1 ≤ j ≤ t
Trong đó p’j = pj hoặc p’j = ¬pj
Lưu ý: Phép lấy phủ định một vị từ không phải lúc nào cũng thực hiện được.
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:
1.. Số lượng các bộ có quan hệ sẽ được truy xuất bởi câu vấn tin được đặc tả theo một vị
từ hội sơ cấp đã cho.
3. Tần số truy xuất và trong một số trường hợp là số truy xuất. Nếu Q = {q1, q2,…, qN} là
các câu vấn tin, acc(qi) biểu thị cho số truy xuất của qi trong một khoảng thời gian đã cho
hoặc trong quan hệ cụ thể.
3.1.2.2. Phân mảnh ngang nguyên thủy.
Phân mảnh ngang nguyên thủy được định nghĩa bằng một phép toán chọn trên các quan hệ
chủ của một lược đồ CSDL. Vì thế cho quan hệ R, các mảnh ngang của R là các Ri với Ri =
R(Ei), 1 ≤ i ≤ k
Trong đó Ei là công thức chọn (hội sơ cấp) được sử dụng để có thể có được mảnh Ri. Chú
ý rằng nếu Ei có dạng chuẩn hội, nó là một vị từ hội sơ cấp mi. Ri là các bộ của R thỏa mãn Ei.
Ví dụ:
Phân rã quan hệ DuAn thành các mảnh ngang DuAn1, DuAn2 trong hình 3.1. được định
nghĩa như sau:
DuAn1 = DuAn(KinhPhi ≤ 200000)
DuAn2 = DuAn(KinhPhi > 200000)
Một mảnh ngang Ri của quan hệ R có chứa tất cả các bộ R thỏa vị từ hội sơ cấp mi. Vì vậy
cho một tập các vị từ hội sơ cấp M, số lượng các mảnh ngang cũng bằng số lượng các vị từ
hội sơ cấp (tất nhiên một mảnh ngang có thể rỗng nếu vị từ không truy xuất đến bộ nào của
quan hệ, các mảnh ngang có thể bằng nhau nếu các vị từ tương đương). Tập các mảnh ngang
này cũng thường được gọi là tập các mảnh hội sơ cấp.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Rõ ràng việc định nghĩa các mảnh ngang phụ thuộc vào cá vị từ hội sơ cấp. Vì thế bước
đầu tiên của mọi thuật toán phân mảnh là phải xác định tập các vị từ đơn giản sẽ tạo ra các vị
từ hội sơ cấp. Tập vi từ này nói chung phụ thuộc vào mục tiêu và yêu cầu của bài toán.
Một số khái niệm quan trọng của các vị từ đơn giản là tính đầy đủ và cực tiểu của tập các
vị từ.
Tập các vị từ đơn giản Pr được gọi là đầy đủ nếu và chỉ nếu xác suất của mỗi bộ của
R(hoặc của các mảnh Ri) được truy xuất bởi các vị từ p ∈ Pr đều bằng nhau.
Lý do cần phải bảo đảm tính đầy đủ là vì các mảnh thu được theo tập vị từ đầy đủ sẽ nhất
quán về mặt logic do tất cả chúng đều thỏa vị từ hội sơ cấp. Chúng cũng đồng nhất và đầy đủ
về mặt thống kê theo cách mà ứng dụng truy xuất chúng.
Đặc tính thứ hai của tập vị từ là tính cực tiểu. Đây là một đặc tính cảm tính. Vị từ đơn giản
phái có liên đới trong việc xác định một phân mảnh. Một vị từ mà không tham gia vào một
tập phân mảnh nào thì có thể coi vị từ đó là thừa. Nếu tất cả các vị từ của Pr đều có liên đới và
không có các vị từ tương đương thì Pr là cựu tiểu.
Chúng ta quy ước:
Thuật toán 3.1. COM-MIN Thuật toán tìm tập vị từ đầy đủ và cực tiểu
Vào: Quan hệ R, tập các vị từ đơn giản Pr
Ra: Pr’ – tập các vị từ đơn giản đầy đủ và cực tiểu
Phương pháp:
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.
PDF created with pdfFactory Pro trial version www.pdffactory.com
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)
i2: ¬(A = giá trị 1) → (A = giá trị 2)
Bốn vị từ hội sơ cấp sau đây được định nghĩa theo Pr’
m1: (A = giá trị 1) ∧ (A = giá trị 2)
m2: (A = giá trị 1) ∧ ¬(A = giá trị 2)
m3: ¬(A = giá trị 1) ∧ (A = giá trị 2)
m4: ¬(A = giá trị 1) ∧ ¬(A = giá trị 2)
Trong trường hợp này các vị từ hội sơ cấp m1 và m4 mâu thuẫn với phép kéo theo I và vì
thế bị loại khỏi M
Thuật toán 3.2. Thuật toán phân mảnh ngang nguyên thủy
Vào: Quan hệ R, tập các vị từ đơn giản Pr
Ra: M – tập các vị từ hội sơ cấp
Phương pháp:
0. Pr’ = COM-MIN(R,Pr)
Xác định tập M các vị từ hội sơ cấp
Xác định tập I các phép kéo theo giữa các Pi ∈ Pr’
1. ∀mi ∈ M nếu mi mâu thuẫn với I
M = M – {mi}
Sau bước này M là tập các vị từ hội sơ cấp.
3.1.2.3. Phân mảnh ngang dẫn xuất
Phân mảnh ngang dẫn xuất được định nghĩa trên một quan hệ thành viên của một đường
nối dựa 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à:
PDF created with pdfFactory Pro trial version www.pdffactory.com
Tải về để xem bản đầy đủ
44 trang
18020
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cơ sở dữ liệu 2", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_co_so_du_lieu_2.pdf
