Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TIN HỌC
BÁO CÁO ĐỀ TÀI
CƠ SỞ DỮ LIỆU NÂNG CAO
ĐỀ TÀI : TỐI ƯU HÓA TRUY VẤN

GVHD : TRẦN QUỐC CHIẾN
Sinh Viên : SUKHOI

Lớp Học Phần : 11 03-A
Đà Nẵng, ngày 8 tháng 5 năm 20131
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
MỤC LỤC
2
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
1. Giới thiệu:
1.1 Thuật toán tối ưu hóa truy vấn:
Tối ưu hóa vấn tin là quá trình sinh ra một hoạch định thực thi vấn tin
(query execution plan – QEP ) biểu thị chiến lược thực thi vấn tin, hạ thấp tối đa
hàm chi phí. Thể tối ưu hóa vấn tin, là một đơn thể phần mềm chịu trách nhiệm
thực hiện tối ưu hóa,cấu tạo bởi ba thành phần: không gian tìm kiếm (seach
space), một mô hình chi phí (cost model ) và một chiến lược tìm kiếm (search
strategy ) như hình sau
CÂU VẤN TIN
QEP TƯƠNG ĐƯƠNG
QEP TỐT NHẤT

trách nhiệm trong làm việc nhóm, làm việc có tổ chức có phân công và đạt hiệu
quả.
Làm việc theo nhóm là một trong những kỹ năng thiết yếu cho sinh viên
trong học tập, nghiên cứu và cho công việc sau này.Cùng với sự giúp đỡ của quý
thầy cô hướng dẫn cộng với sự nỗ lực thì nhóm Sukhoi sẽ đi đến đích của thành
công.
SUKHOI:
STT Họ và tên Công việc
Chữ
kí
Nhận xét
của giáo
viên
1 Nguyễn Thị Diễm Hường Viết báo cáo, thuật
toán,chương trình, ví dụ
của việc nối 2 quan hệ
bằng phương pháp sắp nối
2 Nguyễn Thị Kim Hoàng -Viết báo cáo, thuật toán,
chương trình, ví dụ của
việc nối 2 quan hệ bằng
phương pháp chọn trên
tích.
-Đánh giá chi phí truy xuất
khối phương pháp sắp nối.
-Cấu trúc các file R, S,
RS1, RS2.
3 Khổng Thanh Dũng -Giới thiệu thuật toán tối
ưu hóa truy vấn.
-Viết chương trình sắp xếp
2 quan hệ R và S

là số bản ghi của R và S.

R
B
và
S
B
là số khối chưá R và S.
M là số khối bộ nhớ trong.
Thuật toán trên sẽ cần B lần truy suất khối để đọc quan hệ S và mỗi khối
của R sẽ được truy xuất d lần (d là số đoạn M - 1 khối cúa S). Vì d xấp xỉ bằng
1
S
B
M −
nên chi phí đọc dữ liệu là :

