BDI302c - Phần 13: Cơ sở dữ liệu đồ thị và nền tảng xử lý đồ thị

Đáp án đúng: "match p=shortestPath((a)-[:TO*]->(p)) return p". Trong Cypher, ngôn ngữ truy vấn của Neo4j, hàm shortestPath nhận một mẫu đường đi có độ dài biến thiên và trả về một đường ngắn nhất giữa hai nút; ký hiệu [:TO*] nghĩa là đi qua một hoặc nhiều quan hệ loại TO, còn biến p được gán cho cả đường đi để trả về. Phương án "match p=(a)-[:TO*]->(p) return p" thiếu hàm shortestPath nên trả về mọi đường đi có thể giữa hai nút, không chỉ đường ngắn nhất, và trên đồ thị lớn số đường này có thể bùng nổ. Phương án "match p=(a)-[:TO*1..5]->(p) return p" chỉ giới hạn độ dài từ 1 đến 5 bước, vẫn liệt kê mọi đường trong giới hạn đó chứ không chọn đường ngắn nhất. Còn "shortestPath(a TO P)" không phải câu lệnh Cypher hợp lệ vì thiếu mệnh đề match, thiếu cú pháp nút trong ngoặc tròn và quan hệ trong ngoặc vuông. Lưu ý các truy vấn trong đề viết rút gọn: chúng dùng p vừa làm tên đường đi vừa làm tên nút đích, trên Neo4j thật sẽ báo lỗi biến đã khai báo, nên khi viết thật cần đặt tên nút khác, nhưng ý của từng phương án vẫn đọc được như trên.

Đáp án đúng: "To import structured CSV data". Trong Neo4j, mệnh đề LOAD CSV WITH HEADERS đọc một tệp CSV, coi dòng đầu là tên cột và trả mỗi dòng sau thành một bản ghi dạng map, nhờ đó có thể viết tiếp CREATE hoặc MERGE để tạo nút và quan hệ từ dữ liệu bảng, tức là nạp dữ liệu có cấu trúc vào đồ thị. "To backup graph data" sai vì sao lưu cơ sở dữ liệu Neo4j dùng công cụ quản trị như neo4j-admin dump hoặc backup, không dùng một mệnh đề truy vấn đọc tệp. "To export results to CSV" ngược chiều: mệnh đề này đọc dữ liệu vào chứ không ghi kết quả ra; xuất CSV phải dùng chức năng tải xuống của trình duyệt Neo4j hoặc thủ tục của thư viện APOC. "To visualize graphs" là việc của Neo4j Browser hay Bloom khi hiển thị kết quả truy vấn, không phải tác dụng của việc nạp tệp.

Đáp án đúng: "MATCH p = shortestPath((from)-[:TO*]->(to)) WITH REDUCE(dist = 0, rel in rels(p) | dist + toInt(rel.dist)) AS distance RETURN path, distance". Trong Cypher của Neo4j, shortestPath tìm đường ngắn nhất qua các quan hệ TO với độ dài thay đổi (dấu sao), sau đó rels(p) lấy danh sách các cạnh trên đường p và REDUCE duyệt từng cạnh, cộng dồn thuộc tính dist (đã đổi sang số nguyên bằng toInt) vào biến tích luỹ bắt đầu từ 0; kết quả là tổng khoảng cách, tức trọng số của đường đi. "MATCH (a)-[:TO]->(b) RETURN path" chỉ khớp đúng một cạnh giữa hai nút, không có hàm tìm đường ngắn nhất và không tính trọng số nào. "MATCH (n)-[r]-() RETURN REDUCE(dist=0, r in r | dist + 1)" chỉ cộng 1 cho mỗi quan hệ nên đếm số cạnh, bỏ qua thuộc tính khoảng cách và cũng không có đường đi nào. "MATCH p=(a)-[:TO*]->(b) RETURN reduce(p)" gọi reduce thiếu biến tích luỹ và biểu thức cộng dồn nên không hợp lệ, và mẫu này trả mọi đường chứ không chọn đường ngắn nhất.

Đáp án đúng: "Neo4j". Neo4j là cơ sở dữ liệu đồ thị (graph database) tiêu biểu: lưu dữ liệu thành các nút (node) và quan hệ (relationship) có hướng, cả hai đều mang thuộc tính, truy vấn bằng ngôn ngữ Cypher theo mẫu đường đi, nên duyệt quan hệ nhiều bước như bạn của bạn rất nhanh mà không cần phép JOIN. "MongoDB" là cơ sở dữ liệu hướng tài liệu (document store), lưu bản ghi dạng tài liệu giống JSON (BSON) trong các collection. "Redis" là kho khoá giá trị (key-value store) nằm trong bộ nhớ, giá trị có thể là chuỗi, danh sách, tập hợp, hash, dùng nhiều làm bộ đệm. "Hive" là kho dữ liệu trên Hadoop, tổ chức dữ liệu thành bảng và truy vấn bằng HiveQL kiểu SQL, không theo mô hình đồ thị.

