Tài liệu Xây dựng mô đun sinh tự động mã nguồn trigger trên ngôn ngữ c phục vụ cập nhật gia tăng, đồng bộ các khung nhìn thực với truy vấn lồng cho postgresql

ĐẠI HỌC ĐÀ NẴNG TRƢỜNG ĐẠI HỌC SƢ PHẠM  LÊ THỊ THẢO NGUYÊN XÂY DỰNG MÔ-ĐUN SINH TỰ ĐỘNG MÃ NGUỒN TRIGGER TRÊN NGÔN NGỮ C PHỤC VỤ CẬP NHẬT GIA TĂNG, ĐỒNG BỘ CÁC KHUNG NHÌN THỰC VỚI TRUY VẤN LỒNG CHO POSTGRESQL Chuyên ngành: Hệ thống thông tin Mã số: 8480104 TÓM TẮT LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN Đà Nẵng – Năm 2018 Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC SƯ PHẠM Người hướng dẫn khoa học: TS. Nguyễn Trần Quốc Vinh Phản biện 1: PGS. TS. Nguyễn Thanh Bình Phản biện 2: GS. TS. Nguyễn Thanh Thủy Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ Hệ thống thông tin họp tại Trường Đại học Sư phạm vào ngày 18 tháng 11 năm 2018. Có thể tìm hiểu luận văn tại: Thư viện Trường Đại học Sư phạm – ĐHĐN Khoa Tin Học, Trường Đại học Sư phạm – ĐHĐN 1 LỜI MỞ ĐẦU 1. Lý do chọn đề tài Khung nhìn thực (KNT) là một kỹ thuật giúp cải thiện và nâng cao tốc độ thực thi đối với các truy vấn phức tạp, có tần suất sử dụng cao trên một lượng dữ liệu lớn. Đối với những truy vấn phức tạp bao gồm nhiều phép nối và các hàm thống kê, hiệu quả sử dụng KNT càng rõ rệt, đặc biệt khi áp dụng trên một lượng dữ liệu đủ lớn. Đến nay, kỹ thuật KNT đã được triển khai trên các hệ quản trị cơ sở dữ liệu (HTQCSDL) thương mại lớn như Oracle, Microsoft SQL Server, IBM DB2,… và ngày càng được ứng dụng rộng rãi. PostgreSQL là một HQTCSDL mã nguồn mở hàng đầu trên thế giới, tuy nhiên KNT mới được triển khai trên PostgreSQL ở phiên bản 9.3.4 và chưa hỗ trợ vấn đề cập nhật đồng bộ gia tăng. Thay vào đó, PostgreSQL cập nhật KNT theo cơ chế toàn phần bất đồng bộ, tức là thực thi lại toàn bộ truy vấn dùng để tạo KNT mỗi khi cần cập nhật. Điều này tốn chi phí xấp xỉ chi phí thực hiện truy vấn, và không đảm bảo được dữ liệu trên KNT luôn luôn là mới nhất. Đến phiên bản 10 có bổ sung tính năng cập nhật đồng thời, tuy nhiên tính năng này chỉ hỗ trợ việc truy cập đồng thời đến KNT, nghĩa là cung cấp khả năng truy cập bảng KNT để trả lời truy vấn ngay cả khi nó đang được cập nhật bằng lệnh refresh materialized view, chứ chưa đề cập đến vấn đề CNGT. Cập nhật gia tăng (CNGT) là kỹ thuật cập nhật dữ liệu trên KNT một cách đồng bộ, được thực hiện mỗi khi dữ liệu tại các bảng gốc (BG) tham gia vào KNT có sự thay đổi, nhờ đó giúp cho KNT luôn trong trạng thái được cập nhật. Do vậy, việc nghiên cứu các kỹ thuật CNGT cho KNT trên PostgesSQL đang rất được quan tâm. Việc CNGT KNT có thể được thực hiện thông qua việc xây dựng các trigger bắt các sự kiện làm thay đổi dữ liệu trên các bảng gốc, từ đó tiến hành xác định các thay đổi có thể làm ảnh hưởng đến tính đúng đắn của kết quả được lưu trong KNT, sau đó tiến hành việc cập nhật dữ liệu trong KNT. PostgreSQL hỗ trợ 2 loại trigger là trigger viết bằng ngôn ngữ PL/pgSQL và trigger viết bằng ngôn ngữ C. Đã có nghiên cứu về việc sử dụng trigger mã nguồn PL/pgSQL để CNGT đồng bộ cho KNT trong PostgreSQL [2, 3, 5], nhưng trigger mã nguồn PL/pgSQL được đánh giá là có hiệu năng chưa cao ở hầu hết các xử lý so với trigger trong ngôn ngữ C, trigger trên ngôn ngữ 2 C thực thi nhanh hơn so với trigger trên ngôn ngữ PL/pgSQL (khoảng 13%). Vì vậy, nghiên cứu này đề xuất sử dụng ngôn ngữ C làm mã nguồn cho trigger và xây dựng mô-đun để sinh tự động các trigger cho tất cả các BG tham gia vào truy vấn, phục vụ thực hiện CNGT KNT trong cơ chế đồng bộ, như một phần của giao tác thực hiện thao tác dữ liệu trong các BG. Đã có các nghiên cứu [1, 2, 3] xây dựng được chương trình sinh mã nguồn trigger tự động bằng ngôn ngữ C, triển khai các thuật toán CNGT KNT trên HQTCSDL PostgreSQL. Tuy nhiên nghiên cứu này vẫn chưa quan tâm đến các KNT được tạo bởi truy vấn lồng, truy vấn đệ quy, truy vấn bao gồm phép nối ngoài. Có thể thấy truy vấn lồng (SubQuery) là một dạng truy vấn phổ biến, tần suất xuất hiện cao, tuy nhiên các nghiên cứu về CNGT KNT cho PostgreSQL đến nay vẫn chưa hỗ trợ dạng truy vấn này. Vì vậy, tôi chọn đề tài “Xây dựng mô-đun sinh tự động mã nguồn trigger trên ngôn ngữ C phục vụ cập nhật gia tăng, đồng bộ các khung nhìn thực với truy vấn lồng cho PostgreSQL” làm khóa luận tốt nghiệp cao học. 2. Mục tiêu và nhiệm vụ đề tài 2.1. Mục tiêu Xây dựng chương trình sinh tự động mã nguồn trigger trên ngôn ngữ C phục vụ cập nhật gia tăng, đồng bộ các khung nhìn thực với truy vấn lồng trong PostgreSQL. Chương trình có khả năng sinh mã SQL cài đặt khung nhìn thực, trigger trên các bảng gốc để cập nhật gia tăng, đồng bộ các khung nhìn thực. 2.2. Nhiệm vụ Tìm hiểu các biên dịch và sử dụng trigger viết bằng ngôn ngữ C trên PostgreSQL. Tìm hiểu và nghiên cứu cơ sở lý thuyết về cập nhật gia tăng, đồng bộ KNT với truy vấn lồng. Khai thác các thuật toán CNGT KNT đã có để ứng dụng vào đề tài, đặc biệt là thuật toán CNGT KNT với truy vấn lồng. 3. Đối tƣợng và phạm vi nghiên cứu 3.1. Đối tƣợng nghiên cứu CSDL quan hệ, HQT CSDL quan hệ, ngôn ngữ lập trình C Trigger trên các HQT CSDL quan hệ 3 Truy vấn lồng, khung nhìn thực Thuật toán CNGT KNT với truy vấn lồng 3.2. Phạm vi nghiên cứu HQT CSDL PostgreSQL Kỹ thuật viết trigger cho PostgreSQL bằng ngôn ngữ C Cách sử dụng trigger được viết bằng ngôn ngữ C trên PostgreSQL Các thuật toán CNGT cho KNT trên PostgreSQL Thuật toán CNGT KNT hỗ trợ truy vấn lồng 4. Phƣơng pháp nghiên cứu Về phương pháp nghiên cứu, tôi sử dụng hai phương pháp chính là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. 4.1. Phƣơng pháp lý thuyết Thu thập, chọn lọc, phân loại, ghi chú và nghiên cứu các tài liệu (sách, bài báo, luận văn, trang web) có liên quan đến khung nhìn thực, HQTCSDL PostgreSQL, cập nhật gia tăng KNT, đồng bộ KNT, sinh mã trigger trong ngôn ngữ C. 4.2. Phƣơng pháp thực nghiệm Dựa trên lý thuyết đã nghiên cứu, tiến hành xây dựng chương trình sinh tự động mã các trigger thực hiện cập nhật gia tăng khung nhìn thực với truy vấn lồng trong hệ cơ sở dữ liệu PostgreSQL; thử nghiệm trên máy đơn và đánh giá tốc độ cập nhật dữ liệu trên các bảng gốc (BG) có trigger cập nhật KNT. 5. Ý nghĩa khoa học và thực tiễn của đề tài 5.1. Ý nghĩa khoa học Đề xuất thuật toán cập nhật gia tăng KNT truy vấn lồng. Đề xuất thuật toán sinh tự động mã nguồn các trigger trong ngôn ngữ C phục vụ cập nhật gia tăng các bảng khung nhìn thực truy vấn lồng trong hệ quản trị cơ sở dữ liệu PostgreSQL. 5.2. Ý nghĩa thực tiễn Áp dụng chương trình vào cơ sở dữ liệu PostgreSQL nhằm làm tăng tốc độ thực thi các truy vấn dữ liệu mà vẫn đảm bào ràng buộc toàn vẹn dữ liệu. Chương trình sinh tự động mã trigger C thực hiện CNGT KNT có tính ứng dụng cao, giúp tiết kiệm thời gian và công sức của người quản trị CSDL khi làm việc với HQTCSDL PostgreSQL cũng như các HQTCSDL mã nguồn mở 4 có hỗ trợ trigger trong ngôn ngữ C. Chương trình sinh tự động mã nguồn các trigger có thể hỗ trợ các lập trình viên sinh mã trigger. 6. Cấu trúc của luận văn Chƣơng 1: Nghiên cứu tổng quan, chương này giới thiệu tổng quan về ngôn ngữ lập trình C, truy vấn lồng và KNT; cập nhật gia tăng, đồng bộ KNT. Trình bày các vấn đề liên quan đến trigger trên C trong PostgreSQL. Chƣơng 2: Khung nhìn thực trong PostgreSQL và thuật toán cập nhật gia tăng khung nhìn thực với truy vấn lồng, chương này trình bày các phương pháp cập nhật KNT; phân tích thuật toán cập nhật gia tăng KNT với truy vấn lồng. Chƣơng 3: Xây dựng chương trình sinh tự động mã nguồn các trigger thực hiện cập nhật gia tăng khung nhìn thực với truy vấn lồng, chương này trình bày cách cài đặt môi trường CSDL và ngôn ngữ lập trình; xây dựng mô-đun sinh mã tự động trigger. 5 CHƢƠNG 1 NGHIÊN CỨU TỔNG QUAN 1.1. Tổng quan về ngôn ngữ lập trình C 1.1.1. Ngôn ngữ lập trình C C là ngôn ngữ rất có hiệu quả và được ưa chuộng để viết các phần mềm hệ thống, mặc dù nó cũng được dùng cho việc viết các ứng dụng. C là ngôn ngữ lập trình tương đối nhỏ gọn vận hành gần với phần cứng, được tạo ra với một mục tiêu là làm cho nó thuận tiện để viết các chương trình lớn. 1.1.2. Đặc điểm của ngôn ngữ C Ngôn ngữ C có các đặc điểm sau: C cũng được sử dụng để lập trình bậc thấp. C cung cấp nhiều hàm có sẵn giúp việc phát triển các ứng dụng trở nên nhanh chóng hơn. Ngôn ngữ C có khả năng mở rộng vì nó dễ dàng nhận một tính năng mới. 1.2. Tổng quan về truy vấn lồng 1.2.1. Đặc điểm của truy vấn lồng Là dạng truy vấn mà câu lệnh Select lồng trong câu lệnh select. Câu lệnh Select bên ngoài gọi là truy vấn ngoài Câu lệnh Select bên trong gọi là truy vấn trong hay truy vấn con Có 2 loại: - Loại 1: Truy vấn con nằm trong mệnh đề WHERE SELECT FROM INNER JOIN ON <điều kiện nối> INNER JOIN ON <điều kiện nối>… WHERE (SELECT FROM < danh sách các bảng> WHERE<điều kiện>) - Loại 2: Truy vấn con nằm trong mệnh đề FROM SELECT FROM , , () AS WHERE <điều kiện> Các câu lệnh Select có thể lồng nhau ở nhiều mức Câu truy vấn con thường trả về một tập các giá trị 6 Mệnh đề Where của câu truy vấn ngoài - So sánh tập hợp thường đi cùng với một số toán tử IN, NOT IN, ALL, ANY, EXISTS… 1.2.2. Phân loại Dựa vào đặc điểm của câu truy vấn con người ta phân truy vấn lồng thành 2 loại chính: - Truy vấn lồng phân cấp: Khi nội dung của câu truy vấn con độc lập với câu truy vấn cha. Cú pháp: SELECT A FROM X WHERE … (SELECT B, C FROM Y) … Ví dụ: Đưa ra mã, tên của những sinh viên thuộc lớp CNTT 1 SELECT ma_sv, ten_sv FROM sinhvien WHERE ma_lop IN ( SELECT ma_lop FROM lop WHERE ten_lop = „CNTT – 1‟) Ở ví dụ trên, câu truy vấn con SELECT ma_lop FROM lop WHERE ten_lop = „CNTT – 1‟không sử dụng bất kỳ thành phần nào của câu truy vấn cha. Do đó đây là một câu truy vấn lồng phân cấp. - Truy vấn lồng tương quan: Khi nội dung của câu truy vấn con phụ thuộc vào câu truy vấn cha. Cú pháp: SELECT A FROM X WHERE … (SELECT B, C FROM Y WHERE B = X.A) … Ví dụ: Đưa ra mã, tên của những sinh viên thuộc lớp CNTT 1 SELECT ma_sv, ten_sv FROM sinhvien WHERE EXISTS ( SELECT* FROM Lop WHERE ma_lop = sinhvien.ma_lop AND ten_lop = „CNTT – 1‟) 7 Ở ví dụ này, câu truy vấn con SELECT*. FROM Lop. WHERE ma_lop = sinhvien.ma_lop and ten_lop = „CNTT – 1‟. WHERE ma_lop = sinhvien.ma_lop có sử dụng thành phần của câu truy vấn cha qua biểu thức so sánh ma_lop = sinhvien.ma_lop. Do đó, đây là một câu truy vấn lồng tương quan. 1.3. Tổng quan về khung nhìn thực 1.3.1. Giới thiệu chung Khung nhìn thực (KNT - Materialized view) là một đối tượng trong cơ sở dữ liệu (CSDL) dùng để lưu trữ kết quả thực thi của một truy vấn, giúp cải thiện và nâng cao tốc độ thực thi đối với các truy vấn phức tạp, có tần suất sử dụng cao trên một lượng dữ liệu lớn. Ý tưởng của KNT là dựa trên các bảng kết quả sẵn có để trả lời truy vấn một cách nhanh chóng mà không cần thực thi lại truy vấn. Hiệu quả sử dụng KNT càng rõ rệt đặc biệt khi áp dụng trên một lượng dữ liệu đủ lớn, do đã bỏ qua các bước thực thi phép nối và các hàm thống kê vốn là những thành phần chiếm nhiều chi phí trong quá trình thực thi truy vấn. Tuy nhiên, việc sử dụng KNT cũng có những nhược điểm; đó là: KNT làm tiêu tốn không gian lưu trữ và phải được cập nhật khi các bảng chi tiết cơ bản được sửa đổi. 1.3.2. Phân loại khung nhìn thực Phân loại khung nhìn thực theo một số loại [15] như sau: 1.3.2.1. KNT bản sao (snapshot materialized view) 1.3.2.2. KNT hăm hở (eager materialized view) 1.3.2.3. KNT rất lười (very lazy materialized view): 1.3.2.4. KNT lười (lazy materialized view): 1.4. Tổng quan về cập nhật gia tăng, đồng bộ khung nhìn thực 1.4.1. Tổng quan về cập nhật gia tăng Cập nhật gia tăng chỉ sửa đổi nội dung KNT tương ứng với các thay đổi trong các bảng gốc. Thông thường, cập nhật gia tăng đòi hỏi chi phí tài nguyên rất nhỏ so với cập nhật hoàn toàn. Để duy trì các bảng KNT trong trạng thái thực tiễn, cần phải cập nhật chúng mỗi khi có sự thay đổi dữ liệu trong các bảng gốc. Trên thực tế, có các bài toán của hệ thống thông tin đòi hỏi phải tính đến một cách không chậm trễ chỉ một phần trong số các thay đổi dữ liệu trong các bảng gốc. Từ đó xuất hiện khả năng trì hoãn 8 cập nhật KNT. Khả năng đó cho phép giảm số lượng các cập nhật KNT, thông qua đó nâng cao đáng kể năng suất tổng thể của hệ thống. 1.4.2. Cập nhật đồng bộ khung nhìn thực Phụ thuộc vào thời hạn cập nhật các thay đổi vào các bảng KNT, các cơ chế cập nhật được phân ra đồng bộ và không đồng bộ. Cập nhật đồng bộ được thực thi không chậm trễ ngay khi có thay đổi dữ liệu trong bảng gốc như một phần của giao tác thực hiện thay đổi đó. 1.5. Cập nhật khung nhìn thực bằng trigger trên C trong PostgreSQL 1.5.1. Khái niệm về trigger Trigger là một thủ tục đặc biệt mà việc thực thi của nó tự động khi có sự kiện xảy ra, các sự kiện gọi thủ tục đặc biệt này được định nghĩa trong câu lệnh, thông thường được thực hiện với các sự kiện liên quan đến Insert, Update, Delete dữ liệu. Trigger được sử dụng trong việc bảo đảm toàn vẹn dữ liệu theo quy tắc xác định, được quản lý theo bảng dữ liệu hoặc khung nhìn. 1.5.2. Trigger trên các HQT CSDL Trigger có thể được thực thi trước hoặc sau khi sự kiện xảy ra, bao gồm các mức: Row Level Trigger Column Level Trigger For Each Row Type For Each Statement Type 1.5.3. Trigger trong PostgreSQL Trigger trên PostgreSQL có thể xử lý một tập các bản ghi, hoặc chỉ xử lý một bản ghi. Chỉ trigger xử lý một bản ghi mới có thể nhìn thấy dữ liệu đang được thao tác. Vì vậy đề tài thực hiện sinh mã nguồn trigger bắt sự kiện thay đổi dữ liệu trên các BG theo cơ chế xử lý từng bản ghi một trong tập các bản ghi được cập nhật. 1.5.4. Hàm trong C Hàm trong ngôn ngữ C có thể được biên dịch thành các thư viện chia sẻ với các phần mở rộng tương ứng là *.dll (trên hệ điều hành Windows). 9 1.5.5. Hàm trigger trong C Khi một hàm được khai báo trả về kiểu trigger và được nạp vào server, có thể tạo hàm trigger bằng lệnh: CREATE TRIGGER {BEFORE|AFTER} {INSERT|DELETE|UPDATE} ON FOR EACH ROW EXECUTE PROCEDURE . 1.5.6. Ví dụ tạo trigger trên C trong PostgreSQL Theo ví dụ tạo trigger trên C trong PostgreSQL (phụ lục 1) thì hàm trigf báo cáo số lượng hàng trong bảng ttest và bỏ qua phép toán thực tế nếu lệnh cố gắng chèn một giá trị rỗng vào cột x. (Vì trigger hoạt động như một ràng buộc không rỗng nhưng không hủy bỏ giao tác). [13] 1.6. Kết chƣơng 1 Chương 1 đã giới thiệu các đối tượng mà đề tài đang làm việc trực tiếp là ngôn ngữ C, trigger cũng như những đặc điểm của trigger trong PostgreSQL và cách thức sử dụng các hàm C để xây dựng thành hàm trigger và cài đặt vào cơ sở dữ liệu. Việc hiểu rõ những đặc thù về trigger trong PostgreSQL và khả năng của ngôn ngữ C trong việc triển khai các hàm trigger trong PostgreSQL đóng vai trò quan trọng trong việc triển khai thuật toán CNGT. 10 CHƢƠNG 2 KHUNG NHÌN THỰC TRONG POSTGRESQL VÀ THUẬT TOÁN CẬP NHẬT GIA TĂNG KHUNG NHÌN THỰC VỚI TRUY VẤN LỒNG 2.1. PostgreSQL và khung nhìn thực trong PostgreSQL PostgreSQL là một hệ quản trị cơ sở dữ liệu (HQT CSDL) mã nguồn mở. PostgreSQL đã tạo được lòng tin về độ tin cậy cũng như tính đúng đắn, toàn vẹn dữ liệu, được bộ thông tin và truyền thông khuyến cáo sử dụng. Là một HQT CSDL mã nguồn mở hàng đầu trên thế giới và KNT đã được triển khai trên PostgreSQL ở các phiên bản 9.3.4, 9.4, 10…. KNT là tính năng bảng ảo tiện lợi khác đã được hỗ trợ bởi PostgreSQL. KNT cũng có thể được đánh chỉ mục, không giống các views thông thường được tạo ra mỗi lần chúng được gọi, KNT là các ảnh chụp tại một thời điểm. Chúng không được làm mới (refreshed) ngoại trừ được chỉ định. Điều này có thể tăng đáng kể tốc độ với các truy vấn chạy sử dụng KNT. Tuy nhiên KNT trong PostgreSQL vẫn chưa hỗ trợ vấn đề cập nhật đồng bộ gia tăng. Do vậy, việc nghiên cứu các kỹ thuật CNGT cho KNT trên PostgesSQL đang rất được quan tâm. 2.2. Các phƣơng pháp cập nhật KNT 2.2.1. Phương pháp làm mới KNT Việc triển khai KNT cho HQT CSDL PostgreSQL chỉ mới được đưa vào ở phiên bản 10 và việc cập nhật được thực hiện thông qua lệnh refresh materialized view. Điều này tốn chi phí xấp xỉ chi phí thực hiện truy vấn, và không đảm bảo được dữ liệu trên KNT luôn luôn là mới nhất. Bất cứ khi nào người dùng truy cập dữ liệu của KNT chỉ có thể thấy được dữ liệu ở lần cập nhật gần nhất, không phải ở thời điểm hiện tại. Người dùng vẫn phải cập nhật bằng lệnh refresh materialized view, tùy thuộc vào người quản trị hệ thống và nhu cầu sử dụng dữ liệu. Phương pháp này không hiệu quả, đặc biệt khi dữ liệu trong KNT yêu cầu tính chính xác tại mọi thời điểm. 2.2.2. Phương pháp cập nhật gia tăng đồng bộ Cập nhật gia tăng là kỹ thuật cập nhật dữ liệu trên KNT một cách đồng bộ, được thực hiện mỗi khi dữ liệu tại các BG tham gia 11 vào KNT có sự thay đổi, nhờ đó giúp cho KNT luôn trong trạng thái được cập nhật. Việc CNGT KNT có thể được thực hiện thông qua việc xây dựng các trigger bắt các sự kiện làm thay đổi dữ liệu trên các BG, từ đó xác định các thay đổi có thể làm ảnh hưởng đến tính đúng đắn của kết quả được lưu trong KNT, sau đó tiến hành việc cập nhật dữ liệu trong KNT. Có thể xem thao tác CNGT là một phần trong giao tác thay đổi dữ liệu trên các BG. Nghiên cứu đề xuất tạo KNT như một bảng (table), sau đó sử dụng hệ thống các trigger cài đặt trên các BG bắt sự kiện thay đổi dữ liệu, từ đó cập nhật vào KNT những thay đổi liên quan. 2.2.3. Một số vấn đề cần quan tâm khi CNGT KNT với truy vấn lồng Để quá trình CNGT được tối ưu, ta phải quan tâm đến vấn đề sàng lọc dữ liệu. Chỉ những dữ liệu nào liên quan trực tiếp đến KNT và ảnh hưởng đến tính đúng đắn của dữ liệu trong KNT mới cần được cập nhật. Điều này có thể được thực hiện thông qua việc phân tích các mệnh đề JOIN, WHERE, FROM để đưa ra điều kiện sàng lọc dữ liệu. Mỗi khi thao tác dữ liệu xảy ra trên BG, thông qua điều kiện lọc, ta có thể xác định được dữ liệu đang được xử lý có ảnh hưởng đến KNT hay không, từ đấy đưa ra quyết định tiếp tục thực thi phần mã CNGT hay thoát khỏi hàm trigger. Thứ hai, ta phải quan tâm đến các phép nối trong truy vấn. Khi một KNT được tạo ra trên cơ sở truy vấn bao gồm nhiều phép nối giữa các bảng với nhau, quá trình CNGT cần chắc chắn dữ liệu trên KNT luôn đảm bảo tính toàn vẹn, ràng buộc giữa các bảng khi một trong số các BG có sự thay đổi. 2.3. Thuật toán cập nhật gia tăng KNT với truy vấn lồng 2.3.1. Thuật toán chuyển từ truy vấn lồng sang truy vấn nối trong Một TVG có dạng (chỉ áp dụng 2 bảng và trường hợp IN): SELECT FROM INNER JOIN ON <điều kiện nối> WHERE (SELECT FROM < danh sách các bảng> WHERE<điều kiện nối>) Bƣớc 1: Gọi tập các trường chứa trong mệnh đề lần lượt là: 12 SELECT chính là SELc; FROM chính là FROc IN chính là Inc; WHERE chính là WHEc Phép nối (Join) chính là A; SELECT lồng là SELl FROM lồng là FROl; IN lồng là INl WHERE lồng là WHEl; Phép nối (Join) lồng là B Bƣớc 2: Chuyển câu truy vấn có Join về dạng Where SELECT SELc FROM FROc WHERE WHEc AND A AND Inc IN (SELECT SELl FROM FROl WHERE WHEl AND B) Bƣớc 3: Chuyển câu truy vấn lồng về truy vấn nối trong SELECT SELc FROM FROc  FROl WHERE WHEc AND WHEl AND A AND B Cho CSDL quản lý sinh viên đơn giản với 3 bảng và các quan hệ 1 – n: Hình 2.2 CSDL quản lý sinh viên đơn giản với 3 bảng Ví dụ: Đưa ra danh sách các sinh viên đang học tập tại khoa Tin: Truy vấn lồng: SELECT ma_sv, ten_sv FROM sinh_vien WHERE ma_lop IN (SELECT ma_lop FROM lop WHERE ma_khoa = „TI‟) Truy vấn nối trong: SELECT ma_sv, ten_sv FROM sinh_vien JOIN lop ON sinh_vien.ma_lop = lop.ma_lop WHERE ma_khoa = „TI‟ Phân tích câu lệnh truy vấn lồng 13 Danh sách SELECT chính (SELc): ma_sv, ten_sv Danh sách FROM chính (FROc): sinh_vien Danh sách IN chính (INc): ma_lop Danh sách WHERE chính (WHEc): không có Danh sách SELECT lồng (SELl): ma_lop Danh sách FROM lồng (FROl): lop Danh sách IN lồng (INl): không có Danh sách WHERE lồng (WHEl): ma_khoa = “TI‟ Từ phân tích truy vấn lồng ta có thể chuyển đổi sang truy vấn nối trong như sau: SELECT SELc FROM FROc JOIN FROl ON FROc. INc = FROl.SELl WHERE WHEc AND WHEl Dựa vào thuật toán và phân tích chuyển đổi ở ví dụ trên ta có thể áp dụng thuật toán cập nhật gia tăng khung nhìn thực với truy vấn nối trong được trình bày ở mục 2.3.3 để cập nhật gia tăng khung nhìn thực với truy vấn lồng. 2.3.2. Điều kiện triển khai thuật toán Trong phạm vi đề tài hiện tại chỉ phục vụ cho các KNT được tạo trên cơ sở TVG thỏa mãn những điều kiện sau đây: - Điều kiện nối trên các bảng chỉ liên quan trực tiếp đến các bảng. - Tất cả khóa của các bảng phải tham gia vào mệnh đề SELECT. - Đối với truy vấn lồng có nhiều so sánh tập hợp tuy nhiên trong luận văn này chỉ đề cập đến phép IN. - Các truy vấn lồng được chuyển đổi thành truy vấn nối trong. 2.3.3. Thuật toán cập nhật gia tăng khung nhìn thực với truy vấn nối trong 2.3.3.1. Truy vấn SPJ (Select – Project – Join) Truy vấn SPJ là truy vấn chỉ bao gồm các mệnh đề SELECT, FROM, WHERE, nhưng không bao gồm các chức năng nhóm và tổng hợp. Từ mệnh đề có thể chứa các kết nối bên trong. Đối với trường hợp SPJ KNT, đã xây dựng một chương trình tạo mã kích hoạt thực hiện cập nhật gia tăng dựa trên thuật toán đã cải 14 tiến các bản phát hành trước đó [13] và tạo phần mềm của nó cho tổng hợp tự động của mã nguồn kích hoạt để cập nhật gia tăng KNT xem xét rằng: - Kết quả truy vấn có thể chứa trùng lặp; - Bất kỳ một khóa của mỗi BG được thêm tự động vào mệnh đề SELECT; - Xem xét hoạt động sửa đổi dưới dạng các hoạt động tương đương như xóa và chèn tiếp; - Loại trừ thao tác dữ liệu trong BG không ảnh hưởng đến KNT; 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 với truy vấn gốc: SELECT FROM INNER JOIN ON <điều kiện nối> INNER JOIN ON <điều kiện nối>… WHERE <điều kiện lọc> Trong đó F: Mệnh đề FROM, tập các BG T1, T2…Tn được sử dụng trong truy vấn tạo KNT. J: Tập hợp các điều kiện của các phép nối. W: Mệnh đề WHERE, điều kiện chọn lựa bản ghi để xử lý. Ti={ i=1, 2,..,n}– tập hợp các bảng gốc được sử dụng trong truy vấn. Fins: Mệnh đề FROM trong trường hợp thêm bản ghi. Fdel: Mệnh đề FROM trong trường hợp xóa bản ghi. 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). 15 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. 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. 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. a. Trường h p thêm mới c c bản ghi Giả sử tập hợp các bản ghi Tiins được thêm vào BG Ti. Bước 1: Fins = T1 J T2 J …… d Tiins J … Tn Bước 2: dQiins = Select S from Fins where W Bước 3: Insert into MV Select dQiins b. Trường h p xo c c bản ghi Giả sử tập hợp các bản ghi Tidel được xoá từ BG Ti. Bước 1: Fdel = T1 J T2 J …… d Tidel J … Tn Bước 2: dQidel = Select S from Fdel where W Bước 3: For each X in dQidel: Delete from MV Where MV. (X) = (X) And MV. (X) = (X) And MV. (X) = (X) c. Trường h p sửa đổi c c bản ghi Giả sử trong BG , tập hợp các bản ghi Tiold được thay đổi thành tập hợp Tinew. Trong trường hợp này có thể thực thi mục b và tiếp theo sau đó là mục a để CNGT KNT (update Ti = delete Tiold + insert Tinew), với Tidel = Tiold và Tiins = Tinew tương ứng. Trong đó, mỗi bản ghi < > tương ứng với một bản ghi < >. 2.3.3.2. Truy vấn nối trong bao gồm c c hàm thống kê Thuật toán CNGT đồng bộ KNT trên cơ sở các truy vấn bao gồm phép nối trong được tham khảo từ công trình nghiên cứu [2], chủ yếu được tổng hợp và phát triển từ các nghiên cứu [6-11]. Thuật toán này chưa quan tâm đến KNT được tạo trên cơ sở truy vấn lồng, truy vấn đệ quy, truy vấn bao gồm phép nối ngoài. Giả sử KNT được tạo trên cơ sở truy vấn bao gồm các hàm thống kê Q (S, F, J, W, G). Trong đó: S: Mệnh đề SELECT, tập các cột được lựa chọn. S có thể bao gồm các cột hoặc các hàm thống kê với biểu thức (E) trên các 16 cột từ BG như SUM(E), COUNT(E), AVG(E), MIN(E) và MAX(E). E không chứa các hàm thống kê. F: Mệnh đề FROM, tập các BG T1, T2…Tn được sử dụng trong truy vấn tạo KNT. J: Tập hợp các điều kiện của các phép nối. W: Mệnh đề WHERE, điều kiện chọn lựa bản ghi để xử lý. G: Mệnh đề GROUP BY, tập các cột gộp nhóm. A = S\G - tập hợp các hàm thống kê trong mệnh đề SELECT. a. Tạo khung nhìn thực Thông tin về cách thức biến đổi truy vấn để tạo KNT, cụ thể, thông tin về các cột trong bảng KNT giúp làm rõ các thuật toán cập nhật. Mục đích của việc biến đổi là để có thể sử dụng KNT tối ưu hơn và tối ưu hơn cả trong việc thực hiện CNGT KNT. S bao gồm các cột sẽ được lưu trong bảng KNT. Về các hàm thống kê, ta chỉ xem xét các trường hợp SUM(E), COUNT(E), AVG(E), MIN(E) và MAX(E). Từ quy định về cú pháp của lệnh truy vấn SELECT của ngôn ngữ SQL cũng như suy luận từ đại số quan hệ, có thể khẳng định, “cột” trong S có thể được hiểu là: i) Một cột từ BG, hoặc là ii) Biểu thức đại số trên các hàm thống kê, hoặc là iii) Biểu thức đại số trên cột từ BG và hàm thống kê. Biểu thức (E) được đề cập không bao gồm hàm thống kê, nghĩa là không có trường hợp hàm thống kê là tham số của hàm thống kê. Với trường hợp iii), cột tham gia vào biểu thức một cách ngang hàng với hàm thống kê (chẳng hạn cột colA trong truy vấn: SELECT…, (colA + SUM(colB)) AS sumAB… GROUP BY …, colA), ta có thể xem xét như các cột bình thường khác tham gia vào G. Vậy nên, thay vì lưu kết quả biểu thức đại số giữa các hàm thống kê hoặc hàm thống kê và cột, ta lưu kết quả thực thi của từng hàm thống kê. b. Thuật to n cập nhật gia tăng Sự kiện thay đổi dữ liệu trong các BG được chia theo ba loại thao tác: Thêm mới (insert), cập nhật (update) và xoá (delete) một tập các bản ghi. Nếu xét trên phương diện chỉ các bộ giá trị 17 tương ứng với một tập các cột, thì các bộ giá trị này có thể trùng nhau. Ta gọi các “tập” này là các túi. Hầu hết các công trình liên quan CNGT KNT đã công bố trước đây xem trường hợp thao tác cập nhật (update) tương đương với việc xoá một túi các bản ghi và sau đó thêm mới một túi các bản ghi [2, 6]. Tuy nhiên, việc chia tách này không phải bao giờ cũng tốt hơn. Trong trường hợp truy vấn không bao gồm các hàm thống kê MIN(E), MAX(E), ta có thể không cần phải phân tích update thành insert và delete [2]. Trong trường hợp truy vấn bao gồm các hàm thống kê MIN(E), MAX(E), thì việc phân tích update thành insert và delete là tất nhiên, không có lựa chọn khác. Với insert, ta không cần quan tâm đến dữ liệu trong các BG, vì giá trị được thêm vào có thể thay thế giá trị MIN(E), MAX(E) hiện tại bằng cách so sánh với giá trị trong bảng KNT. Với delete, rõ ràng, nếu xoá bản ghi có giá trị trường đang là MIN(E) hoặc MAX(E), thì ta phải tìm lại giá trị MIN(E), MAX(E) mới từ các BG. Trường hợp thao tác thứ nhất – thêm mới tập bản ghi dTinew vào bảng Ti B1. Loại từ dTinew những bản ghi không thoả C. Tất nhiên, những bản ghi không thoả W không thể có tác động đến kết quả thực thi nên ta không cần thiết xét các bản ghi đó, có thể loại ngay từ đầu. Thường thì J chứa các điều kiện kiểu Ti.C1 = Tj.C2. Tuy nhiên, trong một số trường hợp, J có thể bao gồm cả điều kiện lọc thông thường với một vế là biểu thức đại số trên các cột từ một BG, còn vế thứ hai là một hằng số. Ở bước này, ta chỉ có thể lọc các bản ghi áp dụng các điều kiện trong C chỉ liên quan đến Ti. Việc loại bỏ các bản ghi ở bước này giúp giảm số lượng bản ghi tham gia vào phép nối ở B2. B2. Nối tập dTinew thu được với các bảng còn lại trong F (ngoại trừ Ti), thu được kết quả dQi. B3. Loại từ dQi các bản ghi không thoả C. B4. Nhóm các bản ghi trong dQitheo G, chọn các cột tương ứng tham gia vào S, thực hiện các biểu thức cho mỗi nhóm theo G và cập nhật bảng KNT Tmv cho mỗi bản ghi thu được theo nguyên tắc: - Nếu chưa có bản ghi dạng (G, S\G), thêm mới bản ghi. 18 - SUM(E) = SUM(E) + dSUMnew(E). Trong đó, E là biểu thức. dSUMnew(E) là SUM(E) trên dQi. - COUNT(E) = COUNT(E) + dCOUNTnew(E). dCOUNTnew(E) là COUNT(E) trên dQi. - Nếu MIN(E) > dMINnew(E), nghĩa là bản ghi đang được thêm mới sẽ tạo nên giá trị MIN(E) cho nhóm, thì MIN(E) = dMINnew(E). Ngược lại, MIN(E) không thay đổi. dMINnew(E) là MIN(E) trên dQi. - Nếu MAX(E) < dMAXnew(E), nghĩa là bản ghi đang được thêm mới sẽ tạo nên giá trị MAX(E) mới cho nhóm, MAX(E) = dMAXnew(E). Ngược lại, MAX(E) không thay đổi. dMAXnew(E) là MAX(E) trên dQi. - Thay vì lưu AVG(E), ta lưu SUM(E) và COUNT(E). Khi xuất hiện truy vấn có AVG(E), ta tính AVG(E) từ SUM(E)/COUNT(E). Sự kiện delete tập bản ghi dTiold từ bảng Ti B1. Loại từ dTiold những bản ghi không thoả C. B2. Nối tập dTiold với các bảng còn lại, thu được kết quả dQi. B3. Loại từ dQi các bản ghi không thoả C. B4. Nhóm các bản ghi trong dQi theo G, chọn các cột tương ứng tham gia vào S, thực hiện các biểu thức cho mỗi nhóm theo G và cập nhật bảng KNT Tmv cho mỗi bản ghi thu được theo nguyên tắc: - SUM(E) = SUM(E) - dSUMold(E). dSUMnew(E) là SUM(E) trên dQi. - COUNT(E) = COUNT(E) dCOUNTold(E). dCOUNTold (E) là COUNT(E) trên dQi. - Nếu MIN(E) = dMINold(E), nghĩa là bản ghi đang được xoá tạo nên giá trị MIN(E) của nhóm, ta tính lại MIN(E) dựa trên các BG. Ngược lại, MIN(E) không thay đổi. - Nếu MAX(E) = dMAXold(E), nghĩa là bản ghi đang được xoá tạo nên giá trị MAX(E), ta tính lại MAX(E) dựa trên các BG. Ngược lại, MAX(E) không thay đổi. - Nếu chỉ có COUNT(*) = 0, nghĩa là không còn bản ghi nào thuộc nhóm tham gia vào kết quả truy vấn, xoá bản ghi dạng (G, S\G) từ Tmv. Sự kiện update tập bản ghi dTi trong bảng Ti.