.
1
R S
S
B B
B
M
+
−
Gọi I là tích kích thước miền các thuộc tính chung của R và S(ở đây là chỉ
thuộc tính B chung). Vì số lượng bộ trung bình của nối R><S bằng số bộ của tích
R × S (
.

B 4 5 2 3 1 2 1 3
S B 1 2 1 2 4 3
C U V t x y Z
Giả sử khối S chứa được 2 bản ghi, bộ nhớ trong M=3. Khi đó số khối của
R và S là B
R
= 4, B
s
= 3. Ta dành M-1 = 2 khối, kí hiệu M
s
, để đọc S, 1 khối, ký
hiệu M
r
và M
s
như sau :
M
r
A
B
M
s
B
C
Thực hiện nối như sau:
Vòng 1: Đọc hai khối của S vào M
s
, ta được:
M
s

So sánh các bản ghi của M
s
với các bản ghi của M
r
, ta thấy bản ghi
(2,v) và (2,x) của M
s
nối được với bản ghi (c,2) của M
r
. ta nhân được:
M
r
A C c
B 2 2
6
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
C V x
-Đọc khối thứ ba của R vào M
r
ta có:
M
r
A E f
B 1 2
So sánh các bản ghi của M
s
với các bản ghi của M
r
ta thấy bản ghi (1,
u) và (1,t) của M

tự nhiên S, ta nhân được R nối tự nhiên S có 8 bản ghi:
R ntn
S
A C C e e f F G g
B 2 2 1 1 2 2 1 1
C V X u t v X U t
Vòng 2: Đọc một khối của S vào M
s
ta được:
M
s
B 4 3
C Y Z
Sau đó đọc lần lượt từng khối của R vào M
r
, nối các bản ghi của M
s
với các bản ghi của M
r
, ghi tiếp vào R ntn S. kết thúc vòng này, R ntn S
có thêm 3 bản ghi:
A A D h
B 4 3 3
C Y Z Z
Cuối cùng ta có R ntn S như sau:
R S A C C E e f f g G A d h
B 2 2 1 1 2 2 1 1 4 3 3
C V X U t v x u T Y z z
7
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao

-Đọc tiếp bản ghi v € S;
While đọc hết hoặc R hoặc S
-Nếu S hoặc R còn bản ghi, thì đọc và ghi các bản ghi có giá trị thuộc tính B
bằng giá trị thuộc tính B trong M’ vào M’
-Nếu M’ không rỗng, thì kết xuất các nối trong M’ ra đĩa;
b. Đánh giá chi phí truy xuất khối và độ phức tạp:
8
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
Giả thiết : R và S được xếp chặt.R
T
và

S
T
là số bản ghi của R và S.R
B
và
S
B
là số khối chưá R và S.
M là số khối bộ nhớ trong.
Với phương pháp trên thì mỗi khối của R và S chỉ cần đọc một lần nên chi phí
đọc của thuật toán là :
R S


c. Ví dụ:
Cho R(A, B) và S(B, C) như sau :
R A A B c d
B 1 1 2 3
S B 1 2 2
C X Y z
Bộ nhớ M’ có cấu trúc như sau :
M’ A
B Null
C
9
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
Ban đầu M’ rỗng và giá trị thuộc tính B trong M’ chưa xác định,
M’.B = null. Nối R ntn S có cấu trúc như sau :
R ntn S A
B
C
Ban đầu R ntn S rỗng, chưa có bản ghi nào cả. Ta thực hiên thuật
toán 4.2 để nối R và S như sau:
-Đọc R vào u, và S vào v:
Ta có u(B) = v(B) = 1. Vì M rống nên ta đưa v và u vào M’:
M’ A A
B 1
C X
Đọc tiếp R vào u và S vào v:
R A A b c d
B 1 1 2 3
S B 1 2 2
C X y z

M’ A C
B 2
C Y Z
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
Lúc này S đã hết, R vẫn còn bản ghi.
Vì u(B) = 3 > M’.B = 2, ta nối các bản ghi trong M’, ghi ra R ntn S
RntnS A A b c C
B 1 1 2 2
C X x y Z
Kết thúc.
2.2 Phân tích thiết kế cấu trúc dữ liệu và giải thuật
2.2.1 Thuật toán nối 2 quan hệ bằng phương pháp chọn trên tích
a. Cấu trúc file R.DAT, S.DAT, RS1.DAT
- Cài đặt quan hệ R dưới dạng file có tên là R.dat :
Quan hệ R (A,B )
+R.A có kiểu int : có các số nguyên từ 0 -> 999
+R.B có kiểu int : có các số nguyên từ 0 -> 99
- Khai báo: struct R {
int A;
int B ;
};
- Cài đặt quan hệ S dưới dạng file có tên là S.dat :
Quan hệ S ( B,C )
+S.B có kiểu int : có các số nguyên từ 0 -> 999
+S.C có kiểu int : có các số nguyên từ 0 -> 99
- Khai báo :Struct S{
int C;
int B;
};
- Quan hệ RS1: là nối tự nhiên của 2 quan hệ R và S :

c. Thiết kế giải thuật:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define mMax 20
#define bfR 15
#define bfS 15
#define bfRS 10
FILE *fr, *fs, *frs, *fRS;
char *Rname = "R.DAT";
char *Sname = "S.DAT";
13
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
char *RSname = "RS.DAT";
char *RSname1 = "RS1.TXT";
int sizeR, sizeS, sizeRS;
int pR, pS;//con tro file
int m; //bo nho
int Ts, mTs; //so ban ghi con lai cua S
int Tr, mTr; //so ban ghi con lai cua R
int Trs;
int ks; //khoi cuoi chua S
int js; //ban ghi cuoi trong khoi k cua s
int jr; //ban ghi cuoi trong khoi cua R
int jrs; //ban ghi cuoi trong khoi cua RS
int k, i, j, d = 0;
struct Rbanghi{
int A, B;

//khoi cuoi cua S

for(j = 0; j <= js; j++)
for(i = 0; i <= jr; i++)
{
if(Skhoi[ks][j].B == Rkhoi[i].B)
{
RS.A = Rkhoi[i].A;
RS.B = Rkhoi[i].B;
RS.C = Skhoi[ks][j].C;
fwrite(&RS, sizeof(struct RSbanghi), 1, frs);

}
}
}

void ghiRS()
{

printf("\n**** Nhap so khoi bo nho trong : \a");
scanf("\n %d",&m);

sizeR = sizeof(R);
sizeS = sizeof(S);
sizeRS = sizeof(RS);
//mo file

fr = fopen(Rname,"rb");
fs = fopen(Sname,"rb");
15

} while((ks < m-1)&&(mTs > 0)); mTr = Tr;
fseek(fr,0,SEEK_SET);

do
{
if(mTr > bfR)
{
16
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
fread(Rkhoi, sizeof(struct Rbanghi), bfR, fr);
mTr = mTr - bfR;
jr = bfR - 1;
}
else
{
fread(Rkhoi, sizeof(struct Rbanghi), mTr, fr);
jr = mTr - 1;
mTr = 0;
}
NoiRS();

}while(mTr > 0);
} fclose(fr);
fclose(fs);

