Cải tiến thuật toán xử lý truy vấn trên cơ sở dữ liệu đồ thị Neo4j phân tán

Cơ sở dữ liệu đồ thị Neo4j được tạo được sự quan tâm lớn trong những năm gần đây nhờ khả năng giải quyết các bài toán liên quan đến mạng ngữ nghĩa và mạng xã hội với kích thước lớn. Một trong những giải pháp để xử lý dữ liệu lớn thường được áp dụng là lưu trữ và xử lý phân tán.
Nội dung trích xuất từ tài liệu:
Cải tiến thuật toán xử lý truy vấn trên cơ sở dữ liệu đồ thị Neo4j phân tánKỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019DOI: 10.15625/vap.2019.00010 CẢI TIẾN THUẬT TOÁN XỬ LÝ TRUY VẤN TRÊN CƠ SỞ DỮ LIỆU ĐỒ THỊ NEO4J PHÂN TÁN Phạm Hữu Mão, Ngô Thanh Hùng Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh phamhuumaoit@gmail.com, hungnt@uit.edu.vnTÓM TẮT: Cơ sở dữ liệu đồ thị Neo4j được tạo được sự quan tâm lớn trong những năm gần đây nhờ khả năng giải quyết các bàitoán liên quan đến mạng ngữ nghĩa và mạng xã hội với kích thước lớn. Một trong những giải pháp để xử lý dữ liệu lớn thường đượcáp dụng là lưu trữ và xử lý phân tán. Một số nghiên cứu về phân mảnh ngang cơ sở dữ liệu Neo4j đã được đề xuất. Tuy nhiên chưacó nghiên cứu về phân tán cơ sở dữ liệu Neo4j (phân tán cơ sở dữ liệu quan hệ là phân chia tập hợp các node và quan hệ thành cáctập con, mỗi tập con sẽ đặt tại một nút mạng, các tập con có thể có giao) và module xử lý truy vấn trên Neo4j phân tán ở mức độtrong suốt cao nhất. Nghĩa là người dùng không cần phải thay đổi ứng dụng (câu truy vấn trong ứng dụng) mà vẫn có thể truy vấnđến cơ sở dữ liệu phân tán giống như trước khi phân tán. Kiến trúc phân tán và thuật toán xử lý truy vấn Cypher trên cơ sở dữ liệuphân tán Neo4j đã được trình bày ở [1]. Thuật toán truy vấn này chỉ xử lý được ba mẫu câu truy vấn cơ bản trong Neo4j, nhưngđáp ứng được hầu hết các nhu cầu của các ứng dụng thực tế. Trong nghiên cứu này chúng tôi đề xuất cải tiến kiến trúc phân tán, vàcải tiến hiệu năng của thuật toán xử lý truy vấn Cypher nói trên. Thuật toán cải tiến cho thấy hiệu năng đều cao hơn hoặc bằng sovới thuật toán gốc trong tất cả các trường hợp thử nghiệm.Từ khóa: Neo4j, vertical partitioning model on Neo4j, Cypher query proccessing on vertical partitioning Neo4j, Phân tán Neo4j,Xử lý truy vấn Cypher trên Neo4j phân tán. I. GIỚI THIỆU Trong những năm gần đây, nghiên cứu về cơ sở dữ liệu đồ thị Neo4j đã giải quyết được rất nhiều vấn đề về lưutrữ và xử lý dữ liệu, trở thành vấn đề được chú trọng của các nhà nghiên cứu. [2] Khẳng định ưu thế của cơ sở dữ liệuđồ thị trong các ứng dụng liên quan đến mạng ngữ nghĩa và phân tích mạng xã hội.. [3] Nghiên cứu sử dụng cơ sở dữliệu đồ thị thay cho cơ sở dữ liệu quan hệ trong việc biểu diễn ontology đa ngành trong lĩnh vực lọc hóa dầu. [4] Sửdụng hệ quản trị cơ sở dữ liệu đồ thị Neo4j để lưu trữ dữ liệu về việc làm và các thông tin liên quan của sinh viên tốtnghiệp. [5] Đề xuất một mô hình mạng xã hội thời gian thực (time-varying social network model) để mô tả và truy vấnthông tin về con người và các hoạt động có liên quan trong thời gian thực. Tác giả đã sử dụng hệ quản trị cơ sở dữ liệuđồ thị Neo4j để thực nghiệm mô hình và chứng minh rằng nó hiệu quả hơn nhiều so với sử dụng hệ quản trị cơ sở dữliệu quan hệ. Bên cạnh đó, việc nghiên cứu các kỹ thuật phân mảnh cơ sở dữ liệu đồ thị cũng được triển khai. [6] Đề xuất mộtgiải thuật phân mảnh ngang động để giải quyết bài toán hiệu năng truy vấn đối với cơ sở dữ liệu đồ thị kích thước lớnvới hàm mục tiêu là tăng độ liên quan giữa các node trong cùng phân mảnh và giảm số lượng các cạnh bị cắt edge-cut(là các cạnh mà một node nằm ở phân mảnh này và node ở đầu kia thì nằm ở một phân mảnh khác). Thuật toán đượcthử nghiệm trên một hệ thống gồm nhiều hệ quản trị cơ sở dữ liệu đồ thị Neo4j kết nối với nhau qua hệ thống mạngtruyền thông. Mỗi hệ quản trị chứa đựng một phân mảnh ngang của cơ sở dữ liệu gốc, được tính toán nhờ vào thuậttoán đề xuất. Ƣu điểm của thuật toán là tự thích ứng với sự thay đổi của dữ liệu cũng như truy vấn của người dùng vàgiúp tăng tính cục bộ của các truy vấn duyệt đồ thị (duyệt trong một phân mảnh) từ đó tăng tốc hiệu năng thực thi vàhiệu quả sử dụng bộ nhớ. Bài báo [1] đề xuất một kiến trúc phân tán cho cơ sở dữ liệu đồ thị Neo4j phân tán và xâydựng một module xử lý truy vấn trên kiến trúc đó. Module xử lý truy vấn phân tán đạt mức độ trong suốt cao nhất –trong suốt phân mảnh, nghĩa là người dùng không cần phải thay đổi ứng dụng (câu truy vấn trong ứng dụng) mặc dù cơsở dữ liệu đã bị phân mảnh và phân tán trên một hệ thống các hệ quản trị Neo4j độc lập. Qua đó cho thấy ứng dụng cơ sở dữ liệu đồ thị Neo4j cũng như hệ quản trị cơ sở dữ liệu Neo4j phân tán hiệnđược quan tâm nghiên cứu. Tuy nhiên liên quan đến Neo4j phân tán hiện có ít các nghiên cứu xây dựng hệ xử lý truyvấn phân tán ứng với mức trong suốt phân mảnh còn rất ít (chỉ có [1]). Trong nghiên cứu này chúng tôi phân tích để cảitiến kiến trúc phân mảnh dọc và cải tiến thuật toán xử lý truy vấn Cypher trên hệ quản trị cơ sở dữ liệu Neo4j phân tánđược đề xuất ở [1]. ...