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

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...
Nội dung trích xuất từ tài liệu:
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 dtrê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ê ấnnhư 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 ghitrong 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ínhsố đế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 thequeries that contain only the operations : selection, projection and join, excluding the aggregatefunctions such as SUM, COUNT, AVG, MIN, MAX... The result of their execution can containduplicated records. It should be noted that the incremental update algorithm using the counter of theduplication of the records is the most effective on the SPJ materialized views. In this paper theimprovement of a method for calculating that counter is presented and an algorithm for incrementalupdates 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ánsử 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ếnthu ậ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ốicùng của ba HQT CSDL thương m Oracle, MS SQL Server và IBM DB2. Thực tế, ạimỗ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ủatruy 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 KNTtrê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ầncấ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 baogồm các phép toán thống kê (SUM, COUNT, AVG, MIN, MAX…). Truy vấn tạo KNTkiể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 = jtrong 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à ktậ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 ...