1. Lý do chọn đề tài
PHẦN MỞ ĐẦU
Cùng với sự phát triển như của công nghệ thông tin, các ứng dụng của cơ
sở dữ liệu đã xâm nhập vào các hoạt động quản lý, các lĩnh vực kinh tế… đem
lại những hiệu quả to lớn và cần thiết. Bên cạnh đó, nhu cầu về xử lí thông tin
như: thu thập, lưu trữ, xử lý và trao đổi thông tin ngày càng tăng, nhanh hơn
nhiều lần tốc độ phát triển của tài nguyên phần cứng và phần mềm. Trong
thực tế các doanh nghiệp, đơn vị kinh doanh liên quan đến nhau hay kể cả các
cơ quan hành chính nhà nước được phân bổ ở nhiều khu vực khác nhau do đó
dữ liệu không được tập trung tại một địa điểm nhất định mà rải khắp các địa
điểm mà cơ quan đơn vị đó hoạt động. Khi dữ liệu không còn tập trung thì
vấn đề đưa ra là làm thế nào để quản lý, truy xuất CSDL phục vụ cho công tác
chuyên môn không bị ảnh hưởng, không được gián đoạn, tiêu tốn ít thời gian
công sức tiền bạc. Một số hệ thống tập trung thông thường không đáp ứng
được, không phù hợp với nhu cầu hiện đại hóa. Xây dựng một hệ thống phân
tán có khả năng xử lí đồng thời một bài toán trên nhiều máy tính là một
hướng giải quyết khả thi và đã được chứng minh tính hữu dụng. Hệ thống
phân tán còn tạo nhiều thuận lợi trong việc chia sẻ thông tin trên khắp mọi
nơi. Vì vậy, CSDL phân tán được ra đời để giải quyết vấn đề đó.
Nếu khối lượng thông tin phải xử lý lớn phong ph và đa dạng th vấn
đề được đ t ra là làm thế nào để giảm chi phí một các tối thiểu mà vẫn xử
lý thông tin một cách có hiệu quả và thông suốt. Tối ưu hóa các câu lệnh
khi truy vấn cơ sở dữ liệu phân tán là một trong những cách giải quyết cho
vấn đề này.
Vấn đề tối ưu hóa truy vấn trên CSDL phân tán là rất quan trọng và phức
tạp do tính phân mảnh, nhân bản, tốn kém chi phí trong việc truyền dữ liệu
1
của nó. Nếu không giải quyết tốt vấn đề tối ưu truy vấn thì hiệu năng của các
thao tác trên hệ CSDL phân tán sẽ đạt rất thấp.
Những nhận xét đánh giá trên cũng chính là lý do tôi chọn đề tài nghiên
cứu là: “Tìm hiểu về tối

trên các vị trí khác nhau của một mạng máy tính.
Cơ sở dữ liệu phân tán làm tăng khả năng truy cập tới hệ thống CSDL lớn
trên mạng. Trong hệ thống đó mỗi máy tính quản lý một CSDL thành phần
được gọi là 1 node ho t site.
Một cơ sở dữ liệu phân tán là một tập hợp nhiều CSDL có liên đới logic và
được phân bố trên một mạng máy tính.
Có 2 điểm quan trọng được nêu ra và cần ch ý trong định nghĩa:
- Tính chất phân tán: Tất cả dữ liệu của CSDL phân tán không cư tr trên
cùng một vị trí mà được phân bố trên nhiều máy trạm đ t tại các vị trí khác
nhau thuộc mạng máy tính. Đây là điểm phân biệt giữa CSDL phân tán và
CSDL tập trung.
- Tương quan logic: Dữ liệu của CSDL phân tán có một số thuộc tính ràng
buộc với nhau. Điều này giúp chúng ta có thể phân biệt một CSDL phân tán
với một tập hợp CSDL tập trung. Các file dữ liệu được lưu trữ tại nhiều vị trí
khác nhau, điều này thường thấy trong các ứng dụng mà hệ thống sẽ phân
quyền truy nhập dữ liệu trong môi trường mạng.
Ví dụ 1.1:
Website của google phân tán tìm kiếm theo cách tự nhận biết, yêu cầu nào
gần server nào th server đó xử lý. Các server của google phân bố rông khắp
trên toàn thế giới.
1.1.2. Các đặc điểm chính của CSDL phân tán
1. Chia sẻ tài nguyên
Việc chia sẻ tài nguyên của hệ phân tán được thực hiện qua mạng truyền
thông. Mỗi tài nguyên cần được quản lý bởi một chương tr nh có giao diện
truyền thông để chia sẻ một cách có hiệu quả. Các tài nguyên có thể được truy
cập, cập nhật một cách tin cậy và nhất quán. Quản lý tài nguyên ở đây bao
gồm lập kế hoạch dự phòng, đ t tên cho các lớp tài nguyên, cho phép tài
nguyên được truy cập từ nơi này đến nơi khác, ánh xạ tên tài nguyên vào địa
chỉ truyền thông,
2. Tính mở

