图遍历查询 #

一、图遍历概述 #

1.1 什么是图遍历 #

图遍历是沿着图的边从一个顶点移动到另一个顶点的过程：

text

图遍历类型：
├── 深度优先遍历 (DFS)
├── 广度优先遍历 (BFS)
├── 路径查询
└── 图算法

1.2 OrientDB遍历特点 #

text

遍历特点：
├── 支持SQL语法
├── 支持多种遍历策略
├── 支持条件过滤
├── 支持深度限制
└── 支持路径追踪

二、TRAVERSE语句 #

2.1 基本语法 #

sql

TRAVERSE <fields> 
FROM <target>
[STRATEGY <strategy>]
[MAXDEPTH <depth>]
[WHILE <condition>]
[LIMIT <limit>]

2.2 基本遍历 #

sql

TRAVERSE out() FROM #12:0
TRAVERSE out('KNOWS') FROM #12:0
TRAVERSE in() FROM #12:0
TRAVERSE both() FROM #12:0

2.3 遍历策略 #

sql

TRAVERSE out() FROM #12:0 STRATEGY DEPTH_FIRST
TRAVERSE out() FROM #12:0 STRATEGY BREADTH_FIRST

策略说明：

策略	说明
DEPTH_FIRST	深度优先，沿一条路径走到底
BREADTH_FIRST	广度优先，逐层遍历

2.4 限制深度 #

sql

TRAVERSE out('KNOWS') FROM #12:0 MAXDEPTH 2
TRAVERSE out('KNOWS') FROM #12:0 MAXDEPTH 3

2.5 条件遍历 #

sql

TRAVERSE out('KNOWS') FROM #12:0 WHILE $depth <= 3
TRAVERSE out('KNOWS') FROM #12:0 WHILE @class = 'Person'

2.6 遍历多个边类型 #

sql

TRAVERSE out('KNOWS', 'WORKS_AT') FROM #12:0
TRAVERSE both('KNOWS', 'FRIEND_OF') FROM #12:0

2.7 遍历返回字段 #

sql

