個人中心
退出
讓我們用 SQL 開發(fā)一個圖形數(shù)據(jù)庫吧！
作者: 不剪發(fā)的Tony老師
畢業(yè)于北京航空航天大學(xué)，十多年數(shù)據(jù)庫管理與開發(fā)經(jīng)驗，目前在一家全球性的金融公司從事數(shù)據(jù)庫架構(gòu)設(shè)計。CSDN學(xué)院簽約講師以及GitChat專欄作者。csdn上的博客收藏于以下地址：https://tonydong.blog.csdn.net
文章目錄
設(shè)計表結(jié)構(gòu)
實現(xiàn)圖查詢
插入數(shù)據(jù)
圖的遍歷
最短距離
索引優(yōu)化
大家好！我是只談技術(shù)不剪發(fā)的 Tony 老師。
圖形數(shù)據(jù)庫（Graph Database）是 NoSQL 數(shù)據(jù)庫的一種，使用圖結(jié)構(gòu)來存儲、表示、處理和查詢數(shù)據(jù)。圖是節(jié)點（Node）或者頂點（Vertice）和連接（Link）或者邊緣（Edge）的集合。節(jié)點代表了一個實體（人、物體等），連接代表了兩個節(jié)點之間的聯(lián)系（好友、愛好等）。圖形數(shù)據(jù)庫非常適合社交關(guān)系分析、金融欺詐檢測、知識圖譜等領(lǐng)域，Neo4j 是著名的圖形數(shù)據(jù)庫。
除了使用專門的圖形數(shù)據(jù)庫之外，如今主流的關(guān)系型數(shù)據(jù)庫都提供了 JSON 文檔存儲功能以及通用表表達式（WITH 子句）的支持。我們完全可以基于這些功能實現(xiàn)一個簡單的圖形數(shù)據(jù)庫，同時可以使用 SQL 語句對圖形進行操作和查詢。
如果你覺得這篇文章有用，歡迎關(guān)注??、評論??、點贊??！
設(shè)計表結(jié)構(gòu)
圖要由兩個結(jié)構(gòu)組成：節(jié)點和邊緣。
節(jié)點代表了一個實體對象，例如人、地點、事物等。節(jié)點可以擁有屬性，例如人的姓名、性別等。一個節(jié)點對應(yīng)了關(guān)系型數(shù)據(jù)庫中的一行數(shù)據(jù)或者文檔數(shù)據(jù)庫中的一個文檔。
邊緣代表了兩個對象之間的關(guān)系，例如某人住在某地。邊緣也可以擁有屬性，例如何時開始住在某地。一個邊緣對應(yīng)了關(guān)系型數(shù)據(jù)庫中的一個外鍵記錄或者文檔數(shù)據(jù)庫中的一個鏈接 id。
基于圖的結(jié)構(gòu)，我們可以在關(guān)系型數(shù)據(jù)庫中創(chuàng)建兩個表：node 和 edge。它們的 ERD 如下圖所示：
創(chuàng)建以上表結(jié)構(gòu)的 SQL 腳本如下（MySQL 語法）：
-- MySQL
CREATE TABLE IF NOT EXISTS node (
node_id BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
properties JSON
);
CREATE TABLE IF NOT EXISTS edge (
edge_id BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
source_id BIGINT NOT NULL,
target_id BIGINT NOT NULL,
properties JSON,
FOREIGN KEY(source_id) REFERENCES node(node_id),
FOREIGN KEY(target_id) REFERENCES node(node_id)
);
CREATE INDEX idx_edge_source_id ON edge(source_id);
CREATE INDEX idx_edge_target_id ON edge(target_id);
對于節(jié)點表 node，我們創(chuàng)建了一個自增主鍵 node_id，以及一個存儲節(jié)點屬性的 JSON 字段 properties。對于邊緣表 edge，我們創(chuàng)建了一個自增主鍵 edge_id，表示關(guān)系起點的字段 source_id 和表示關(guān)系終點的字段 target_id，以及一個存儲關(guān)系屬性的 JSON 字段 properties。
同時，為了數(shù)據(jù)操作和提高查詢性能，我們創(chuàng)建了兩個索引 idx_edge_source_id 和 idx_edge_target_id。
??完整的表結(jié)構(gòu)和查詢腳本可以從 GitHub 或者 CODE CHINA 下載。除了 MySQL 之外，我們還提供了 Oracle、Microsoft SQL Server、PostgreSQL 以及 SQLite 版本。
實現(xiàn)圖查詢
插入數(shù)據(jù)
接下來我們使用 SQL 語句插入一些測試數(shù)據(jù)，首先插入幾個節(jié)點：
INSERT INTO node(properties) VALUES('{"Label":"Person", "Name":"張三", "Age": 22}');
INSERT INTO node(properties) VALUES('{"Label":"Person", "Name":"李四", "Age": 30}');
INSERT INTO node(properties) VALUES('{"Label":"Person", "Name":"王五", "Age": 28}');
以上語句插入了 3 個節(jié)點，它們的 Label 都是 Person，擁有姓名和年齡屬性。
然后我們再建立一些關(guān)系：
INSERT INTO edge(source_id, target_id, properties)
VALUES((SELECT node_id FROM node WHERE json_value(properties, '$.Name')='張三'),
(SELECT node_id FROM node WHERE json_value(properties, '$.Name')='李四'), '{"Label":"關(guān)注", "Degree": 80}');
INSERT INTO edge(source_id, target_id, properties)
VALUES((SELECT node_id FROM node WHERE json_value(properties, '$.Name')='李四'),
(SELECT node_id FROM node WHERE json_value(properties, '$.Name')='王五'), '{"Label":"關(guān)注", "Degree": 90}');
INSERT INTO edge(source_id, target_id, properties)
VALUES((SELECT node_id FROM node WHERE json_value(properties, '$.Name')='張三'),
(SELECT node_id FROM node WHERE json_value(properties, '$.Name')='王五'), '{"Label":"關(guān)注", "Degree": 60}');
其中，json_value 是 MySQL 提供的 JSON 函數(shù)，用于提取 JSON 文檔中的元素。
以上測試數(shù)據(jù)建立的關(guān)系圖如下所示：
對于節(jié)點和邊緣的查詢和普通表類似，例如：
SELECT properties FROM node WHERE json_value(properties, '$.Name')='張三';
properties |
--------------------------------------------+
{"Age": 22, "Name": "張三", "Label": "Person"}|
SELECT * FROM edge WHERE source_id = 1 AND target_id = 2;
edge_id|source_id|target_id|properties |
-------+---------+---------+-----------------------------+
1| 1| 2|{"Label": "關(guān)注", "Degree": 80}|
圖的遍歷
我們從節(jié)點“張三”出發(fā)，遍歷所有的節(jié)點：
WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, '$.Name') AS CHAR(100)), 0
FROM node
WHERE json_value(properties, '$.Name')='張三'
UNION ALL
SELECT target_id, CONCAT(relation,'->',json_value(n.properties, '$.Name')), hops + 1
FROM edge e
JOIN traverse t ON e.source_id = t.id
JOIN node n ON e.target_id = n.node_id
)
SELECT id, relation, hops
FROM traverse;
id|relation |hops|
--+---------------+----+
1|張三 | 0|
2|張三->李四 | 1|
3|張三->王五 | 1|
3|張三->李四->王五| 2|
首先，我們定義了一個遞歸形式的通用表表達式 traverse，它由兩部分組成，使用 UNION ALL 進行組合。第一個 SELECT 語句返回了起點“張三”，第二個 SELECT 語句引用了 traverse 自身，通過不停的迭代返回所有連接的節(jié)點。字段 hops 代表了節(jié)點之間的跳躍次數(shù)。最后的 SELECT 語句返回了全部的節(jié)點信息。
??關(guān)于通用表表達式的語法和使用案例，可以參考這篇文章和這篇文章。
從遍歷的結(jié)果可以看出，MySQL 默認采用的是廣度優(yōu)先搜索方法。如果想要實現(xiàn)深度優(yōu)先搜索，可以使用 ORDER BY 排序：
WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, '$.Name') AS CHAR(100)), 0
FROM node
WHERE json_value(properties, '$.Name')='張三'
UNION ALL
SELECT target_id, CONCAT(relation,'->',json_value(n.properties, '$.Name')), hops + 1
FROM edge e
JOIN traverse t ON e.source_id = t.id
JOIN node n ON e.target_id = n.node_id
)
SELECT id, relation, hops
FROM traverse
ORDER BY relation;
id|relation |hops|
--+---------------+----+
1|張三 | 0|
2|張三->李四 | 1|
3|張三->李四->王五| 2|
3|張三->王五 | 1|
最短距離
基于以上圖的遍歷，我們可以很容易地找出兩個節(jié)點之間的最短距離。例如，以下語句可以找出“張三”和“王五”之間的最短距離：
WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, '$.Name') AS CHAR(100)), 0
FROM node
WHERE json_value(properties, '$.Name')='張三'
UNION ALL
SELECT target_id, CONCAT(relation,'->',json_value(n.properties, '$.Name')), hops + 1
FROM edge e
JOIN traverse t ON e.source_id = t.id
JOIN node n ON e.target_id = n.node_id
)
SELECT id, relation, hops
FROM traverse
JOIN node ON id = node_id
WHERE json_value(properties, '$.Name')='王五'
ORDER BY hops
LIMIT 1;
id|relation |hops|
--+-----------+----+
3|張三->王五 | 1|
索引優(yōu)化
我們使用 EXPLAIN 命令查看一下最短距離搜索語句的執(zhí)行計劃：
EXPLAIN
WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, '$.Name') AS CHAR(100)), 0
FROM node
WHERE json_value(properties, '$.Name')='張三'
UNION ALL
SELECT target_id, CONCAT(relation,'->',json_value(n.properties, '$.Name')), hops + 1
FROM edge e
JOIN traverse t ON e.source_id = t.id
JOIN node n ON e.target_id = n.node_id
)
SELECT id, relation, hops
FROM traverse
JOIN node ON id = node_id
WHERE json_value(properties, '$.Name')='王五'
ORDER BY hops
LIMIT 1;
id|select_type|table |partitions|type
|possible_keys |key
|key_len|ref
|rows|filtered|Extra |
--+-----------+----------+----------+------+-------------------------------------+------------------+-------+----------------+----+--------+------------------------------------------+
1|PRIMARY |<derived2>| |ALL
| | |
| | 6| 100.0|Using temporary; Using
filesort |
1|PRIMARY |node | |ALL
|PRIMARY | |
| | 3| 50.0|Using where; Using join buffer (hash
join)|
2|DERIVED |node | |ALL
| | |
| | 3| 100.0|Using
where |
3|UNION |t
| |ALL |
| | | | 3| 100.0|Recursive;
Using where |
3|UNION |e |
|ref |idx_edge_source_id,idx_edge_target_id|idx_edge_source_id|8
|t.id | 1|
100.0| |
3|UNION
|n | |eq_ref|PRIMARY
|PRIMARY |8 |hrdb.e.target_id| 1|
100.0| |
由于 node 表的 properties 字段中的 Name 元素缺少合適的索引，查詢使用了大量的全表掃描，如果圖中的節(jié)點數(shù)量很多時性能比較差。對此，我們可以使用數(shù)據(jù)庫的函數(shù)索引為 JSON 文檔中的節(jié)點數(shù)據(jù)創(chuàng)建索引，從而提高訪問性能。例如：
CREATE INDEX idx_node_name ON node ( (json_value(properties, '$.Name')) );
1
執(zhí)行以上命令創(chuàng)建索引之后，我們再次查看執(zhí)行計劃：
id|select_type|table |partitions|type
|possible_keys |key
|key_len|ref
|rows|filtered|Extra |
--+-----------+----------+----------+------+-------------------------------------+-------------+-------+-----------------+----+--------+------------------------------------------+
1|PRIMARY |node | |ref
|PRIMARY,idx_node_name |idx_node_name|2051
|const | 1| 100.0|Using temporary; Using
filesort |
1|PRIMARY |<derived2>|
|ref |<auto_key0> |<auto_key0>
|9 |hrdb.node.node_id| 2|
100.0| |
2|DERIVED
|node | |ref |idx_node_name
|idx_node_name|2051 |const | 1|
100.0| |
3|UNION
|t | |ALL |
| | | | 2|
100.0|Recursive |
3|UNION
|e | |ALL
|idx_edge_source_id,idx_edge_target_id| |
| | 2| 50.0|Using where; Using join buffer (hash
join)|
3|UNION |n |
|eq_ref|PRIMARY |PRIMARY |8
|hrdb.e.target_id | 1|
100.0| |
分類導(dǎo)航