Xử lý và tối ưu hóa truy vấn trong cơ sở dữ liệu hướng đối tượng phân tán

Trong Hình 3.6, thuật toán sinh ra các cây con cảm sinh, tính chi phí thực hiện từng cây và so sánh để tìm cây tối ưu có 1 đỉnh, 2 đỉnh,…, 20 đỉnh. Phương án tối ưu tìm được biểu diễn một trình tự thực hiện biểu thức đường dẫn: Mảnh F10 được truyền từ trạm 3 đến trạm 2, sau đó thực hiện kết nối F6 và F10 tại trạm 2, kết quả được truyền tới trạm 1, tiếp tục nối với F7 tại trạm 1,…

Bảng 3.4: So sánh PathExpOpt với các thuật toán khác

Thuật toán

Bộ dữ liệu 1	Bộ dữ liệu 2	Bộ dữ liệu 3	Bộ dữ liệu 4
Đồ thị truy vấn	7 đỉnh	10 đỉnh	15 đỉnh	20 đỉnh hình sao
PathExpOpt	43,016	134,017	40,262	150,641
Sun et al	45,066	158,073	65,534	229,634
Kim and Lee	44,214	142,425	52,215	180,974

Có thể bạn quan tâm!

Xem toàn bộ 136 trang tài liệu này.

Hình 3.7: Biểu đồ so sánh chi phí PathExpOpt với các thuật toán khác

So sánh chi phí thực hiện phương án tối ưu của thuật toán đề xuất và hai thuật toán của Sun và các cộng sự [52], Kim và Lee [34] trên cùng một số bộ dữ liệu. Thuật toán PathExpOpt có chi phí tốt nhất vì đã kết hợp các biểu thức đường dẫn

để thực hiện cũng như dùng bộ lọc Bloom để hạn chế việc truyền dữ liệu. Kết quả so sánh chi tiết như Bảng 3.4 và biểu diễn như Hình 3.7.

3.5. Kết luận chương 3

Tối ưu hóa truy vấn trong CSDL HĐT PT phức tạp hơn nhiều trong môi trường CSDL do các đặc tính của hướng đối tượng như đóng gói, kế thừa, phân cấp lớp. Một truy vấn với biểu thức đường dẫn sẽ liên quan đến nhiều lớp trong phân cấp lớp.

Bộ lọc Bloom được sử dụng như một cơ chế để tính toán chi phí và thực hiện việc truyền dữ liệu. 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, như vậy chi phí truyền sẽ giảm đi. Đặc biệt với các mảnh dữ liệu chỉ làm nhiệm vụ thực hiện phép kết nối ẩn trung gian mà không cần lấy ra thông tin gì thì bộ lọc Bloom thực sự hiệu quả vì chỉ cần gửi bộ lọc để lọc dữ liệu, không cần lấy các bộ dữ liệu đã lọc gửi trả lại để thực hiện phép kết nối dữ liệu. Luận án đề xuất thuật toán BloomOpt thực hiện việc tối ưu hóa kết nối hai lớp trong biểu thức đường dẫn bằng cách sử dụng bộ lọc Bloom.

Truy vấn với biểu thức đường dẫn qua nhiều lớp có thể biểu diễn bởi một đồ thị truy vấn. Đồ thị này có thể tách thành các đồ thị con cảm sinh, các đồ thị con cảm sinh này tương ứng với các truy vấn con. Luận án đề xuất thuật toán PathExpOpt theo hướng tiếp cận quy hoạch động tách bài toán thành nhiều bài toán nhỏ hơn, tương đương với việc tách đồ thị thành các đồ thị con. Mô hình chi phí được xây dựng giúp cho việc lựa chọn các bài toán con tối ưu.

Các kết quả đã được công bố trong các công trình (2) và (5).

KẾT LUẬN

