Многошаговые обходы по связям

В первом уроке раздела мы обещали ответить на вопрос Ани «кто из друзей моих друзей ещё не знаком со мной». Теперь у нас есть всё нужное: паттерны, WHERE и DISTINCT. Этот урок про обходы на несколько шагов: как их писать, почему в ответе появляются повторы и как граф защищает тебя от хождения по кругу.

Шаг за шагом

Обход в Cypher пишется цепочкой: каждый новый кусок «связь, узел» это ещё один шаг. Два шага от Ани по исходящим знакомствам:

MATCH (a:Person {name: 'Аня'})-[:KNOWS]->(f)-[:KNOWS]->(fof)
RETURN f.name, fof.name
ORDER BY f.name, fof.name;

+--------------------+
| f.name  | fof.name |
+--------------------+
| "Борис" | "Вера"   |
| "Борис" | "Глеб"   |
| "Глеб"  | "Дина"   |
+--------------------+

3 rows

Каждая строка это одна найденная цепочка из трёх узлов. Через Бориса Аня выходит на Веру и Глеба, через Глеба на Дину.

Глеб в ответе дважды: он друг Ани напрямую и друг её друга Бориса. Если нужен только список людей, повторы убирает DISTINCT:

MATCH (a:Person {name: 'Аня'})-[:KNOWS]->()-[:KNOWS]->(fof)
RETURN DISTINCT fof.name
ORDER BY fof.name;

+----------+
| fof.name |
+----------+
| "Вера"   |
| "Глеб"   |
| "Дина"   |
+----------+

3 rows

Вы можете знать

Знакомство в клубе взаимно, поэтому для рекомендаций направление не важно, пишем связи без стрелок, как в уроке про направление. Остаётся убрать из ответа саму Аню и тех, кого она уже знает:

MATCH (a:Person {name: 'Аня'})-[:KNOWS]-(f)-[:KNOWS]-(fof)
WHERE fof <> a AND NOT (a)-[:KNOWS]-(fof)
RETURN fof.name AS suggestion, count(*) AS mutual
ORDER BY mutual DESC, suggestion;

+---------------------+
| suggestion | mutual |
+---------------------+
| "Дина"     | 1      |
+---------------------+

1 row

fof <> a сравнивает узлы: это разные узлы или один и тот же. NOT (a)-[:KNOWS]-(fof) отбрасывает тех, с кем Аня знакома напрямую. А count(*) считает, через скольких общих знакомых нашёлся человек. Это и есть «вы можете знать» из соцсетей, на чистом Cypher.

Цепочки разных связей

Шаги не обязаны быть одного типа. Где живут знакомые Ани:

MATCH (a:Person {name: 'Аня'})-[:KNOWS]->(f)-[:LIVES_IN]->(c:City)
RETURN f.name, c.name
ORDER BY f.name;

+--------------------+
| f.name  | c.name   |
+--------------------+
| "Борис" | "Москва" |
| "Глеб"  | "Москва" |
+--------------------+

2 rows

Цепочка может сходиться в середине. Пары соседей, то есть участников, живущих в одном городе, это два шага к городу с двух сторон:

MATCH (p:Person)-[:LIVES_IN]->(c:City)<-[:LIVES_IN]-(q:Person)
WHERE p.name < q.name
RETURN c.name, p.name, q.name
ORDER BY c.name, p.name, q.name;

+------------------------------+
| c.name   | p.name  | q.name  |
+------------------------------+
| "Казань" | "Вера"  | "Дина"  |
| "Москва" | "Аня"   | "Борис" |
| "Москва" | "Аня"   | "Глеб"  |
| "Москва" | "Борис" | "Глеб"  |
| "Пермь"  | "Егор"  | "Жанна" |
| "Пермь"  | "Егор"  | "Зоя"   |
| "Пермь"  | "Жанна" | "Зоя"   |
+------------------------------+

7 rows

Условие p.name < q.name оставляет каждую пару один раз. Без него ответ удвоился бы: и «Аня, Борис», и «Борис, Аня».

Круги

В графе бывают циклы: можно выйти из узла и вернуться в него. Аня, Борис и Вера знакомы по кругу. Паттерн, который заканчивается тем же узлом, с которого начался, находит такой круг:

MATCH (a:Person {name: 'Аня'})-[:KNOWS]->(b)-[:KNOWS]->(c)-[:KNOWS]->(a)
RETURN b.name, c.name;

+------------------+
| b.name  | c.name |
+------------------+
| "Борис" | "Вера" |
+------------------+

1 row

Переменная a в конце та же, что в начале, поэтому база ищет путь, который замыкается на Аню.

Одна связь дважды не проходится

Внутри одного MATCH действует важное правило: одна и та же связь не может встретиться в паттерне дважды. Его называют уникальностью связей. Посмотрим на два шага без стрелок от Ани:

MATCH (a:Person {name: 'Аня'})-[:KNOWS]-(f)-[:KNOWS]-(back)
RETURN f.name, back.name
ORDER BY f.name, back.name;

+---------------------+
| f.name  | back.name |
+---------------------+
| "Борис" | "Вера"    |
| "Борис" | "Глеб"    |
| "Вера"  | "Борис"   |
| "Глеб"  | "Борис"   |
| "Глеб"  | "Дина"    |
+---------------------+

5 rows

Казалось бы, от Бориса можно шагнуть обратно к Ане по той же связи, и Аня оказалась бы в конце. Но такой строки нет: связь «Аня, Борис» уже использована на первом шаге. Узлы при этом повторяться могут, как в круге из прошлого раздела. Правило защищает от бесконечных хождений туда и обратно, и это особенно важно для путей переменной длины из следующего урока.

Попробуй сам

Запрос возвращает пути «Аня, знакомый, знакомый знакомого» без учёта направления. На картинке видно, как Аня через Бориса и Глеба выходит почти на всю верхнюю половину клуба.

Добавь третий шаг -[:KNOWS]-() и посмотри, кто появился. Потом напиши рекомендации «вы можете знать» для Зои.

Проверь себя

Задание

Дальше

Два шага, три шага, а если нужно «сколько угодно шагов»? Писать цепочку руками для каждой длины утомительно. В следующем уроке разберём пути переменной длины *1..3 и узнаем, почему у такого пути всегда стоит ставить верхнюю границу.