1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

ĐÀO NGỌC SƠN NGHIÊN CỨU TỐI ƯU HÓA TRUY VẤN
HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN

Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60.48.15
Người hướng dẫn khoa học: PGS.TS ĐOÀN VĂN BAN
TÓM TĂT LUẬN VĂN THẠC SĨ KỸ THUẬT

HÀ NỘI- 2012

2

MỞ ĐẦU
1. Lý do chọn đề tài
Thực trạng hiện nay Viễn thông thanh hóa đang sử dụng phần mềm phục vụ
công tác quản lý và điều hành sản xuất của mình, các ứng dụng chính gồm: Hệ

1.1. Khái niệm về hệ cơ sở dữ liệu phân tán
1.1.1. Khái niệm
Cơ sở dữ liệu phân tán là một tập hợp các dữ liệu phục thuộc lôgic lẫn nhau
của cùng một hệ thống và được lưu trữ trên các trạm 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 nhập tới cơ sở dữ liệu lớn trên mạng.
Trong hệ thống đó mỗi máy tính quản lý một cơ sở dữ liệu thành phần được gọi là 1
node hoặc site. [4]
Định nghĩa này nhấn mạnh hai khía cạnh quan trọng của cơ sở dữ liệu phân
tán
- Tính phân tán: Thực tế dữ liệu không cư trú ở cùng một trạm, vì vậy chúng
ta có thể phân biệt một cơ sở dữ liệu phân tán với cơ sở dữ liệu tập trung
- Sự tương quan logic: Các dữ liệu có một số tính chất ràng buộc lẫn nhau và
như vậy có thể phân biệt cơ sở dữ liệu phân tán với tập các cơ sở dữ liệu địa
phương hoặc với các tệp ở các trạm khác nhau trên mạng.
1.1.2. Hệ quản trị cơ sở dữ liệu phân tán(DDBMS)
Khác DDBMS có chức năng hỗ trợ việc tạo và bảo trì cơ sở dữ liệu phân tán, chúng
có các thành phần tương tự như một hệ quản trị cơ sở dữ liệu tập trung thành các
thành phần hỗ trợ trong việc chuyển tải dữ liệu đến các trạm và ngược lại
Hệ quản trị cơ sở dữ liệu phân tán được phân làm 2 loại
- Cơ sở dữ liệu phân tán thuần nhất
- Cơ sở dữ liệu phân tán hỗn tạp
1.1.3 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 cơ sở dữ liệu phân tán là dữ liệu của các cơ sở dữ
liệu 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 [7].
1. Cho phép quản lý dữ liệu với nhiều mức trong suốt
2. Tăng độ tin cậy và khả năng sẵn sàng
3. Cải thiện hiệu năng
4
4. Dễ dàng mở rộng

5
tương ứng với một
đoạn. Ký hiệu R
i
là đoạn thứ i của quan hệ tổng thể R.
- Lược đồ định vị: Định nghĩa ánh xạ từ các phân đoạn vào những trạm chứa
những phân đoạn đó. Tất cả các đoạn tương ứng với cùng quan hệ tổng thể
R và được đặt tại cùng trạm j tạo thành hình ảnh vật lý của quan hệ tổng thể
R tại trạm j.
- Lược đồ ánh xạ địa phương: Ánh xạ các hình ảnh vật lý tới các đối tượng
được thao tác bởi các hệ quản trị cơ sở dữ liệu địa phương. Trong hệ không
thuần nhất ta có các kiểu ánh xạ địa phương khác nhau tại các trạm khác
nhau.
i
=p
i
, với p
i
là tân từ của R
i
. Để có thể khôi phục được R ta dùng phép hợp các
quan hệ R = R
1
 R
2
  R
n
.
1.4.1.2 Phân mảnh ngang dẫn tiếp
Phân mảnh ngang dẫn tiếp là sự phân chia một quan hệ ban đầu thành các
quan hệ thứ hai khác mà các quan hệ đó liên hệ với quan hệ ban đầu bằng một khoá
ngoài. Điều này như là liên hệ dữ liệu giữa quan hệ ban đầu và quan hệ thứ hai
được phân đoạn trong cùng một cách.
7
1.4.1.3 Phân mảnh dọc
Phân mảnh dọc là sự chia một quan hệ thành tập con các bộ, mỗi tập
được xác định bởi một phép chiếu được áp dụng cho quan hệ: R
i
= П
ATTRi
R,
trong đó ATTR
i

