Báo cáo nghiên cứu khoa học: SIÊU ĐỒ THỊ KẾT NỐI ĐỐI TƯỢNG – MỘT CÁCH TIẾP CẬN TRONG TỐI ƯU HOÁ CÂU TRUY VẤN ĐỐI TƯỢNG LỒNG NHAU

Trong cơ sở dữ liệu hướng đối tượng, truy vấn đối tượng lồng được sử dụng khá thường xuyên. Các cấu trúc lồng được biểu diễn ở biểu thức điều kiện của truy vấn dưới hai dạng: các truy vấn con lồng hoặc biểu thức đường dẫn có chứa các kết nối ẩn là các tân từ lồng nhau trong mệnh đề where.
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: "SIÊU ĐỒ THỊ KẾT NỐI ĐỐI TƯỢNG – MỘT CÁCH TIẾP CẬN TRONG TỐI ƯU HOÁ CÂU TRUY VẤN ĐỐI TƯỢNG LỒNG NHAU"TẠP CHÍ KHOA HỌC, Đại học Huế, Số 58, 2010 SIÊU ĐỒ THỊ KẾT NỐI ĐỐI TƯỢNG – MỘT CÁCH TIẾP CẬN TRONG TỐI ƯU HOÁ CÂU TRUY VẤN ĐỐI TƯỢNG LỒNG NHAU Lê Mạnh Thạnh Đại học Huế Hoàng Bảo Hùng Sở Thông tin và Truyền thông tỉnh Thừa Thiên Huế TÓM TẮT Trong cơ sở dữ liệu hướng đối tượng, truy vấn đối tượng lồng được sử dụng khá thườngxuyên. Các cấu trúc lồng được biểu diễn ở biểu thức điều kiện của truy vấn dưới hai dạng: cáctruy vấn con lồng hoặc biểu thức đường dẫn có chứa các kết nối ẩn là các tân từ lồng nhautrong mệnh đề where. Đối với truy vấn lồng, khi phân tích ước lượng chi phí của biểu thức đạisố lồng nhau, thì việc định giá sẽ cho kết quả chi phí không hiệu quả. Vì vậy, phương pháp củachúng tôi đưa ra trong bài báo này là làm phẳng các truy vấn con trong các truy vấn có cấutrúc lồng nhau sử dụng siêu đồ thị kết nối đối tượng, phương pháp này sẽ làm tăng tính hiệuquả cho việc thực thi xử lý truy vấn trên cơ sở dữ liệu hướng đối tượng.1. Mở đầu Để xử lý các tân từ lặp (lồng), Cho W. [3] đưa ra phương pháp ước lượng chi phíphụ thuộc tỷ số giữa số các đối tượng của lớp bắt đầu trong biểu thức đường dẫn vàtổng số các đối tượng của lớp, dựa trên mối quan hệ nhiều - nhiều giữa các lớp. Tỷ sốnày là một trong những tham số lựa chọn trong quá trình thiết kế CSDL vật lý. Đối với là các truy vấn con lồng, Cluet S. [4] đề xuất phương pháp tối ưu theohai bước. Đầu tiên, biến đổi các truy vấn ở mức ngôn ngữ nhằm xử lý một cách hiệuquả các biểu thức con chung và các truy vấn con độc lập. Sau đó, các truy vấn đượcbiên dịch thành các biểu thức đại số lồng nhau và áp dụng phương pháp biến đổi đại số.Tuy nhiên, khi phân tích sự ước lượng đối với các vòng lặp lồng nhau trong các biểuthức đại số, chúng ta nhận thấy biểu thức kết quả có chi phí là không hiệu quả. Do đó,phương pháp chúng tôi đề xuất trong phần sau sẽ giải quyết vấn đề xử lý cho các truyvấn con lồng trong giai đoạn “làm phẳng” các truy vấn lồng nhau bằng phương pháp rútgọn siêu đồ thị kết nối đối tượng, giúp cho phép định giá hiệu quả hơn. Trong bài báo này, xuất phát từ ý tưởng biểu diễn và tối ưu hóa các truy vấn bằngsiêu đồ thị của Ullman J.D [9] và Han [5], chúng tôi đưa ra khái niệm siêu đồ thị kết nốiđối tượng để biểu diễn các truy vấn đối tượng trong OQL, đặc biệt là xử lý các truy vấnlồng. Từ đó, đề xuất các thuật toán ước lượng các siêu cạnh và thuật toán thu gọn siêu đồthị kết nối đối tượng. 1212. Biểu diễn truy vấn đối tượng bằng ký pháp siêu đồ thị Trước hết, một cách hình thức chúng ta xét định nghĩa của khái niệm siêu đồ thịkết nối đối tượng như sau [6]: Định nghĩa. Siêu đồ thị kết nối đối tượng là một bộ sáu H = (CH, VH, EH, LH,sH, lbH), trong đó: (i) CH là tập hữu hạn các lớp tham gia trong truy vấn (ii) VH là tập hữu hạn các nút (iii) LH là tập hữu hạn các nhãn (iv) EH = EC ∪ EQ - tập các siêu cạnh (hữu hạn), trong đó EC, EQ là tập cácsiêu cạnh biểu diễn các lớp đối tượng và các thành phần của truy vấn. (v) sH: VH → EH là ánh xạ khởi tạo các siêu cạnh từ tập các nút lbH: EH → LH là hàm gán nhãn cho siêu cạnh, sao cho ∀ e ∈ EH lbH(e) ∈ (vi)LH Ví dụ 2.1. Xét siêu đồ thị kết nối đối tượng biểu diễn truy vấn sau: select A from c1, c2, c3 where c1.A = c2.F and (c1.A + c1.B > c3.D) and (c3.E ≤ c2.G) head e1 A B C f1 D e2 E G H f2 e3 Hình 1. Siêu đồ thị kết nối đối tượng của ví dụ 2.1 Trong đó, ta có: CH = {c1, c2, c3}, c1 = (A, B, C), c2 = (G, H) và c3 = (D, E, F) là các lớp đối tượng. VH = {A, B, C, D, E, F, G, H}: tập các nút, LH = {e1, e2, f1, f2, “head”}: các nhãn EH = EC ∪ EQ, với EC gồm tập các siêu cạnh được gán nhãn {e1, e2, e3} biểudiễn các lớp c1, c2, c3. Và EQ có các siêu cạnh biểu diễn lần lượt là kết quả của truy vấn,biểu thức điều kiện truy vấn tương ứng có nhãn là {f1, f2, “head”}. Đối với điều kiện“c1.A = c2.F” chúng ta thực hiện “t ...