可变长度模式

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都CALLS_AT一个Station。每个Stop都有arrives和departs属性，它们给出火车在Station的时间。沿着Stop的NEXT关系走，将得到服务的下一个Stop。

对于本示例，将构建一个路径模式来匹配允许乘客从Denmark Hill到Clapham Junction旅行的每项服务。以下显示了路径模式应匹配的两个路径

patterns qpp solutions

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

patterns qpp motif1

要匹配从Denmark Hill17: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 的范围，表示为{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 示例，但添加了一个额外的属性 distance 到 NEXT 关系中

patterns group variables graph

顾名思义，此属性表示两个 Stops 之间的距离。为了返回连接一对 Stations 的每条服务的总距离，需要一个引用每个遍历关系的变量。类似地，为了提取每个 Stop 的 departs 和 arrives 属性，需要引用每个遍历节点的变量。在本例中，匹配 Denmark Hill 和 Clapham Junction 之间的服务，声明变量 l 和 m 来匹配 Stops，并声明变量 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]

回到最初的目标，即返回 Stops 的出发时间序列以及每条服务的总距离，最终查询利用了组变量与列表推导和列表函数（如 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 节点，但为 Stations 添加了地理空间 location 属性，以及 LINK 关系，该关系具有一个表示一对 Stations 之间距离的 distance 属性

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 查找所有按跳跃次数最短的路径，正如结果所示，图中存在两条路径，它们在最短路径方面并列。可以通过查看两个端点 Stations 之间的每条路径，并在按 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 返回的任何一条具有较少 Stations 的路径都要短。但是为了获得此结果，查询必须首先找到从 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 属性：对于路径上的每对 Stations，第二个 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 来按距离找到最短的路径。它还表明，只有一种路径可以解决查询（即使包含来自英国铁路网络其余部分的数据，该数字也保持不变）。因此，使用内联谓词或在可能的情况下使量化路径模式更具体，可以极大地提高查询性能。