mạng cho các truy vấn toàn bộ vì dữ liệu sẽ
được lấy từ các trạm cục bộ.
Nhược điểm: Các thao tác cập nhập dữ liệu rất chậm vì phải copy, đồng
bộ dữ liệu cho mọi trạm. Kỹ thuật điểu khiển tương tranh và
phục hồi sẽ phức tạp
hơn.
2. Không có nhân bản dữ liệu: Mỗi phân mảnh chỉ được lưu trữ trên một
trạm, phương án này còn được gọi là định vị không dư thừa dữ liệu.
Trong
trường hợp này các phân đoạn phải tách rời nhau để tránh lặp bản ghi
giống nhau
cho các phân đoạn ngang và phân đoạn hỗn hợp.
8
3. Nhân bản dữ liệu từng phần: Một vài phân mảnh có thể được tạo bản sao
và có thể một số phân mảnh sẽ không có bản sao. Việc tạo bản sao này rất có tác
dụng cho các nhân viên làm việc di động, tại các nơi xa trung tâm dữ liệu, có thể
tạo ra bản sao dữ liệu trên laptop của mình và theo chu kỳ đồng bộ dữ liệu với cơ sở
dữ liệu server.
1.4.3 Định vị dữ liệu
Là quá trình gán từng phân đoạn, từng bản sao của phân đoạn cho một trạm
cụ thể trong hệ thống phân tán. Việc chọn trạm nào và số bản sao phụ thuộc vào
yêu cầu hiệu năng và mục tiêu sẵn sàng của hệ thống với các loại giao tác trên các
trạm. Đối với hệ yêu cầu tính sẵn sàng cao, mọi giao dịch thao tác lấy dữ liệu, giao
dịch cập nhật chỉ làm tại một trạm thì nên tổ chức tạo bản sao đầy đủ. Nếu các giao
dịch thường cập nhật một phần dữ liệu tại một trạm thì các phân đoạn cho phần dữ
liệu đó nên được định vị trên trạm đó.
1.5 Kết luận
Cơ sở dữ liệu 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 cơ sở dữ liệu phân tán đó là: Cơ sở

nhiều để thực hiện quá trình biến đổi đó.
- Các phép biến đổi phải bảo toàn kết quả của câu truy vấn trước và sau khi
biến đổi, có nghĩa là hai biểu thức trước và sau khi biến đổi phải cho cùng một kết
quả khi thay các lược đồ trong biểu thức bởi các thể hiện cụ thể.
- Các phép biến đổi phải làm giảm chi phí để 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ỉ quan tâm đến một số
thông báo cơ bản nhất sau đây: số 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ớ để lưu trữ
các kết quả trung gian trong quá trình thực hiện câu truy vấn.
2.1.2 Các phương pháp xử lý truy vấn cơ bản
Phương pháp biến đổi đại số :
10
Đơn giản hóa câu truy vấn nhờ các phép biến đổi đại số tương đương nhằm
giảm thiểu thời gian thực hiện các phép toán, phương pháp này không quan tâm đến
cấu trúc và kích thước dữ liệu
Phương pháp ước lượng chi phí :
Xác định kích thước dữ liệu, thời gian thực hiện mỗi phép toán trong câu
truy vấn. Phương pháp này phải xác định kích thước dữ liệu và chi phí thời gian
thực hiện mỗi phép toán trong câu truy vấn
2.2 Các kỹ thuật tối ưu hóa tập trung
Phần này sẽ trình bày hai kỹ thuật tối ưu hoá câu truy vấn đối với hệ tập
trung. Sự biểu diễn này là điều kiện để tối ưu hóa câu truy vấn phân tán với ba lý
do:
-
Một câu
truy vấn
phân tán được biến đổi thành các câu
truy vấn
địa
phương được

i
, nghĩa là
qi-1
được thực hiện trước và kết quả của nó được sử dụng bởi q
i
.
11
Bộ

xử lý câu truy vấn INGRES phân tích q thành n câu truy vấn q
1
 q
