1
PHẦN MỞ ĐẦU
1. Lý do chọn đề tài
Cùng vi s phát tria công ngh thông tin, các ng dng c
s d lip vào các hong quc kinh t
li nhng hiu qu to ln và cn thit. Bên cu v x lí thông tin
 thu th, x 
nhiu ln t 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 n nhau hay k c các
c c phân b  nhiu khu v
d lic tp trung ti mm nhnh mà ri kha
 ng. Khi d liu không còn tp trung thì
v   qun lý, truy xut CSDL phc v cho công tác
chuyên môn không b 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 ng
c, không phù hp vi nhu cu hii hóa. Xây dng mt h thng phân
tán có kh   l ng thi mt bài toán trên nhiu máy tính là mt
ng gii quyt kh  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
. Vì vy, CSDL  gii quyt vn  
N
 
t cách có hiu qu và thông sunh
khi truy vt trong nhng cách gii quyt cho
v 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

2
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

c gi là 1 node hot site.
M d liu phân tán là mt tp hp nhiu CSDL i logic và
c phân b trên mt mng máy tính.
m quan trc nêu ra và c:
- Tính chất phân tán: Tt c d liu ca CSDL phân tán 
cùng mt v 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. 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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 ti nhiu v trí
khác nhau, ng thy trong các ng dng mà h thng s phân
quyn truy nhp d li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 lý. Các server ca google phân b rông khp
trên toàn th gii. 4
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 c thc hin qua mng truyn
thông. Mi tài nguyên cc qun lý bi m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  bao
gm lp k hoch d  t tên cho các lp tài nguyên, cho phép tài
c truy cp t  ta
ch truyn thông,
2. Tính mở

nhau.
Kh  rng ca mt h  i tính không
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.
u này ch t  m i vi h phân tán hin ti (không th
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c 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t ngt  tránh tình
trng tc nghn xy ra khi ch có mt Server và phng các yêu cu truy
nhp  i ta nhân bn file trên mt Server khác và h thc
thit k sao cho vic b sung c d dàng. Có th n gii pháp
khác là s dng Cache và các bn sao d liu. 6
5. Khả năng thứ lỗi
Kh  li th hin vic h thng không b s 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
Vic thit k kh  li các h thng máy tính da trên hai gii
pháp sau:
- Dùng kh   m bo s hong liên tc và hiu qu.
-  m b 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 tin c
- Bí mt ca d liu.
- Các chng phm bo.
- Ngoài ra các yêu cu ca h thng v tính nh 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 nhược điểm của cơ sở dữ liệu phân tán
-  phc tp thit k t h th qun tr CSDL phân tán
phi b sung thêm các ch
+ Theo dõi du vt d liu
+ X lý các truy vn phân tán
+ Qun lý giao dch phân tán
+ Phc hi CSDL phân tán
+ Qun lý các bn sao
+ Quc - catalog phân tán
- H thng phn cc tn có nhiu trm và các trm
phc kt ni trên mng.

8
- Các phn mm h thm bo qun tr, duy trì kt ni d liu
trên mng.
- Bo m
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n thì vic truy cc thc hin
 phân tán và không ng ti s dng.
Ví dụ 1.3: Xét quan h tng th NCC (Id, Tên, Tui) n
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 
thy tính trong suc th hi
Khi mun tìm m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 *

+   NCC2 c sao làm hai bn trên hai v trí 2 và v trí
3, ta ch cn tìm thông tin trên quan h NCC2 mà không cn quan tâm nó
 v trí nào.

10

Hình 1.2: Sự trong suốt về vị trí
1.2.3. Trong suốt ánh xạ địa phương (local mapping transparency)
- Là mc tính quan trng trong mt h thng nht.
- ng dng tham chi   c lp t các h
thng cc b .
- ng dt trên mt h thng nhc
s dt h th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)
- nh tt c các d liu s  trong CSDL 
 lic phân tán  các trm trong h thng.