Mục tiêu của luận án là nghiên cứu các vấn của bài toán đánh giá hiệu năng, thiết kế và tối ưu hóa truy vấn trong môi trường CSDL HĐT PT. Các đóng góp chính của luận án bao gồm:

 Đánh giá hiệu năng một số CSDL HĐT phổ biến như Db4o thông qua thư viện OO7 trên các tiêu chí chính: Tốc độ xử lí trong việc duyệt đối tượng, mức độ hiệu quả trong việc thay đổi đối tượng (tạo, xóa và cập nhật), hiệu quả của việc xử lý các loại câu truy vấn đối tượng.

 Đề xuất các thuật toán cho phân mảnh và cấp phát các lớp đối tượng: Thuật toán AttrFrag phân mảnh dựa trên tương quan thuộc tính và thuật toán FragAlloS phân mảnh và cấp phát đồng thời. Thuật toán FragAlloS là một thuật toán heuristic thực hiện cả phân mảnh và cấp phát với độ phức tạp chỉ tương đương các thuật toán phân mảnh và chưa thực hiện cấp phát.

 Đề xuất thuật toán BloomOpt truyền dữ liệu bằng bộ lọc Bloom để thực hiện truy vấn có chứa biểu thức đường dẫn và thuật toán PathExpOpt tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT. Thuật toán PathExpOpt là thuật toán quy hoạch động sử dụng cơ chế sinh cây con cảm sinh để tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT.

Các kết quả nghiên cứu của luận án đã được công bố trong các công trình (1), (2), (3), (4), và (5).

Bài toán xử lý và tối ưu hóa truy vấn trong CSDL HĐT PT rất phức tạp vì kết hợp giữa mô hình dữ liệu phân tán và mô hình hướng đối tượng. Thực tế không phổ biến các tập dữ liệu thử nghiệm chung cho mô hình này, đây là khó khăn lớn nhất khi giải quyết bài toán.

Nhìn vào xu hướng phát triển hiện nay, điện toán đám mây là một môi trường phân tán nổi trội, môi trường này sử dụng các máy chủ trung tâm từ xa và mạng internet để duy trì dữ liệu và các ứng dụng. Các hệ thống CSDL PT nói chung và CSDL HĐT PT nói riêng khi phát triển trong môi trường điện toán đám mây sẽ

đòi hỏi các kỹ thuật nâng cao về phân mảnh, cấp phát và sao chép. Những kỹ thuật này là một trong những hướng nghiên cứu tiếp theo của luận án.

Hơn nữa, một trong những xu hướng lớn nhất của khoa học dữ liệu là dữ liệu lớn (big data) với các loại dữ liệu có cấu trúc và dữ liệu không cấu trúc. NoSQL (Not Only SQL) là loại cơ sở dữ liệu hỗ trợ lưu trữ dữ liệu không cấu trúc. Trong danh sách các cơ sở dữ liệu NoSQL có sự góp mặt của các CSDL HĐT PT như Versant, Db4o, GemStone,… Như vậy CSDL HĐT PT trong môi trường dữ liệu lớn với các vấn đề như thiết kế phân tán, tối ưu hóa truy vấn cần được quan tâm nghiên cứu.

Tóm lại, từ các xu thế phát triển của khoa học dữ liệu và từ kết quả của luận án đặt ra các hướng nghiên cứu tiếp theo như sau:

 Thiết kế các thuật toán phân mảnh, cấp phát, tối ưu hóa truy vấn trong CSDL HĐT PT để thử nghiệm trên Hadoop nhằm nâng cao hiệu quả của thuật toán trong môi trường dữ liệu lớn trên điện toán đám mây.

 Nghiên cứu cách kết hợp giữa hai hướng tiếp cận dựa trên tương quan và heuristic dựa trên chi phí trong phân mảnh và cấp phát CSDL HĐT PT để đạt hiệu quả tốt hơn.

 Xây dựng các thuật toán heuristic dựa trên chi phí để tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT hiệu quả hơn, cải thiện độ phức tạp thuật toán hiện tại trong trường hợp xấu nhất (truy vấn hình sao).

 Nghiên cứu về tối ưu hóa biểu thức đường dẫn trong các trường hợp tổng quát hơn và nghiên cứu các dạng khác của truy vấn trong CSDL HĐT PT.

DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ

(1) Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng (2015), “Thuật toán phân mảnh dọc và cấp phát đồng thời trong Cơ sở dữ liệu hướng đối tượng phân tán”, Tạp chí Khoa học và công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, 53(3), tr. 265-276.