thay đổi phần mềm hệ thống và phần mềm ứng dụng khi hệ thống được mở
rộng.
Điều này chỉ đạt ở mức độ nào đó đối với hệ phân tán hiện tại (không thể
hoàn toàn như định nghĩa trên). Yêu cầu mở rộng không chỉ là mở rộng về
phần cứng hay về mạng mà còn cần phải được phân tích, đánh giá trên tất cả
các khía cạnh khi thiết kế hệ phân tán.
Ví dụ 1.2: Tần suất sử dụng file trên mạng đột ngột tăng cao. Để tránh tình
trạng tắc nghẽn xảy ra khi chỉ có một Server và phải đáp ứng các yêu cầu truy
nhập file đó. Người ta nhân bản file trên một Server khác và hệ thống được
thiết kế sao cho việc bổ sung Server được dễ dàng. Có thể tính đến giải pháp
khác là sử dụng Cache và các bản sao dữ liệu.
5. Khả năng thứ lỗi
Khả năng thứ lỗi thể hiện việc hệ thống không bị sụp đổ bởi các sự cố do
các lỗi thành phần (cả phần cứng lẫn phần mềm) trong một bộ phận nào đó.
Việc thiết kế khả năng thứ lỗi các hệ thống máy tính dựa trên hai giải
pháp sau:
- Dùng khả năng thay thế để đảm bảo sự hoạt động liên tục và hiệu quả.
- Dùng các chương tr nh đảm bảo cơ chế phục hồi dữ liệu khi xảy ra sự cố.
6. Đảm bảo tin cậy và nhất quán
Hệ thống yêu cầu độ tin cậy như:
- Bí mật của dữ liệu.
- Các chức năng khôi phục hư hỏng phải đảm bảo.
- Ngoài ra các yêu cầu của hệ thống về tính nhất quán cũng thể hiện ở chỗ:
không có mâu thuẫn trong nội dung CSDL.
1.1.3. Những ưu nhược điểm của cơ sở dữ liệu phân tán
• Những ưu điểm của cơ sở dữ liệu phân tán
Lợi ích cơ bản nhất của CSDL phân tán là dữ liệu của các CSDL vật lý
riêng biệt được tích hợp logic với nhau làm cho nhiều người sử dụng trên
mạng có thể truy nhập được [6].
- Cho phép quản lý dữ liệu với nhiều mức trong suốt:

+ Quản lý các bản sao
+ Quản lý thư mục - catalog phân tán
- Hệ thống phần cứng cũng phức tạp hơn v cần có nhiều trạm và các trạm
phải được kết nối trên mạng.
- Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu
trên mạng.
- Bảo mật khó khăn.
1.2. Các đặc
trƣng
trong suốt của cơ sở dữ liệu phân tán
1.2.1. Trong suốt phân đoạn (fragmentation transparency)
Khi dữ liệu đã được phân đoạn thì việc truy cập vào CSDL được thực hiện
b nh thường như là chưa bị phân tán và không ảnh hưởng tới người sử dụng.
Ví dụ 1.3: Xét quan hệ tổng thể NCC (Id, Tên, Tuổi) và các phân đoạn
ngang được tách ra từ nó:
NCC1 (Id, Tên, Tuổi)
NCC2 (Id, Tên, Tuổi)
NCC3 (Id, Tên, Tuổi)
Giả sử DDBMS cung cấp tính trong suốt về phân đoạn, khi đó ta có thể
thấy tính trong suốt này được thể hiện như sau:
Khi muốn tìm một người có Id= “Id1” thì chỉ cần tìm trên quan hệ tổng
thể NCC mà không cần biết quan hệ NCC có phân tán hay không.
SELECT * FROM
NCC WHERE
Id=“Id1”
Hình 1.1:Trong suốt phân đoạn
1.2.2. Trong suốt về vị trí (location transparency)
- Người sử dụng không cần biết về vị trí vật lý của dữ liệu mà có quyền
truy cập đến CSDL tại bất cứ vị trí nào.
- Các thao tác để lấy ho c cập nhật một dữ liệu từ xa được tự động thực

