路径模式

路径模式是确定节点或关系在路径模式匹配中是否可以多次出现的约束级别。

Cypher® 支持三种路径模式:

  • WALK:不施加约束;路径中的节点和关系均可重复出现。

  • TRAIL:关系不可重复,但路径中的节点可以重复。

  • ACYCLIC:路径中的节点不可重复,这也意味着关系不可重复;然而,节点可以在不同的路径之间重复,从而可以形成等值连接 (equijoins)。

路径模式与匹配模式

路径模式的作用域是路径模式 (path pattern),而匹配模式的作用域是单个 MATCH 下的所有路径模式。单个路径模式匹配中的有效唯一性约束由两者中限制性更强的一方决定,同时匹配模式仍适用于整个图模式匹配。

由于默认匹配模式是 DIFFERENT RELATIONSHIPS,且唯一能与 REPEATABLE ELEMENTS 结合的路径模式是 WALK,因此唯一会改变唯一性约束的路径模式是 ACYCLIC。因此,本页面重点介绍 ACYCLIC 路径模式。

有关匹配模式的更多信息,请参阅 匹配模式

语法

将路径模式关键字放置在 MATCH 子句中每个路径模式的开头,例如:

MATCH p = ACYCLIC (start:User {id: 1})-[:FRIEND]->+(target:User)
RETURN p

更多信息,请参阅 语法和语义 → 路径模式

示例

为了说明 ACYCLIC 修剪的实际应用,请考虑用于模拟数据包转发的路由器网络。在网络中,识别无环传输路由对于避免广播风暴和网络拥塞至关重要。

下图包含几个路由环路和路由器之间的双向链路。

CREATE
  (a:Router {name: 'A'}), (b:Router {name: 'B'}), (c:Router {name: 'C'}),
  (d:Router {name: 'D'}), (e:Router {name: 'E'}), (f:Router {name: 'F'}),
  (g:Router {name: 'G'}), (h:Router {name: 'H'}), (i:Router {name: 'I'}),
  (j:Router {name: 'J'}), (k:Router {name: 'K'}), (z:Router {name: 'Z'}),

  (a)-[:LINK]->(b), (a)-[:LINK]->(c), (a)-[:LINK]->(d), (c)-[:LINK]->(b),
  (c)-[:LINK]->(d), (b)-[:LINK]->(e), (c)-[:LINK]->(e), (d)-[:LINK]->(f),
  (e)-[:LINK]->(g), (f)-[:LINK]->(g), (h)-[:LINK]->(i), (h)-[:LINK]->(j),
  (i)-[:LINK]->(j), (i)-[:LINK]->(z), (g)-[:LINK]->(j), (g)-[:LINK]->(k),
  (j)-[:LINK]->(k), (j)-[:LINK]->(z), (k)-[:LINK]->(z)

数据包转发中的关系唯一性

在许多图上下文中,Cypher 默认的关系唯一性模式已足够。然而,在数据包转发中,数据包不应两次访问同一个路由器,即使它使用了不同的链路。关系唯一性仅确保不重复使用关系——它不能防止节点被重复访问,这意味着循环仍然可能发生。例如,在路由器网络图中,存在一些路径,其中没有重复的关系,但节点被重复访问,例如涉及路由器 BCD 的循环。

例如,以下查询使用了图元素唯一性的默认行为,它禁止重复关系,但允许重复节点:

// This query uses a quantified path pattern with inline predicates to exclude paths
// that either return to the start router or pass through the target router. The (l)
// node pattern steps through every node in the path except the last i.e. 'Z', whereas
// the (m) node pattern steps through every node in the path except the first i.e. 'A'.
MATCH p = (:Router {name: 'A'})
  ((l WHERE l.name <> 'Z')-[:LINK]-(m WHERE m.name <> 'A'))+
  (:Router {name: 'Z'})

