变长模式

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

量化路径模式

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

当需要搜索从锚点节点可达的所有节点、查找连接两个节点的所有路径，或者遍历可能具有不同深度的层次结构时，量化路径模式非常有用。

本示例使用了一个新的图模型

要重新创建该图，请在空的 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 关系可以找到该服务（Service）的下一个 Stop。

对于本示例，构建了一个路径模式，用于匹配所有允许乘客从 Denmark Hill 前往 Clapham Junction 的服务。以下展示了该路径模式应匹配的两条路径

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

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

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

(: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

结果
departureTime	arrivalTime
`"17:07:00Z"`	`"17:19:00Z"`
`"17:10:00Z"`	`"17:17:00Z"`
行：2

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

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

最短路径包含该模式的一个实例，最长包含三个。因此，应用于包装括号的量词是 1 到 3 的范围，表示为 {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

由此，路径模式的并集简化为

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

连接 Station 和 Stop 的原始路径模式片段也可以重写。以下是这些片段与第一次重复拼接后的样子

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

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

将固定长度路径模式的并集转换为量化路径模式，会生成一个能返回正确路径的模式。以下查询添加了一个 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

结果
departureTime	arrivalTime
`"17:10Z"`	`"17:17Z"`
`"17:07Z"`	`"17:19Z"`
行：2

量化关系

量化关系允许以更简洁的方式重写某些简单的量化路径模式。继续沿用上一节中 Station 和 Stop 的例子，考虑以下查询

查询

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>

在引入量化路径模式和量化关系之前，Cypher 中匹配可变长度路径的唯一方法是通过可变长度关系。这种语法仍然可用，但它不符合 GQL 标准。它与量化关系的语法非常相似，区别如下

量词的位置和语法。
星号 (*) 符号的语义。
类型表达式仅限于析取运算符。
不允许使用 WHERE 子句。

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

组变量

本节使用了上一节中关于 Station 和 Stop 的示例，但在 NEXT 关系中添加了一个额外的 distance 属性

顾名思义，该属性表示两个 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)

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

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

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

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

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

origin l r m

origin	l	r	m
`n2`	`[n2, n3, n4]`	`[r2, r3, r4]`	`[n3, n4, n5]`
`n7`	`[n7]`	`[r8]`	`[n8]`

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

结果
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 属性。
对于量化路径模式的每次迭代，构造路径上的聚合值必须满足谓词。例如，在构造路径的每一步，路径中关系的 distance 属性之和必须小于 50。有关此谓词的更多信息，请参阅 allReduce。

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

要重新创建该图，请在空的 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

结果
stops	stopCount	距离
`["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.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

结果
numPaths
`7`
行：1

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

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

在此示例中，可以添加一个利用 Station 的地理空间 location 属性的内联谓词：对于路径上的每对 Station，第二个 Station 将更接近终点（这并非总是正确的，但在此假设以使示例保持简单）。为了编写该谓词，使用 point.distance() 函数来比较沿路径通往目的地 North Dulwich 的每个节点对的左侧 Station (a) 和右侧 Station (b) 之间的距离

查询

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

结果
距离
`5.96`
行：1

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

另一种替代方法是使用总距离的上界，例如 6.05。一旦路径超过此上界，您就可以剪枝并继续搜索其他路径。allReduce 谓词函数可以表达如下

查询

MATCH (bfr:Station {name: "London Blackfriars"}),
      (ndl:Station {name: "North Dulwich"})
MATCH p = (bfr) ((a)-[l:LINK]-(b:Station))+ (ndl)
WHERE allReduce(
  pathLength = 0,
  link IN l | pathLength + link.distance,
  pathLength < 6.05
)
RETURN reduce(acc = 0, r in relationships(p) | round(acc + r.distance, 2))
  AS distance
ORDER BY distance LIMIT 1

变长模式

量化路径模式

量化关系

组变量

量化路径模式中的谓词

延伸阅读