sử dụng như một hệ thống đồng nhất.
Hình 1.3: Sự trong suốt ánh xạ địa phương
1.3. Kiến trúc cơ bản của một cơ sở dữ liệu phân tán
1.3.1. Sơ đồ tổng thể (Global Schema)
- Xác định tất cả các dữ liệu sẽ được lưu trữ trong CSDL phân tán cũng
như các dữ liệu không được phân tán ở các trạm trong hệ thống.
- Sơ đồ tổng thể được định nghĩa theo cách như trong CSDL tập trung.
- Trong mô hình quan hệ, sơ đồ tổng thể bao gồm định nghĩa của tập các
quan hệ tổng thể (Globle relation).
1.3.2. Sơ đồ phân đoạn dữ liệu (fragment schema)
- Mỗi quan hệ tổng thể có thể chia thành một vài phần không giao nhau gọi
là phân đoạn (fragment).
- Có nhiều cách khác nhau để thực hiện việc phân chia này.
- Sơ đồ phân đoạn mô tả các ánh xạ giữa các quan hệ tổng thể và các đoạn
được định nghĩa trong sơ đồ phân đoạn (fragmentation Schema).
- Các đoạn được mô tả bằng tên của quan hệ tổng thể cùng với chỉ mục
đoạn.
Chẳng hạn, Ri được hiểu là đoạn thứ i của quan hệ R.
1.3.3. Sơ đồ định vị dữ liệu (allocation schema)
- Các đoạn là các phần logic của một quan hệ tổng thể được định vị vật lý
trên một hay nhiều trạm.
- Sơ đồ định vị xác định đoạn dữ liệu nào được định vị tại trạm nào trên
mạng.
- Tất cả các đoạn được liên kết với cùng một quan hệ tổng thể R và được
định vị tại cùng một trạm j cấu thành ảnh vật lý quan hệ tổng thể R tại trạm j.
- Do đó ta có thể ánh xạ một-một giữa một ảnh vật lý và một c p (quan hệ
tổng thể, trạm).
- Các ảnh vật lý có thể chỉ ra bằng tên của một quan hệ tổng thể và một chỉ
mục trạm.
- Ký hiệu R

biết được vị trí của các đoạn dữ liệu trên các trạm.
b. Biết được dữ liệu dư thừa:
• Người lập trình ứng dụng có thể biết được dư thừa dữ liệu ở các trạm.
• Trên h nh vẽ trên, chúng ta thấy rằng hai ảnh vật lý R2 và R3 có trùng l p
dữ liệu. Do đó các đoạn dữ liệu trùng nhau có thể tránh được khi xây dựng
các khối ảnh vật lý.
c. Độc lập với các DBMS địa phương
Tính chất này còn được gọi là trong suốt ánh xạ địa phương (local
mapping transparency), cho phép chúng ta khảo sát các vấn đề về quản lý
CSDL phân tán mà không cần phải hiểu rõ mô hình dữ liệu của DBMS địa
phương đang sử dụng.
1.4. Kết luận
CSDL 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 CSDL phân tán đó là: CSDL phân
tán được xây dựng để khắc phục các thiếu sót của CSDL 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 CSDL phân
tán được mở rộng và phát triển từ kỹ thuật của CSDL 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 CSDL. 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ị CSDL 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: CÁC NGUYÊN LÝ CHUNG CỦA TỐI
ƢU
HÓA

