Gremlin 查询（SQL 自连接）

Question

我对 Gremlin 还很陌生，我已经对 this guide 进行了一些练习，但是当涉及到编写更复杂的查询时，我显然还没有掌握它的窍门。为了让您了解上下文，我正在尝试回答 SQL 中的一个问题，该问题可以通过自连接轻松破解。

想象一下下面的简化图：

如您所见，图中有两种类型的实体：路线和航段。一条路线由 1+ 条腿按照特定顺序（在边缘指定）组成，一条腿可以在多条路线中。

我想回答的问题是：有哪些路线从一个国家到另一个国家，然后又回到之前的国家？

在上图中，Route 1 在第一段从 ES 到 FR，在第三段从 FR 到 ES，因此查询的输出如下：

=> Route id: 1
=> Leg1 order: 1
=> Leg1 id: 1
=> Leg2 order: 3
=> Leg2 id: 3

如果我有以下关系 table:

route_id   leg_id   order  source_country   destination_country
1          1        1      ES               FR
1          2        2      FR               FR
1          3        3      FR               ES

我可以通过以下查询获得所需的输出：

SELECT
  a.route_id
  ,a.leg_id
  ,a.order
  ,b.leg_id
  ,b.order
FROM Routes a
JOIN Routes b
  ON a.route_id = b.route_id
  AND a.source_country = b.destination_country
  AND a.destination_country = b.source_country
WHERE a.source_country <> a.destination_country;

说到用 Gremlin 编写它，我真的不太确定如何开始。我的经验不足让我也想执行自连接，但即便如此我也没有走得太远：

g.V().hasLabel('Route').as('a').V().hasLabel('Route').as('b').where('a', eq('b')).and(join 'a' edges&legs with 'b' edges&legs)...

仅此而已，因为我不知道如何再次引用 a 作为可以遍历以查找连接到路线的边和腿的对象。

任何 help/guidance 将不胜感激，这个问题肯定可以用更简单的方法解决:)

谢谢，本托

Answer 1

对于图表，您应该尝试考虑 "navigating connected things" 而不是 "joining disparate things" 的术语，因为对于图表，事物已经明确地连接在一起。这也有助于思考被惰性评估的事物流（即对象从一个 Gremlin 步骤进入下一个步骤）。

首先，图片很好，但以 Gremlin 脚本的形式提供一些示例数据总是更有帮助：

g = TinkerGraph.open().traversal()
g.addV('route').property('rid',1).as('r1').
  addV('route').property('rid',2).as('r2').
  addV('route').property('rid',3).as('r3').
  addV('leg').property('lid',1).property('source','ES').property('dest','FR').as('l1').
  addV('leg').property('lid',2).property('source','FR').property('dest','FR').as('l2').
  addV('leg').property('lid',3).property('source','FR').property('dest','ES').as('l3').
  addV('leg').property('lid',4).property('source','ES').property('dest','FR').as('l4').
  addV('leg').property('lid',5).property('source','FR').property('dest','FR').as('l5').
  addV('leg').property('lid',6).property('source','FR').property('dest','US').as('l6').
  addE('has_leg').from('r1').to('l1').property('order',1).
  addE('has_leg').from('r1').to('l2').property('order',2).
  addE('has_leg').from('r1').to('l3').property('order',3).
  addE('has_leg').from('r3').to('l4').property('order',1).
  addE('has_leg').from('r3').to('l5').property('order',2).
  addE('has_leg').from('r3').to('l6').property('order',3).
  addE('has_leg').from('r2').to('l2').property('order',1).iterate()

您的问题是：

which routes travel from one country to another, and then back to the previous country?

请注意，我添加了一些不符合该问题要求的额外数据，以确保我的遍历工作正常。我想我假设你愿意接受只停留在国内的路线，就像从 "FR" 到 FR 的腿一样，因为它开始于 "FR" 并结束于 "previous country" .我想我可以进一步修改它来做到这一点，如果你真的需要我这样做，但现在我会坚持这个假设，因为你只是在学习。