(2) Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng (2015), “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”, Tạp chí Khoa học, Trường Đại học Sư phạm Hà nội, 60(7A), tr. 196-203.

(3) Mai Thuy Nga, Doan Van Ban (2016), “ Heuristic algorithm for fragmentation

and allocation in distributed object-oriented database”, Journal of Computer Science and Cybernertics, Vietnam Academy of Science and Technology, 32(1), pp. 45-58.

(4) Mai Thúy Nga, Đoàn Văn Ban (2014), “Thuật toán Heuristic để phân mảnh và

cấp phát đồng thời trong Cơ sở dữ liệu hướng đối tượng phân tán”, Kỷ yếu Hội thảo Khoa học Quốc gia lần thứ XVII Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, Nhà xuất bản Khoa học và Kỹ thuật, Hà nội, tr. 318– 323.

(5) Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng (2015), “Tối ưu hóa truy vấn

trong Cơ sở dữ liệu hướng đối tượng phân tán”, Kỷ yếu Hội thảo Khoa học Quốc gia lần thứ XVIII Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, Nhà xuất bản Khoa học và Kỹ thuật, Hà nội, tr. 318–323.

TÀI LIỆU THAM KHẢO

Tiếng Việt:

1. Đoàn Văn Ban (2012), Giáo trình các mô hình Cơ sở dữ liệu hướng đối tượng, Viện Công nghệ thông tin.

2. Trương Ngọc Châu (2011), Tối ưu hóa truy vấn dữ liệu hướng đối tượng, Luận án Tiến sĩ Toán học, Viện công nghệ Thông tin.

Tiếng Anh:

3. Al-Sayyed R.M., Al Zaghoul F.A., Suleiman D. et al. (2014). A New Approach for Database Fragmentation and Allocation to Improve the Distributed Database Management System Performance. J Softw Eng Appl, 7(11), 891.

4. Ozsu, M. T. and Valduriez, P. (2011), Principles of Distributed Database Systems, Springer.

5. Navathe S., Ceri S., Wiederhold G. et al. (1984). Vertical partitioning algorithms for database design. ACM Trans Database Syst, 9(4), 680–710.

6. Sarhan A. (2009). A new allocation technique for methods and attributes in distributed object-oriented databases using genetic algorithms. Int Arab J Inf Technol, 6(1), 17–26.

7. Singh A. and Kahlon K.S. (2009). Non-replicated dynamic data allocation in distributed database systems. IJCSNS Int J Comput Sci Netw Secur, 9(9), 176–180.

8. Ulus T. and Uysal M. (2003). Heuristic approach to dynamic data allocation in distributed database systems. Pak J Inf Technol, 2(3), 231–239.

9. Wasa K., Arimura H., and Uno T. (2014). Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph. Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings. Springer International Publishing, Cham, 94–102.

10. Abdalla H.I. (2012). A New Data Re-Allocation Model for Distributed Database Systems. Int J Database Theory Appl, 5(2), 45–60.

11. Anderson T.L., Berre A.J., Mallison M. et al. (1990). The hypermodel benchmark.

Advances in Database Technology—EDBT’90. Springer, 317–331.

12. Baião F. and Mattoso M. (1998). A mixed fragmentation algorithm for distributed object oriented databases. Proc Int’l Conf Computing and Information (ICCI’98), Winnipeg, 141–148.

13. Barker K. and Bhar S. (2001). A graphical approach to allocating class fragments in distributed objectbase systems. Distrib Parallel Databases, 10(3), 207–239.

14. Bellatreche L., Karlapalem K., and Li Q. (1998). Complex Methods and Class Allocation in Distributed OODBSs. OOIS’98. Springer, 239–256.

15. Bernstein P.A., Goodman N., Wong E. et al. (1981). Query processing in a system for distributed databases (SDD-1). ACM Trans Database Syst TODS, 6(4), 602–625.

16. Bloom B.H. (1970). Space/time trade-offs in hash coding with allowable Replication. Databases and Applications, 116–121.

21. Darabant A.S., Campan A., and Navroschi-Szasz A. (2004). Optimal Class Fragmentation Ordering in Object Oriented Databases. Stud Univ Babes Bolyai Inform, 49(1), 45–54.