11
-  tng th p trung.
- Trong mô hình quan h tng th bao g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à n (fragment).
- Có nhi thc hin vic phân chia này.
-  n mô t các ánh x gia các quan h tng th n
c  n (fragmentation Schema).
- c mô t bng tên ca quan h tng th cùng vi ch mc

nh vt lý.

Hình 1.4: Các đoạn và hình ảnh vật lý của một quan hệ tổng thể
Ba yu t c suy ra t kiu kin trúc này là:
- Tách ri khái nin d liu vi khái ninh v d liu.
- Bic d lia.
- c lp v.
Ba yếu tố này tương ứng với ba mức trong suốt tương ứng
a. Tách ri khái nin d liu vi khái ninh v d liu.

13
 Phân đoạn dữ liệu, bao gm nhng công vi  i lp trình
ng dng làm vic vi quan h tng th, phân chia quan h tng th
n.
Thông qua tính trong suốt phân đoạn (fragmentation transparencyi
lp trình s nhìn thc nhn d liu b  nào.
Định vị dữ liệu li liên n các công vic ci s dng và
i lp trình ng dng tn d linh v ti các trm.
Thông qua tính trong suốt vị trí (location transparency) i lp trình s
bic v trí cn d liu trên các trm.
b. Biết được dữ liệu dư thừa:
i lp trình ng dng có th bia d liu  các trm.
 trên, chúng ta thy rng hai nh vt lý R2 và R3 có trùng lp
d lin d liu trùng nhau có th 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   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 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
 dng.

tích Decartes và phép kt ni là rt tn thi gian.
Ví dụ 2.1: Xét biu thc AB × CD (AB là mt quan h vi các thuc tính
A, B); ta ng nht hai quan h này vi hai tp d li  ca
tích Decartes này phi duyt ht bn ghi ca mt quan h, chng hn AB, 
vòng ngoài, vi mi bn ghi r ca tp AB, duyt tp CD  vòng trong và ni r
vi mi bn ghi ca tp CD. Gi s quan h AB có n bn ghi, CD có m bn
ghi thì tích Decartes AB × CD có n × m bn ghi. Rõ ràng phép tính trên rt
tn kém v thi gian và ô nh.
Ullman J.D trong các kt qu nghiên cu cn
c tng quát cho vic tn. ý tng t
nhóm: Nhóm 1 gm các phép bii s có liên quan hoc không liên
 các quan h, nhóm 2 gm các chic có li cho
vi các quan h khoá, ch s. Các chic thc hi
sau [4]:

16
1. Thực hiện phép chọn sớm nhất có thể: Bi i câu truy v 
phép chn vào thc hic nhm làm gic ca kt qu trung
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:
 bit, phép kt nc bit là kt ni bng có th thc hi
 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 i s ca phép chn và phép chn phép
so sánh gia các thuc tính c phép kt n 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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 i.
, 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

mt kt qu  trong biu thc bi các th hin c th.
- Các phép bii phi làm gi thc hin câu truy vn. Chi
phí cho x lý câu truy vn có rt nhiu yu t, tuy nhiên ta ch n
mt s n nh ln truy xut khi nh gia b nh
trong và b nh ngoài; s bn ghi cn phi x lý  thit b trung tâm; phn b
nh   các kt qu trung gian trong quá trình thc hin câu truy vn.
2.2.2. Biểu thức tương đương
Hai biu thc E
1
và E
2
gu E
1
E
2
, nu quan h kt
qu ca hai biu th bi các th hin c th.
Vt s phép bi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

Trích đoạn Thuật toán INGRES phân tán Thuật toán System R* Thuật toán SDD- Các thuật toán AHY (Apers – Hevner – Yao) CHƢƠNG 4: MỘT VÍ DỤ (CASE STUDY) VỀ TỐI ƢU HOÁ TRUY VẤN ĐỂ THỬ NGHIỆM THUẬT TOÁN

---