// The following filters for paths that have cycles, where the number of nodes in the
// path is greater than the number of distinct nodes in the path.
WHERE size(nodes(p)) > COUNT { UNWIND nodes(p) AS n RETURN DISTINCT n }

// A list comprehension converts the sequence of nodes to a compact list of their names.
RETURN [n IN nodes(p) | n.name] AS routeWithCycles

// For illustration purposes, this picks one of the 88 possible paths.
ORDER BY length(p), p LIMIT 1
结果
routeWithCycles

["A", "B", "E", "G", "J", "I", "H", "J", "Z"]

行:1

注意 J 节点是如何被访问两次的。

ACYCLIC 转发路径

使用 ACYCLIC 可以严格模拟避免重复访问的数据包转发。此模式确保没有节点重复:

MATCH p = ACYCLIC (:Router {name: 'A'})-[:LINK]-+(:Router {name: 'Z'})
RETURN [n IN nodes(p) | n.name] AS routeWithoutCycles
ORDER BY p LIMIT 1

请注意,使用 ACYCLIC 路径模式时,无需使用谓词来排除对起始或结束节点的访问。

结果
routeWithoutCycles

["A", "B", "E", "G", "J", "I", "Z"]

行:1

您还可以使用 ACYCLIC 来检查从源路由器到目标路由器的可能路由数量。这将受到每个故障的影响:

// Collect all the ACYCLIC paths to count the total number of paths from 'A' to 'Z'.
LET middleNodesOfPaths = COLLECT {
  MATCH p = ACYCLIC (start:Router {name: 'A'})-[:LINK]-+(end:Router {name: 'Z'})

// List slicing is a convenient way to remove the first and last node.
  RETURN nodes(p)[1..-1]
}

// The number of lists of middle nodes equals the number of paths.
LET numPaths = size(middleNodesOfPaths)

// middleNodesOfPaths is a list of lists, which the flatten function unnests into
// a single list of nodes.
UNWIND coll.flatten(middleNodesOfPaths) AS node

// As the paths are ACYCLIC, counting the number of times a particular node appears in
// the list of lists tells you in how many paths that node appears.
WITH node.name AS node, count(*) AS numPathsWithNode, numPaths

RETURN node, round(100.0 * numPathsWithNode / numPaths, 1) AS `% of paths with node`
ORDER BY numPathsWithNode DESC
结果
"node" "% of paths with node"

"G"

100.0

"J"

87.5

"C"

80.0

"E"

70.0

"K"

62.5

"D"

60.0

"B"

60.0

"I"

50.0

"F"

40.0

"H"

25.0

行数: 10

这表明路由器 G 是网络中最薄弱的点,从 AZ 的 100% 流量都经过它。

使用 ACYCLIC 提升性能

使用 ACYCLIC 比使用手动后置过滤器进行节点唯一性检查要高效得多。

使用 WHERE 丢弃结果

在早期的 Cypher 版本中,引擎会返回所有满足模式结构要求的路径。只有在生成这些路径后,WHERE 过滤器才会丢弃那些包含循环的路径。

MATCH p = (start:User {id: 1})-[:FRIEND]->+(target:User)
  WHERE size(nodes(p)) = COUNT { UNWIND nodes(p) AS n RETURN DISTINCT n }
RETURN p
  • 评估: 引擎生成所有可能的路径,包括那些无限循环或多次访问相同节点的路径。

  • 开销: 引擎必须在内存中计算并保留大量的循环解,然后过滤器才能将其丢弃。

使用 ACYCLIC 进行内联修剪

ACYCLIC 路径模式在评估期间应用唯一性约束。

MATCH p = ACYCLIC (start:User \{id: 1})-[:FRIEND]->+(target:User)
RETURN p
  • 评估: 当引擎遍历图时,它会监控路径中已存在的节点。

  • 修剪: 如果引擎尝试移动到当前路径中已访问过的节点,它会立即修剪该特定的候选解。

  • 效率: 因为无效路径永远不会被完整生成或保存在内存中,所以执行速度更快且占用更少的资源。