sau [4]:
1. Thực hiện phép chọn sớm nhất có thể: Biến đổi câu truy vấn để đưa
phép chọn vào thực hiện trước nhằm làm giảm kích thước của kết quả trung
gian, do đó tiết kiệm thời gian thực hiện và không gian nhớ.
2. Tổ hợp phép chọn xác định với phép tích Decartes thành phép kết nối:
Ta đã biết, phép kết nối đ c biệt là kết nối bằng có thể thực hiện nhanh hơn
đáng kể so với phép tích Decartes trên cùng các quan hệ. Nếu kết quả của tích
Decartes R × S là đối số của phép chọn và phép chọn có liên quan đến phép
so sánh giữa các thuộc tính của R và S th ta đưa về phép kết nối để giảm chi
phí tính toán.
3. Tổ hợp dãy các phép toán một ngôi như phép chọn và phép chiếu: Bất
kỳ dãy các phép toán một ngôi như phép chọn ho c phép chiếu có kết quả phụ
thuộc vào các bộ của một quan hệ độc lập thì có thể nhóm các phép đó lại.
Tương tự, ta có thể nhóm các phép toán một ngôi với kết quả của phép toán
hai ngôi bằng cách áp dụng các phép toán một ngôi với mỗi bộ kết quả của
phép toán hai ngôi.
4. Tìm các biểu thức con chung trong một biểu thức: Nếu kết quả của một
biểu thức con chung (biểu thức xuất hiện hơn một lần) là một quan hệ không
lớn và nó có thể được đọc từ bộ nhớ thứ cấp với ít thời gian, thì nên tính toán
trước biểu thức đó chỉ một lần. Nếu biểu thức con chung, có liên quan đến
phép kết nối, th trong trường hợp tổng quát không thể được thay đổi nhờ việc
đẩy phép chọn vào trong.
5. Xử lý các tệp trước: Hai vấn đề quan trọng cần xử lý trước cho các tệp
số là sắp xếp các tệp và thiết lập các tệp chỉ số, khi đó thực hiện các phép toán
liên quan đến hai tệp (phép tính hai ngôi) sẽ nhanh hơn nhiều.
6. Đánh giá trước khi thực hiện phép toán: Khi cần chọn trình tự thực hiện
các phép toán trong biểu thức ho c chọn một trong hai đối của phép toán hai
ngôi, ta nên tính toán chi phí thực hiện các phép toán đó (thường là số phép
tính, thời gian, dung lượng bộ nhớ theo kích thước các quan hệ, ) theo các
cách khác nhau. Từ đó sẽ quyết định phương án có chi phí thấp.

Với định nghĩa tương đương này ta có một số phép biến đổi đại số có lợi [4].
2.2.3. Các qui tắc liên quan đến phép kết nối và tích Decartes
Qui tắc giao hoán của phép kết nối và qui tắc giao hoán phép tích
Decartes:
Nếu E
1
và E
2
là các biểu thức quan hệ; p là điều kiện trên các thuộc tính E
1
và E
2
thì E
1

pE
2
≡ E
2

pE
1
E
1

E
2
≡ E
2


2
là hai quan
hệ tương ứng của E
1
, E
2
. Khi đó giá trị của
E
1
E
2
là tập các ánh xạ v từ A
1
,
A
2
, , A
n
, B
1
, B
2
, , B
m
vào tập giá trị sao cho các ánh xạ µ
1
∈ r
1
và µ
2

1
, E
2
, E
3
là biểu thức quan hệ; p
1
, p
2
là biểu thức điều kiện thì:
(E
1

p
1
E
2
)
p
2
E
3
≡ E
1

