Khung nhìn th (materialized view, KNT) kiểu Select-Project-Join (SPJ) là KNT ựa ực d trên truy v 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ê ấn như SUM, COUNT, AVG, MIN, MAX...
AMBIENT/
Chủ đề:
Nội dung Text: Báo cáo khoa học: "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"
- 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 (materialized view, KNT) kiểu Select-Project-Join (SPJ) là KNT ựa
ực d
trên truy v 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ê
ấn
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.
2. KNT kiểu SPJ
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.
50
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
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 Oracle, MS SQL Server và IBM DB2. Thực tế,
ại
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
gồm các phép toán thống kê (SUM, COUNT, AVG, MIN, MAX…). Truy vấn tạo KNT
kiểu SPJ thứ j có thể được biểu diễn như sau:
==
Z mv Z j ( Fj , C j , T j ) .
Fj FjS ∪ FjC – tập hợp các trường của KNT thứ j;
=
Với
FjS – tập hợp các trường lựa chọn của truy vấn thứ j;
C j – câu điều kiện lựa chọn WHERE;
FjC – tập hợp các trường từ câu điều kiện lựa chọn WHERE C j ;
= {T jk k 1, 2,.. N T } – tập hợp các bảng gốc (base tables, BG) được sử dụng
Tj = j
trong Z j .
Ngoài ra, ta sẽ sử dụng một số ký hiệu sau đây:
T jikns ( T jdel ) – 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à
k
tập có thể chứa các phần tử trùng lặp) được thêm vào (xoá từ) BG T j k ;
< T jins > (< T jdel >) – một bản ghi trong tập T jikns ( T jdel );
k k k
Fj (< T jikns >) ( Fj (< T jdel >) ) – bản ghi của KNT tương ứng với bản ghi được
k
thêm mới (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 t iễ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).
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 (FORCE) [8]. Cập nhật hoàn toàn thực tế là thực thi lại
ộc
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.
51
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
3. Cải tiến thuật toán CNGT KNT kiểu SPJ bằng cách sử dụng số đếm
3.1. Cải tiến cách tính số đếm
Đề 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
bản ghi cần phải thêm mới Z ijns vào (hoặc xoá Z del từ) KNT trong quá trình CNGT.
j
T jins T jikns
Cho mỗi bản ghi < > trong tập hợp các bản ghi được thêm vào (tương tự
k
del del
F (< T jins >) Fj (< T jdel >)
T T
cho trường hợp xoá, < ) kiểm tra xem bản ghi j
jk jk
> và ( ) có
k k
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
CNT ins COUNT ( Fj (< T jins >))
=
trong KNT. Tiếp theo, tính số cho trường hợp thêm mới và
k
CNT del COUNT ( Fj (< T jdel >))
= T jk
cho trường h ợp xo á từ BG . Nếu hai bản ghi của BG
k
Tk
< j > 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ừ định nghĩa của phép nối JOIN. Theo đó, mod( CNT ) = 0 và mod( CNT ) = 0 . Từ đó
CNT del
CNT ins
suy ra, có thể tăng (giảm) số đếm trong KNT thêm một giá trị bằng CNT (xuống một
CNT ins
giá trị CNT ) tương ứng với mỗi bản ghi < T jikns > (< T jdel >) và loại bỏ < T jikns > (< T jdel >)
CNT del
k
k
T jikns T jdel
từ ( ).
k
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
trong tập hợp T jikns ( T jdel ) cần phải thực hiện thuật toán CNGT thông thường – dựa trên
k
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,
nếu số lượng các bản ghi của BG T jk lớn hơn tích các số lượng bản ghi của các BG còn
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.
3.2.1. Trường hợp thêm mới các bản ghi
Giả sử tập h ợp các b ản gh i Tikins được thêm vào BG Tik , tương ứng với lệnh
INSERT Tikins INTO Tik .
52
- 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 toán đã được công bố tập trung tính tập hợp các bản ghi
ật
được thêm mới – tương đương với truy vấn:
Z= ( Fj ∪ {CNT ins }, C j , T j ) ,
ins
j
với T j = (T j1 , T j2 ,..., T jins ,..., T j T ) và N T – số BG.
k N
Thay vì thực hiện phép nối các bảng T j , ta sử dụng cách tính số đếm cải tiến để
tính CNT ins . Sau đó, với mỗi bản ghi trong tập Z ijns , kiểm tra sự có mặt của bản ghi
dạng < Fj > trong KNT. Nếu có thì thực hiện truy vấn có dạng:
UPDATE KNT SET CNT CNT + CNT ins WHERE Fj = < Fj >.
=
Trong trường hợp ngược lại, thực thi truy vấn:
INSERT INTO KNT VALUES (< Fj ∪ {1} >).
3.2.2. Trường hợp xoá các bản ghi
Giả sử tập h ợp các bản gh i T jdel được xoá từ BG Tik , tương ứng với lệnh:
k
DELETE T jdel FROM T jk .
k
Tính tập hợp các bản ghi được xoá:
Z= ( Fj ∪ {CNT del }, C j , T j ) ,
del
j
với T j = (T j1 , T j2 ,..., T jdel ,..., T j T ) .
k N
Thay vì thực hiện phép nối các bảng T j , ta sử dụng cách tính số đếm cải tiến để
tính CNT del . Sau đó, với mỗi bản ghi từ tập hợp Z del , kiểm tra sự có mặt của bản chi
j
dạng < Fj > trong KNT. Nếu có, thì xét hai trường hợp sau đây:
– Nếu CNT > CNT del đối với bản ghi < Fj >, thì thực thi truy vấn có dạng:
UPDATE KNT SET CNT CNT − CNT del WHERE Fi = Fi > ;
= <
– Nếu CNT , thì thực thi truy vấn có dạng:
DELETE FROM KNT WHERE Fj = < Fj >;
Ngược lại, nếu không có bản ghi dạng < Fj > trong KNT, thì không cần thực hiện
hành động nào cả.
3.2.3. Trường hợp sửa đổi các bản ghi
Giả sử trong BG Tik , tập hợp các bản ghi Tikold được thay đổi thành tập hợp Tiknew ,
tương ứng với truy vấn:
UPDATE Tik SET Tiold = Ti new .
k k
53
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(36).2010
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à
mục 3.2.1 để CNGT KNT, với Tidel = Tiold và Tikins = Tiknew tương ứng . Trong đó, mỗi
k k
bản ghi < Tik > tương ứng với một bản ghi < Tiknew >.
old
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
thoả mãn điều kiện chọn lựa C j chắc chắn sẽ không được thêm (xoá) khỏi KNT, nên
đối với mỗi bản ghi < T jins > và < T jdel > cần phải kiểm tra hai trường hợp sau đây. Nếu
k k
C j (< T jk >)=false, thì loại bỏ bản ghi < T jk > từ T jk , nếu C j (< T jk >)=false, thì loại bỏ
del del del ins
bản ghi < T jins > từ T jikns . 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
k
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 C j và theo đó đơn
giản hoá quá trình thực thi phép nối.
Nếu các bản ghi có dạng < T jold > và < T jnew > thoả mãn điều kiện Fi (< T jold >) =
k k k
>), thì không cần thực hiện thay đổi nào cả . Vì xoá một bản ghi, sau đó thêm
F j (< T new
jk
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 < T jold > và < T jnew > này kh T jold và
ỏi k
k k
T jnew . Ngược lại, cần phải giữ lại các bản ghi có dạng < T jold > và < T jnew > thoả mãn điều
k k k
kiện F j (< T jold >) # F j (< T jnew >). Kết quả của quá trình đó là tập hợp T jdel và T jikns tối
k k k
thiểu.
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
bị xoá từ BG và tập hợp các bản ghi T jikns được thêm mới vào BG tương ứng.
del
T jk
Ta cũng có thể thay thế việc giản lược T jold và T jnew bằng cách sau. Khi đã tính
k k
Z del và Z ijns , so sánh Z del và Z ijns theo t ng bản ghi. Nếu < Z del > = < Z ins >, thì
ừ
j j j j
CNT ins CNT ins − CNT del khi CNT ins > CNT del
= và CNT del CNT del − CNT ins
= khi
CNT ins < CNT del . Tương ứng, CNT del = 0 và CNT ins = 0 khi CNT ins = CNT del .
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
bản ghi từ phép nối JOIN( T j ), trong khi KNT chỉ chứa mỗi bản ghi bao gồm các trường
lựa chọn F jS . 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 F jS
và điều kiện chọn lựa F jC trong một bản ghi, vì mỗi < F jS > tương ứng với nhiều < F jC >.
54
- 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.
ACM SIGMOD. 1986. – tr. 61-71. http://portal.acm.org/citation.cfm?
id=16894.16861.
[3] Gupta A., Mumick I. S., Subrahmanian V. S. Maintaining Views Incrementally. In
SIGMOD. 1993. – tr. 157-167. http://portal.acm.org/ citation.cfm?
id=170036.170066.
[4] Gupta A., Mumick I.S. Maintenance of materialized views: Problems, Techniques
and Applications. http://www.informatik.uni-trier.de/~ley/db/
journals/debu/GuptaM95.html.
[5] Gupta D.K., Mumick I.S. Counting solutions to the view maintenance problem.
Tech. rep. AT&T Bell Laboratories. 1992. http://www.tempo.att
.com/~jeannie/dept/pspapers/att-db-92-8.ps.Z.
[6] SQL Server 2005 manual. http://msdn.microsoft.com/en-us/library/ms191432
(SQL.90).aspx. 15/12/2008.
[7] Oracle 11g manual. http://download.oracle.com/docs/cd/B28359_01/server.
111/b28286/statements_6002.htm. 17/01/2009.
[8] Thomas Kyte. Expert one-on-one Oracle. Apress, 2003.
55
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