2
 q
3

q
n
. Sự phân tích này sử dụng hai kỹ thuật cơ bản phân tách và thay thế.
2.2.2 Thuật toán SYSTEM R
System R thực hiện tối ưu hóa truy vấn tĩnh, đầu vào là một cây đại số quan hệ
do phân tích một truy vấn SQL, đầu ra là sơ đồ thực hiện cây đại số quan hệ "tối
ưu". Thuật toán tối ưu bao gồm hai bước chính:
-

Dự đoán phương pháp truy nhập tới
mỗi quan hệ đơn tốt nhất dựa trên
một
giả thiết chọn.
- Với mỗi quan hệ R, đánh giá thứ tự kết nối tốt nhất, trong đó R được truy

kết nối bằng, và khi các quan hệ được sắp xếp trước. Nếu chỉ một hoặc không có
quan hệ nào được sắp xếp, chi phí của vòng lặp lồng nhau được so sánh với chi phí
của phương pháp trộn + chi phí sắp xếp. Chi phí sắp xếp n bộ bản ghi là nlog
2
n.

12
2.3 Tối ưu hóa truy vấn phân tán

2.3.1 Mục tiêu của bài toán truy vấn
Mục tiêu của bài toán truy vấn trong môi trường phân tán là biến đổi câu vấn tin
cáp cao trên CSDL phân tán (mà người sử dụng vẫn tưởng là CSDL tập trung) thành một
chiến lược thực thể hiệu quả được diễn tả bằng một ngôn ngữ cấp thấp trên các CSDL cục
bộ. Giả sử ngôn ngữ cấp cao là phép tính quan hệ, ngôn ngữ cấp thấp là một dạng mở rộng
của đại số quan hệ đi kèm với các thao tác truyền dữ liệu.
Xét các quan hệ EMP (ENO, ENAME, TITLE)
ASG (ENO, PNO, RESP, DUR)
Và câu vấn tin: “Cho biết các nhân viên hiện đang quản lý một dự án”
Câu SQL là: SELECT ENAME
FROM EMP, ASG
WHERE EMP.ENO = ASG.ENO
AND ASG.RESP = “Manager”
Hai biểu thức tương đương đại số quan hệ do biến đổi từ câu vấn tin trên là:

ENAME
(
RESP = “Manager”  EMP.ENO = ASG.ENO
(EMP x ASG)) (*)
Và 
ENAME

(EMP)
EMP
2
= 
ENO > “E3”
(EMP)
ASG
1
= 
ENO  “E3”
(ASG)
ASG
2
= 
ENO > “E3”
(ASG)
Các mảnh ASG
1
, ASG
2
, EMP
1
, EMP
2
theo thứ tự được lưu tại các vị trí 1, 2, 3, 4 kết quả
lưu tại vị trí 5.


1

ENO
ASG
1
’ EMP
2
’ = EMP
2

