ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đào Thị Thu Vân XỬ LÝ TRUY VẤN VÀ QUẢN LÝ GIAO TÁC
LUẬN VĂN THẠC SĨ
1.4.1 Các thành phần chi phí cho việc thực thi truy vấn 39
1.4.2 Thông tin danh mục sử dụng trong các hàm giá 40
1.4.3 Ví dụ của các hàm giá đối với phép SELECT 41
1.4.4 Ví dụ của các hàm giá đối với phép JOIN 43
1.4.5 Các truy vấn có quan hệ và thứ tự nối phức tạp 46
1.4.6 Ví dụ minh hoạ cho việc tối ƣu truy vấn dựa trên giá 48
1.5 Tối ƣu truy vấn ngữ nghĩa 51
1.6 Tổng kết 51 2
CHƢƠNG 2 XỬ LÝ GIAO TÁC 53
2.1 Giới thiệu về xử lý giao tác 53
2.1.1 Hệ thống đơn ngƣời dùng - hệ thống đa ngƣời dùng 53
2.1.2 Các giao tác, thao tác đọc - ghi và các vùng đệm DBMS 54
2.1.3 Tại sao điều khiển đồng thời là cần thiết 56
2.1.4 Tại sao khôi phục là cần thiết 59
2.2 Các khái niệm hệ thống và giao tác 61
2.2.1 Các trạng thái giao tác và các phép toán bổ xung 61
2.2.2 File log hệ thống 62
2.2.3 Điểm xác nhận của một giao tác 63
2.3 Các đặc tính mong muốn của giao tác 64
2.4 Lịch biểu và sự khôi phục 64
2.4.1 Lịch biểu của các giao tác 65
2.4.2 Miêu tả đặc tính các lịch biểu dựa trên việc khôi phục 66
2.5 Xếp thứ tự của lịch biểu 68
2.5.1 Các lịch biểu theo thứ tự, không theo thứ tự và lịch biểu có thứ tự
xung đột 68
2.5.2. Kiểm tra thứ tự xung đột của một lịch biểu 72
khiển sự tƣơng tác giữa các giao tác đồng thời.
Do kinh nghiệm làm việc với cơ sở dữ liệu còn ít, chắc chắn trong luận
văn còn nhiều thiếu sót. Chúng tôi chân thành mong đƣợc các thầy, các cô, và
bạn bè đóng góp ý kiến. 4
CHƢƠNG 1 XỬ LÝ VÀ TỐI ƯU TRUY VẤN
Trong chƣơng này trình bầy các kỹ thuật mà hệ quản trị cơ sở dữ liệu
(DBMS) sử dụng để xử lý, tối ƣu hoá và thực thi các truy vấn bậc cao. Một
truy vấn đƣợc trình bầy trong một ngôn ngữ bậc cao, nhƣ SQL, đầu tiên phải
đƣợc kiểm tra, phân tích và xác nhận tính hợp lệ. Bộ quét sẽ xác định các dấu
hiệu ngôn ngữ, nhƣ các từ khóa SQL, tên các thuộc tính và tên các quan hệ
trong nội dung câu truy vấn, trong khi đó bộ phân tích sẽ kiểm tra cú pháp của
truy vấn để xác định xem nó có đƣợc trình bầy phù hợp với các luật cú pháp
của ngôn ngữ truy vấn hay không. Một truy vấn cũng phải đƣợc xác nhận tính
hợp lệ bằng cách kiểm tra tất cả các tên quan hệ và thuộc tính là hợp lệ, và các
tên có ý nghĩa trong lƣu đồ cơ sở dữ liệu cụ thể đƣợc truy vấn. Sau đó một
biểu diễn bên trong của truy vấn đƣợc tạo ra, thƣờng là nhƣ một cấu trúc dữ
liệu cây gọi là một cây truy vấn. Cũng có thể biểu diễn truy vấn bằng cách sử
dụng một cấu trúc dữ liệu đồ thị gọi là đồ thị truy vấn. Sau đó DBMS sẽ phải
đƣa ra một chiến lƣợc thực hiện để lấy ra kết quả của truy vấn từ các file cơ
sở dữ liệu. Một truy vấn thƣờng có nhiều chiến lƣợc thực hiện, và quá trình
chọn một chiến lƣợc phù hợp để xử lý một truy vấn gọi là tối ƣu truy vấn. [1,
3, 4, 5, 6, 7]
Hình 1.1 thể hiện các bƣớc khác nhau của việc xử lý một truy vấn bậc
cao. Bộ tối ƣu truy vấn có nhiệm vụ tạo ra một phƣơng án thực hiện và bộ tạo
mã tạo ra chƣơng trình để thực hiện phƣơng án đó. Bộ xử lý cơ sở dữ liệu thời
gian chạy có nhiệm vụ chạy chƣơng trình truy vấn trong kiểu thông dịch hoặc
1.1 Chuyển các truy vấn SQL thành đại số quan hệ
Một truy vấn SQL đầu tiên chuyển đổi thành một biểu thức đại số quan
hệ mở rộng tƣơng đƣơng, đƣợc biểu diễn nhƣ là cấu trúc dữ liệu cây truy vấn,
và sau đó đƣợc tối ƣu. Thông thƣờng các truy vấn SQL đƣợc phân tích thành
các khối truy vấn, tạo nên các đơn vị cơ sở mà có thể chuyển đổi thành những
Truy vấn viết trong ngôn ngữ bậc cao
Dạng biểu diễn bên trong
Scanning, parsing,
validating
Query Optimiser
Runtime Database
Processor
Query Code
Generator
Phương án thực hiện
Chương trình thực hiện truy vấn
Kết quả của truy vấn
Hình 1.1 Các bước điển hình khi xử lý một truy vấn bậc cao 6
phép toán đại số và đƣợc tối ƣu. Một khối truy vấn chứa một biểu thức
SELECT – FROM – WHERE đơn và có thể có các mệnh đề Group by và
Having nếu chúng là một phần của biểu thức. Vì vậy các truy vấn đƣợc lồng
bên trong một truy vấn đƣợc xác định nhƣ các khối truy vấn riêng rẽ. [6]
Xét các quan hệ sau: EMPLOYEE, DEPARTMENT, WORKS-ON và
PROJECT.
PNAME
PNUMBER
PLOCATION
DNUM
WORKS-ON
ESSN
PNO
HOURS
Bảng 1.1 Các quan hệ Trong đó:
Quan hệ EMPLOYEE chứa thuộc tính của các nhân viên:
FNAME: tên của các nhân viên
LNAME: họ và tên đệm của nhân viên
SSN: mã nhân viên
BDATE: ngày sinh của mỗi nhân viên
ADDESS: địa chỉ của nhân viên
SEX: giới tính của nhân viên
SALARY: mức lƣơng của từng nhân viên
7
DNO: mã số phòng ban mà nhân viên đó làm việc
Quan hệ DEPARTMENT chứa thông tin về các phòng ban:
DNAME: tên của mỗi phòng ban
DNUMBER: mã số của mỗi phòng ban
WHERE SALARY > c
Với c biểu diễn kết quả do khối trong trả lại. Khối trong có thể đƣợc
chuyển thành biểu thức quan hệ mở rộng nhƣ sau:
F
MAX SALARY
(
DNO=5
(EMPLOYEE))
Và khối ngoài đƣợc chuyển sang biểu thức quan hệ nhƣ sau:
LNAME, FNAME
(
SALARY>C
(EMPLOYEE))
Sau đó bộ tối ƣu truy vấn sẽ chọn một phƣơng án thực hiện cho từng
khối. Chú ý rằng trong ví dụ ở trên khối trong chỉ cần thực hiện một lần để
đƣa ra lƣơng lớn nhất, sau đó khối ngoài sử dụng lƣơng lớn nhất này nhƣ là
hằng số c. Truy vấn đó gọi là truy vấn lồng nhau không liên kết. Việc tối ƣu
các truy vấn lồng nhau liên kết sẽ khó khăn hơn nhiều. [1, 5]
1.2 Các thuật toán cơ bản thực hiện phép toán truy vấn
Một hệ quản trị cơ sở dữ liệu (RDBMS) phải có các thuật toán để thực
hiện các kiểu phép toán quan hệ khác nhau có thể xuất hiện trong một chiến
lƣợc thực hiện truy vấn. Các phép toán bao gồm phép toán đại số quan hệ cơ
bản và mở rộng, hoặc là tổ hợp các phép toán này. Với mỗi phép toán (hoặc
một tổ hợp phép toán) nhƣ thế, thƣờng phải có sẵn một hoặc nhiều thuật toán
để thực hiện nó. [1, 5, 6, 8]
1.2.1 Sắp xếp ngoài
Sắp xếp là một trong các thuật toán cơ bản đƣợc sử dụng trong xử lý
truy vấn. Ví dụ, khi một truy vấn SQL chỉ ra một mệnh đề Order by, kết quả
=(b/n
B
) hoặc 205 run ban đầu. Mỗi run có cỡ 5 khối
(ngoại trừ run cuối cùng sẽ có 4 khối). Vì vậy, sau pha sắp xếp, 205 run đƣợc
sắp xếp nhƣ là một file con trên đĩa. [1,6]
set i 1;
j b;
k N ;
m (j/k);
while (i <= m)
do {
read next k blocks of the file into the buffer or if
there are less than k blocks remaining, then read in
the remaining blocks;
10
sort the records in the buffer and write as a
temporary subfile;
i i + 1 ;
}
set i 1 ;
p log
k-1
m;
j m;
while (j <=p )
do { n 1 ;
q j/(k-1);
while (n <= q )
do {
11
run ở cuối đoạn đầu tiên. Sau đó chƣơng trình trộn thành 13 run, tiếp đó thành
4 run và sau đó thành 1 file. Điều đó nghĩa là cần 4 pass. Cực tiểu d
M
của 2
cho thực hiện tồi nhất của thuật toán, đó là: (2*b)+(2*(b*(log
2
b))). Số hạng
đầu tiên biểu diễn số các khối truy cập đối với giai đoạn sắp xếp, bởi vì mỗi
khối đƣợc truy cập hai lần, một lần để đọc vào bộ nhớ và một lần để ghi các
bản ghi trở lại đĩa sau khi đã sắp xếp. Số hạng thứ hai biểu diễn số các khối
truy cập đối với giai đoạn trộn, với giả thiết trƣờng hợp xấu nhất d
M
của 2.
Nói chung, log lấy cơ số d
M
và biểu thức đối với số khối truy cập trở thành:
(2*b)+(2*(b*(log
d
M
b)))
1.2.2 Thực thi phép chọn (SELECT) [6, 8]
Có rất nhiều lựa chọn cho việc thực thi một phép toán SELECT. Trong
phần này, trình bầy một số thuật toán để thực thi phép SELECT. Để minh
hoạ, sử dụng các phép toán sau đƣợc chỉ ra trong cơ sở dữ liệu quan hệ của
bảng 1.1 ở trang 7
(OP1):
SSN=‟123456789‟
(EMPLOYEE)
(OP2):
S4: Sử dụng một chỉ số sơ cấp để lấy ra nhiều bản ghi: Nếu điều kiện
so sánh là >, >=, <, <= trên trƣờng khoá. Ví dụ: trong OP2 với file
DEPARTMENT lấy ra những bản ghi có DNUMBER>5 thì sử dụng chỉ số để
tìm bản ghi thoả mãn điều kiện bằng tƣơng ứng (DNUMBER=5), sau đó lấy
ra tất cả các bản ghi tiếp theo bản ghi đó trong một file đƣợc sắp xếp. Còn với
điều kiện DNUMBER<5, thì lấy ra tất cả các bản ghi đi trƣớc.
S5: Sử dụng một chỉ số nhóm để lấy ra nhiều bản ghi: Nếu điều kiện
chọn đòi hỏi một phép so sánh bằng trên thuộc tính không phải là khoá. Ví
dụ: DNO=5 trong OP3, hãy sử dụng chỉ số đó để lấy ra tất cả các bản ghi thoả
mãn điều kiện.
S6: Sử dụng chỉ số thứ cấp (B
+
-tree) trên một phép so sánh bằng:
Phƣơng pháp này có thể đƣợc sử dụng để lấy ra một bản ghi đơn nếu trƣờng
chỉ số là một khoá hoặc lấy ra nhiều bản ghi nếu trƣờng chỉ số không phải là
khoá. Phƣơng pháp này cũng có thể sử dụng đối với các phép so sánh liên
quan đến >, >=, <, <=.
Phƣơng pháp S1 áp dụng cho bất kỳ file nào, còn tất cả các phƣơng
pháp khác phụ thuộc vào có đƣờng dẫn truy cập thích hợp trên thuộc tính
đƣợc sử dụng trong điều kiện chọn. Phƣơng thức S4 và S6 có thể đƣợc sử
dụng để lấy ra các bản ghi trong một phạm vi nhất định, ví dụ
30000<=SALARY<=35000. Các truy vấn bao gồm các điều kiện nhƣ thế
đƣợc gọi là các truy vấn vùng.
13
Các phƣơng pháp tìm kiếm cho lựa chọn phức tạp: Nếu điều kiện của
phép SELECT là một điều kiện liên kết, tức là điều kiện đó đƣợc tạo thành từ
nhiều điều kiện đơn, kết nối với nhau bằng toán tử logic liên kết AND nhƣ
OP4, thì DBMS có thể sử dụng các phƣơng pháp sau đây để thực thi.
S7: Phép chọn có điều kiện liên kết sử dụng một chỉ số đơn: nếu một
Khi bộ truy vấn lựa chọn giữa nhiều điều kiện đơn trong điều kiện liên
kết, nó thƣờng xem xét tính lựa chọn của từng điều kiện. Tính lựa chọn (s)
đƣợc định nghĩa là tỉ số giữa số bản ghi thoả mãn điều kiện trên tổng số bản
ghi có trong file (hay quan hệ), và do đó giá trị này nằm giữa 0 và 1, nếu nhƣ
độ chọn lọc là 0 thì không có bản ghi nào thỏa mãn điều kiện và là 1 nếu tất
cả các bản ghi đều thoả mãn điều kiện. Mặc dù độ chọn lọc chính xác của tất
cả các điều kiện có thể không sẵn có, sự ƣớc lƣợng của độ chọn lọc đƣợc giữ
trong danh mục DBMS và đƣợc sử dụng bởi bộ lọc. Ví dụ, với điều kiện bằng
trên thuộc tính khoá của quan hệ r(R), s=1/|r(R)| với |r(R)| là bản ghi trong
quan hệ r(R). Với một điều kiện bằng trên thuộc tính có các giá trị phân biệt i,
s đƣợc ƣớc lƣợng bởi (|r(R)|/i)/(|r(R)|) hoặc l/i, giả sử các bản ghi đó đƣợc
phân bổ đều giữa các giá trị phân biệt. Cùng với giả thiết này, |r(R)|/i bản ghi
sẽ thoả mãn một điều kiện bằng trên thuộc tính này. Tổng quát, số các bản ghi
thoả mãn một điều kiện lựa chọn với độ chọn lọc s đƣợc ƣớc lƣợng là
|r(R)|)*s. Ƣớc lƣợng càng nhỏ thì độ thoả dụng càng cao.
So sánh phép chọn có điều kiện đơn và điều kiện liên kết (AND), hoặc
điều kiện tách rời (OR) (các điều kiện đơn giản đƣợc nối với nhau bởi toán tử
kết nối logic OR hoặc AND) thì phép chọn có điều kiện tách khó xử lý và tối
ƣu hơn. Ví dụ, xét OP4‟:
(OP4‟):
(DNO=5)
OR (SALARY>3000) OR (SEX=‟F‟)
(EMPLOYEE)
Với một điều kiện nhƣ vậy thì một phép tối ƣu ít có thể đƣợc thực hiện
bởi vì tất cả các bản ghi thoả mãn điều kiện là hợp của các bản ghi thoả mãn
các điều kiện riêng lẻ. Do đó, nếu bất kỳ một điều kiện nào không có một
đƣờng dẫn truy nhập thì chúng ta buộc phải sử dụng cách tìm kiếm tuyến tính.
Nếu đƣờng dẫn truy nhập tồn tại trên từng điều kiện thì tối ƣu hoá lựa chọn
bằng cách lấy ra những bản ghi hoặc địa chỉ bản ghi thoả mãn điều kiện, và
trong 2 thuộc tính nối, ví dụ là B của S, lấy ra từng bản ghi t trong R, tại một
thời điểm chỉ lấy ra 1 bản ghi (vòng lặp đơn), sau đó sử dụng cấu trúc truy
nhập để lấy ra tất cả các bản ghi tƣơng xứng s từ S thoả s[B]=t[A] một cách
trực tiếp.
J3. Sắp xếp trộn: Nếu các bản ghi của R và S đƣợc sắp xếp một cách
vật lý (có thứ tự) bởi giá trị của các thuộc tính nối A và B một cách riêng biệt,
khi đó có thể thực thi phép nối một hiệu quả. Cả 2 file đƣợc quét đồng thời
16
theo thứ tự của các thuộc tính nối và đối chiếu các bản ghi có cùng giá trị với
A và B. Nếu các file không đƣợc sắp xếp thì trƣớc tiên chúng đƣợc sắp xếp
bằng cách sử dụng các thuật toán sắp xếp ngoài. Trong phƣơng pháp này, các
cặp của các khối file đƣợc sao chép vào trong bộ đệm theo thứ tự và các bản
ghi của từng file đó chỉ đƣợc quét một lần để đối chiếu với file khác trừ khi cả
A và B không là các thuộc tính khoá, trong trƣờng hợp này thì phƣơng pháp
cần phải đƣợc sửa đổi phù hợp. Phác hoạ của thuật toán sắp xếp trộn đƣợc
đƣa ra trong hình 1.3(a). R(i) đƣợc sử dụng để chỉ bản ghi thứ i trong R. Sự
khác nhau của sắp xếp trộn khi sử dụng các chỉ số thứ cấp tồn tại trên cả 2
thuộc tính nối. Các chỉ số cung cấp khả năng quét các bản ghi theo thứ tự của
các thuộc tính nối, nhƣng bản thân các bản ghi lại nằm rải rác trên toàn bộ các
khối file, vì vậy phƣơng pháp này tỏ ra khá kém hiệu quả, bởi vì truy nhập
vào các bản ghi có thể bao hàm việc truy cập đến một khối đĩa khác.
(a) sort the tuples in R on attribute A; (assume R has n tuples (records))
sort the tuples in S on attribute B; (assume S has m tuples (records))
set i 1, j 1;
while ( i
set l l + 1
}
17
(* output other tuples that match S(i),if any*)
set k i + 1;
while( k
n) and (R(k)
A
= S(j)
B
do { output the combined tuple < R(k), S (j)> to T;
set k k + 1
}
set i k, j l
}
}
(b) create a tuple t [ <attribute list>] in T‟ for each tuple t in R;
(* T‟ contains the projection result before duplicate elimination*)
if <attribute list> includes a key of R then T T‟
else { sort the tuples in T‟;
set i 1, j 2;
while i n do
{ output the tuple T‟(i) to T;
while T‟[i] = T‟[j] and j
(c). sort the tuples in R and S using the same unique sort attribules;
set i 1, j 1;
while( i <= n) and(j <= m)
do { if R(i) > S(j) then { output S(j) to T;
set j j+1;
}
elseif R(i) < S(j) then { output R(i) to T;
set i i+1
}
else set j j+1;
}
if (i <= n) then add tuples R(i) to R(n) to T;
if (j <= m) then add tuples s(J) to S(m) to T;
(d) sort the tuples in R and R using the same unique sort attribules;
set i 1; j 1;
while( i <= n) and (j <= m)
do { if R (i)>S(j) then set j <- j+1
elseif R(i) < S(j) then set i<-i+1
else { output R(i) to T;
Set i i+1,j j+1
}
}
(e). Sort the tuples in R and S using the same unique sort attribules;
Set i 1, j 1;
While ( i <= n) and (j <= m)
19
Do { if R(i)>S(j) then set j j + 1
elseif R(i) < S(j) then { output R(i) to T
đƣợc đọc 1 lần cho mỗi lần lặp ứng với (n
B
-2) khối của file EMPLOYEE. Kết
quả là thu đƣợc công thức sau [6]:
Tổng số lần truy cập khối cho file ngoài = b
E
Số lần truy cập của (n
B
-2) khối đối với vòng lặp ngoài = (b
E
/(n
B
-2)
Tổng số lần truy cập khối cho file trong là = b
D
*(b
E
/(n
B
-2)
Do đó tổng số các lần truy cập khối đƣợc tính theo công thức sau:
b
E
+ ((b
E
/(n
B
-2)*b
D
EMPLOYEE cho nhà quản lý của từng phòng ban đó. Ở đây, mỗi bản ghi
DEPARTMENT (có 50 bản ghi) đƣợc chờ để nối với từng bản ghi đơn
EMPLOYEE, nhƣng rất nhiều bản ghi EMPLOYEE (4950 bản ghi không
phải là ngƣời quản lý phòng ban) sẽ không đƣợc nối.
Giả sử rằng các chỉ số thứ cấp tồn tại trên các thuộc tính SSN của
EMPLOYEE và MGRSSN của DEPARTMENT với số mức chỉ số x
SSN
=4 và
x
MGRSSN
=2.
Khi đó có 2 lựa chọn để thực hiện phƣơng pháp J2. Đầu tiên là việc lấy
ra từng bản ghi EMPLOYEE và sử dụng chỉ số trên MGRSSN của
DEPARTMENT để thìm ra các bản ghi trong DEPARTMENT tƣơng xứng.
Trong trƣờng hợp này, không có bản ghi nào tƣơng xứng đƣợc tìm thấy cho
các nhân viên không quản lý một phòng ban nào cả.
Số lần truy cập khối cho trƣờng hợp này xấp xỉ:
b
E
+ (r
E
*(x
MGRSSN
+1))=2000 + (5000*3) = 17000 lần truy cập khối
21
Lựa chọn thứ 2 là lấy ra từng bản ghi DEPARTMENT và sau đó sử
dụng chỉ số trên SSN của EMPLOYEE để tìm ra bản ghi EMPOYEE quản lý
tƣơng xứng. Trong trƣờng hợp này, mỗi bản ghi DEPARTMENT sẽ cho một
bản ghi EMPOYEE tƣơng xứng. Số lần truy cập khối cho trƣờng hợp này xấp
+ b
D
+ b
E
log
2
b
E
+ b
D
log
2
b
D
).
1.2.4 Thực thi phép chiếu và các phép toán tập hợp
Một phép chiếu
<danh sách thuộc tính>
(R) dễ thực thi nếu <danh sách thuộc
tính> bao gồm một khoá của quan hệ R, bởi vì trong trƣờng hợp này kết quả
của thao tác sẽ có số bản ghi cùng số bản ghi của R nhƣng chỉ có các giá trị
trong <danh sách thuộc tính>. Nếu <danh sách thuộc tính> không chứa một
khoá của R, các bộ giá trị trùng lặp phải đƣợc loại trừ. Việc này thông thƣờng
đƣợc thực hiện bằng việc sắp xếp kết quả của phép toán và sau đó loại trừ các
bộ giá trị trùng lặp xuất hiện liên tiếp sau khi sắp xếp. Một phác hoạ của thuật
toán đƣợc đƣa ra trong hình 1.3(b). Việc băm có thể cũng đƣợc sử dụng để
22
loại trừ trùng lặp: bởi từng bản ghi đƣợc băm và chèn vào một khối của file
băm trong bộ nhớ, file băm đƣợc kiểm tra lại xem bản ghi đã có trong vùng
và sau đó băm các bản ghi của S, nhƣng chỉ chèn các bản ghi giống nhau vào
trong bộ nhớ. Để thực thi R S, đầu tiên phân mảnh các bản ghi của R vào
trong một file băm. Sau đó, trong khi băm từng bản ghi của S, thăm dò và
kiểm tra nếu chính bản ghi từ S đƣợc tìm thấy trong vùng nhớ thì thêm bản
ghi đó vào file kết quả. Để thực thi R – S, đầu tiên băm các bản ghi của R vào
trong vùng nhớ. Trong khi băm từng bản ghi của S, nếu đúng bản ghi đó tìm
thấy trong vùng nhớ thì xoá bản ghi khỏi vùng nhớ.
1.2.5 Thực thi các phép toán kết hợp
Các phép toán kết hợp (MIN, MAX, COUNT, AVERAGE, SUM) khi
áp dụng vào bảng thì có thể đƣợc thực hiện bởi một lần quét bảng hoặc bằng
việc sử dụng một chỉ số thích hợp nếu có. Ví dụ xét truy vấn sau:
SELECT MAX(SALARY)
FROM EMPLOYEE;
Nếu một chỉ số (tăng dần) trên SALARY tồn tại cho quan hệ
EMPLOYEE thì bộ tối ƣu có thể chọn việc sử dụng chỉ số để tìm kiếm giá trị
lớn nhất theo con trỏ phải nhất. Nút đó chứa giá trị lƣơng lớn nhất. Trong hầu
hết các trƣờng hợp, cách này có hiệu quả hơn so với việc quét toàn bộ bảng
của EMPLOYEE, bởi không có bản ghi chính xác đƣợc lấy ra. Phép toán
MIN thực hiện tƣơng tự, và con trỏ trái nhất đƣợc lấy ra. Nút đó chứa giá trị
lƣơng nhỏ nhất.
Khi mệnh đề GROUP BY đƣợc sử dụng trong truy vấn, phép toán kết
hợp phải đƣợc áp dụng cho từng nhóm của các bộ giá trị. Do đó, bảng đầu
tiên phải đƣợc phân mảnh thành các tập con các bộ giá trị, ở đó mỗi mảnh có
cùng giá trị đối với các thuộc tính nhóm. Trong trƣờng hợp này việc tính toán
trở nên phức tạp hơn. Xét truy vấn sau:
SELECT DNO, AVR(SALARY)
FROM EMPLOYEE
GROUP BY DNO;
24
Copyright: Tài liệu đại học ©