在考虑了数据并阅读了那个问题后，我立即想到，让我们找到您做得足够好的路线，然后让我们看看如何获得旅行的起点和终点那条路线：

gremlin> g.V().hasLabel('route').
......1>   map(outE('has_leg').
......2>       order().by('order').
......3>       union(limit(1).inV().values('source'), tail().inV().values('dest')).
......4>       fold())
==>[ES,ES]
==>[FR,FR]
==>[ES,US]

所以，我找到了一个带有 hasLabel('route') 的 "route" 顶点，然后我将每个顶点转换为起始国家和结束国家的 List（即第一项是"source" 国家，第二项是 "dest" 国家）。为此，我遍历传出的 "has_leg" 边，对它们进行排序。一旦订购，我抓住流中的第一个边缘（即 limit(1)）并遍历传入的 "leg" 顶点并获取其 "source" 值并对最后一个传入顶点执行相同的操作边缘（即 tail()），但这次获取其 "dest" 值。然后我们使用 fold() 将那两个项目流从 union() 推入 List。同样，因为这一切都发生在 map() 内部，我们有效地为每个 "route" 顶点做了这件事，所以我们得到三对作为结果。

有了这个输出，我们现在需要比较成对的 start/end 值，以确定哪个代表起始和结束于同一国家/地区的路线。

gremlin> g.V().hasLabel('route').
......1>   filter(outE('has_leg').
......2>          order().by('order').
......3>          fold().
......4>          project('start','end').
......5>            by(unfold().limit(1).inV().values('source')).
......6>            by(unfold().tail().inV().values('dest')).
......7>          where('start', eq('end'))).
......8>   elementMap()
==>[id:0,label:route,rid:1]
==>[id:2,label:route,rid:2]

在第 1 行，请注意我们将 map() 更改为 filter()。我最初只使用 map() 这样我就可以看到我正在遍历的结果，然后我担心如何使用这些结果来摆脱我不想要的数据。当您在遍历中构建越来越复杂时，这是 Gremlin 的常见做法。所以我们现在准备将 filter() 应用于每个 "route" 顶点。我想有很多方法可以做到这一点，但我选择将所有有序边收集到第 3 行的 List 中。然后我 project() 在第 4 行的那一步并转换边列表对于使用关联的 by() 调制器的 "start" 和 "end" 键。在这两种情况下，我都必须 unfold() 将边列表添加到流中，然后应用前面解释过的相同 limit(1) 和 tail() 类型的遍历。结果是带有 "start" 和 "end" 键的 Map，可以使用 where() 步骤进行比较。从结果可以看出，第三条从"ES"开始到"US"结束的路由已经被过滤掉了

我将根据您的评论扩展我的答案 - 因为我之前的所有数据似乎都符合您想要找到 returns 任何意义上通往某个国家/地区的任何路线的更一般情况：

g = TinkerGraph.open().traversal()
g.addV('route').property('rid',1).as('r1').
  addV('route').property('rid',2).as('r2').
  addV('route').property('rid',3).as('r3').
  addV('route').property('rid',4).as('r4').
  addV('leg').property('lid',1).property('source','ES').property('dest','FR').as('l1').
  addV('leg').property('lid',2).property('source','FR').property('dest','FR').as('l2').
  addV('leg').property('lid',3).property('source','FR').property('dest','ES').as('l3').
  addV('leg').property('lid',4).property('source','ES').property('dest','FR').as('l4').
  addV('leg').property('lid',5).property('source','FR').property('dest','FR').as('l5').
  addV('leg').property('lid',6).property('source','FR').property('dest','US').as('l6').
  addV('leg').property('lid',7).property('source','ES').property('dest','FR').as('l7').
  addV('leg').property('lid',8).property('source','FR').property('dest','CA').as('l8').
  addV('leg').property('lid',9).property('source','CA').property('dest','US').as('l9').
  addE('has_leg').from('r1').to('l1').property('order',1).
  addE('has_leg').from('r1').to('l2').property('order',2).
  addE('has_leg').from('r1').to('l3').property('order',3).
  addE('has_leg').from('r3').to('l4').property('order',1).
  addE('has_leg').from('r3').to('l5').property('order',2).
  addE('has_leg').from('r3').to('l6').property('order',3).
  addE('has_leg').from('r4').to('l7').property('order',1).
  addE('has_leg').from('r4').to('l8').property('order',2).
  addE('has_leg').from('r4').to('l9').property('order',3).
  addE('has_leg').from('r2').to('l2').property('order',1).iterate()