Đáp án đúng: "match (n)-[r]-(m) return n,r,m". Trong Cypher, mệnh đề match nhận một mẫu đồ thị: (n) và (m) là hai nút bất kỳ, -[r]- là một quan hệ bất kỳ không xét chiều nối chúng; câu lệnh vì vậy khớp mọi cặp nút có quan hệ và trả về cả nút lẫn quan hệ, Neo4j Browser hiển thị ra toàn bộ phần đồ thị có cạnh. "show graph" không phải câu lệnh Cypher; Cypher không có lệnh show để in cả đồ thị. "select * from graph" là cú pháp SQL cho bảng quan hệ, Neo4j không có bảng tên graph và Cypher không dùng mệnh đề select from. "return all" thiếu mệnh đề match để xác định cần lấy gì và all không phải biến được khai báo, nên câu lệnh không hợp lệ.

Đáp án đúng: "False". Phát biểu cho rằng Cypher không có lệnh riêng để tìm đường đi ngắn nhất là sai, vì Cypher cung cấp sẵn hai hàm shortestPath và allShortestPaths; ví dụ viết match p=shortestPath((a)-[:TO*]-(b)) return p sẽ trả về một đường ngắn nhất giữa hai nút, còn allShortestPaths trả về mọi đường có cùng độ dài ngắn nhất. Ngoài ra thư viện Graph Data Science của Neo4j còn có thủ tục Dijkstra cho đồ thị có trọng số. Phương án "True" sai vì nó phủ nhận sự tồn tại của các hàm dựng sẵn này; người dùng không phải tự viết thuật toán duyệt đồ thị mà chỉ cần bọc mẫu đường đi có độ dài biến thiên trong hàm shortestPath là đủ.

Đáp án đúng: "True". Cypher được thiết kế để người quen SQL dễ học nên mượn nhiều từ khoá và mệnh đề của SQL: WHERE để lọc, ORDER BY để sắp xếp, LIMIT và SKIP để phân trang, DISTINCT để bỏ trùng, các hàm gộp như count, sum, avg, cùng UNION; khác biệt chính là thay FROM bằng MATCH với mẫu đồ thị và dùng RETURN ở cuối thay cho SELECT ở đầu. Phương án "False" sai vì nó cho rằng hai ngôn ngữ không có điểm chung nào, trong khi phần lọc, sắp xếp, gộp nhóm của Cypher gần như trùng tên và ngữ nghĩa với SQL; chỗ khác biệt chỉ nằm ở cách mô tả dữ liệu cần lấy theo mẫu nút và quan hệ thay vì theo bảng.

Đáp án đúng: "A type of data to contain both edge and vertex info.". Trong Spark GraphX, đồ thị gồm VertexRDD chứa thuộc tính đỉnh và EdgeRDD chứa thuộc tính cạnh; triplet là khung nhìn ghép chúng lại: mỗi phần tử EdgeTriplet mang mã và thuộc tính của đỉnh nguồn (srcAttr), đỉnh đích (dstAttr) cùng thuộc tính của cạnh nối chúng (attr), lấy ra qua graph.triplets. Nhiều tài liệu ôn tập lại ghi "A type of data to contain the information on connections between vertices and edges." vì triplet nghe như mô tả mối nối; nhưng theo tài liệu GraphX, triplet không chứa quan hệ giữa đỉnh với cạnh mà chứa trọn dữ liệu của một cạnh và hai đỉnh đầu mút, nên mô tả đúng là chứa cả thông tin cạnh lẫn đỉnh. "A type of data to contain vertex info." chỉ đúng với VertexRDD, thiếu phần cạnh. "A type of data to contain edge info." chỉ đúng với EdgeRDD, thiếu thuộc tính hai đỉnh mà triplet gắn thêm vào.

Đáp án đúng: "True". Trong Cypher, mẫu (n)-[r]-(n) dùng cùng một biến n cho cả hai đầu của quan hệ r, nên chỉ khớp những quan hệ có điểm đầu và điểm cuối là cùng một nút, tức là các vòng tự thân (self-loop); dấu gạch không có mũi tên nghĩa là không xét chiều, nên bắt được mọi vòng bất kể khai báo chiều nào. Mệnh đề return n, r trả về nút và quan hệ đó, Neo4j Browser hiển thị thành đồ thị gồm các vòng đang tồn tại; nếu đồ thị không có vòng nào thì kết quả rỗng, đúng với ý những vòng có thể tồn tại trong câu hỏi. Phương án "False" sai vì cho rằng truy vấn không làm được việc này, trong khi việc lặp lại cùng biến ở hai đầu chính là cách chuẩn để tìm vòng tự thân trong Cypher.

Đáp án đúng: "Giraph". Apache Giraph là hệ xử lý đồ thị quy mô lớn chạy trên Hadoop, theo mô hình Pregel của Google: tính toán chia thành các siêu bước (superstep), trong mỗi bước mọi đỉnh song song nhận thông điệp, cập nhật giá trị và gửi thông điệp cho láng giềng, phù hợp với PageRank, đường đi ngắn nhất, thành phần liên thông trên đồ thị hàng tỷ cạnh. "Hive" là kho dữ liệu truy vấn bằng HiveQL kiểu SQL trên dữ liệu dạng bảng, không có mô hình tính toán theo đỉnh. "HDFS" là hệ thống tệp phân tán, chỉ lưu dữ liệu chứ không xử lý đồ thị. "Storm" là hệ xử lý luồng thời gian thực, xử lý từng sự kiện khi nó đến, không thiết kế cho thuật toán lặp trên đồ thị.