可变长度模式

Cypher® 可用于匹配可变长度或未知长度的模式。可以使用量化路径模式和量化关系来查找此类模式。本页面还讨论了在量化路径模式中声明变量（组变量）的工作方式，以及如何在量化路径模式中使用谓词。

量化路径模式

本节探讨如何使用量化路径模式来匹配可变长度的路径，从而允许您搜索长度未知或在特定范围内的路径。

量化路径模式在以下情况下非常有用，例如，搜索从锚点节点可到达的所有节点，查找连接两个节点的所有路径，或者遍历可能具有不同深度的层次结构时。

此示例使用一个新图

patterns qpp calling points

要重新创建该图，请针对空的 Neo4j 数据库运行以下查询

CREATE (pmr:Station {name: 'Peckham Rye'}),
  (dmk:Station {name: 'Denmark Hill'}),
  (clp:Station {name: 'Clapham High Street'}),
  (wwr:Station {name: 'Wandsworth Road'}),
  (clj:Station {name: 'Clapham Junction'}),
  (s1:Stop {arrives: time('17:19'), departs: time('17:20')}),
  (s2:Stop {arrives: time('17:12'), departs: time('17:13')}),
  (s3:Stop {arrives: time('17:10'), departs: time('17:11')}),
  (s4:Stop {arrives: time('17:06'), departs: time('17:07')}),
  (s5:Stop {arrives: time('16:58'), departs: time('17:01')}),
  (s6:Stop {arrives: time('17:17'), departs: time('17:20')}),
  (s7:Stop {arrives: time('17:08'), departs: time('17:10')}),
  (clj)<-[:CALLS_AT]-(s1), (wwr)<-[:CALLS_AT]-(s2),
  (clp)<-[:CALLS_AT]-(s3), (dmk)<-[:CALLS_AT]-(s4),
  (pmr)<-[:CALLS_AT]-(s5), (clj)<-[:CALLS_AT]-(s6),
  (dmk)<-[:CALLS_AT]-(s7),
  (s5)-[:NEXT {distance: 1.2}]->(s4),(s4)-[:NEXT {distance: 0.34}]->(s3),
  (s3)-[:NEXT {distance: 0.76}]->(s2), (s2)-[:NEXT {distance: 0.3}]->(s1),
  (s7)-[:NEXT {distance: 1.4}]->(s6)

服务上的每个 Stop 在一个 Station 处进行 CALLS_AT。每个 Stop 具有 arrives 和 departs 属性，表示火车在 Station 的时间。沿着 Stop 的 NEXT 关系将给出服务的下一个 Stop。

在此示例中，构建了一个路径模式来匹配允许乘客从 Denmark Hill 到 Clapham Junction 的每个服务。以下显示了路径模式应匹配的两条路径

patterns qpp solutions

以下模式代表一个固定长度的路径模式，用于匹配从 Denmark Hill 站 17:07 出发的服务

patterns qpp motif1

要匹配第二趟从 Denmark Hill 17:10 出发的列车服务，需要一个更短的路径模式

patterns qpp motif2

将这些模式转换为 Cypher，并添加谓词以匹配起点和终点 Stations，分别得到以下两个路径模式

(:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(:Stop)
  -[:NEXT]->(:Stop)
  -[:NEXT]->(:Stop)
  -[:NEXT]->(:Stop)-[:CALLS_AT]->
(:Station { name: 'Clapham Junction' })
(:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(:Stop)
  -[:NEXT]->(:Stop)-[:CALLS_AT]->
(:Station { name: 'Clapham Junction' })

要使用这些固定长度路径模式在同一查询中返回两个解决方案，需要对两个 MATCH 语句进行 UNION。例如，以下查询返回两个服务的 departure

查询
MATCH (:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(d:Stop)
        -[:NEXT]->(:Stop)
        -[:NEXT]->(:Stop)
        -[:NEXT]->(a:Stop)-[:CALLS_AT]->
      (:Station { name: 'Clapham Junction' })
RETURN d.departs AS departureTime, a.arrives AS arrivalTime
UNION
MATCH (:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(d:Stop)
        -[:NEXT]->(a:Stop)-[:CALLS_AT]->
      (:Station { name: 'Clapham Junction' })
RETURN d.departs AS departureTime, a.arrives AS arrivalTime
表 1. 结果
departureTime arrivalTime

"17:07:00Z"

"17:19:00Z"

"17:10:00Z"

"17:17:00Z"

行数: 2

这个解决方案的问题在于它不仅冗长，而且只能在目标路径长度事先已知的情况下使用。量化路径模式通过将路径模式的重复部分提取到括号中并应用量词来解决这个问题。该量词指定了提取模式可能重复的匹配范围。对于当前示例，第一步是识别重复模式，在此例中它是交替的 Stop 节点和 NEXT 关系的序列，代表 Service 的一个段

(:Stop)-[:NEXT]->(:Stop)

最短路径包含此模式的一个实例，最长路径包含三个实例。因此，应用于括号的量词是范围一到三，表示为 {1,3}

((:Stop)-[:NEXT]->(:Stop)){1,3}

这还包括两个重复，但在本例中，此重复不会返回匹配项。要理解此模式的语义，有助于通过重复的展开来理解。以下是量词指定的三种重复，组合成一个路径模式的并集

(:Stop)-[:NEXT]->(:Stop) |
(:Stop)-[:NEXT]->(:Stop)(:Stop)-[:NEXT]->(:Stop) |
(:Stop)-[:NEXT]->(:Stop)(:Stop)-[:NEXT]->(:Stop)(:Stop)-[:NEXT]->(:Stop)

这里的联合运算符 (|) 和将节点模式彼此相邻放置仅用于说明；这样使用不属于 Cypher 语法的一部分。在上述扩展中，当两个节点模式相邻时，它们必须匹配同一个节点：Service 的下一个段从前一个段结束的地方开始。因此，它们可以重写为单个节点模式，并以合取方式组合任何过滤条件。在此示例中，这很简单，因为应用于这些节点的过滤条件只是标签 Stop

patterns qpp illustration

有了这个，路径模式的并集简化为

(:Stop)-[:NEXT]->(:Stop) |
(:Stop)-[:NEXT]->(:Stop)-[:NEXT]->(:Stop) |
(:Stop)-[:NEXT]->(:Stop)-[:NEXT]->(:Stop)-[:NEXT]->(:Stop)

连接 Stations 到 Stops 的原始路径模式的段也可以重写。以下是这些段与第一次重复连接时的样子

(:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(:Stop)
(:Stop)-[:NEXT]->(:Stop)
(:Stop)-[:CALLS_AT]->(:Station { name: 'Clapham Junction' })

原始的 MATCH 子句现在包含以下三个部分

patterns qpp query breakdown

将固定长度路径模式的并集转换为量化路径模式，会得到一个将返回正确路径的模式。以下查询添加了一个 RETURN 子句，该子句返回两个服务的出发和到达时间

查询
MATCH (:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(d:Stop)
      ((:Stop)-[:NEXT]->(:Stop)){1,3}
      (a:Stop)-[:CALLS_AT]->(:Station { name: 'Clapham Junction' })
RETURN d.departs AS departureTime, a.arrives AS arrivalTime
表 2. 结果
departureTime arrivalTime

"17:10Z"

"17:17Z"

"17:07Z"

"17:19Z"

行数: 2

量化关系

量化关系允许将一些简单的量化路径模式以更简洁的方式重写。继续上一节中 Stations 和 Stops 的示例，考虑以下查询

查询
MATCH (d:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(n:Stop)
      ((:Stop)-[:NEXT]->(:Stop)){1,10}
      (m:Stop)-[:CALLS_AT]->(a:Station { name: 'Clapham Junction' })
WHERE m.arrives < time('17:18')
RETURN n.departs AS departureTime

如果关系 NEXT 仅连接 Stop 节点，则可以删除 :Stop 标签表达式

查询
MATCH (d:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(n:Stop)
      (()-[:NEXT]->()){1,10}
      (m:Stop)-[:CALLS_AT]->(a:Station { name: 'Clapham Junction' })
WHERE m.arrives < time('17:18')
RETURN n.departs AS departureTime

当量化路径模式具有一个关系模式时，它可以缩写为量化关系。量化关系是带有后缀量词的关系模式。下面是使用量化关系重写的上一个查询

查询
MATCH (d:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-
        (n:Stop)-[:NEXT]->{1,10}(m:Stop)-[:CALLS_AT]->
        (a:Station { name: 'Clapham Junction' })
WHERE m.arrives < time('17:18')
RETURN n.departs AS departureTime

量词 {1,10} 的作用域是关系模式 -[:NEXT]->，而不是与其相邻的节点模式。更一般地，当量化路径模式中包含的路径模式具有以下形式时

(() <relationship pattern> ()) <quantifier>

那么它可以重写如下

<relationship pattern> <quantifier>

在 Neo4j 5.9 中引入量化路径模式和量化关系之前，Cypher 中匹配可变长度路径的唯一方法是通过可变长度关系。此语法仍然可用，但它不符合 GQL 规范。它与量化关系的语法非常相似，但存在以下差异

  • 量词的位置和语法。

  • 星号符号的语义。

  • 类型表达式仅限于 析取运算符。

  • 不允许使用 WHERE 子句。

有关更多信息，请参阅关于 可变长度关系 的参考部分。

组变量

本节沿用上一节中 Stations 和 Stops 的示例，但为 NEXT 关系添加了额外的属性 distance

patterns group variables graph

顾名思义，此属性表示两个 Stop 之间的距离。要返回连接一对 Station 的每个服务的总距离，需要一个引用每个遍历关系的变量。同样，要提取每个 Stop 的 departs 和 arrives 属性，需要引用每个遍历节点的变量。在此示例中，匹配 Denmark Hill 和 Clapham Junction 之间的服务时，变量 l 和 m 用于匹配 Stop，变量 r 用于匹配关系。变量 origin 只匹配路径中的第一个 Stop

MATCH (:Station { name: 'Denmark Hill' })<-[:CALLS_AT]-(origin)
      ((l)-[r:NEXT]->(m)){1,3}
      ()-[:CALLS_AT]->(:Station { name: 'Clapham Junction' })

在量化路径模式中声明的变量称为组变量。之所以这样称呼它们，是因为当在量化路径模式之外引用它们时，它们是匹配中绑定的节点或关系的列表。要理解组变量如何绑定到节点或关系，有助于展开量化路径模式，并观察不同变量如何匹配整个匹配路径的元素。这里是量词 {1,3} 给定范围内的每个值的三个不同展开

(l1)-[r1:NEXT]->(m1) |
(l1)-[r1:NEXT]->(m1)(l2)-[r2:NEXT]->(m2) |
(l1)-[r1:NEXT]->(m1)(l2)-[r2:NEXT]->(m2)(l3)-[r3:NEXT]->(m3)

每个变量的下标表示它们属于路径模式重复的哪个实例。下图显示了具有三次重复的路径模式的变量绑定，该模式匹配从 Denmark Hill 17:07 出发的服务。它追踪每个索引变量绑定的节点或关系。请注意，当路径从 Denmark Hill 开始时，索引从右到左增加

patterns group variables graph2

对于此匹配路径，组变量具有以下绑定

l => [n2, n3, n4]
r => [r2, r3, r4]
m => [n3, n4, n5]

第二个解决方案是以下路径

patterns group variables graph3

下表显示了两个匹配的绑定，包括变量 origin。与组变量相反，origin 是一个单例变量，因为它在量化外部声明。单例变量最多绑定到一个节点或关系。

origin l r m

n2

[n2, n3, n4]

[r2, r3, r4]

[n3, n4, n5]

n7

[n7]

[r8]

[n8]

回到最初的目标，即返回 Stop 的出发时间序列以及每个服务的总距离，最终查询利用了组变量与列表推导和列表函数（如 reduce()）的兼容性。

查询
MATCH (:Station {name: 'Denmark Hill'})<-[:CALLS_AT]-(origin)
      ((l)-[r:NEXT]->(m)){1,3}
      ()-[:CALLS_AT]->(:Station {name: 'Clapham Junction'})
RETURN origin.departs + [stop in m | stop.departs] AS departureTimes,
       reduce(acc = 0.0, next in r | round(acc + next.distance, 2)) AS totalDistance
表 3. 结果
departureTimes totalDistance

["17:10:00Z", "17:20:00Z"]

1.4

["17:07:00Z", "17:11:00Z", "17:13:00Z", "17:20:00Z"]

1.4

行数: 2

量化路径模式中的谓词

量化路径模式的一个陷阱是，根据图的不同，它们最终可能匹配非常大量的路径，从而导致查询性能缓慢。当搜索具有较大最大长度的路径或模式过于通用时，尤其如此。但是，通过使用内联谓词精确指定结果中应包含哪些节点和关系，可以在遍历图时剪除不需要的结果。

以下是一些您可以对量化路径模式遍历施加的约束类型示例

  • 节点必须具有特定的标签组合。例如，所有节点必须是 Employee，但不能是 Contractor。

  • 关系必须具有特定类型。例如，路径中的所有关系都必须是 EMPLOYED_BY 类型。

  • 节点或关系必须具有满足某些条件的属性。例如，所有关系都必须具有属性 distance > 10。

为了展示量化路径模式中谓词的实用性，本节考虑一个通过物理距离查找最短路径的示例，并将其与使用 SHORTEST 关键字得到的结果进行比较。此示例中的图继续使用 Station 节点，但为 Station 添加了地理空间 location 属性，以及具有表示一对 Station 之间距离的 distance 属性的 LINK 关系。

patterns qpp predicates

要重新创建该图，请针对空的 Neo4j 数据库运行以下查询

CREATE (lbg:Station {name: "London Bridge"}),
    (bfr:Station {name: "London Blackfriars"}),
    (eph:Station {name: "Elephant & Castle"}),
    (dmk:Station {name: "Denmark Hill"}),
    (pmr:Station {name: "Peckham Rye"}),
    (qrp:Station {name: "Queens Rd Peckham"}),
    (sbm:Station {name: "South Bermondsey"}),
    (lgj:Station {name: "Loughborough Jn"}),
    (hnh:Station {name: "Herne Hill"}),
    (tuh:Station {name: "Tulse Hill"}),
    (ndl:Station {name: "North Dulwich"}),
    (edw:Station {name: "East Dulwich"}),
    (brx:Station {name: "Brixton"})
 SET lbg.location = point({longitude: -0.08609, latitude: 51.50502}),
    bfr.location = point({longitude: -0.10333, latitude: 51.51181}),
    eph.location = point({longitude: -0.09873, latitude: 51.49403}),
    dmk.location = point({longitude: -0.08936, latitude: 51.46820}),
    pmr.location = point({longitude: -0.06941, latitude: 51.47003}),
    qrp.location = point({longitude: -0.05731, latitude: 51.47357}),
    sbm.location = point({longitude: -0.05468, latitude: 51.48814}),
    lgj.location = point({longitude: -0.10218, latitude: 51.46630}),
    hnh.location = point({longitude: -0.10229, latitude: 51.45331}),
    tuh.location = point({longitude: -0.10508, latitude: 51.43986}),
    ndl.location = point({longitude: -0.08792, latitude: 51.45451}),
    edw.location = point({longitude: -0.08057, latitude: 51.46149}),
    brx.location = point({longitude: -0.11418, latitude: 51.46330})
CREATE (lbg)<-[:LINK {distance: 1.13}]-(bfr),
    (bfr)<-[:LINK {distance: 1.21}]-(eph),
    (eph)-[:LINK {distance: 2.6}]->(dmk),
    (dmk)-[:LINK {distance: 0.86}]->(pmr),
    (pmr)-[:LINK {distance: 0.71}]->(qrp),
    (qrp)<-[:LINK {distance: 0.95}]-(sbm),
    (sbm)<-[:LINK {distance: 1.8}]-(lbg),
    (lgj)-[:LINK {distance: 0.88}]->(hnh),
    (hnh)-[:LINK {distance: 1.08}]->(tuh),
    (tuh)<-[:LINK {distance: 1.29}]-(ndl),
    (ndl)-[:LINK {distance: 0.53}]->(edw),
    (edw)-[:LINK {distance: 0.84}]->(pmr),
    (eph)-[:LINK {distance: 2.01}]->(lgj),
    (dmk)-[:LINK {distance: 1.11}]->(brx),
    (brx)-[:LINK {distance: 0.51}]->(hnh)

以下查询查找从 London Blackfriars 到 North Dulwich 的 ALL SHORTEST 路径的路径长度和总距离

查询
MATCH (bfr:Station {name: 'London Blackfriars'}),
      (ndl:Station {name: 'North Dulwich'})
MATCH p = ALL SHORTEST (bfr)-[:LINK]-+(ndl)
RETURN [n in nodes(p) | n.name] AS stops,
       length(p) as stopCount,
       reduce(acc = 0, r in relationships(p) | round(acc + r.distance, 2)) AS distance
表 4. 结果
stops stopCount distance

["London Blackfriars", "Elephant & Castle", "Denmark Hill", "Peckham Rye", "East Dulwich", "North Dulwich"]

5

6.04

["London Blackfriars", "Elephant & Castle", "Loughborough Jn", "Herne Hill", "Tulse Hill", "North Dulwich"]

5

6.47

行数: 2

ALL SHORTEST 按跳数查找所有最短路径，结果显示，图中有两条路径并列最短路径。这些路径中是否有任何一条对应于按距离计算的最短路径，可以通过查看两个终点 Station 之间的每条路径并按 distance 排序后返回第一个结果来检查。

查询
MATCH (bfr:Station {name: 'London Blackfriars'}),
      (ndl:Station {name: 'North Dulwich'})
MATCH p = (bfr)-[:LINK]-+(ndl)
RETURN reduce(acc = 0, r in relationships(p) | round(acc + r.distance, 2))
    AS distance
ORDER BY distance LIMIT 1
表 5. 结果
distance

5.96

行数: 1

这表明存在一条路线，其距离比使用 ALL SHORTEST 返回的具有更少 Station 的任何路径都短。但要获得此结果，查询必须首先找到从 London Blackfriars 到 North Dulwich 的所有路径，然后才能选择最短的一条。以下查询显示了可能的路径数量

查询
MATCH (bfr:Station {name: 'London Blackfriars'}),
      (ndl:Station {name: 'North Dulwich'})
MATCH p = (bfr)-[:LINK]-+(ndl)
RETURN count(*) AS numPaths
表 6. 结果
numPaths

7

行数: 1

对于这样的小数据集，查找所有路径会很快。但随着图的大小增长，执行时间将呈指数级增长。对于真实数据集，例如英国的整个铁路网络，这可能需要不可接受的长时间。

避免路径呈指数级增长的一种方法是为量化路径模式设置一个有限上限（例如 {,10}），以限制返回的路径迭代次数。当已知解决方案在一定跳数范围内时，这很有效。但在未知的情况下，另一种替代方案是通过例如添加节点标签或指定关系方向来使模式更具体。另一种替代方案是向量化路径模式添加内联谓词。

在此示例中，可以添加一个利用 Stations 地理空间 location 属性的内联谓词：对于路径上的每对 Station，第二个 Station 将更靠近终点（并非总是如此，但在此处假定为简化示例）。为了构成谓词，使用 point.distance() 函数来比较路径上每个节点对中左侧 Station (a) 与右侧 Station (b) 到目的地 North Dulwich 的距离。

查询
MATCH (bfr:Station {name: "London Blackfriars"}),
      (ndl:Station {name: "North Dulwich"})
MATCH p = (bfr)
          ((a)-[:LINK]-(b:Station)
            WHERE point.distance(a.location, ndl.location) >
              point.distance(b.location, ndl.location))+ (ndl)
RETURN reduce(acc = 0, r in relationships(p) | round(acc + r.distance, 2))
  AS distance
表 7. 结果
distance

5.96

行数: 1

此查询避免了必须查找所有可能的路径，然后施加 LIMIT 1 来按距离查找最短路径。它还表明，解决此查询只有一条路径（即使包含英国铁路网络其余数据，该数字也保持不变）。因此，在可能的情况下使用内联谓词或使量化路径模式更具体可以大大提高查询性能。

延伸阅读

© . All rights reserved.