如果我有这个权利，应该过滤新添加的 "rid=4" 路线，因为它的路线永远不会重新访问同一个国家。我认为 Gremlin 的这一点比我之前建议的更容易，因为现在我们只需要寻找独特的路线，这意味着如果我们满足这两种情况之一，那么我们就找到了我们关心的路线：

有一条腿而且starts/ends在同一个国家
有多个航段，如果该国家/地区在路线中出现的次数超过 2 次（因为我们正在考虑 "source" 和 "dest"）

这是 Gremlin：

gremlin> g.V().hasLabel('route').
......1>   filter(out('has_leg').
......2>          union(values('source'), 
......3>                values('dest')).
......4>          groupCount().
......5>          or(select(values).unfold().is(gt(2)),
......6>             count(local).is(1))).
......7>   elementMap()
==>[id:0,label:route,rid:1]
==>[id:2,label:route,rid:2]
==>[id:4,label:route,rid:3]

如果您理解我之前对代码的解释，那么您可能会按照第 5 行之前的所有内容进行操作，我们采用 groupCount() 对国家名称生成的 Map 并应用两个过滤条件我刚刚描述。在第 5 行，我们应用第二个条件，从 Map 中提取值（即每个国家/地区出现次数的计数）并检测是否有大于 2 的值。在第 6 行，我们对条目进行计数在映射到第一个条件的 Map 中。请注意，我们在那里使用 local 是因为我们不计算流中的 Map-对象，而是计算 Map 中的条目（即 Map 的本地条目）。

Answer 2

以防万一它在这里有用是我在看到斯蒂芬已经回答之前正在玩的一个类似的例子。这使用教程中的航线数据集。第一个示例专门从 LHR 开始。第二个是查看所有机场。我假设一个常数为 2 段。您可以通过修改查询来更改它，而且正如 Stephen 提到的那样，您可以通过多种方式来解决这个问题。

gremlin> g.V().has('code','LHR').as('a').
......1>       out().
......2>       where(neq('a')).by('country').
......3>       repeat(out().simplePath()).times(1).
......4>       where(eq('a')).by('country').
......5>       path().
......6>         by(values('country','code').fold()).
......7>       limit(5) 

==>[[UK,LHR],[MA,CMN],[UK,LGW]]
==>[[UK,LHR],[MA,CMN],[UK,MAN]]
==>[[UK,LHR],[MA,TNG],[UK,LGW]]
==>[[UK,LHR],[CN,CTU],[UK,LGW]]
==>[[UK,LHR],[PT,FAO],[UK,BHX]]  



gremlin> g.V().hasLabel('airport').as('a').
......1>       out().
......2>       where(neq('a')).by('country').
......3>       repeat(out().simplePath()).times(1).
......4>       where(eq('a')).by('country').
......5>       path().
......6>         by(values('country','code').fold()).
......7>       limit(5) 

==>[[US,ATL],[CL,SCL],[US,DFW]]
==>[[US,ATL],[CL,SCL],[US,IAH]]
==>[[US,ATL],[CL,SCL],[US,JFK]]
==>[[US,ATL],[CL,SCL],[US,LAX]]
==>[[US,ATL],[CL,SCL],[US,MCO]]

对于您的具体示例，斯蒂芬使用的利用具有订单号的段的技术要好得多。航线数据集没有分段的概念，但当您开始更多地探索 Gremlin 时，认为这可能会引起一些兴趣。

Gremlin 查询（SQL 自连接）

Gremlin query (SQL self-join)

graph

self-join

graph-databases

gremlin