ENO
ASG
2
’
ASG
1
’ = 
RESP = “Manager”
(ASG
1
) ASG
2
’ = 
RESP = “Manager”
(ASG
2
)
Result = (EMP
1
 EMP

EMP
1
’

EMP
2
’

ASG
1
’

ASG
2
’

V
ị

trí 3

V
ị

trí 4

V
ị

trí 1

Hình 2.4: Sơ đồ phân lớp cho việc xử lý truy vấn phân tán
2.3.3 Phân rã câu truy vấn
Phân rã câu truy vấn là biến đổi một câu truy vấn các phép tính quan hệ
thành câu truy vấn
đại số trên các quan hệ tổng thể. Cả hai câu
truy vấn
vào và ra
đều trên các quan hệ
tổng thể và không quan tâm đến tính phân tán của dữ liệu. Vì
Vấn tin dạng phép tính trên
các quan hệ phân tán
Phân rã
câu

truy v
ấn

Vấn tin dạng đại số

trên các quan h
ệ phân tán

Đ
ịnh vị

d
ữ liệu

khiển
Các vị
trí cục
bộ
15
vậy, phân rã câu
truy vấn
là chung cho cả quan hệ tập trung và phân tán. Trong
phần này, giả sử câu
truy vấn
vào là đúng đắn (chỉnh). Khi việc phân rã được
thực hiện xong câu
truy vấn
ra là chỉnh và tránh được các công việc dư thừa.
Giai đoạn này chia làm 4 bước[3]
:
-
Chuẩn hoá
-
Phân tích
-
Loại bỏ dư thừa
- Viết lại
2.3.4 Định vị dữ liệu phân tán
Như đã biết, tầng định vị biến đổi một câu truy vấn đại số trên các quan
hệ tổng thể, thành một câu truy vấn đại số được hiển thị trên các phân đoạn
vật lý.
Việc định vị sử dụng thông tin được lưu trữ trên lược đồ phân đoạn.
Chương
trình đại số quan hệ xây dựng lại quan hệ tổng thể từ các phân đoạn của nó

Mục đích của phân đoạn hỗn hợp là hỗ trợ các câu truy vấn liên quan đến
phép chiếu, chọn, kết nối một cách hiệu quả. Chương trình định vị cho một quan hệ
đã phân đoạn hỗn hợp sử dụng phép hợp và phép kết nối của các đoạn.
2.3.4 Tối ưu hoá các truy vấn phân tán
Ta đã biết, một câu truy vấn trong phép tính quan hệ biểu diễn trên các
quan
hệ phân tán có thể được ánh xạ thành một câu truy vấn trên các đoạn quan hệ
bằng
cách phân rã và định vị dữ liệu. ánh xạ này sử dụng lược đồ phân đoạn.
Trong xử lý này, việc áp dụng các luật biến đổi cho phép đơn giản hoá câu truy
vấn bằng
cách tìm các biểu thức con chung và loại bỏ các biểu thức vô ích. Câu
truy vấn
thu được từ giai đoạn phân rã và định vị dữ liệu có thể được thực thi một
cách đơn
giản bằng việc thêm vào các thao tác truyền thông. Tuy nhiên, hoán vị
thứ tự các phép toán trong câu truy vấn có thể cung cấp nhiều chiến lược tương
đương để thực thi chúng. Tìm một thứ tự “tối ưu” của các phép toán cho một câu
truy vấn đã
cho là chức năng chính của bộ tối ưu hoá câu truy vấn.
Sự lựa chọn thứ tự tối ưu đối với một câu truy vấn là bài toán khó thực
hiện nên mục đích thực sự của bộ tối ưu là tìm một chiến lược gần tối ưu. Sau
đây
ta sẽ gọi chiến lược (hoặc thao tác sắp thứ tự) được đưa ra bởi bộ tối ưu
là
chiến lược tối ưu (hoặc sắp chiến lược tối ưu). Đầu ra của bộ tối ưu là một lịch
trình được tối ưu bao gồm câu truy vấn đại số được xác định trên các trạm.
2.3.4.1. Đầu vào bộ tối ưu hoá câu truy vấn
1. Mô hình chi phí
Chi phí của một chiến lược thực hiện phân tán có thể được biểu diễn hoặc

các
xử lý địa phương song song và truyền thông song song phải được xét. Công
thức tổng quát tính thời gian trả lời (response time) là [8]:
Response_time = C
CPU
*seq_#insts + C
I/O
*seq_#I/Os
+ C
MSG
*seq_#msgs + C
TR
*seq_#bytes
Trong đó: seq_#x (x có thể là các lệnh CPU, I/O, các thông báo, các
byte) là số lớn nhất của x phải được thực hiện tuần tự đối với sự thực thi của
câu truy vấn.

2 Các thống kê cơ sở dữ liệu
Yếu tố chính ảnh hưởng đến hiệu suất của một chiến lược thực thi là
kích thước của các quan hệ trung gian sinh ra trong quá trình thực hiện. Khi
gặp phép toán tiếp theo đặt tại một trạm khác, quan hệ trung gian phải được

