TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
CẢI TIẾN THUẬT TOÁN CẬP NHẬT GIA TĂNG CÁC KHUNG NHÌN THỰC KIỂU SPJ
IMPROVEMENT OF THE INCREMENTAL ACTUALIZATION ALGORITHM FOR THE SPJ MATERIALIZED VIEWS
Nguyễn Trần Quốc Vinh Trường Đại học Kinh tế, Đại học Đà Nẵng
TÓM TẮT
Khung nhìn thực (materialized view, KNT) kiểu Select-Project-Join (SPJ) là KNT dựa trên truy vấn chỉ chứa các phép chọn, chiếu và nối, không bao gồm các phép toán thống kê như SUM, COUNT, AVG, MIN, MAX... Kết quả thực thi nó có thể chứa các bản ghi trùng lặp. Có thể nói rằng, thuật toán cập nhật gia tăng sử dụng số đếm số lần lặp lại của các bản ghi trong KNT là hiệu quả nhất đối với các KNT kiểu SPJ. Bài viết trình bày cải tiến trong cách tính số đếm và đề nghị thuật toán cập nhật gia tăng các KNT kiểu SPJ có sử dụng cách tính số đếm đã được cải tiến.
ABSTRACT
The SPJ (Select-Project-Join) materialized views are the materialized views based on the queries that contain only the operations : selection, projection and join, excluding the aggregate functions such as SUM, COUNT, AVG, MIN, MAX... The result of their execution can contain duplicated records. It should be noted that the incremental update algorithm using the counter of the duplication of the records is the most effective on the SPJ materialized views. In this paper the improvement of a method for calculating that counter is presented and an algorithm for incremental updates of the SPJ materialized views with improved counter calculation is also suggested.
1. Đặt vấn đề
Có nhiều thuật toán khác nhau được phát triển để thực hiện cập nhật gia tăng (CNGT) các KNT nói chung và KNT kiểu SPJ nói riêng. Trong đó, n hiều công trình đã công bố [1–5] nghiên cứu thuật toán cập nhật các KNT kiểu SPJ sử dụng số đếm (counter) số lần lặp lại của các bản ghi trong KNT. Từ các công trình này có thể thấy rằng, thuật toán sử dụng số đếm là hiệu quả nhất đối với CNGT các KNT kiểu SPJ. Trong thuật toán đó, số đếm được lưu trong bản ghi của KNT như là một trường riêng biệt. Số đếm sẽ được tăng (giảm) một đơn vị tương ứng với mỗi bản ghi trùng khớp được thêm mới vào (xoá từ) KNT. Qua nghiên cứu các thuật toán đã được công bố, tác giả nhận thấy có thể cải tiến thuật toán đó để nâng cao hiệu quả của nó trong một số trường hợp.
KNT kiểu SPJ 2.
50
KNT – kết quả thực thi của các truy vấn được giữ lại trong các bảng riêng biệt , được tạo ra với ý tưởng ban đầu là một công cụ hỗ trợ cho các kho dữ liệu và các hệ thống hỗ trợ ra quyết định. Tuy nhiên, nó có thể được ứng dụng cho bất kỳ CSDL nào.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
=
=
Z
Z
(
F C T ,
,
)
KNT chỉ được triển khai thực tế cách đây không lâu trong các phiên bản cuối cùng của ba HQT CSDL thương mại Oracle, MS SQL Server và IBM DB2. Thực tế, mỗi hệ quản trị cơ sở dữ liệu có hỗ trợ KNT có thể có các ràng buộc về cấu trúc của truy vấn chọn lựa dữ liệu để tạo KNT [6, 7]. Nhưng về mặt lý thuyết, có thể tạo KNT trên cơ sở bất kỳ truy vấn nào, kể cả truy vấn phức tạp nhất với đầy đủ các thành phần cấu trúc và hàm cho phép trong cấu trúc của một truy vấn SELECT. KNT kiểu SPJ là KNT được tạo ra trên cơ sở truy vấn SPJ – truy vấn chỉ chứa các phép chọn, chiếu và nối; kết quả thực thi các truy vấn có thể chứa các bản ghi trùng lặp, nhưng không bao Truy vấn tạo KNT gồm các phép toán thống kê (SUM, COUNT, AVG, MIN, MAX…). kiểu SPJ thứ j có thể được biểu diễn như sau:
mv
j
j
j
j
=
.
F
F
∪ – tập hợp các trường của KNT thứ j;
j
C j
S
jF – tập hợp các trường lựa chọn của truy vấn thứ j;
jC – câu điều kiện lựa chọn WHERE;
C
jF – tập hợp các trường từ câu điều kiện lựa chọn WHERE
jC ;
=
=
F Với S j
T
N
1, 2,..
}
T j
T k { j k
j .
– tập hợp các bảng gốc (base tables, BG) được sử dụng
jZ
del
ins
trong
kjT ) – tập hợp các bản ghi (từ đây về sau, tập hợp các bản ghi có nghĩa là
Ngoài ra, ta sẽ sử dụng một số ký hiệu sau đây: kjT (
kjT ;
del
ins
kjT (
kjT );
(
)
T<
> ) – bản ghi của KNT tương ứng với bản ghi được
j
j
ins j k
del j k
kjT > (< del < ins kjT >) – một bản ghi trong tập > ( T< F ) ( F thêm mới (xoá từ) BG.
tập có thể chứa các phần tử trùng lặp) được thêm vào (xoá từ) BG
Cứ mỗi khi dữ liệu trong các BG được cập nhật, các KNT sử dụng các dữ liệu đó trở nên không thực tiễn. Để duy trì các bảng KNT trong trạng thái thực tiễn (actual state), cần phải cập nhật chúng mỗi khi có sự thay đổi dữ liệu (insert, update, delete) trong các BG. Quá trình làm cho dữ liệu trong KNT tương ứng với dữ liệu trong các BG được gọi là sự thực tiễn hoá (actualization, cập nhật).
51
Tuỳ thuộc vào cách thức thực hiện, cập nhật được chia thành ba phương pháp chính, đó là cập nhật hoàn toàn (COMPLETE), cập nhật gia tăng (INCREMENTAL hay còn gọi là FAST) và ép buộc (FORCE) [8]. Cập nhật hoàn toàn thực tế là thực thi lại truy vấn trên cơ sở KNT đã được tạo ra và lưu kết quả vào KNT . CNGT chỉ thực hiện điều chỉnh phần dữ liệu trong KNT liên quan đến các sửa đổi dữ liệu trong các BG. Cập nhật ép buộc nghĩa là khi có khả năng thì thực hiện CNGT, còn nếu không thì sử dụng cập nhật hoàn toàn. Trong hầu hết các trường hợp có thể thực hiện CNGT đối với các KNT kiểu SPJ.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
Cải tiến thuật toán CNGT KNT kiểu SPJ bằng cách sử dụng số đếm 3.
3.1. Cải tiến cách tính số đếm
ins
del
Đề nghị sử dụng cách thức sau đây để tính các truy vấn SQL tính các tập hợp
jZ vào (hoặc xoá
jZ từ) KNT trong quá trình CNGT.
ins
ins
kjT
kjT
bản ghi cần phải thêm mới
del
>
>
F
(
T<
)
F
(
T<
)
j
j
> trong tập hợp các bản ghi được thêm vào (tương tự
kjT
ins j k
del j k
ins
=
<
>
Cho mỗi bản ghi < del kjT ) kiểm tra xem bản ghi > và (
CNT
))
T
(
(
j
ins j k
del
=
<
>
CNT
COUNT F
T
(
(
))
j
kjT
del j k
cho trường hợp xoá, < ) có mặt trong KNT hay không. Nếu có, thì tính giá trị CNT – số lần lặp lại của một bản ghi COUNT F trong KNT. Tiếp theo, tính số cho trường hợp thêm mới và
cho trường h ợp xo á từ BG . Nếu hai bản ghi của BG
mod(
= và ) 0
mod(
del
ins
CNT CNT
< kjT > có mặt trong KNT và giá trị các trường của chúng có mặt trong KNT trùng nhau, thì các số lượng lặp lại của chúng trong KNT giống nhau . Khẳng định này được suy ra = . Từ đó từ định nghĩa của phép nối JOIN. Theo đó, ) 0
CNT CNT CNT ins CNT
<
suy ra, có thể tăng (giảm) số đếm trong KNT thêm một giá trị bằng (xuống một
<
> và loại bỏ
T
> < (
T
> )
T
T
> < (
)
ins j k
del j k
ins j k
del j k
ins
kjT
giá trị ) tương ứng với mỗi bản ghi
CNT del CNT del kjT
del
ins
). ( từ
kjT (
trong tập hợp
Việc thực hiện phép nối chiếm tỉ trọng lớn về mặt chi phí tài nguyên của hệ thống trong thực thi truy vấn. Cải tiến này cho phép giảm đáng kể số lượng các bản ghi kjT ) cần phải thực hiện thuật toán CNGT thông thường – dựa trên việc thực thi phép nối. Qua đó nâng cao hiệu quả thực hiện CNGT các KNT. Tuy nhiên, kjT lớn hơn tích các số lượng bản ghi của các BG còn nếu số lượng các bản ghi của BG
lại, thì cải tiến này có thể sẽ không hiệu quả.
Sau đây, bài viết đề nghị thuật toán CNGT các KNT kiểu SPJ có sử dụng cải tiến
trong cách tính số đếm vừa được trình bày.
3.2. Thuật toán CNGT các KNT kiểu SPJ
Chúng ta xét riêng rẽ ba trường hợp thêm mới, sửa đổi và xoá các bản ghi. Việc sửa đổi một bản ghi có thể xem là tương đương với nhóm hai hành động liên tiếp: xoá một bản ghi và sau đó thêm mới một bản ghi.
kiT , tương ứng với lệnh
kiT được thêm vào BG
ins
3.2.1. Trường hợp thêm mới các bản ghi ins Giả sử tập h ợp các b ản gh i
kiT .
kiT INTO
52
INSERT
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
Nhìn chung, các thuật toán đã được công bố tập trung tính tập hợp các bản ghi
ins
=
∪
Z
(
F
CNT {
},
)
được thêm mới – tương đương với truy vấn:
ins j
j
C T , j
j
=
T
,...,
T
,...,
T
)
,
TN – số BG.
j
j
T T ( , j 1
j 2
ins j k
TN
với và
jT , ta sử dụng cách tính số đếm cải tiến để
ins
ins
Thay vì thực hiện phép nối các bảng
jZ , kiểm tra sự có mặt của bản ghi
tính CNT . Sau đó, với mỗi bản ghi trong tập
ins
=
+
dạng < jF > trong KNT. Nếu có thì thực hiện truy vấn có dạng:
CNT CNT CNT
jF
UPDATE KNT SET WHERE = < jF >.
Trong trường hợp ngược lại, thực thi truy vấn:
jF ∪ >). {1}
INSERT INTO KNT VALUES (<
del
3.2.2. Trường hợp xoá các bản ghi
kiT , tương ứng với lệnh:
kjT được xoá từ BG
del
Giả sử tập h ợp các bản gh i
kjT .
kjT FROM
DELETE
del
=
∪
Z
(
F
CNT {
},
)
Tính tập hợp các bản ghi được xoá:
del j
j
C T , j
j
=
,...,
,...,
)
T
T
T
,
j
j
( , T T j 1
j 2
del j k
TN
với .
jT , ta sử dụng cách tính số đếm cải tiến để
del
del
Thay vì thực hiện phép nối các bảng
CNT . Sau đó, với mỗi bản ghi từ tập hợp
jZ , kiểm tra sự có mặt của bản chi
tính
del
dạng < jF > trong KNT. Nếu có, thì xét hai trường hợp sau đây:
> CNT CNT
del
=
−
– Nếu đối với bản ghi < jF >, thì thực thi truy vấn có dạng:
> ;
CNT CNT CNT
F i
F= < i
del
<=
UPDATE KNT SET WHERE
CNT
CNT
– Nếu đối với bản ghi < jF >, thì thực thi truy vấn có dạng:
jF = < jF >;
DELETE FROM KNT WHERE
Ngược lại, nếu không có bản ghi dạng < jF > trong KNT, thì không cần thực hiện
hành động nào cả.
old
new
3.2.3. Trường hợp sửa đổi các bản ghi
kiT , tập hợp các bản ghi
kiT được thay đổi thành tập hợp
kiT
Giả sử trong BG ,
tương ứng với truy vấn:
kiT SET
old T i k
new T= i k
53
UPDATE .
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
new
ins
tương ứng. Trong đó, mỗi và mục 3.2.1 để CNGT KNT, với
T= i k
T i k
del T i k
Dễ nhận thấy rằng, sửa đổi một bản ghi tương đương với xoá bỏ một bản ghi sau đó thêm mới một bản ghi khác. Đối với trường hợp tập hợp, cập nhật một tập hợp các bản ghi tương đương với xoá bỏ một tập hợp bản ghi, sau đó thêm mới một tập hợp bản ghi khác. Suy ra, trong trường hợp này có thể thực thi mục 3.2.2 và tiếp theo sau đó là old T= i k
kiT > tương ứng với một bản ghi < new
kiT
bản ghi < old >.
thoả mãn điều kiện chọn lựa Bởi vì những bản ghi được thêm mới (xoá khỏi) BG có giá trị các trường không jC chắc chắn sẽ không được thêm (xoá) khỏi KNT, nên
kjT > và < del
del
jC (< ins
kjT >)=false, thì loại bỏ bản ghi < del
kjT > từ
ins
jC (< del bản ghi < ins
kjT > từ
đối với mỗi bản ghi < ins
kjT > cần phải kiểm tra hai trường hợp sau đây. Nếu kjT >)=false, thì loại bỏ kjT , nếu kjT . Cải tiến này giảm số lượng các bản ghi cần phải xét thông qua jC và theo đó đơn
việc loại bỏ các bản ghi không thoả mãn một cách rõ ràng điều kiện
giản hoá quá trình thực thi phép nối.
iF (< old
kjT > và < new
kjT
kjT >) =
> thoả mãn điều kiện Nếu các bản ghi có dạng < old
kjT
old
>), thì không cần thực hiện thay đổi nào cả. Vì xoá một bản ghi, sau đó thêm
jF (< new mới một bản ghi hoàn toàn trùng khớp với bản ghi vừa xoá tương đương với việc không thực hiện thay đổi nào cả. Ta có thể loại bỏ cặp < old
kjT
new
> này khỏi và
kjT
kjT > và < new kjT
kjT kjT > và < new
del
ins
. Ngược lại, cần phải giữ lại các bản ghi có dạng < old > thoả mãn điều
jF (< old
jF (< new
kjT và
kjT >) #
kjT
kjT
kiện >). Kết quả của quá trình đó là tập hợp tối
thiểu.
del
ins
kjT bị xoá từ BG và tập hợp các bản ghi
kjT được thêm mới vào BG tương ứng.
old
new
Và bây giờ có thể thực thi các trường hợp 3.2.2 và 3.2.1 cho tập hợp các bản ghi
kjT
kjT
ins
del
ins
del
Ta cũng có thể thay thế việc giản lược bằng cách sau. Khi đã tính và
jZ và
jZ >, thì
jZ , so sánh ins
jZ và del
ins
ins
del
ins
del
=
−
jZ > = < ins −
jZ theo từng bản ghi. Nếu < del
CNT
del CNT và
CNT
ins
del
ins
CNT del
CNT CNT . Tương ứng,
CNT = 0 khi
CNT CNT <
CNT > del CNT = 0 và
CNT .
= CNT ins CNT =
S
khi khi
lựa chọn Không thể sử dụng thuật toán này các KNT được tạo trên cơ sở các truy vấn có thống kê, bởi vì đối với các KNT đó, mỗi một bản ghi KNT tương ứng với một tập hợp jT ), trong khi KNT chỉ chứa mỗi bản ghi bao gồm các trường bản ghi từ phép nối JOIN( S jF
jF . Ta không thể đồng thời lưu các các giá trị của các trường chọn lựa jF > tương ứng với nhiều < C
C jF
54
và điều kiện chọn lựa trong một bản ghi, vì mỗi < S jF >.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
4. Kết luận
Thông qua nghiên cứu vấn đề, có thể kết luận:
Thuật toán cập nhật gia tăng sử dụng số đếm số lần lặp lại của các bản ghi trong
KNT là hiệu quả nhất đối với các KNT kiểu SPJ.
Bài viết trình bày cải tiến trong cách tính số đếm và đề nghị thuật toán cập nhật gia tăng các KNT kiểu SPJ có sử dụng cách tính số đếm đã được cải tiến. Các cải tiến mang lại hiệu quả cao đặc biệt trong trường hợp số lượng bản ghi trong BG có dữ liệu thay đổi nhỏ hơn nhiều so với tích của số lượng bản ghi của các BG còn lại trong truy vấn. Sự chênh lệch đó càng lớn thì sự cải tiến càng có hiệu quả. Thuật toán được đề nghị tương đối đơn giản so với các thuật toán đã được đề cập để triển khai trong thực tiễn.
TÀI LIỆU THAM KHẢO
[1] Shmueli O. Maintenance of views. SIGMOD record. 1984. – 14. – tr. 240-255.
. http://portal.acm.org/citation.cfm?id=602293
[2] Blakeley A. J, Larson P., Tompa F.W. Efficiently Updating Materialized Views. http://portal.acm.org/citation.cfm? tr. 61-71.
ACM SIGMOD. 1986. – . id=16894.16861
tr. 157-167. [3] Gupta A., Mumick I. S., Subrahmanian V. S. Maintaining Views Incrementally. In citation.cfm? http://portal.acm.org/
. SIGMOD. 1993. – id=170036.170066
[4] Gupta A., Mumick I.S. Maintenance of materialized views: Problems, Techniques http://www.informatik.uni-trier.de/~ley/db/
and Applications. . journals/debu/GuptaM95.html
[5] Gupta D.K., Mumick I.S. Counting solutions to the view maintenance problem. http://www.tempo.att Laboratories. 1992. rep. AT&T Bell
Tech. . .com/~jeannie/dept/pspapers/att-db-92-8.ps.Z
http://msdn.microsoft.com/en-us/library/ms191432 [6] SQL Server 2005 manual.
(SQL.90).aspx . 15/12/2008.
http://download.oracle.com/docs/cd/B28359_01/server. [7] Oracle
. 17/01/2009. 11g manual. 111/b28286/statements_6002.htm
55
[8] Thomas Kyte. Expert one-on-one Oracle. Apress, 2003.
