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

Chia sẻ: Y Y | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

41
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

JOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1075.2015-0067 Educational Sci., 2015, Vol. 60, No. 7A, pp. 196-203 This paper is available online at http://stdb.hnue.edu.vn 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 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 CSDL hướ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ồn tạ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ính củ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ới cá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 quan hệ. 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ác hệ 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úng tô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 CSDL HĐ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.vn 196
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 2. Nội dung nghiên cứu 2.1. Cơ sở dữ liệu hướng đối tượng phân tán và biểu thức đường dẫn 2.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ột thự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ập trì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 CSDL HĐ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ụng khá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ức hợ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 đối tượ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 chia thà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ông gọ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ức khác trong cùng lớp đó hoặc các phương thức của lớp khác. CSDL HĐT phát triển trong môi trường mạng hình thành hệ CSDL hướng đối tượng phân tán. Phần lớn các hệ quản trị CSDLHĐT PT đều theo kiến trúc client/server. Với các đặc trưng của mô hình đối tượng, kiến trúc các hệ quản trị CSDL HĐT PT thường phức tạp hơn, các vấn đề phức tạp cần xem xét đó là [3]: - Các đối tượng đóng gói dữ liệu và phương thức, vậy cần xác định đơn vị truyền giao giữa client và server. Đơn vị này có thể là một trang, một đối tượng hoặc một nhóm các đối tượng. Đối tượng không phải dữ liệu thụ động, và cần xét đến các vị trí, nơi các phương thức của đối tượng được thực thi. - Trong các hệ client/server quan hệ, client chỉ đơn giản gửi các truy vấn đến các server, server thực hiện chúng rồi trả kết quả về cho client. Điều này được gọi là chuyển gửi chức năng để xử lí. Trong các hệ client/server đối tượng, đây không phải là cách tốt nhất bởi vì quá trình duyệt qua các cấu trúc đối tượng phức hợp của chương trình ứng dụng có thể chỉ ra rằng dữ liệu phải được chuyển qua bên client. Vì dữ liệu được nhiều client dùng chung, quản lí bộ đệm lưu trữ (cache) bên client để đảm bảo nhất quán dữ liệu là vấn đề quan trọng. - Đối tượng có thể thuộc loại phức hợp, nhiều thành phần, có khả năng phải gửi trước các đối tượng thành phần mỗi khi có một đối tượng yêu cầu. Các hệ client/server thông thường không phải gửi trước dữ liệu, nhưng có thể các hệ client/server đối tượng sẽ phải chọn giải pháp gửi trước dữ liệu. Nhóm quản trị CSDL đối tượng (Object Database Management Group – ODMG) đề xuất một chuẩn CSDL đối tượng, phiên bản mới nhất là ODMG 3.0 [9]. ODMG 3.0 định nghĩa các khái niệm, các nghi thức giao tiếp chung giữa các hệ CSDL và cung cấp các đặc tả cơ bản nhằm hỗ trợ cho các hệ quản trị CSDL khả năng chia sẻ dữ liệu, tính khả chuyển (portable) và các thao tác truy vấn cơ bản. Chuẩn này gồm 3 thành phần: ngôn ngữ định nghĩa đối tượng ODL (Object Definition Language), ngôn ngữ truy vấn dữ liệu OQL (Object Query Language) và các liên kết với các ngôn ngữ lập trình hướng đối tượng. 197
Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng 2.1.2. Truy vấn có biểu thức đường dẫn Các truy vấn trong CSDL hướng đối tượng được biểu diễn bởi ngôn ngữ OQL, OQL là ngôn ngữ mở rộng và kế thừa từ ngôn ngữ SQL, ngôn ngữ truy vấn chuẩn của CSDL quan hệ. Thiết kế của OQL ở dạng hàm, kết quả của truy vấn có kiểu, điều này cho phép kết quả truy vấn này lại là đầu vào cho một truy vấn khác, vì vậy có thể biểu diễn các truy vấn phức tạp. Khi thực hiện truy vấn trong CSDL hướng đối tượng, nếu các lớp có các thuộc tính phức hợp sẽ dẫn dắt truy vấn tới các đối tượng lồng nhau theo một biểu thức đường dẫn. Ví dụ lược đồ cơ sở dữ liệu gồm bốn lớp: CanBoNghienCuu (Cán bộ nghiên cứu), CoQuan (Cơ quan), DiaChi (Địa chỉ), ThanhPho (thành phố). Lớp CanBoNghienCuu có thuộc tính coQuan là một tập đối tượng của lớp CoQuan, lớp CoQuan có thuộc tính diaChi là một đối tượng của lớp DiaChi, lớp DiaChi có thuộc tính thanhPho là một đối tượng của lớp ThanhPho. Giả sử truy vấn ở đây là liệt kê họ tên các cán bộ nghiên cứu trong thành phố Hà Nội và có thể viết dưới dạng: select c.hoTen from CanBoNghienCuu as c where c.coQuan.diaChi.thanhPho.ten = ”Hà Nội” Hình 1. Minh hoạ biểu thức đường dẫn c.coQuan.diaChi.thanhPho.ten là một biểu thức đường dẫn hay còn gọi là nối ẩn. Mỗi đối tượng của lớp có một định danh duy nhất được hệ thống khởi tạo, các nối ẩn được thực hiện thông qua các định danh này. Biểu thức đường dẫn được minh họa như hình 1. Biểu thức đường dẫn có thể là trị đơn nếu mỗi thành phần của nó đều là trị đơn, ngược lại nếu có ít nhất một thành phần là trị tập thì toàn bộ biểu thức là trị tập. Tối ưu hoá biểu thức đường dẫn cũng là một mục tiêu trong xử lí truy vấn. 2.2. Bộ lọc Bloom 2.2.1. Cấu trúc bộ lọc Bloom Bộ lọc Bloom được giới thiệu trong [6], là một cấu trúc dữ liệu xác suất để kiểm tra xem một phần tử có nằm trong một tập hợp hay không. Cấu trúc của một bộ lọc Bloom bao gồm: - Một dãy gồm n bit, được khởi tạo tất cả các giá trị là 0. - Một tập các hàm băm h1 , h2 , hk . Mỗi hàm băm sẽ ánh xạ các giá trị khóa vào một giá trị trong khoảng từ 1 đến n, tương ứng bit của bộ lọc. - Một tập S gồm m giá trị khóa. Với mỗi giá trị khóa k trong S: băm nó với các hàm băm, hàm băm thứ i có giá trị hi (k), thiết lập bit thứ hi (k) của bộ lọc Bloom thành giá trị 1. Chức năng của bộ lọc Bloom là xác định một phần tử x có thuộc tập S hay không. Nó được dùng là bước tiền xử lí của quá trình tìm kiếm. Nếu sau khi lọc qua bộ lọc Bloom trả về kết quả 198
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 “không” thì không cần thực hiện việc tìm kiếm nữa, nếu trả về kết quả “có thể có” thì thực hiện tìm kiếm. Để xác định một phần tử x bất kì có thuộc tập S hay không, chúng ta cũng tính toán k giá trị là h1 (x), ..., hk (x) từ x qua k hàm băm. Nếu k bit trong vector n-bit tại các vị trí tương ứng là h1 (x), h2 (x), . . . , hk (x) đều có giá trị là 1 thì x “có thể” có trong tập S với một xác suất nào đó, còn nếu chỉ cần ít nhất 1 bit có giá trị là 0 thì khẳng định là x không thuộc tập S. Chúng ta chỉ có thể khẳng định là x “có thể” thuộc tập S là bởi vì trong vector bit, 1 bit có thể được gán giá trị là 1 nhiều lần bởi nhiều phần tử trong S khi khởi tạo bộ lọc. Chỉ cần một bit 0 chúng ta có thể khẳng định x không thuộc S bởi vì nếu x thuộc S thì tất cả k bit tương ứng sẽ được gán là 1 khi khởi tạo bộ lọc với phần tử x đó. Ví dụ: - Bộ lọc Bloom gồm 9 bit, ban đầu gán giá trị tất cả các bit bằng 0. - Sử dụng hai hàm băm: Hàm thứ nhất h1 (k) lấy các giá trị tại các vị trí lẻ (tính từ trái sang) của k khi biểu diễn sang hệ nhị phân, chuyển về giá trị thập phân rồi chia dư cho 9. Hàm h2 (k) tương tự nhưng lấy giá trị tại các vị trí chẵn. - S = {23, 147, 352} - Quá trình xây dựng bộ lọc Bloom được minh hoạ như Bảng 1. - Nếu x = 15, biểu diễn x nhị phân là 1111, h1 (x) = h2 (x) = 3. Tại bit số 3 của bộ lọc Bloom giá trị là 0 nên x chắc chắn không thuộc S. Bảng 1. Minh hoạ xây dựng bộ lọc Bloom Biểu diễn nhị Bộ lọc Bước h1 (k) h2 (k) phân của k Bloom Khởi tạo 000000000 k = 23 10111 7 1 010000010 k = 147 10010011 0 (9 mod 9) 5 110001010 k = 352 101100000 6 (24 mod 9) 4 110011110 2.2.2. Phân tích sai số Với một bộ lọc có thể xảy ra hai lỗi sau: - Lỗi dương tính sai (false positive): Kiểm tra qua bộ lọc là có nhưng tìm kiếm thực thì lại không có. - Lỗi âm tính sai (false negative): Kiểm tra qua bộ lọc là không có nhưng tìm kiếm thực thì lại có. Với bộ lọc Bloom sẽ không có khả năng xảy ra lỗi false negative mà chỉ có thể gặp phải lỗi false positive với xác suất rất nhỏ. Xác suất gặp phải lỗi false positive phụ thuộc vào mật độ các bit có giá trị 1 và số các hàm băm. 1 Xác suất để một bit ngẫu nhiên của mảng n bit được gán giá trị 1 bởi hàm băm là , xác n 1 xuất để bit đó không được gán giá trị 1 là (1 − ). Xác suất để bit đó không được gán giá trị 1 bởi n 1 k bất kì hàm băm nào là (1 − ) trong đó k là số các hàm băm. Với m giá trị khóa xác suất để bit n 1 mk 1 đó vẫn có giá trị 0 là (1 − ) , và xác suất để bit đó được thiết lập thành 1 là 1 − (1 − )mk . n n 199
Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng Xét quá trình kiểm tra một phần tử có nằm trong một tập hợp hay không. Thuật toán kiểm tra k vị trí trong mảng xem chúng có bằng 1 hay không, xác suất tất cả chúng đều bằng 1 là 1 km (1 − [1 − ]mk )k ≈ (1 − e− n )k với n rất lớn. Xác suất này không phụ thuộc vào phần tử được n kiểm tra nên được gọi là xác suất false positive. Xác xuất false positive có thể giảm xuống nếu chọn giá trị n, k, và m thích hợp. Giá trị n cần phải khá lớn so với m, xác xuất này còn có thể giảm n nếu tăng số hàm băm. Trong trường hợp tốt nhất, giá trị k tối ưu là k = ln 2, khi đó xác suất m nin2 minp false positive được cực tiểu hóa theo k và sẽ là p = 2−k = 2− m ⇒ n = − . Nghĩa là để (in2)2 xác suất false positive là hằng số cố định, kích thước của mảng là tuyến tính với số phần tử của tập hợp. 2.3. Sử dụng bộ lọc Bloom trong xử lí truy vấn có biểu thức đường dẫn 2.3.1. Mô tả thuật toán Chúng ta sẽ mô tả thuật toán sử dụng bộ lọc bloom để xử lí truy vấn có biểu thức đường dẫn giữa hai lớp. Giả sử lớp Ci có một thuộc tính ak là một đối tượng của lớp Cj , lớp Ci đặt tại trạm S, lớp Cj đặt tại trạm R. Dễ nhận thấy rằng kích thước một đối tượng của lớp Cj nhỏ hơn kích thước một đối tượng lớp Ci . Giả sử có truy vấn chứa biểu thức đường dẫn từ lớp Ci sang lớp Cj . Gọi chi phí truyền một đơn vị dữ liệu từ trạm S đến trạm R là cost(S, R), giả sử chi phí truyền này có tính đối xứng, nghĩa là cost(S, R) = cost(R, S). Ý tưởng ở đây là thay vì truyền toàn bộ các đối tượng của Cj từ S đến R đề kết hợp với Ci (hoặc ngược lại), chúng ta sẽ lọc một số đối tượng của Cj mà cần thiết cho việc kết nối với Ci . Như vậy khối lượng dữ liệu được truyền đi sẽ giảm đáng kể và đồng nghĩa với chi phí truyền dữ liệu sẽ giảm. Cơ chế lọc sẽ được thực hiện bởi bộ lọc Bloom. Có ba trường hợp xảy ra: Truy vấn xảy ra tại trạm S (là trạm chứa Ci ), truy vấn xảy ra tại trạm R (là trạm chứa Cj ), truy vấn xảy ra tại một trạm khác cả S và R. Chúng ta sẽ xét lần lượt từng trường hợp. Trường hợp 1: Truy vấn tại trạm S - Xây dựng bộ lọc Bloom cho tất cả các đối tượng thuộc lớp Ci theo giá trị thuộc tính ak , gọi là BF (Ci ). - Gửi BF (Ci ) đến R (trạm chứa Cj ), BF (Ci ) được sử dụng để lọc các đối tượng của Cj . - Gửi các đối tượng của Cj mà thỏa mãn điều kiện lọc ở trên đến S. - Thực hiện việc truy vấn từ các đối tượng của Ci và Cj tại S. Algorithm1 Case1(Ci , Cj , R, S) BF (Ci ) = createBloomFilter(Ci , ak ); send(BF (Ci ), S, R); Cj′ = filter(Cj , BF (Ci )); send(Cj′ , R, S); result = join(Ci , Cj ); return result; Trường hợp 2: Truy vấn tại trạm R - Xây dựng bộ lọc Bloom cho tất cả các đối tượng thuộc lớp Cj theo giá trị thuộc tính định danh, gọi là BF (Cj ). 200
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 - Gửi BF (Cj ) đến S (trạm chứa Ci ), BF (Cj ) được sử dụng để lọc các đối tượng của Ci . - Gửi các đối tượng của Ci mà thỏa mãn điều kiện lọc ở trên đến R. - Thực hiện việc truy vấn từ các đối tượng của Ci và Cj tại R. Algorithm2 Case2(Ci , Cj , R, S) BF (Cj ) = createBloomFilter(Ci , oid(Cj )); send(BF (Cj ), R, S); Ci′ = filter(Ci , BF (Ci )); send(Ci′ , S, R); result = join(Ci′ , Cj ); return result; Trường hợp 3: Truy vấn tại trạm không chứa cả Ci và Cj , giả sử là trạm P (P 6= S, P 6= R) - So sánh chi phí để truyền một đơn vị dữ liệu trong 3 trường hợp: + (a) cost(S, R) + cost(R, P ) + (b) cost(R, S) + cost(S, P ) + (c) cost(S, P ) + cost(R, P ) - Nếu chi phí nhỏ nhất là trường hợp (a), thực hiện các bước như trường hợp 1, sau đó truyền kết quả tử S đến P . - Nếu chi phí nhỏ nhất là trường hợp (b), thực hiện các bước như trường hợp 2, sau đó truyền kết quả tử R đến P . - Nếu chi phí nhỏ nhất là trường hợp (c). + Nếu cost(S, P ) ⇐ cost(R, P ) Xây dựng bộ lọc Bloom cho tất cả các đối tượng thuộc lớp Ci theo giá trị thuộc tính ak, gọi là BF (Ci ). Gửi BF (Ci ) đến P, rồi từ P gửi tiếp BF (Ci ) đến R. BF (Ci ) được sử dụng để lọc các đối tượng của Cj . Gửi các đối tượng của Cj mà thỏa mãn điều kiện lọc ở trên từ R đến P , rồi từ P đến S. Thực hiện việc truy vấn từ các đối tượng của Ci và Cj tại S. Truyền kết quả từ S về P . + Nếu cost(S, P ) > cost(R, P ). Xây dựng bộ lọc Bloom cho tất cả các đối tượng thuộc lớp Cj theo giá trị thuộc tính định danh, gọi là BF (Cj ). Gửi BF (Cj ) đến P, rồi từ P gửi tiếp BF (Cj ) đến S. BF (Cj ) được sử dụng để lọc các đối tượng của Ci . Gửi các đối tượng của Ci mà thỏa mãn điều kiện lọc ở trên từ S đến P , rồi từ P đến R. Thực hiện việc truy vấn từ các đối tượng của Ci và Cj tại R. Truyền kết quả từ R về P . Algorithm3 Case3(Ci , Cj , R, S, P ) cost1 = cost(S, R) + cost(R, P ) cost2 = cost(R, S) + cost(S, P ) cost3 = cost(S, P ) + cost(R, P ) cost = min(cost1, cost2, cost3) if (min == cost1) { result = case1(Ci , Cj , R, S); 201
Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng send(result, S, P ) } if (min == cost2) { result = case2(Ci , Cj , R, S); send(result, R, P ) } if (min == cost3) if (cost(S, P ) ⇒ cost(R, P )) { BF (Ci ) = createBloomFilter(Ci , ak); send(BF (Ci ), S, P ); send(BF (Ci ), P, R); Cj′ = filter(Cj , BF (Ci )); send(Cj′ , R, P ); send(Cj′ , P, S); result = join(Ci , Cj′ ); } else { BF (Cj ) = createBloomFilter(Cj , oid(Cj )); send(BF (Cj ), R, P ); send(BF (Ci ), P, S); Ci′ = filter(Ci , BF (Cj )); send(Ci′ , S, P ); send(Ci′ , P, R); result = join(Ci′ , Cj , R); send(result, R, P ); } 2.3.2. Thảo luận về các tham số mlnp Trong phần 3.2 chúng ta đã phân tích sai số và có công thức n = − . Khi chọn p là (ln2)2 một sai số cố định có giá trị đủ bé thì kích thước bộ lọc Bloom n tuyến tính với số lượng các giá trị khóa, trong trường hợp này là số lượng đối tượng của lớp cần xây dựng bộ lọc Bloom (Ci hoặc Cj ). Bộ lọc Bloom có thể xây dựng một lần cho mỗi lớp và sử dụng nhiều lần khi có nhiều kết nối với các lớp khác nhau. Khi chi phí giao tiếp đường truyền càng lớn thì thuật toán càng hiệu quả vì giảm một cách đáng kể chi phí truyền dữ liệu. Chi phí giảm này chính là tích của chi phí truyền một đơn vị dữ liệu và tổng kích thước tất cả các đối tượng mà bị loại ra (khi thử với bộ lọc Bloom). 3. Kết luận Bộ lọc Bloom là một cơ chế để kiểm tra sự có mặt của một phần tử trong một tập hợp, với bộ lọc Bloom thay vì gửi toàn bộ dữ liệu chúng ta chỉ gửi đại diện của nó đến nơi cần kiểm tra. Bài báo đề xuất một phương pháp sử dụng bộ lọc Bloom để xử lí truy vấn có biểu thức đường dẫn giữa hai lớp. Với truy vấn xảy ra tại các vị trí khác nhau, chúng tôi đã cố gắng lựa chọn một cách truyền dữ liệu mà chi phí truyền thấp nhất. 202
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 Bài báo mới dừng lại ở việc xét truy vấn đường dẫn giữa hai lớp, một cơ sở để mở rộng cho truy vấn với biểu thức đường dẫn qua nhiều lớp. Với biểu thức đường dẫn qua nhiều lớp chúng ta sẽ phải quan tâm đến việc duyệt biểu thức đường dẫn, cách duyệt đơn giản nhất là duyệt tuần tự. Hơn nữa để tối ưu hóa truy vấn phải tìm cách tối ưu hóa cục bộ tại mỗi trạm. Kết hợp tối ưu hóa cục bộ tại mỗi trạm và tối ưu hóa việc truyền dữ liệu là hướng nghiên cứu tiếp theo của chúng tôi. TÀI LIỆU THAM KHẢO [1] Oscar Nierstrasz and Dennis Tsichritzis, 1986. An object-oriented environment for OIS applications. In Proceedings of the 11th international conference on Very Large Data Bases, Vol. 11, pp.335-345. [2] David L. Spooner, 1986. An object-oriented data management system for mechanical CAD. In Proceedings on the 1986 international workshop on Object-oriented database systems (OODS ’86), pp. 233-234. [3] Ozsu M. T. and Valduriez P., 2011. Principles of Distributed Database Systems. Third Edition, Springer, New York. [4] G. Graefe and D. Maier, 1988. Query optimization in object-oriented database systems: A prospectus. In Lecture notes in computer science on Advances in object-oriented database systems, K. R. Dittrich (Ed.). Springer-Verlag New York, pp. 358-363. [5] Hyeokman Kim, Sukho Lee, 1994. Tree query optimization in distributed object-oriented databases. EUROMICRO 94. System Architecture and Integration. Proceedings of the 20th EUROMICRO Conference, pp. 45-52. [6] Bloom, B. H., 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, vol.13, no. 7, pp. 422–426. [7] Paraschos Koutris, 2008. Bloom Filters in Distributed Query Execution. CSE 544 Project, University of Washington. [8] Sukriti Ramesh, Odysseas Papapetrou, Wolf Siberski, 2009. Optimizing Distributed Joins with Bloom Filters. Distributed Computing and Internet Technology, vol. 5375, pp 145-156. [9] Mark Berler, et al., 1999. The Object Data Standard: ODMG 3.0. Morgan Kaufmann Publishers. ABSTRACT Query processing in a distributed Object-oriented database using a Bloom filter The objective of query processing in a distributed database is to find a strategy to execute queries in a way that minimizes the value of the cost function. Calculated cost here consists of input cost, CPU cost and communication cost, of which the communication cost is usually the biggest. Query processing in an object-oriented database will bring forth more complex problems due to the characteristics of object-orientation, which are packaging, inheritance and class hierarchy. This paper presents an algorithm using a Bloom filter to reduce the cost of communication in the process of executing a database query in a distributed object-oriented database. Keywords: Object-Oriented Database, Distributed Database, Query Processing, Bloom Filter. 203