truyền lên mạng. Do vậy, để tối thiểu hoá khối lượng dữ liệu truyền, điểm
quan tâm đầu tiên là đánh giá kích thước kết quả trung gian của các phép toán đại
số quan hệ. Đánh giá này dựa trên các thông tin thống kê về các quan hệ cơ sở
và các công thức ước tính lực lượng của kết quả của các ph p toán quan
hệ. Quan
hệ R xác định trên A = {A
1
, A

(số giá trị phân biệt trên mỗi thuộc tính).

18
2. Miền xác định của A
i
là tập số nguyên hoặc tập số thực, có max(A
i
)
và
min(A
i
).
3. Lực lượng của miền A
i
kí hiệu là card(dom[A
i
]), đó là số các giá trị
duy
nhất trên mỗi miền trị của thuộc tính A
i
.
4. Số các bộ trong mỗi đoạn R
j
ký hiệu là card(R
j
)
Ngoài ra, dữ liệu thống
kê cũng bao gồm hệ số chọn của phép kết nối
(SF
J

2.3.4.2. Thứ tự kết nối trên các câu truy vấn đoạn
Ta đã thấy thứ tự kết nối có vai trò quan trọng trong việc tối ưu hoá câu truy
vấn tập trung. Thứ tự kết nối trong môi trường phân tán còn quan trọng hơn vì các
phép kết nối giữa các đoạn có thể làm tăng chi phí truyền thông. Có hai cách tiếp
cận cơ bản để sắp thứ tự các phép kết nối trong các câu truy vấn đoạn.
- Cố gắng tối ưu thứ tự của các phép kết nối một cách trực tiếp
- Thay các phép kết nối bởi kết hợp các phép nửa kết nối để cực tiểu
19
hoá
các chi phí truyền thông.
Thứ tự kết nối
Một số thuật toán tối ưu hoá thứ tự của các phép kết nối một cách trực
tiếp không sử dụng phép nửa kết nối. Thuật toán INGRES phân tán và R
*
là
đại diện cho lớp này. Phần này đề cập đến việc sử dụng các phép nửa kết nối
để
tối ưu hoá các câu truy vấn kết nối .
Trước khi đi vào vấn đề chính, ta giả thiết như sau:
- Câu truy vấn được định vị và biểu diễn trên các đoạn, ta không cần phân biệt
giữa các đoạn của cùng một quan hệ và các đoạn của các quan hệ khác.
- Dùng thuật ngữ quan hệ để chỉ một đoạn lưu trữ tại một trạm cụ thể.
- Bỏ qua chi phí xử lý địa phương.
- Chỉ xét các câu truy vấn kết nối mà các toán hạng quan hệ được lưu tại
các
trạm khác nhau.
- Bỏ qua chi phí truyền dữ liệu tại trạm kết quả.
Vấn đề truyền toán hạng trong phép kết nối đơn, hiển nhiên là gửi quan
hệ
nhỏ hơn tới trạm của quan hệ lớn hơn, có hai khả năng như hình 4.2

-
Các thành phần tối ưu của hàm chi phí, SDD-1: kích thước thông báo,
AYH: kích thước thông báo và số thông báo; System R*: kích thước
thông báo,
số thông báo và chi phí I/O và CPU; INGRES phân tán: kích
thước thông báo và
chi phí I/O + CPU.
-
Kiểu mạng, SDD-1 và AHY: mạng diện rộng điểm tới điểm, INGRES
phân tán và R*: mạng cục bộ và diện rộng.
-
SDD_1 và AHY sử dụng các phép nửa kết nối như một kỹ thuật tối ưu
hoá câu truy vấn, INGRES phân tán và R* thực hiện kết nối tương tự các giải
thuật
tối ưu hoá câu truy vấn tập trung INGRES và System R:
- Mỗi thuật toán đều có nhận thông tin thống kê về dữ liệu:
+ INGRES phân tán: lực lượng của quan hệ.
+ R*: lực lượng của quan hệ, số các giá trị duy nhất trên thuộc tính
SDD-1: lực lượng của quan hệ, hệ số chọn kết nối, kích thước của
phép chiếu trên mỗi thộc tính kết nối, kích thước thuộc tính và
kích thước bộ dữ liệu.
+ AHY: lực lượng quan hệ, hệ số chọn kết nối, kích thước thuộc
tính và kích thước bộ dữ liệu.
-
INGRES phân tán có thể sử dụng các đoạn, còn R*, SDD-1, AHY
không sử dụng.
2.4 Kết Luận

21
Chương này đã trình bày những khái niệm cơ bản về tối ưu hóa truy vấn

TRUY VẤN PHÂN TÁN

1. Xác định thuật toán
Chương trình sẽ cài đặt thuật toán tối ưu phân tán của System R* là một mở rộng về
chất của các kỹ thuật đã được phát triển cho bộ tối ưu hóa trong môi trường tập
trung của System R. Nó là thuật toán tối ưu tĩnh, trong đó thực hiện việc tìm kiếm
vét cạn tất cả các chiến lược khác nhau để chọn ra được một chiến lược với chi phí
thấp nhất.
Cơ sở dữ liệu được thiết kế theo mô hình phân mảnh dọc dựa trên hệ thống cơ sở dữ
liệu ORACLE hiện tại của viễn thông thanh hóa:
- Bảng DM_TTOAN chứa các thông tin khác hàng người chịu trách nhiệm trả
tiền cước các loại dịch vụ, được cài đặt trên máy trạm địa chỉ IP cuối là 62,
gọi tắt là máy trạm 62
- Bảng DM_SOMAY chứa thông tin các dịch vụ của thuê bao được cài đặt
trên máy trạm địa chỉ IP cuối 21, gọi tắt là máy trạm 21
- Việc kết nối tới trạm còn lại thực hiện qua DBLINK là chức năng hỗ trợ hệ
cơ sở dữ liệu phân tán của ORACLE
- Thuật toán thực hiện việc truy vấn với giả thiết thực hiện kết nối tập trung,
thực hiện kết nối ở trạm 21 và trạm 62 để chọn ra kết quả tối ưu nhất
2.

Kết Luận
Nghiên cứu cơ sở dữ liệu phân tán là một hướng đi đúng đắn, phù hợp với tổ
chức lớn, có nhiều chi nhánh. Việc ứng dụng cơ sở dữ liệu phân tán giải quyết
tốt các bài toán xử lý nhanh khi chỉ có yêu cầu truy xuất cục bộ, Và thực hiện
tốt vấn đề chia tải
Hệ thống phân tán là một hệ thống cơ sở dữ liệu phức tạp hơn, đòi hỏi việc tổ
chức vật lý, mô hình mạng phức tạp, Việc tìm hiểu và tối ưu hóa phân tán có ý
nghĩa quan trọng quyết định đến hiệu năng hệ thống, làm hệ thống cơ sở dữ
liệu phân tán mang những lợi ích giống như cơ sở dữ liệu tập trung và phát huy 24
TÀI LIỆU THAM KHẢO

[1] Phạm Thế Quế (2009) “Giáo trình Cơ sở dữ liệu phân tán”, NXB thông tin và
truyền thông
[2] Nguyễn Bá Tường (2005), Nhập môn cơ sở dữ liệu dữ liệu phân tán, NXB Khoa
học và kỹ thuật
[3] Nguyễn Văn Nhuận, Phạm Việt Bình(2009), “Giáo trình hệ cơ sở dữ liệu phân
tán & suy diễn:Lý thuyết và thực hành”, NXB Khoa học và kỹ thuật
[4] Vũ Đức Thi (1997) Cơ sở dữ liệu – kiến thức và thực hành, NXB Thống kê.
[5]Kenneth H. Rosen, người dịch: Phạm Văn Thiều, Đặng Hữu Thịnh (1998), Toán
rời rạc Ứng dụng trong tin học, NXB Khoa học và kỹ thuật.
[6] M. Tamer Ozsu, Patrick Valduriez, biên dịch Trần Đức Quang (1999), Nguyên
lý các hệ CƠ SỞ DỮ LIỆU phân tán, tập I, NXB Thống kê.
[7] Clement T.Yu, Weiyi Meng (1998), Principles of Database Query Processing
for Advanced Applications, Morgan Kaufmann Publishers, Inc.
[8] Sakti Pramanik, David Ittiner (1985), Use of Graph-Theoretic Models for
Optimal Relational Database Accesses to Perform Join, pages 57-76 , ACM
Transaction on Database Systems.
[9] Zhe Li, Kenneth A. Ross (1994), Better Semijoin Using Tuple Bit-Vectors,
Technical Report No. CUCS-010-94.
[10] Ramzi A. Haraty, Roula C.Fany (2001), Query Acceleration in Distributed
Database Systems, Colombian Journal of Computation. Volume 2, Number 1.