Xử lí truy vấn trong cơ sở dữ liệu hướng đối tượng phân tán sử dụng bộ lọc Bloom

Mục tiêu của việc xử lí truy vấn cơ sở dữ liệu phân tán là tìm một chiến lược thực thi các truy vấn một cách hợp lí nhằm tối thiểu hóa giá trị hàm chi phí. Chi phí được tính toán ở đây là chi phí theo thao tác xuất/nhập, chi phí CPU và chi phí giao tiếp, trong đó chi phí giao tiếp thông thường là chi phí lớn nhất.
Nội dung trích xuất từ tài liệu:
Xử lí truy vấn trong cơ sở dữ liệu hướng đối tượng phân tán sử dụng bộ lọc BloomJOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1075.2015-0067Educational Sci., 2015, Vol. 60, No. 7A, pp. 196-203This paper is available online at http://stdb.hnue.edu.vnXỬ LÍ TRUY VẤN TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG PHÂN TÁN SỬ DỤNG BỘ LỌC BLOOM Mai Thúy Nga1 , Đoàn Văn Ban2 , Nguyễn Mạnh Hùng3 1 Khoa Toán Tin, Trường Đại học Thăng Long, 2 Viện Công nghệ Thông tin 3 Học viện Kỹ thuật Quân sự Tóm tắt. Mục tiêu của việc xử lí truy vấn cơ sở dữ liệu phân tán là tìm một chiến lược thực thi các truy vấn một cách hợp lí nhằm tối thiểu hóa giá trị hàm chi phí. Chi phí được tính toán ở đây là chi phí theo thao tác xuất/nhập, chi phí CPU và chi phí giao tiếp, trong đó chi phí giao tiếp thông thường là chi phí lớn nhất. Xử lí truy vấn trong các hệ Cơ sở dữ liệu hướng đối tượng sẽ nảy sinh nhiều vấn đề phức tạp hơn do các đặc tính của hướng đối tượng, đó là tính đóng gói, kế thừa, phân cấp lớp. Bài báo này trình bày một thuật toán sử dụng bộ lọc Bloom với mục tiêu giảm chi phí giao tiếp trong quá trình thực hiện truy vấn cơ sở dữ liệu hướng đối tượng phân tán. Từ khóa: Cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu phân tán, xử lí truy vấn, bộ lọc Bloom..1. Mở đầu Nhiều kết quả nghiên cứu [1, 2, 3] chỉ ra rằng cơ sở dữ liệu hướng đối tượng (CSDL HĐT)có thể được áp dụng với quy mô lớn và trong nhiều lĩnh vực ứng dụng phức tạp. Mô hình CSDLhướng đối tượng được tạo ra cũng nhằm để tích hợp trực tiếp với các ngôn ngữ lập trình hướngđối tượng, ngôn ngữ mà ngày nay được sử dụng trong phần lớn các ứng dụng. Hiện nay đã tồntại một số hệ quản trị CSDL hướng đối tượng như GEMSTONE, Versant, ObjectStore, Orion,OpenOODB, IRIS,. . . Đặc điểm cơ bản của CSDL hướng đối tượng là sự đóng gói các thuộc tínhcủa đối tượng và các thao tác lên đối tượng này. CSDL HĐT được phát triển trong môi trường mạng tạo thành mô hình cơ sở dữ liệu hướngđối tượng phân tán (CSDL HĐT PT). Trong CSDL HĐT PT, dữ liệu được phân bố trên một sốtrạm của mạng máy tính, các ứng dụng sẽ phải truy cập, xử lí dữ liệu tại các trạm khác nhau. Vớicác đặc trưng cơ bản của công nghệ hướng đối tượng như tính đóng gói, kế thừa, phân cấp lớp, vấnđề xử lí truy vấn trong CSDL HĐT PT phức tạp hơn nhiều so với các hệ thống cơ sở dữ liệu quanhệ. Một số kết quả nghiên cứu về xử lí truy vấn trong CSDL HĐT PT như trong [4, 5]. Để tối ưu hoá truy vấn phân tán thì phải hạn chế chi phí truyền tải dữ liệu giữa các trạm vìchi phí này thông thường là chi phí khá lớn. Có nhiều thuật toán lọc để hạn chế dữ liệu truyền trongđó có cơ chế lọc của bộ lọc Bloom [6]. Sử dụng bộ lọc Bloom để xử lí truy vấn phân tán trong cáchệ thống cơ sở dữ liệu quan hệ đã được đề cập trong các bài báo [7, 8]. Trong báo cáo này chúngtôi thảo luận về việc sử dụng bộ lọc Bloom để xử lí truy vấn có biểu thức đường dẫn trong CSDLHĐT PT nhằm mục đích giảm thiểu các chi phí truyền dữ liệu phân tán.Ngày nhận bài: 15/7/2015. Ngày nhận đăng: 10/11/2015.Liên hệ: Mai Thúy Nga, e-mail: ngamt@thanglong.edu.vn196 Xử lí truy vấn trong cơ sở dữ liệu hướng đối tượng phân tán sử dụng bộ lọc Bloom2. Nội dung nghiên cứu2.1. Cơ sở dữ liệu hướng đối tượng phân tán và biểu thức đường dẫn2.1.1. Cơ sở dữ liệu hướng đối tượng phân tán Khái niệm cơ bản nhất trong CSDL HĐT là đối tượng (object). Đối tượng biểu diễn mộtthực thể có thực trong hệ thống đang được mô hình hóa. Khác với đối tượng trong ngôn ngữ lậptrình hướng đối tượng chỉ tồn tại trong thời gian chương trình hoạt động, các đối tượng trong CSDLHĐT mang tính bền vững, được bảo toàn và được chia sẻ với nhiều chương trình, nhiều ứng dụngkhác nhau. Mỗi đối tượng có một định danh duy nhất được tạo ra bởi hệ thống. Các đối tượng làthể hiện của lớp, hay một lớp là khuôn mẫu để tạo ra các đối tượng. Phân cấp lớp được định nghĩađể chỉ ra mối quan hệ giữa các lớp khác nhau. Lớp là cấu trúc đóng gói các thuộc tính mô tả các đặc trưng, tính chất của đối tượng vàcác phương thức (hàm) mô tả các hành vi ứng xử của các đối tượng. Các thuộc tính trong một lớpđược chia thành hai loại: đơn giản và phức hợp. Thuộc tính đơn giản là thuộc tính có miền giátrị là các kiểu nguyên thủy như int, long, float, double, boolean, char, string . . . Thuộc tính phứchợp là thuộc tính có miền giá trị không phải là các kiểu nguyên thủy, mà là tham chiếu tới các đốitượng khác thông qua các định danh của chúng. Các phương thức trong một lớp cũng được chiathành hai loại: đơn giản và phức hợp. Phương thức đơn giản là phương thức khi thực hiện khônggọi các phương thức khác. Phương thức phức hợp là phương thức khi thực hiện gọi phương thứckhác trong cùng lớp đó hoặc các phương thức của lớp khác ...