個(gè)人中心
退出
讓我們用 SQL 開(kāi)發(fā)一個(gè)圖形數(shù)據(jù)庫(kù)吧！
作者: 不剪發(fā)的Tony老師
畢業(yè)于北京航空航天大學(xué)，十多年數(shù)據(jù)庫(kù)管理與開(kāi)發(fā)經(jīng)驗(yàn)，目前在一家全球性的金融公司從事數(shù)據(jù)庫(kù)架構(gòu)設(shè)計(jì)。CSDN學(xué)院簽約講師以及GitChat專(zhuān)欄作者。csdn上的博客收藏于以下地址：https://tonydong.blog.csdn.net
文章目錄
設(shè)計(jì)表結(jié)構(gòu)
實(shí)現(xiàn)圖查詢(xún)
插入數(shù)據(jù)
圖的遍歷
最短距離
索引優(yōu)化
大家好！我是只談技術(shù)不剪發(fā)的 Tony 老師。
圖形數(shù)據(jù)庫(kù)（Graph Database）是 NoSQL 數(shù)據(jù)庫(kù)的一種，使用圖結(jié)構(gòu)來(lái)存儲(chǔ)、表示、處理和查詢(xún)數(shù)據(jù)。圖是節(jié)點(diǎn)（Node）或者頂點(diǎn)（Vertice）和連接（Link）或者邊緣（Edge）的集合。節(jié)點(diǎn)代表了一個(gè)實(shí)體（人、物體等），連接代表了兩個(gè)節(jié)點(diǎn)之間的聯(lián)系（好友、愛(ài)好等）。圖形數(shù)據(jù)庫(kù)非常適合社交關(guān)系分析、金融欺詐檢測(cè)、知識(shí)圖譜等領(lǐng)域，Neo4j 是著名的圖形數(shù)據(jù)庫(kù)。
除了使用專(zhuān)門(mén)的圖形數(shù)據(jù)庫(kù)之外，如今主流的關(guān)系型數(shù)據(jù)庫(kù)都提供了 JSON 文檔存儲(chǔ)功能以及通用表表達(dá)式（WITH 子句）的支持。我們完全可以基于這些功能實(shí)現(xiàn)一個(gè)簡(jiǎn)單的圖形數(shù)據(jù)庫(kù)，同時(shí)可以使用 SQL 語(yǔ)句對(duì)圖形進(jìn)行操作和查詢(xún)。
如果你覺(jué)得這篇文章有用，歡迎關(guān)注??、評(píng)論??、點(diǎn)贊??！
設(shè)計(jì)表結(jié)構(gòu)
圖要由兩個(gè)結(jié)構(gòu)組成：節(jié)點(diǎn)和邊緣。
節(jié)點(diǎn)代表了一個(gè)實(shí)體對(duì)象，例如人、地點(diǎn)、事物等。節(jié)點(diǎn)可以擁有屬性，例如人的姓名、性別等。一個(gè)節(jié)點(diǎn)對(duì)應(yīng)了關(guān)系型數(shù)據(jù)庫(kù)中的一行數(shù)據(jù)或者文檔數(shù)據(jù)庫(kù)中的一個(gè)文檔。
邊緣代表了兩個(gè)對(duì)象之間的關(guān)系，例如某人住在某地。邊緣也可以擁有屬性，例如何時(shí)開(kāi)始住在某地。一個(gè)邊緣對(duì)應(yīng)了關(guān)系型數(shù)據(jù)庫(kù)中的一個(gè)外鍵記錄或者文檔數(shù)據(jù)庫(kù)中的一個(gè)鏈接 id。
基于圖的結(jié)構(gòu)，我們可以在關(guān)系型數(shù)據(jù)庫(kù)中創(chuàng)建兩個(gè)表：node 和 edge。它們的 ERD 如下圖所示：
創(chuàng)建以上表結(jié)構(gòu)的 SQL 腳本如下（MySQL 語(yǔ)法）：
-- 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);
對(duì)于節(jié)點(diǎn)表 node，我們創(chuàng)建了一個(gè)自增主鍵 node_id，以及一個(gè)存儲(chǔ)節(jié)點(diǎn)屬性的 JSON 字段 properties。對(duì)于邊緣表 edge，我們創(chuàng)建了一個(gè)自增主鍵 edge_id，表示關(guān)系起點(diǎn)的字段 source_id 和表示關(guān)系終點(diǎn)的字段 target_id，以及一個(gè)存儲(chǔ)關(guān)系屬性的 JSON 字段 properties。
同時(shí)，為了數(shù)據(jù)操作和提高查詢(xún)性能，我們創(chuàng)建了兩個(gè)索引 idx_edge_source_id 和 idx_edge_target_id。
??完整的表結(jié)構(gòu)和查詢(xún)腳本可以從 GitHub 或者 CODE CHINA 下載。除了 MySQL 之外，我們還提供了 Oracle、Microsoft SQL Server、PostgreSQL 以及 SQLite 版本。
實(shí)現(xiàn)圖查詢(xún)
插入數(shù)據(jù)
接下來(lái)我們使用 SQL 語(yǔ)句插入一些測(cè)試數(shù)據(jù)，首先插入幾個(gè)節(jié)點(diǎn)：
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}');
以上語(yǔ)句插入了 3 個(gè)節(jié)點(diǎn)，它們的 Label 都是 Person，擁有姓名和年齡屬性。
然后我們?cè)俳⒁恍╆P(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 文檔中的元素。
以上測(cè)試數(shù)據(jù)建立的關(guān)系圖如下所示：
對(duì)于節(jié)點(diǎn)和邊緣的查詢(xún)和普通表類(lèi)似，例如：
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é)點(diǎn)“張三”出發(fā)，遍歷所有的節(jié)點(diǎn)：
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|
首先，我們定義了一個(gè)遞歸形式的通用表表達(dá)式 traverse，它由兩部分組成，使用 UNION ALL 進(jìn)行組合。第一個(gè) SELECT 語(yǔ)句返回了起點(diǎn)“張三”，第二個(gè) SELECT 語(yǔ)句引用了 traverse 自身，通過(guò)不停的迭代返回所有連接的節(jié)點(diǎn)。字段 hops 代表了節(jié)點(diǎn)之間的跳躍次數(shù)。最后的 SELECT 語(yǔ)句返回了全部的節(jié)點(diǎn)信息。
??關(guān)于通用表表達(dá)式的語(yǔ)法和使用案例，可以參考這篇文章和這篇文章。
從遍歷的結(jié)果可以看出，MySQL 默認(rèn)采用的是廣度優(yōu)先搜索方法。如果想要實(shí)現(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|
最短距離
基于以上圖的遍歷，我們可以很容易地找出兩個(gè)節(jié)點(diǎn)之間的最短距離。例如，以下語(yǔ)句可以找出“張三”和“王五”之間的最短距離：
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 命令查看一下最短距離搜索語(yǔ)句的執(zhí)行計(jì)劃：
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 元素缺少合適的索引，查詢(xún)使用了大量的全表掃描，如果圖中的節(jié)點(diǎn)數(shù)量很多時(shí)性能比較差。對(duì)此，我們可以使用數(shù)據(jù)庫(kù)的函數(shù)索引為 JSON 文檔中的節(jié)點(diǎn)數(shù)據(jù)創(chuàng)建索引，從而提高訪問(wèn)性能。例如：
CREATE INDEX idx_node_name ON node ( (json_value(properties, '$.Name')) );
1
執(zhí)行以上命令創(chuàng)建索引之后，我們?cè)俅尾榭磮?zhí)行計(jì)劃：
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| |
分類(lèi)導(dǎo)航