TRAVERSE name, age, out('KNOWS') FROM #12:0
SELECT name, age FROM (TRAVERSE out('KNOWS') FROM #12:0)

三、路径变量 #

3.1 内置路径变量 #

变量	说明
$path	完整路径
$depth	当前深度
$current	当前顶点
$parent	父顶点
$previous	前一个顶点

3.2 使用路径变量 #

sql

SELECT 
    name,
    $path AS path,
    $depth AS depth
FROM (
    TRAVERSE out('KNOWS') FROM #12:0 MAXDEPTH 3
)

3.3 路径格式 #

sql

SELECT 
    name,
    $path AS path
FROM (
    TRAVERSE out('KNOWS') FROM #12:0 MAXDEPTH 2
)

输出示例：

text

name: Jerry
path: (#12:0)--KNOWS-->(#12:1)

3.4 深度过滤 #

sql

SELECT name, $depth AS depth
FROM (
    TRAVERSE out('KNOWS') FROM #12:0 MAXDEPTH 3
)
WHERE $depth = 2

四、SELECT遍历 #

4.1 使用out/in函数 #

sql

SELECT out('KNOWS').name FROM Person WHERE name = 'Tom'
SELECT out('KNOWS').out('KNOWS').name FROM Person WHERE name = 'Tom'

4.2 指定深度范围 #

sql

SELECT out('KNOWS')[0].name AS friend FROM Person WHERE name = 'Tom'
SELECT out('KNOWS')[0-2].name AS friends FROM Person WHERE name = 'Tom'
SELECT out('KNOWS')[0,2].name AS friends FROM Person WHERE name = 'Tom'

4.3 遍历所有层级 #

sql

SELECT out('KNOWS')[0-].name FROM Person WHERE name = 'Tom'

4.4 条件遍历 #

sql

SELECT out('KNOWS')[age > 25].name FROM Person WHERE name = 'Tom'

五、最短路径 #

5.1 shortestPath函数 #

sql

SELECT shortestPath(#12:0, #12:5)
SELECT shortestPath(#12:0, #12:5, 'OUT')
SELECT shortestPath(#12:0, #12:5, 'BOTH')

5.2 指定边类型 #

sql

SELECT shortestPath(#12:0, #12:5, 'BOTH', 'KNOWS')
SELECT shortestPath(#12:0, #12:5, 'OUT', 'KNOWS', 'WORKS_AT')

5.3 获取路径详情 #

sql

SELECT expand(shortestPath(#12:0, #12:5))
SELECT name FROM (SELECT expand(shortestPath(#12:0, #12:5)))

5.4 最短路径长度 #

sql

SELECT SIZE(shortestPath(#12:0, #12:5)) AS pathLength

六、所有路径查询 #

6.1 allShortestPaths #

sql

SELECT allShortestPaths(#12:0, #12:5)
SELECT allShortestPaths(#12:0, #12:5, 'BOTH', 'KNOWS')

6.2 限制路径数量 #

sql

SELECT allShortestPaths(#12:0, #12:5, 'BOTH', 'KNOWS', 3)

七、图算法 #

7.1 度中心性 #

sql

SELECT 
    name,
    SIZE(bothE()) AS degree
FROM Person
ORDER BY degree DESC

7.2 入度/出度 #

sql

SELECT 
    name,
    SIZE(inE('KNOWS')) AS inDegree,
    SIZE(outE('KNOWS')) AS outDegree,
    SIZE(bothE('KNOWS')) AS totalDegree
FROM Person
ORDER BY totalDegree DESC

7.3 共同邻居 #

sql

SELECT 
    intersection(
        (SELECT out('KNOWS') FROM Person WHERE name = 'Tom'),
        (SELECT out('KNOWS') FROM Person WHERE name = 'Jerry')
    ) AS mutualFriends

7.4 Jaccard相似度 #

sql

LET $tomFriends = (SELECT out('KNOWS') FROM Person WHERE name = 'Tom')
LET $jerryFriends = (SELECT out('KNOWS') FROM Person WHERE name = 'Jerry')
SELECT 
    SIZE(intersection($tomFriends, $jerryFriends)) * 1.0 / 
    SIZE(union($tomFriends, $jerryFriends)) AS jaccardSimilarity

7.5 PageRank模拟 #

sql

SELECT 
    name,
    SIZE(in('KNOWS')) AS incomingLinks,
    SIZE(in('KNOWS')) * 1.0 / (SELECT COUNT(*) FROM Person) AS pageRank
FROM Person
ORDER BY pageRank DESC

八、复杂遍历示例 #

8.1 社交网络分析 #

sql

SELECT 
    name,
    SIZE(out('KNOWS')) AS friendCount,
    SIZE(out('KNOWS').out('KNOWS')) AS friendsOfFriendsCount,
    SIZE(intersection(out('KNOWS'), out('KNOWS').out('KNOWS'))) AS mutualFriendsCount
FROM Person
ORDER BY friendCount DESC

8.2 影响力分析 #

sql

SELECT 
    name,
    SIZE(in('FOLLOWS')) AS followers,
    SIZE(out('FOLLOWS')) AS following,
    SIZE(in('FOLLOWS')) - SIZE(out('FOLLOWS')) AS influence
FROM User
ORDER BY influence DESC
LIMIT 10

8.3 推荐好友 #

sql

LET $tom = SELECT FROM Person WHERE name = 'Tom'
LET $tomFriends = $tom.out('KNOWS')
LET $friendsOfFriends = $tomFriends.out('KNOWS')
SELECT 
    name,
    COUNT(*) AS mutualFriendCount
FROM $friendsOfFriends
WHERE @rid NOT IN $tomFriends AND @rid != $tom[0].@rid
GROUP BY @rid
ORDER BY mutualFriendCount DESC
LIMIT 5

8.4 知识图谱推理 #

sql

SELECT 
    e.name AS entity,
    out('RELATED_TO').name AS relatedEntities,
    out('RELATED_TO').out('RELATED_TO').name AS indirectlyRelated
FROM Entity e
WHERE e.type = 'Concept'

九、遍历优化 #

9.1 使用索引 #

sql

CREATE INDEX Person.name UNIQUE
SELECT FROM Person WHERE name = 'Tom'

9.2 限制深度 #

sql

TRAVERSE out('KNOWS') FROM #12:0 MAXDEPTH 3

9.3 限制结果 #

sql

SELECT FROM (TRAVERSE out('KNOWS') FROM #12:0) LIMIT 100

9.4 条件过滤 #

sql

TRAVERSE out('KNOWS') FROM #12:0 WHILE $depth < 4 AND @class = 'Person'

9.5 使用RID #

sql

TRAVERSE out('KNOWS') FROM #12:0

十、实际应用示例 #

10.1 社交网络好友推荐 #

sql

LET $user = SELECT FROM User WHERE id = 'user_001'
LET $friends = $user.out('FOLLOWS')
LET $friendsOfFriends = $friends.out('FOLLOWS')
SELECT 
    u.name,
    u.username,
    COUNT(*) AS mutualFriends
FROM $friendsOfFriends u
WHERE u.@rid NOT IN $friends AND u.@rid != $user[0].@rid
GROUP BY u
ORDER BY mutualFriends DESC
LIMIT 10

10.2 组织架构层级查询 #

sql

SELECT 
    name,
    $depth AS level,
    $path AS path
FROM (
    TRAVERSE out('REPORTS_TO') FROM (SELECT FROM Employee WHERE title = 'CEO')
    STRATEGY BREADTH_FIRST
    MAXDEPTH 5
)
ORDER BY $depth

10.3 产品推荐 #

sql

LET $user = SELECT FROM Customer WHERE id = 'customer_001'
LET $purchasedProducts = $user.out('PURCHASED')
LET $similarUsers = (SELECT FROM Customer WHERE out('PURCHASED') IN $purchasedProducts)
SELECT 
    p.name AS productName,
    COUNT(*) AS recommendationScore
FROM $similarUsers.out('PURCHASED') p
WHERE p.@rid NOT IN $purchasedProducts
GROUP BY p
ORDER BY recommendationScore DESC
LIMIT 10

10.4 欺诈检测 #

sql

SELECT 
    a.name AS person1,
    b.name AS person2,
    SIZE(shortestPath(a.@rid, b.@rid)) AS distance
FROM Person a, Person b
WHERE a.@rid < b.@rid
AND SIZE(shortestPath(a.@rid, b.@rid)) <= 3
AND a.suspicious = true
AND b.suspicious = true

10.5 知识图谱问答 #

sql

LET $entity = SELECT FROM Entity WHERE name = 'Python'
SELECT 
    $entity.name AS subject,
    out('RELATED_TO').name AS relatedEntity,
    out('RELATED_TO').out('RELATED_TO').name AS secondLevelRelated
FROM $entity

十一、总结 #

图遍历查询要点：

操作	语法	说明
遍历	TRAVERSE	图遍历操作
出边	out()	出边遍历
入边	in()	入边遍历
最短路径	shortestPath()	最短路径查询
路径变量	$path, $depth	路径信息

下一步，让我们学习索引管理！