RS.C);
fprintf(fRS, "\n\t\t\t %3d\t %2d\t %3d\t\n", RS.A, RS.B, RS.C);
fprintf(fRS, "\t\t\t");
d++;
}
printf("\n***** Tong so luong cac bo trong file RS sau khi noi R va S la :
%d",d);
printf("");
// fprintf(fRS,"\n**** Tong so ban ghi trong baang RS (phuong phap chon
tren tich) la : %d\n",d);
fclose(frs);
}
int main()
{
ghiRS();
getch();
}

2.2.2 Thuật toán nối 2 quan hệ bằng phương pháp sắp nối.
a. Cấu trúc file R2.DAT, S2.DAT, RS2.DAT
- Quan hệ R2 (A,B )
+ R2.A có kiểu int : có các số trong file R.DAT đã được sắp xếp
+ R2.B có kiểu int : có các số trong file R.DAT đã được sắp xếp
- Khai báo : struct R2 {
int A;
int B;
};
Cài đặt quan hệ R2 dưới dạng file có tên là R2.dat chứa các bản ghi kiểu R2 ,
các bản ghi có trường B giống nhau được đặt liên tiếp nhau và được sắp xếp, có J
giá trị R2.B.

#include <time.h>
#define max 100 // so cuc dai ban ghi kha noi
#define bfR 15
#define bfS 15
#define bfRS 10
#define oo 100000
FILE *fr, *fs, *frs, *fRS;
char *Rname = "R.DAT";
char *Sname = "S.DAT";
19
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
char *RSname = "RS2.DAT";
char *RSname1 = "RS2.TXT";
int sizeR, sizeS, sizeRS;
int pR, pS;//con tro file
int Ts, mTs;//so ban ghi con lai cua S
int Tr, mTr;//so ban ghi con lai cua R
int Trs;
int js;//ban ghi cuoi trong khoi cua S
int jr;//ban ghi cuoi trong khoi cua R
int jrs;//ban ghi cuoi trong khoi cua RS
int k, i, j, d = 0;
struct Rbanghi { int A, B; };
struct Sbanghi { int B, C; };
struct RSbanghi { int A, B, C; };
struct Rbanghi R, MRkhoi[bfR];
struct Sbanghi S, MSkhoi[bfS];
struct RSbanghi RS;
int mB; //thuoc tinh B chung
int RA[max], SC[max];//mang chua thuoc tinh A va C noi voi mB

{
GhiRS();
}
else
{
jsc++;
SC[jsc] = MSkhoi[j].C;
}
}
void Case3()
{
if (MRkhoi[j].B > mB)
{
GhiRS();
}
else
{
jra++;
RA[jra] = MRkhoi[i].A;
}
}
void GhiRS()
21
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
{
int p, q;
for (p = 0 ; p <= jra; p++)
for (q = 0; q <= jsc; q++)
{
RS.B = mB;

if (jr < 0) //doc 1 khoi R
22
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
{
if (mTr > bfR)
{
fread(MRkhoi, sizeof(struct Rbanghi), bfR, fr);
mTr = mTr - bfR; jr = bfR-1; i = 0;
}
else
{
fread(MRkhoi, sizeof(struct Rbanghi), mTr, fr);
jr = mTr-1;mTr = 0; i = 0;
}
}
if (js < 0) //doc 1 khoi S
{
if (mTs > bfS)
{
fread(MSkhoi, sizeof(struct Sbanghi), bfS, fs);
mTs = mTs - bfS; js = bfS-1; j = 0;
}
else
{
fread(MSkhoi, sizeof(struct Sbanghi), mTs, fs);
js = mTs-1; mTs = 0; j = 0;
}
}
while ((i <= jr) && (j <= js))
{

jr = -1;
}
}
}
}
// Xu ly ban ghi conlai
while (mTr > 0)
{
if (jr < 0) //doc 1 khoi R
{
if (mTr > bfR)
{
fread(MRkhoi, sizeof(struct Rbanghi), bfR, fr);
mTr = mTr - bfR; jr = bfR-1; i = 0;
}
else
{
fread(MRkhoi, sizeof(struct Rbanghi), mTr, fr);
jr = mTr-1;mTr = 0; i = 0;
}
}
while ((i <= jr) && (MRkhoi[i].B == mB))
{
24
Nhóm Su Khoi – Đề tài Cơ Sở Dữ Liệu Nâng Cao
jra++;
RA[jra] = MRkhoi[i].A;
i++;
}
if (i > jr)

if (j > js)
{
js = -1;
}
25