Data Model (2) – Graph-Like Data Model

Graph Data Model 初探

若你軟體的資料關係是大部份一對多，使用 Document Model 就很足夠了，但若多對多關係是佔你軟體資料中的很大部份呢？

Relational Model 可以處理較簡單的多對多關係，但如果較複雜的話就不太適合，例如朋友之間的關係，此時看起來直覺多的 Graph Model 就是個好選擇了，一個 Graph 通常分 2 個型態的物件：

• Vertices (也可稱 Nodes 或 Entities)
• Edges (也可稱 Relationships 或 Arcs)

用不同場景舉例的話則能分別代表不同意思：

社群 Graph

• Vertices 就是人，Edges 就是人之間的關係

網頁 Graph

• Vertices 就是網頁，Edges 就代表每個網頁之間的連結

道路或鐵路 Graph

• Vertices 就是交叉路口，Edges 就代表每個路口間的路

在學資料結構時應該都有學到圖論的演算法，這些算法能幫助操作圖，例始找到 2 個路口間的最短距離，或者看哪個網頁被連結的最多，讓搜尋引擎能做排序等等。

除此之外，同一個 Graph 裡能用多種類型的資料，例如 Facebook Graph Model 的 Vertices 就有人、地點、活動、評論等等，如下圖，每一個長方形都是 Vertices，但同時有人和地點 2 種類型，彼此用 Edge 代表某種關係，如 Lucy 嫁給 Alain，2 人一起住在倫敦。

接下來會介紹 2 種不同的 Graph Data Model 架構，分別是 property graph (Neo4j, Titan 實作) 跟 triple-store (Datomic, AllegroGraph 實作)，然後跟如何做 Query。

Property Graphs

在 property graph model 裡，每一個 vertex 都包含：

• 唯一識別 ID
• 一個連出去的 edges set
• 一個連進來的 edges set
• 一個 key-values 的集合 (collection)

每一個 edge 都包含：

• 唯一識別 ID
• 起點 vertex
• 終點 vertex
• 一個標記這是什麼關係的 label
• 一個 key-values 的集合 (collection)

這可以用以下 2 個 relational 表格來示範 (PostgreSQL schema)，連出去跟連進來的 edges sets 可直接用查詢 edges 表格來產生：

CREATE TABLE vertices (
    vertex_id integer PRIMARYKEY, 
  properties json
);

CREATE TABLE edges (
    edge_id integer PRIMARY KEY,
    tail_vertex integer REFERENCES vertices (vertex_id), 
  head_vertex integer REFERENCES vertices (vertex_id), 
  label text,
    properties json
);

CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

Graph model 可以很簡單的新增不同類型的 Vertex，以圖 2-5 舉例，我們可以新增食物的 Vertex 和喜不喜歡吃的 Edge。

Cypher Query Language

Cypher 是一個 property graph 用的宣告式的查詢語言，為了 Neo4j 建立的，我們可以用下面這個 Cypher 語法來新增圖 2-5 的 Graph 資料到 Graph database 裡，其他的 Vertex 跟 Edge 可用類似的語法建立資料，

CREATE
  (NAmerica:Location {name:'North America', type:'continent'}),
  (USA:Location      {name:'United States', type:'country'  }),
  (Idaho:Location    {name:'Idaho',         type:'state'    }),
  (Lucy:Person       {name:'Lucy' }),
(Idaho) -[:WITHIN]-> (USA) -[:WITHIN]-> (NAmerica), (Lucy) -[:BORN_IN]-> (Idaho)

當資料都建完時，就可用 Cypher 來做一些有趣的查詢，例如 有哪些人是從 US 搬到 Europe？ 我們可以這樣查詢：

MATCH
    (person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
    (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'}) 
RETURN person.name

先找到在 US 出生的人：

1. (person) -[:BORN_IN]-> () 從 person 的 vetex 找到任一 edge label 有 BORIN_IN，右邊的 () 代表不指定終點 vertex
2. 在用 [:WITHIN*0..] edge 建成一條鍊找到符合 name 為 US 的 Vertex

然後用一樣邏輯找到現在住在 Europe 的人，最後返回同時 Match 的人名。

Cypher Query In SQL

你也可以把資料存到前面舉例過的 Relational database 裡，然後又 SQL 來查詢 有哪些人是從 US 搬到 Europe？但查起可能就沒這麼方便了，

在 Realtional database 中，我們也是可以用 Join 的方式去 traverse (遍歷) 所有 Vertex，但寫起來會像這樣：

WITH RECURSIVE
-- in_usa is the set of vertex IDs of all locations within the United States
  in_usa(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'United States'
    UNION
      SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'within' 
  ),
-- in_europe is the set of vertex IDs of all locations within Europe
  in_europe(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe'
    UNION
      SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'within' 
  ),
-- born_in_usa is the set of vertex IDs of all people born in the US
  born_in_usa(vertex_id) AS (
      SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'born_in' 
  ),
-- lives_in_europe is the set of vertex IDs of all people living in Europe
  lives_in_europe(vertex_id) AS (
      SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'lives_in' 
  )

SELECT vertices.properties->>'name'
FROM vertices
-- join to find those people who were both born in the US *and* live in Europe 
JOIN born_in_usa ON vertices.vertex_id = born_in_usa.vertex_id
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

我也懶的解釋這個 SQL 邏輯了XD (頭疼中)，這還只是上面那個簡單問題的查詢，更不消說比較複雜的查詢了。

如 Relational Model and Document Model 最一開始提到的那樣，為你的軟體選擇適合的 data model 是再重要不過了！