Tổng quan về Graph Database

Graph (Computer Science)

Một cách không chính thức, graph (đồ thị) là một tập các đối tượng gọi là đỉnh nối với nhau bởi các cạnh. Thông thường, đồ thị được vẽ dưới dạng một tập các điểm (đỉnh, nút) nối với nhau bởi các đoạn thẳng (cạnh). Tùy theo ứng dụng mà một số cạnh có thể có hướng.

Graph là một cách mô hình hoá trực tiếp hầu hết tất cả mọi vấn đề. Đối với phim ma trận ta có một graph tương ứng sau:

matrix-graph

Tại sao lại là graph database (GD)

Chúng ta đã quá quen với cách biểu diễn theo cơ sở dữ liệu quan hệ (RD) truyền thống, nhưng với những bài toán cần nhiều quan hệ việc sử dụng RD để lưu trữ không phải là một giải pháp hay vì :

  • Việc biểu diễn quan hệ dưới dạng bảng không phải là một cách làm trực quan.
  • Các phép join thường tốn rất nhiều chi phí

Trong GD quan hệ là những liên kết trực tiếp giữa các thực thể (các đỉnh). Do đó GD giúp trả lời rất nhiều câu hỏi liên quan đến truy vấn dữ liệu một cách hiệu quả hơn so với RD, đồng thời khả năng trực quan hoá dữ liệu của GD so với RD cũng tốt hơn rất nhiều.

Giả sử ta có một cơ sở dữ liệu quan hệ lưu trữ thông tin người dùng và các bạn bè của họ như sau:

friend-rd

Rất phức tạp và tốn nhiều chi phí nếu muốn trả lời các câu hỏi sau:

  • Ai là bạn của bạn Alice
  • Giả sử Alice không quen Bob, vậy họ phải thông qua những ai để có thể làm quen với nhau một cách nhanh nhất

Tuy nhiên GD trả lời câu hỏi trên một cách rất trực tiếp và đơn giản!

Neo4j

Neo4j là một trong những GD phổ biển nhất hiện nay. Neo4j hỗ trợ ngôn ngữ truy vấn Cypher, một ngôn ngữ rất trực quan trong việc truy vấn dữ liệu dưới dạng Graph.

Đỉnh trong Neo4j

  • được ký hiệu là (A)
  • có thể có nhiều thuộc tính dưới dạng key:value
  • có thể có một hoặc nhiều nhãn (B: Person) : B có nhãn là Person

Cạnh trong Neo4j

  • được ký hiệu là -[rel]-
  • có thể có nhiều thuộc tính dưới dạng key:value
  • có duy nhất một kiểu của cạnh : (a)-[rel:KNOW]-(b) mô tả a và b được liên kết với nhau bởi cạnh rel có kiểu là KNOW
  • có thể có hướng : (a)-[rel:KNOW]->(b)

Case Study

Case study trong bài viết này sử dụng dataset movielens http://grouplens.org/datasets/movielens/.

MovieLens bao gồm ba thực thể chính:

  • Movie : các bộ phim
  • Genre : thể loại phim
  • User : người sử dụng

Và hai loại cạnh sau:

  • HAS_GENRE : là cạnh nối giữa phim và genre mô tả thể loại phim. Ví dụ: (M:Movie)-[:HAS_GENRE]->(G:Genre) phim M có thể loại là G
  • RATED : là cạnh nối giữa phim và user mô tả user đánh giá phim. Ví dụ: (U:User)-[:RATED]->(M:Movie) người sử dụng U đánh giá phim M
    • stars : là thuộc tính của cạnh RATED mô tả đánh giá của người sử dụng (từ 1 đến 5 sao)

Screen Shot 2014-06-10 at 3.43.15 PMMô tả giữa User và các Movie được RATED bởi User đó

Câu hỏi của case study này là ta có bộ phim “Toy Story” với movie_id=1. Ta cần đưa ra một tập các movie liên quan đến phim “Toy Story”.

Hướng giải quyết :

  • tìm tập U các người dùng đã đánh giá phim “Toy Story” với số sao lớn hơn 3
  • tìm tập R các phim được đánh giá bởi U
  • xếp hạng R theo số lượng người sử dụng đánh giá

movie-graph

Toy story

Ta cùng lần lượt điểm qua những câu truy vấn cypher giúp giải quyết vấn đề trên :

  • MATCH (n:Movie{movie_id:1}) RETURN n : lấy ra phim toy story
  • MATCH (t:Movie{movie_id:1})<-[r:RATED]-(u:User) WHERE r.stars>3 RETURN count(u) : lấy số lượng những người sử dụng đánh giá phim toy story lớn hơn 3 sao
  • MATCH (t:Movie{movie_id:1})<-[r:RATED]-(u:User)-[r2:RATED]->(t2:Movie) WHERE r.stars>3 AND r2.stars>3 RETURN t2.name,count(t2) ORDER BY count(t2) DESC LIMIT 25 : lấy ra tập phim tương tự dựa trên lượt đánh gía của người sử dụng

Cài đặt và thử nghiệm

Để có thể thử nghiệm case study đã trình bày ở trên :

  • Ta tiến hành download Neo4j bản mới nhất trên trang chủ của Neo4j http://www.neo4j.org.
  • Download movielens db cho Neo4j từ link sau movielens.db.zip
  • Giải nén db vừa download về copy vào thư mục data/graph.db của Neo4j
  • Thực hiện khởi chạy Neo4j bằng cách gõ lệnh bin/neo4j start
  • Truy cập vào trang web : http://localhost:7474 để thực hiện việc thử nghiệm truy vấn trên dữ liệu movielens

Đồng thời bạn có thể gõ lệnh :play movie graph để có thể được hướng dẫn về việc xây dựng ứng dụng The Movie Graph cùng Neo4j

Screen Shot 2014-06-10 at 4.31.08 PM

Neo4j trong môi trường bigdata

Neo4j cung cấp một môi trường rất trực quan cho những ai muốn tìm hiểu và khai thác graph database. Nhưng khi lưu trữ graph bằng Neo4j thì toàn bộ graph phải nằm trên một máy duy nhất. Đây là nhược điểm rất lớn của Neo4j, điều này khiến việc lưu trữ một big graph bao gồm rất nhiều đỉnh và cạnh bằng Neo4j là rất khó khăn.

Tuy nhiên vào năm 2010 Google có publish một bài báo về Pregel một mô hình hiệu quả cho việc xử lý big graph. Sau đó hai năm, apache đưa ra thư viện mã nguồn mở mới cài đặt mô hình Pregel là Apache Giraph dựa trên hệ sinh thái Hadoop. Đây chính là giải pháp cho việc lưu trữ và xử lý cho các bài toán liên quan đến big graph (facebook) mà chúng tôi sẽ trình bày trong những bài viết sau.

Advertisements