Tập bài giảng Cơ sơ dữ liệu phân tán (Phần 2)
Tập bài giảng Cơ sở dữ liệu phân tán
Chƣơng 4
BIẾN ĐỔI CÁC TRUY VẤN TOÀN CỤC
THÀNH CÁC TRUY VẤN MẢNH
Một thao tác truy xuất trong một ứng dụng có thể đƣợc biểu diễn nhƣ là một truy
vấn tham chiếu đến các quan hệ toàn cục. DDBMS phải biến đổi truy vấn này thành
các truy vấn đơn giản hơn mà chúng chỉ tham chiếu đến các mảnh. Chƣơng này giải
quyết phép biến đổi này.
Có nhiều cách khác nhau để biến đổi một truy vấn trên các quan hệ toàn cục đƣợc
gọi là truy vấn toàn cục (global query) thành các truy vấn trên các mảnh đƣợc gọi là
truy vấn mảnh (fragment query). Các biến đổi khác nhau này tạo ra các truy vấn mảnh
tƣơng đƣơng theo nghĩa chúng tạo ra cùng kết quả. Vì lí do này, chƣơng này cũng giải
quyết các phép biến đổi tƣơng đƣơng (equivalence transformation), nghĩa là các quy
tắc có thể đƣợc áp dụng cho một truy vấn để viết truy vấn này thành một biểu thức
tƣơng đƣơng.
Các quy tắc tƣơng đƣơng đƣợc sử dụng để đơn giản hóa biểu thức truy vấn (query
expression). Ví dụ xác định các biểu thức con chung và các phép toán đƣợc “phân tán”
cho các mảnh. Tuy nhiên, điều nhấn mạnh trong chƣơng này là tính đầy đủ
(completeness) và tính đúng đắn (correctness) của phép biến đổi. Mục tiêu của chúng
ta là đƣa ra một tập hợp các quy tắc biến đổi tƣơng đƣơng và bao quát tất cả các khía
cạnh liên quan đến các phép biến đổi truy vấn.
Các nội dung chính trong chƣơng này:
- Các kỹ thuật đƣợc sử dụng trong các hệ thống tập trung để biến đổi truy vấn.
Trƣớc tiên, chúng ta đƣa ra cách biểu diễn truy vấn bằng cách sử dụng một cây truy
vấn (query tree). Sau đó chúng ta đƣa ra một cách tiếp cận về ngữ nghĩa cho các phép
biến đổi tƣơng đƣơng và cuối cùng cho thấy cách biến đổi một cây truy vấn thành một
đồ thị truy vấn (query graph) để xác định các biểu thức con chung trong một truy vấn.
Ở đây, chúng ta đƣa ra nhiều nhắc nhở này bởi vì nó liên hệ chặt chẽ với những gì đi
theo sau. Hơn nữa, các khía cạnh này trong các CSDL phân tán càng quan trọng hơn
so với trong các CSDL tập trung và phép biến đổi truy vấn đƣợc đƣa vào trong các
môi trƣờng phân tán.
Các truy vấn toàn cục đƣợc biến đổi thế nào thành các truy vấn mảnh. Chúng ta
nêu ra một ánh xạ chuẩn tắc (canomical mapping) và cho thấy ánh xạ chuẩn tắc là
đúng đắn. Sau đó, chúng ta sử dụng các phép biến đổi tƣơng đƣơng để biến đổi biểu
thức chuẩn tắc (canomical mapping) của truy vấn. Cơ sở của các phép biến đổi này là
áp dụng các phép toán đại số (algebraic operation). Chẳng hạn phép chiếu và phép
175
Tập bài giảng Cơ sở dữ liệu phân tán
chọn, để làm giảm kích thƣớc của các toán hạng của chúng càng nhiều càng tốt trên
mỗi mảnh trƣớc khi truyền dữ liệu giữa các nơi.
Các truy vấn có liên quan đến cách đánh giá của việc gom nhóm từng phần: mệnh
đề GROUP BY của lệnh SELECT và các hàm kết hợp (aggregate function). Chúng ta
mở rộng đại số quan hệ (relational algebra) để bao quát các vấn đề này, và sau đó nêu
ra một số phép biến đổi tƣơng đƣơng áp dụng cho các phép toán mới. Cơ sở của các
phép toán này là phân tán việc xử lý đến các mảnh.
Các truy vấn tham số (parametric query), nghĩa là các truy vấn này có chứa các
điều kiện chọn bao gồm các tham số mà giá trị sẽ đƣợc xác định ở thời gian thực hiện.
Các truy vấn là các thao tác truy xuất cơ bản tiêu biểu trong các ứng dụng tham số
(parametric application) nhƣ đƣợc nêu ra trong chƣơng 2. Chúng ta nêu ra các biện
pháp biến đổi tƣơng đƣơng có thể đƣợc sử dụng nhƣ thế nào để cải tiến tính hiệu quả
của chúng.
4.1. Các phép biến đổi tƣơng đƣơng dùng cho các truy vấn
Một truy vấn quan hệ (relational query) có thể đƣợc biểu diễn bằng cách sử dụng
các ngôn ngữ khác nhau. Ở đây, chúng ra sử dụng đại số quan hệ và ngôn ngữ SQL
cho mục đích này. Hầu hết các truy vấn SQL đều có thể đựơc biến đổi thành các biểu
thức đại số quan hệ tƣơng đƣơng và ngƣợc lại. Do đó, bất kỳ các ngôn ngữ nêu trên có
thể đƣợc sử dụng để biểu diễn ngữ nghĩa của truy vấn. Tuy nhiên, chúng ta có thế diễn
dịch một biểu thức quan hệ đại số (expression of relational algebra) không chỉ là sự
đặc tả ngữ nghĩa của một truy vấn, mà còn là sự đặc tả của một chuỗi các phép toán)
sequence of operations). Từ quan điểm này, hai biểu thức có cùng ngữ nghĩa có thể mô
tả hai chuỗi phép toán khác nhau.
Ví dụ 4.1:
MANV, MAQL
(NV)
MAP=1
và
MANV, MAQL (NV)
MAP=1
là các biểu thức tƣơng đƣơng nhƣng định nghĩa hai chuỗi phép toán khác nhau.
Trong chƣơng này, vì chúng ta quan tâm đến thứ tự thực hiện của các phép toán,
bắt đầu từ việc sử dụng các biểu thức đại số quan hệ ban đầu và phân tích các phép
biến đổi tƣơng đƣơng của chúng.
4.1.1. Cây toán tử của một truy vấn
1) Mục đích:
- Dùng để biểu diễn các truy vấn
- Giúp theo dõi các thao tác trên biểu thức
- Xác định một thứ tự bộ phận mà trong đó các phép toán phải đƣợc thực hiện cho
ra kết quả của truy vấn.
2) Cấu tạo cây:
176
Tập bài giảng Cơ sở dữ liệu phân tán
- Nút lá: chứa các quan hệ toàn cục
- Các nút trung gian và nút gốc: biểu diễn
+ phép toán một ngôi (unary operation)
+ phép toán hai ngôi (binary operation)
Ví dụ 4.2: Xét hệ thống quản lý kinh doanh của một công ty trong ví dụ 2.13 và có
một ứng dụng: Đƣa ra mã của nhà cung cấp đã cung cấp hàng mà có địa chỉ ở Nam
Định.
Truy vấn Q1 tƣơng ứng với biểu thức đại số quan hệ:
Q1:
(
DC= “Nam Định” (NCC>< MANCC = MANCC KD))
MANCC
Cây toán tử của truy vấn Q1:
Cây toán tử của một biểu thức đại số quan hệ có thể đƣợc xem nhƣ một cây phân
tích cú pháp (pharse tree) của chính biểu thức đó, giả sử có văn phạm sau đây:
R identifier
R (R)
R un_op R
un_op
F A
bin_op
- F <F <
Để dễ biểu diễn, chúng ta loại bỏ trong cây phân tích cú pháp các dấu ngoặc trong
luật sinh thứ hai và chúng đƣợc thể hiện bởi cấu trúc của cây toán tử.
4.1.2. Các phép biến đổi tƣơng đƣơng dùng cho đại số quan hệ
1) Quan hệ tƣơng tƣơng
Hai quan hệ là tƣơng đƣơng khi các bộ của chúng biểu diễn cùng ánh xạ từ các tên
thuộc tính vào các giá trị ngay cả khi thứ tự của các thuộc tính là khác nhau.
2) Biểu thức tƣơng đƣơng
177
Tập bài giảng Cơ sở dữ liệu phân tán
Hai biểu thức đại số quan hệ E1 và E2 là tƣơng đƣơng, kí hiệu E1 E2 hoặc E1
E2 nếu thay thế cùng các quan hệ cho các tên giống nhau trong hai biểu thức thì ta có
các kết quả tƣơng đƣơng.
Các phép biến đổi tƣơng đƣơng đƣợc xây dựng từ các biểu thức đơn giản (các biểu
thức có hai hoặc ba quan hệ toán hạng) và đƣợc phân loại theo loại toán tử.
3) Các tính chất của các phép toán đại số quan hệ:
Cho U là phép một ngôi và B là phép hai ngôi.
- Tính giao hoán (commutativity) của các phép toán một ngôi:
U1(U2(R)) U2(U1(R))
- Tính giao hoán của các phép toán hạng của các phép toán hai ngôi:
R B S S B R
- Tính kết hợp (associativity) của các phép toán hai ngôi:
R B (S B T) (R B S) B T
- Tính lũy đẳng (idempotence) của các phép toán một ngôi:
U (R) U1(U2 (R))
trong đó U1, U2 thuộc cùng loại phép toán.
- Tính phân phối (distributivity) của các phép toán một ngôi đối với các phép toán
hai ngôi
U(R B S) U(R) B U(S)
- Tính rút thừa số (factorization) của các phép toán một ngôi (phép biến đổi này
ngƣợc với tính phân phối):
U(R) B U(S) U(R B S)
4) Các phép biến đổi tƣơng đƣơng
Từ các tính chất trên của các phép toán đại số quan hệ, chúng ta có thể liệt kê các
phép biến đổi tƣơng đƣơng sau đây, còn đƣợc gọi là quy tắc đạo sinh (generation rule)
mà chúng cho thấy phần mô tả bên vế phải đƣợc suy diễn nhƣ thế nào từ phần mô tả
bên vế trái. Các quy tắc đạo sinh không đƣợc thể hiện khi các phần mô tả của vế trái
và vế phải giống nhau.
1- Hai phép chọn kề nhau
-
-
F1(F2(R)) F2(F1(R))
F1 F2 F1F2
R
R
2 - Hai phép chiếu kề nhau
X1(R) với X1 X2
3 - Phép chiếu kề với phép chọn
X1
X 2 R
-
X
F
R
F
X
R; nếu Attr(F) X
178
Tập bài giảng Cơ sở dữ liệu phân tán
-
X (F (R)) X (F X Attr(F)(R)))
4 - Phép hợp kề với phép chọn
F
R S F (R) F (S)
5 - Phép kết nối kề với phép chọn
-
-
F
R S
F
R
S ; nếu Attr(F) Attr(R)
F1F2
R S
F1
R F2(S)
;
nếu Attr(F1) Attr(R) và Attr(F2) Attr(S))
-
F
R S
F2 (F1
R S)
;
nếu F = F1 F2 và Attr(F1) Attr(R) và Attr(F2) Attr(R) Attr(S))
6 - Phép tích Đề- Các kề với phép chọn
F (R) S ; nếu Attr(F) Attr(R)
-
F
R S
-
F1F2
R S
F1
R F2(S);
nếu Attr(F1) Attr(R) và Attr(F2) Attr(S)
S ) ; nếu F = F1 F2 và
Attr(F1) Attr(R) và Attr(F2) (R) Attr(S)
7 - Phép giao kề với phép chọn
-
F
R S
F2(F1
R
-
F
RS
F (R)F (S)
F1(R)F2(S);
-
F1F2
RS
nếu Attr(F1) Attr(R) và Attr(F2) Attr(S)
8 - Phép trừ kề với phép chọn
F
R S F (R) F (S)
9 - Phép trừ kề với phép chiếu
X (R S) X (R) X (S)
10 - Phép hợp kề với phép chiếu
X (RS) X (R)X (S)
11 - Phép kết nối kề với phép chiếu
-
X
R S
X
R
S ; nếu Attr(FR) X (Attr(FR) là các thuộc
tính trong R của phép kết nối và X Attr(R)
X 2(S); nếu Attr(F) X1 X2 và
-
X1X 2
R S
X1
R
X1 Attr(R) và X2 Attr(S) (Attr(F) là các thuộc tính trong R và S của phép
kết nối).
12 - Phép tích Đề- Các kề với phép chiếu
X1X 2
RS
X1
R X 2(S);
179
Tập bài giảng Cơ sở dữ liệu phân tán
nếu X1 Attr(R) và X2 Attr(S)
13 - Các phép hợp, giao, tích Đề- Các và kết nối
- (R S) T (R T) S
- (R S) T (R T) S
- (R S) T (R T) S
-
R F1 S
F2 T
R F2 T F1 S
;
nếu Attr(F2) Attr(R) Attr(T) và Attr(F1) Attr(R) Attr(S)
14 - Phép kết nối đi sau phép hợp
R S
T
R T
S T
S T
S T
R S T R T S
15 - Phép giao đi sau phép hợp
RS
T
RT
16 - Phép hiệu đi sau phép hợp
RS
T
R T
17 - Phép hiệu đi trƣớc phép hợp
R
S T
R S
R T
5) Các tiêu chuẩn áp dụng các phép biến đổi tƣơng đƣơng để đơn giản hóa việc
thực hiện các truy vấn
Các phép toán hai ngôi và đặc biệt là các phép kết nối là các phép toán tốn kém
nhất trong các hệ thống CSDL. Do đó cần phải giảm kích thƣớc của các toán hạng của
các phép toán hai ngôi trƣớc khi thực hiện chúng bằng cách sử dụng các phép biến đổi
tƣơng đƣơng.
Tiêu chuẩn 1: Sử dụng tích lũy đẳng của phép chọn và phép chiếu để tạo ra các
phép chọn và các phép chiếu thích hợp đối với mỗi quan hệ toán hạng.
Tiêu chuẩn 2: Đẩy các phép chọn và các phép chiếu xuống phía dƣới cây nếu có
thể đƣợc.
Khi một phép chiếu di chuyển xuống dƣới qua một phép kết nối thì các thuộc tính
trong điều kiện kết nối phải có trong tập thuộc tính chiếu của phép này.
Trong các CSDL phân tán, các tiêu chuẩn này còn quan trọng hơn: các phép toán
hai ngôi đòi hỏi so sánh các toán hạng mà chúng có thể đƣợc đặt tại các nơi khác nhau.
Truyền dữ liệu là một trong các thành phần chính của các chi phí và các trì hoãn gắn
liền với việc thực hiện truy vấn. Do đó, việc làm giảm kích thƣớc của các toán hạng
của các phép toán hai ngôi là một điều quan tâm chính.
Ví dụ 4.3: Xét truy vấn Q1 trong ví dụ 4.2. Áp dụng hai tiêu chuẩn trên, ta biến đổi
truy vấn Q1 nhƣ sau:
- Phép chọn đƣợc phân phối đối với phép kết nối. Do đó, phép chọn đƣợc áp dụng
trực tiếp cho quan hệ NCC.
180
Tập bài giảng Cơ sở dữ liệu phân tán
- Hai phép chiếu mới đƣợc tạo ra và đƣợc phân phối đối với phép kết nối.
Khi một phép chiếu di chuyển xuống dƣới quan một phép kết nối thì các thuộc tính
trong điều kiện kết nối phải có trong tập thuộc tính chiếu của phép này.
4.1.3. Đồ thị toán tử và xác đinh biểu thức con chung
Một vấn đề quan trọng việc áp dụng các phép biến đổi cho một biểu thức cho một
biểu thức truy vấn là tìm ra các biểu thức con chung (common subexpresion) của nó.
Rõ ràng, điều này sẽ tiết kiệm thời gian thực hiện của một truy vấn nếu các biểu thức
con chung chỉ đƣợc định trị một lần.
Phƣơng pháp xác định biểu thức con chung là biến đổi cây toán tử thành một đồ thị
toán tử.
1) Các bƣớc biến đổi cây toán tử thành đồ thị toán tử:
Bƣớc 1: Gộp các nút lá giống nhau của cây tức là các quan hệ toán hạng giống
nhau.
Bƣớc 2: Gộp các nút trung gian khác của cây tƣơng ứng với cùng các phép toán và
có cùng các toán hạng.
2) Các đặc tính đƣợc dùng để đơn giản hóa một cây toán tử
(1) R R R
(2) R R R
(3) R - R
(4) R F(R) F(R)
(5) R F(R) R
(6) R - F(R) F(R)
(7) F1(R) F2(R) F1 F2(R)
(8) F1(R) F2(R) F1 F2(R)
(9) F1(R) - F2(R) F1 F2(R)
Ví dụ 4.4: Đƣa ra tên của các nhân viên làm việc trong một phòng ban có mã quản
lí là 100 nhƣng họ không đƣợc lĩnh lƣơng nhiều hơn 2000.
181
Tập bài giảng Cơ sở dữ liệu phân tán
Ta có biểu thức của truy vấn:
- NV1 = NV ><NV.MAPPH.MAP (σMAQL100 PH)
- NV2 = σLUONG2000 NV ><NV.MAPPH.MAP σMAQL100 PH
-
TENNV NV NV
2
1
Vì phép kết nối giữa các quan hệ là phép kết nối bằng nền các biểu thức truy vấn
có thể đƣợc viết lại nhƣ sau:
- NV1 = NV(σMAQL100 PH)
- NV2 = σLUONG2000 NV σ
PH
MAQL100
-
TENNV NV NV
2
1
Ta có cây toán tử tƣơng ứng với biểu thức
Bƣớc 1: Gộp các nút lá tƣơng ứng với các quan hệ NV và PH
+ Đặt thừa số là phép chọn trên LUONG đối với phép kết nối bằng cách di chuyển
phép chọn lên phía trên
+ Gộp các nút tƣơng ứng với phép chọn trên MAQL ta đƣợc các nút tƣơng ứng với
phép kết nối
Ta có đƣợc cây toán tử nhƣ sau:
Ta đƣợc biểu thức con tƣơng ứng với cây toán tử trên là
182
Tập bài giảng Cơ sở dữ liệu phân tán
NV1= NV(σMAQL100DEPT)
Bƣớc 2: Áp dụng đặc tính thứ 6: NV1 - σLUONG2000 NV LUONG 2000(NV1), ta
1
rút gọn cây toán tử thành cây nhƣ sau:
Ta đƣợc biểu thức con tƣơng ứng với cây toán tử trên
TENNV
σ
NV(σ
PH)
MAQL100
LUONG2000
Bƣớc 3: Áp dụng phép biến đổi tƣơng đƣơng (2)
TENNV
σ
NV(σ
PH)
MAQL100
LUONG2000
TENNV
σLUONG2000(NV(σMAQL100 PH))
MAP,TENNV
Áp dụng phép biến đổi tƣơng đƣơng (5)
σ
LUONG2000(NV)σMAQL100(PH)
TENNV MAP, TENNV
Áp dụng phép biến đổi tƣơng đƣơng (12)
σ
(NV
σ
PH
MAQL100
MAP
TENNV MAP, TENNV
LUONG2000
Ta đƣợc cây toán tử nhƣ sau:
183
Tập bài giảng Cơ sở dữ liệu phân tán
4.2. Biến đổi truy vấn toàn cục thành các truy vấn mảnh
1) Biểu thức chuẩn tắc
Biểu thức chuẩn tắc (canonical expression) của một biểu thức đại số trên lƣợc đồ
toàn cục là biểu thức mà mỗi tên quan hệ toàn cục xuất trong nó đƣợc thay thế bởi biểu
thức đại số tái tạo các quan hệ toàn cục từ các mảnh.
Ví dụ 4.5: Xét lƣợc đồ phân mảnh của quan hệ toàn cục PH trong ví dụ 2.13
PH1=
PH2=
PH3=
MAP 10(PH)
MAP >10 AND MAP < 20 (PH)
MAP 20 (PH)
Cho truy vấn Q2: MAP = 1(PH)
Biểu thức chuẩn tắc
MAP = 1(PH1 PH2 PH3)
2) Cây toán tử trên lƣợc đồ phân mảnh
Biến đổi một cây toán tử trên lƣợc đồ toàn cục thành một cây toán tử trên lƣợc đồ
phân mảnh bằng cách thay thế các nút lá của cây toán tử trên lƣợc đồ toàn cục bởi các
biểu thức tái tạo tƣơng ứng của lƣợc đồ phân mảnh.
3) Tối ƣu hóa biểu thức chuẩn tắc
- Sử dụng các phép biến đổi tƣơng đƣơng.
- Sử dụng tính phân phối của phép chọn và phép chiếu đối với phép hợp và phép
kết nối để phân phối việc xử lý đến các mảnh.
Ví dụ 4.6: Xét truy vấn Q1 trong ví dụ 4.3 với truy vấn Q1 và biểu thức tái tạo quan
hệ toàn cục NCC và PH
NCC= NCC1 NCC2
KD= KD1 KD2
Vì phép kết nối là phép kết nối bằng nên cây toán tử có thể đƣợc biểu diễn nhƣ sau:
184
Tập bài giảng Cơ sở dữ liệu phân tán
Cây toán tử đƣợc của truy vấn Q1 đƣợc biểu diễn trong thành cây toán tử của biểu
thức chuẩn tắc của truy vấn Q1 nhƣ sau:
Áp dụng phép biến đổi tƣơng đƣơng (4) và (11), ta đƣợc cây toán tử nhƣ sau:
1) Khái niệm:
Một quan hệ định tính là một quan hệ đƣợc mở rộng bởi một vị từ định tính. Vị từ
định tính có thể đƣợc xem là một đặc tính ngữ nghĩa (intensional property) của tất cả
các bộ của quan hệ.
Ký hiệu một quan hệ định tính (qualified relation) là một cặp [R:qr ]
Trong đó:
- Một quan hệ đƣợc gọi là thân (body) của quan hệ định tính
- qr là một vị từ đƣợc gọi là vị từ định tính (qualification) của quan hệ định tính.
185
Tập bài giảng Cơ sở dữ liệu phân tán
Các mảnh ngang là các ví dụ tiêu biểu của các quan hệ định tính, trong đó vị từ
định tính tƣơng ứng với vị từ phân mảnh.
Ví dụ 4.7: Xét lƣợc đồ phân mảnh trong ví dụ 2.13, ta có các quan hệ định tính
[PH1: MAP 10]; [PH2: MAP >10 AND MAP < 20].
[NCC1: DC = „Miền Bắc‟]; [NCC2: DC = „Miền Nam‟].
[KD1: KD.MANCC = NCC.MANCC NCC. DC = „Miền Bắc‟]
[KD2: KD.MANCC = NCC.MANCC NCC. DC = „Miền Nam‟]
Vị từ định tính của một quan hệ không cần phải đƣợc định trị trên các bộ của quan
hệ. Tuy nhiên, nếu vị từ định tính đƣợc định trị thì vị từ định tính phải đúng. Cụ thể,
một vị từ định tính không thể đƣợc định trị khi chúng ta không địng trị đƣợc một số
thuộc tính trong biểu thức của vị từ định tính.
Đại số các quan hệ định tính là sự mở rộng của đại số quan hệ, trong đó sử dụng
các quan hệ định tính nhƣ là các toán hạng. Rõ ràng, đại số này đòi hỏi việc thao tác
trên các điều kiện định tính cũng nhƣ trên các quan hệ.
2) Các quy tắc
Các quy tắc sau đây xác định kết quả của việc áp dụng các phép toán đại số quan
hệ cho các quan hệ định tính:
a) Quy tắc 1: F [R: qR] [F R: F AND qR]
Quy tắc này phát biểu rằng việc áp dụng một phép chọn F cho một quan hệ định
tính [R: qR] tạo ra một quan hệ định tính có quan hệ F R là thân của nó và vị từ F
AND qR là vị từ định tính của nó. Việc mở rộng vị từ định tính F AND qR sau khi chọn
phản ánh rằng F và qR đều đƣợc thỏa mãn trên tất cả các bộ đƣợc chọn.
b) Quy tắc 2: A [R: qR] A [R: qR]
Vị từ định tính của kết quả của một phép chiếu vẫn không thay đổi, ngay cả khi
phép chiếu loại bổ một số thuộc tính dùng để định trị vị từ định tính. Lý do là các vị từ
định tính mang thông tin ngữ nghĩa (intensional information). Do đó, điều này vẫn
đúng khi loại bỏ các thuộc tính đƣợc dùng đẻ biểu diễn vị từ định tính, mà không loại
bỏ chính định vị từ định tính
c) Quy tắc 3: [R: qR] [S: qS] [R S: qR AND qS]
Việc mở rộng vị từ định tính qR AND qS là trực quan. Lƣu ý rằng hai vị từ định tính
áp dụng riêng cho các thuộc tính của R S.
d) Quy tắc 4: [R: qR] - [S: qS] [R - S: qR]
Việc mở rộng phép hiệu là hơi trực quan. Khi chúng ta loại bỏ các bộ của quan hệ
S có trong quan hệ R, vì từ định tính của kết quả vẫn giống với vị từ định tính của R.
Điều không đúng khi thay thế nó thành qr AND NOT qs, bởi vì có thể các bộ của R
186
Tập bài giảng Cơ sở dữ liệu phân tán
không thỏa mãn qR AND NOT qS, nhƣng nó có trong kết quả bởi vì S không chứa các
bộ này.
Tuy nhiên, vấn đề sau đây đƣợc đặt ra với quy tắc 4:
Xét phép giao của hệ số quan hệ truyền thống, đƣợc định nghĩa là R S = R - (R -
S). Từ định nghĩa, dễ dàng thấy rằng phép giao có tính giao hoán, nghĩa là:
R S = S R
Nếu chúng ta áp dụng định nghĩa của đại số mở rộng, chúng ta đi đến 1 kết quả
đáng ngạc nhiên:
[R: qR] [S: qS] [R: qR] - ([R: qR] - [S: qS])
[R: qR] - [R - S: qR] [R (R - S): qR] [R S:qR]
[S: qS] [R: qR] [S: qS] - ([S: qS] - [R: qR]
(4.2.a)
[S: qS] - [S - R: qS] [S- (S - R): qS] - [R: qR] [S R: qS] (4.2b)
Trên thực tế, kết quả mà chúng ta muốn tìm là.
[R S: qR AND qS]
Bởi vì các bộ của phép giao là những bộ thuộc cả hai quan hệ thỏa mãn cả hai qr và
qs. Lƣu ý rằng, qr AND qs bao hàm cả hai qr và qs. Do đó, các kết quả (4.2a) và (4.2b)
là không sai, nhƣng dĩ nhiên một số thông tin bị mất.
e) Quy tắc 5: [R: qR] [S: qS] [R S: qR OR qS]
Phép hợp đƣợc mở rộng bằng cách lấy OR của các vị từ định tính.
Cho trƣớc các quy tắc trên, chúng ta thấy các phép toán đại số đƣợc suy đoán nhƣ
thế nào, chẳng hạn phép kết nối và phép nửa kết nối. Chúng ta có thêm hai quy tắc
f) Quy tắc 6:
[R: qR] [S: qS] [R F S: qR AND qS AND F]
Chứng minh quy tắc 6 (nên nhớ rằng phép kết nối đựơc suy dẫn từ việc sử dụng
phép chọn và tích Descarters).
[R: qR] [S: qS]
F ([R: qR] [S: qS]
F [R S: qR AND qS]
F (R S): qR AND qS AND F]
[R: F S: qR AND qS AND F]
g) Quy tắc 7: [R: qR] F [S: qS] [R F S: qR AND qS AND F]
Chứng minh quy tắc 7 (nên nhớ rằng phép nửa kết nối đƣợc suy dẫn từ việc sử
dụng phép chiếu và phép kết nối)
[R: qR] F [S: qS]
Atlr(R)([R: qR] F [S: qS])
Atlr(R)[R F S: qR AND qS AND F]
[Atlr(R)(R F S): qR AND qS AND F]
187
Tập bài giảng Cơ sở dữ liệu phân tán
[R: F S: qR AND qS AND F]
Chứng minh hai quy tắc này sẽ cho chúng ta thấy cách thao tác các quan hệ định
tính nhƣ thế nào.
3) Tính tƣơng đƣơng của hai quan hệ định tính
Hai quan hệ định tính là tƣơng đƣơng nếu các thân của chúng là các quan hệ tƣơng
đƣơng và các vị từ định tính của chúng biểu diễn cùng hàm chân trị. Nghĩa là, nếu
chúng ta áp dụng cả hai vị từ định tính cho cùng một bộ thì chúng ta có cùng một chân
trị
Hệ quả: Tất cả các phép biến đổi tƣơng của đại số quan hệ vẫn còn đúng với các
đại số quan hệ định tính.
4) Các phép biến đổi tƣơng đƣơng để xác định một truy vấn là rỗng
Chúng ta sử dụng các vị từ định tính để loại bỏ các mảnh không liên quan đến truy
vấn.
Xét vị từ định tính đƣợc tạo ra sau một phép chọn hoặc một phép chiếu. Trong
những trƣờng hợp này, vị từ định tính sẽ có dạng chuẩn giao các vị từ (conjunction of
predicates). Vị từ định tính này có thể bị mâu thuẫn. Một ví dụ về một vị từ định tính
mâu thuẫn là MAP =1 AND MAP= 5.
Các quan hệ định tính với các vị từ định tính mâu thuẫn về thực chất là rỗng. Điều
nhận biết này là có ích hơn so với việc phát hiện ra kết quả của một biểu thức là rỗng
khi thực hiện truy vấn.
Trên thực tế, sự mâu thuẫn là rút giảm các đặc tính ngữ nghĩa (intensional propety)
của các mảnh, và có thể sử dụng trong lúc biên dịch truy vấn.
Bằng cách sử dụng các vị từ định tính ở trên, đại số quan hệ định tính sẽ cho các
kết quả nhất quan mà các vị từ định tính của các toán hạng của nó đƣợc cho một cách
đúng đắn và sẽ không biết trƣớc kết quả nhƣ thế nào nếu các vị từ định tính là không
đúng.
Vì chúng ta áp dụng đại số này cho các mảnh của các quan hệ, điều cảnh báo này
cho thấy các vị từ định tính của các mảnh cần phải đƣợc cho trƣớc một cách chính xác.
Ví dụ 4.8: Các biểu thức con dẫn đến quan hệ rỗng là:
DC = „Miền Nam‟ [NCC1: DC = „Miền Bắc‟]
[PH1: MAP < 10] MAP = MAP[NV3: MAP > 20]
Việc nhận biết một trong các biểu thức con của một truy vấn thực chất là rỗng sẽ
dẫn đến các phép đơn giản hóa đáng kể của cây truy vấn.
Việc nhận biết một trong các biểu thức con của một truy vấn thực chất là rỗng sẽ
dẫn đến các phép đơn giản hóa đáng kể của cây truy vấn. Các phép biến đổi tƣơng sau
đây là có ích, trong đó R có thể đựơc xem là một quan hệ thông thƣờng hoặc một quan
hệ định tính:
188
Tập bài giảng Cơ sở dữ liệu phân tán
()
A()
R R
R R
R - R
- R
R
R
F
F
F R
Trong đó, R là một quan hệ thông thƣờng hoặc một quan hệ định tính.
Việc nhận biết một trong các biểu thức con của một truy vấn thực chất là rỗng sẽ
dẫn đến các phép đơn giản hóa đáng kể của cây truy vấn.
5) Các tiêu chuẩn để đơn giản hóa các biểu thức trên một lƣợc đồ phân mảnh:
Tiêu chuẩn 1: Sử dụng tích lũy đẳng của phép chọn và phép chiếu để tạo ra các
phép chọn và các phép chiếu thích hợp đối với mỗi quan hệ toán hạng.
Tiêu chuẩn 2: Đẩy các phép chọn và các phép chiếu xuống phía dƣới cây nếu có
thể đƣợc.
Tiêu chuẩn 3: Rút gọn với phép chọn
- Đẩy các phép chọn xuống phía các nút lá của cây
- Thực hiện chúng bằng cách dùng đại số quan hệ định tính
- Thay thế kết quả của phép chọn bởi quan hệ rỗng nếu vị từ định tính của kết quả
bị mâu thuẫn.
Tiêu chuẩn 4: Sử dụng đại số quan hệ định tính để định trị vị từ định tính của các
toán hạng của các phép kết nối.
Thay thế cây con (bao gồm phép kết nối và các toán hạng của nó) bằng quan hệ
rỗng nếu vị từ định tính của kết quả của phép kết nối bị mâu thuẫn.
Tiêu chuẩn 5: Để phân tán các phép kết nối xuất hiện trong một truy vấn toàn cục,
các phép hợp (biểu diễn việc tập hợp các mảnh) phải đƣợc đẩy lên phía trên các phép
kết mà chúng ta muốn phân phối.
Năm tiêu chuẩn trên đƣợc dùng để đơn giản hóa các quan hệ đƣợc phân mảnh
ngang đơn giản các phép kết nối giữa các quan hệ đƣợc phân mảnh ngang.
Các bước đơn giản hóa:
Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn
Bƣớc 2: Đẩy phép chọn xuống phía các nút lá của cây
189
Tập bài giảng Cơ sở dữ liệu phân tán
Bƣớc 3: Rút gọn với phép chọn bằng cách loại bỏ phần chứa phép chọn sinh ra
quan hệ rỗng
Cho quan hệ R đƣợc phân mảnh ngang chính thành R1, R2, ..., Rn, trong đó
Ri=
Quy tắc rút gọn phép chọn
p
(R), pi là vị từ chọn
pi
(Ri)= nếu u R: (pi(u)pj(u))
j
Trong đó:
+ pi, pj là các vị từ chọn
+ u là một bộ của R
+ p(u): vị từ p đúng với u
Ví dụ 4.9: Xét hệ thống quản lý kinh doanh của một công ty với lƣợc đồ phân
mảnh trong ví dụ 2.13. Hãy đơn giản hoá câu truy vấn trên các mảnh:
Select *
From PH
Where MAP=1
Ta có biểu thức đại số quan hệ tƣơng ứng:
Q3: MAP = 1(PH)
Bƣớc 1: Dạng chuẩn tắc của truy vấn Q3
MAP = 1(PH1 PH2 PH3)
Bƣớc 2: Đẩy phép chọn hƣớng xuống các nút lá bằng cách phân phối nó đối với phép
hợp.
Bƣớc 3: Rút gọn với phép chọn
MAP = 1(PH2) = u PH: (p2(u)pj(u))
190
Tập bài giảng Cơ sở dữ liệu phân tán
p2(u): 10<MAP < 20
pj(u): MAP = 1
MAP = 1(PH3) = u PH: (p3(u)pj(u))
p3(u): MAP > 20
pj(u): MAP = 1
Bƣớc 4: Đơn giản phép hợp
chính
Các bƣớc đơn giản hóa:
Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn theo hai giải pháp sau
Giải pháp 1:
R
F S = ( Ri) F ( Sj), nếu có nhiều mảnh đƣợc kết nối với nhau
Giải pháp 2:
F S = (Ri F Sj), nếu có một số cặp mảnh đƣợc kết nối với nhau
R
Bƣớc 2: Đẩy phép hợp lên phía các phép kết nối
( Ri) F ( Sj)= (Ri F Sj)
Bƣớc 3: Rút gọn với phép nối bằng cách loại bỏ phần đƣợc tạo bởi phép kết nối
sinh ra quan hệ rỗng.
Cho quan hệ R đƣợc phân mảnh ngang chính thành R1, R2, ..., Rn, trong đó
Ri=
(R), pi là vị từ chọn
pi
Quy tắc rút gọn phép nối
Ri F Rj = nếu u Ri, v Rj: (pi(u)pj(v))
Trong đó
pi, pj là các vị từ chọn
u là một bộ của Ri, v là một bộ của Rj
p(u): vị từ p đúng với u
191
Tập bài giảng Cơ sở dữ liệu phân tán
Chú ý: Nếu phép kết nối là phép kết nối bằng thì sử dụng kí hiệu *.
Ví dụ 4.10: Xét hệ thống quản lý kinh doanh của một công ty với lƣợc đồ phân
mảnh trong ví dụ 2.13. Hãy đơn giản hoá câu truy vấn trên các mảnh:
Select *
Form KD, NCC
Where KD.MANCC= NCC.MANCC
Ta có biểu thức đại số quan hệ tƣơng ứng:
Q4: KD * NCC
Các bƣớc đơn giản hóa:
Bƣớc 1: Dạng chuẩn tắc của truy vấn Q4
(KD1 KD2) * (NCC1NCC2)
Bƣớc 2: Đẩy phép hợp lên phía các phép kết nối
Bƣớc 3: Rút gọn với phép nối
KD1 * NCC2 =
KD2 * NCC1 =
4.2.5. Đơn giản hóa cho phân mảnh ngang dẫn xuất
Các bƣớc đơn giản hóa:
192
Tập bài giảng Cơ sở dữ liệu phân tán
Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn
Bƣớc 2: Đẩy phép chọn xuống phía dƣới các nút lá của cây
Bƣớc 3: Rút gọn phép chọn, đơn giản phép hợp
Bƣớc 4: Đẩy phép hợp lên phía các phép kết nối
( Ri) F ( Sj)= (Ri F Sj)
Bƣớc 5: Rút gọn với phép nối, đơn giản phép hợp
Ví dụ 4.11: Xét hệ thống quản lý kinh doanh của một công ty với lƣợc đồ phân
mảnh trong ví dụ 2.13. Hãy đơn giản hoá câu truy vấn trên các mảnh:
Select *
Form NCC, KD
Where NCC.MANCC = KD.MANCC and DC=”Miền Bắc”
Ta có biểu thức đại số quan hệ tƣơng ứng:
Q5: NCC * DC=”Miền Bắc” KD
KD * DC=”Miền Bắc” NCC
Các bƣớc đơn giản hóa:
Bƣớc 1: Dạng chuẩn tắc của truy vấn Q5
(KD1 KD2)* DC=”Miền Bắc” (NCC1 NCC2 )
Bƣớc 2: Đẩy phép chọn xuống phía dƣới
Bƣớc 3: Rút gọn với phép chọn, đơn giản phép hợp
DC=”Miền Bắc” (NCC2)=
193
Tập bài giảng Cơ sở dữ liệu phân tán
Bƣớc 4: Đẩy phép hợp lên phía các phép kết nối
Bƣớc 5: Rút gọn với phép nối, đơn giản phép hợp
KD2* DC=”Miền Bắc” (NCC1) =
4.2.6. Đơn giản hóa các quan hệ đƣợc phân mảnh dọc
Các bƣớc đơn giản hóa:
Bƣớc 1: Tìm dạng chuẩn tắc của truy vấn
Bƣớc 2: Đẩy phép chiếu xuống phía dƣới các nút lá của cây
Bƣớc 3: Rút gọn phép chiếu bằng cách loại bỏ các phép chiếu trên một mảnh dọc
sinh ra quan hệ vô dụng, mặc dù không phải là quan hệ rỗng.
Cho quan hệ R đƣợc đƣợc phân thành các mảnh R1, R2, …Rn
K là khóa của R
Ri = ΠX(R), trong đó X Attr(R)
Quy tắc rút gọn phép chiếu
ΠY, K(Ri)=vô dụng nếu tập thuộc tính chiếu Y X
Bƣớc 4: Đơn giản phép kết nối
194
Tải về để xem bản đầy đủ
119 trang
14100
Free
Bạn đang xem 20 trang mẫu của tài liệu "Tập bài giảng Cơ sơ dữ liệu phân tán (Phần 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:
- tap_bai_giang_co_so_du_lieu_phan_tan_phan_2.pdf