p
1
(E
2


≡ E
1
× (E
2
× E
3
)
2.2.4. Các qui tắc liên quan đến phép chọn và phép chiếu
Qui tắc hợp nhất của các phép chiếu: Dãy các phép chiếu có thể tổ hợp
thành một phép chiếu.
π
A1, ,An
(
π
B1, ,Bm
(E))
≡ π
A1, ,An
(E)
Với các thuộc tính A
1
, A
2
, …, A
n
phải nằm trong tập các thuộc tính B
1
, B
2
,

2
, , B
m
mà không thuộc tập
thuộc tính A
1
, A
2
, ,A
n
thì:π
A1, ,An
(
σ
p
(E))
≡ π
A1, ,An
(
σ
p
(
π
A1, ,An, B1, ,Bm
(E)))
Qui tắc giao hoán của phép chọn và tích Decartes:
Nếu tất cả các thuộc tính của p là thuộc tính của E

(E
1
) × σp
2
(E
2
)
Nếu p
1
chỉ liên quan tới các thuộc tính E
1
, còn p
2
liên quan tới các thuộc
tính của cả E
1
và E
2
thì:
σp(E
1
× E
2
) ≡σp
2
(σp
1
(E
1
) × E

(E
2
)
Nếu tên các thuộc tính của E
1
và/ho c E
2
khác tên thuộc tính của E thì
trong p ở vế phải của công thức trên cần sửa đổi để sử dụng tên cho phù hợp.
Qui tắc giao hoán của phép chọn và phép hiệu tập hợp:
σp(E
1
- E
2
) ≡ σp(E
1
) - σp(E
2
)
Theo qui tắc , nếu tên các thuộc tính của E
1
và E
2
là khác nhau thì cần
thay thế các thuộc tính trong p ở vế phải tương ứng các thuộc tính của E
1
.
Chú ý: Phép chọn σp(E
2
) là không cần thiết, có thể thay bởi E

, các thuộc tính còn lại C
1
, ,C
k
thuộc E
2
.
Khi đó:π
A1, ,An
(E
1
×
E
2
) =
π
B1, ,Bm
(E
1
)
× π
C1, ,Ck
(E
2
)
Qui tắc giao hoán của phép chiếu và phép hợp:


ở vế phải bởi các tên phù hợp.
2.2.5. Thuật toán cải tiến cây biểu diễn biểu thức quan hệ
Chúng ta có thể áp dụng các qui tắc trên để tối ưu các biểu thức quan hệ.
Biểu thức “tối ưu” kết quả phải tuân theo các nguyên tắc trong mục 2.1, m c
dù các nguyên tắc không có nghĩa bảo đảm để tối ưu cho tất cả các biểu thức
tương đương [4].
Đầu ra của thuật toán này là một chương tr nh, bao gồm các bước như sau:
1. Áp dụng của một phép chọn ho c một phép chiếu đơn giản
2. Áp dụng của một phép chọn và một phép chiếu, ho c
3. Áp dụng của một tích Decartes, phép hợp ho c phép hiệu tập hợp cho hai
biểu thức mà trước đó các phép chọn và / ho c các phép chiếu đã được áp
dụng cho một hay hai hạng thức.
Thuật toán: Tối ưu hóa biểu thức quan hệ
Vào: Cây biểu diễn biểu thức quan hệ
Ra: Chương tr nh đánh giá biểu thức đó
Phương pháp:
1. Sử dụng qui tắc  để tách mỗi phép chọn σp
1
∧p
2
∧ ∧p
n
(E) thành dãy
σp
1
( (σp
n
(E))).
2. Sử dụng quy tắc ,  để đẩy sâu phép chọn xuống đến mức có thể trong
biểu diễn.

quan hệ SACH, DOCGIA, MUON có thể xác định như sau:
π
S
(σ
P
(MUON × DOCGIA × SACH)
Trong đó:
P = DOCGIA.SOTHE = MUON.SOTHE and SACH.SHTV =
MUON.SHTV
S = TENSACH, TACGIA, TEN_NXB, SHTV, TEN, DIACHI,
THPHO, SOTHE, NGAY
Cần đưa ra danh sách những cuốn sách đã cho mượn trước ngày
13/10/2013:
π
TENSACH
σ
NGAY<13/10/2013
(XMUON)
Sau khi thay thế cho XMUON, biểu thức trên biểu diễn dạng cây như sau:
Hình 2.1: Cây biểu diễn biểu thức
hỏi
Bước1: Tách phép chọn p thành hai phép chọn với điều kiện
SACH.SHTV=MUON.SHTV và DONGIA.SOTHE=MUON.SOTHE
Đẩy sâu một trong ba phép chọn xuống đến mức có thể trong cây biểu
diễn. Phép chọn σ
NGAY<13/10/2013
được đẩy xuống dưới phép chiếu và hai phép
chọn kia bởi qui tắc  và . Phép chọn này áp dụng cho tích (MUON
× DOCGIA) × SACH), v thuộc tính NGAY trong phép chọn chỉ ở quan hệ
MUON nên có thể thay:

bởi:π
TENSACHσ
SACH.SHTV=MUON.SHTVπ
TENSACH, SACH.SHTV, MUON.SHTV
Áp dụng qui tắc  để thay thế phép chiếu cuối cùng bởi π
TENSACH,SACH.SHTV
áp dụng cho SACH và π
MUON.SHTV
áp dụng cho hạng thức bên trái của tích
Decartes trong hình 2.2.
Hình 2.2: Cây với tổ hợp phép
chọn
Phép chiếu cuối tác động với phép chọn bởi luật  để có dãyπ
MUON.SHTVσ
DOCGIA.SOTHE=MUON.SOTHE