22. (Editor) R.G.C., (Editor) D.K.B., (Editor) M.B. et al. (2000). The Object Data Standard: ODMG 3.0 (The Morgan Kaufmann Series in Data Management Systems)..

23. Epstein R., Stonebraker M., and Wong E. (1978). Distributed query processing in a relational data base system. Proceedings of the 1978 ACM SIGMOD international conference on management of data, ACM, 169–180.

24. Ezeife C.I. and Barker K. (1998). Distributed Object Based Design: Vertical Fragmentation of Classes. Distrib Parallel Databases, 6(4), 317–350.

25. Ezeife C.I. and Barker K. (1995). A comprehensive approach to horizontal class fragmentation in a Distributed Object Based System. Distrib Parallel Databases, 3(3), 247–272.

26. Fung C.-W., Karlapalem K., and Li Q. (1997). Cost-Driven Evaluation of Vertical Class Partitioning in Object-Oriented Databases. DASFAA, 11–20.

27. Goli M. and Rankoohi S.M.T.R. (2012). A new vertical fragmentation algorithm based on ant collective behavior in distributed database systems. Knowl Inf Syst, 30(2), 435–455.

28. Gope D.C. (2012). Dynamic data allocation methods in distributed database system.

Am Acad Sch Res J, 4(6), 1.

29. Graham J. and Alves-Foss J. (2003). Efficient Allocation in Distributed Object Oriented Databases. ISCA PDCS, 471-.

30. Hevner A.R. and Yao S.B. (1979). Query processing in distributed database system.

IEEE Trans Softw Eng, (3), 177–187.

31. Jenq B.P., Woelk D., Kim W. et al. (1990). Query processing in distributed ORION.

International Conference on Extending Database Technology, Springer, 169–187.

32. John R. and Saravanan V. (2008). Vertical Partitioning in Object Oriented Databases Using Intelligent Agents. IJCSNS, 8(10), 205.

33. Khan S.I. and Hoque A. (2010). A new technique for database fragmentation in distributed systems. Int J Comput Appl, 5(9), 20–24.

34. Kim H. and Lee S. (1994). Tree query optimization in distributed object-oriented databases. EUROMICRO 94. System Architecture and Integration. Proceedings of the 20th EUROMICRO Conference., IEEE, 45–52.

35. Koutris P. (2011), Bloom filters in distributed query execution, University of Washington.

36. Le Gall F. (2014). Powers of tensors and fast matrix multiplication. Proceedings of the 39th international symposium on symbolic and algebraic computation, ACM, 296–303.

37. Lee S.-M., Ha Y., and Park H.-S. (2009). Allocation of classes in distributed object- oriented databases. Software Engineering, Artificial Intelligences, Networking and Parallel/Distributed Computing, 2009. SNPD’09. 10th ACIS International Conference on, IEEE, 237–242.

38. Ma H., Schewe K.-D., and Kirchberg M. (2006). A heuristic approach to vertical fragmentation incorporating query information. Databases and Information Systems, 2006 7th International Baltic Conference on, IEEE, 69–76.

39. Marwa F.F., Ali I.E., and Hesham A.A. (2008). A heuristic approach for horizontal fragmentation and alllocation in DOODB. Proc INFOS2008, 9–16.

40. McCormick Jr W.T., Schweitzer P.J., and White T.W. (1972). Problem decomposition and data reorganization by a clustering technique. Oper Res, 20(5), 993–1009.

41. Melton J. (2002), Advanced SQL 1999: Understanding Object-Relational, and Other Advanced Features, Elsevier Science Inc.

42. Mitchell G., Dayal U., and Zdonik S.B. (1993). Control of an extensible query optimizer: A planning-based approach. VLDB, 517–528.

43. Navathe S.B. and Ra M. (1989). Vertical partitioning for database design: a graphical algorithm. SIGMOD Rec, 18(2), 440–450.

44. Nierstrasz O. and Tsichritzis D. (1985). An object-oriented environment for OIS applications. Proceedings of the 11th international conference on Very Large Data Bases - Volume 11, Stockholm, Sweden, VLDB Endowment, 335–345.