Пути переменной длины: *1..3

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

Звёздочка в связи

Вспомни игру «шесть рукопожатий»: любые два человека на Земле связаны цепочкой знакомств не длиннее шести шагов. Чтобы проверить её на клубе, нужен паттерн «от одного до шести шагов». В Cypher он пишется звёздочкой внутри квадратных скобок связи:

• -[:KNOWS*1..3]-> от одного до трёх шагов;
• -[:KNOWS*2]-> ровно два шага;
• -[:KNOWS*..2]-> до двух шагов, нижняя граница по умолчанию 1;
• -[:KNOWS*]-> сколько угодно шагов, от одного и дальше.

Такой кусок паттерна называют путём переменной длины. Все, до кого Аня дотягивается за три шага, и длина каждого пути:

MATCH p = (:Person {name: 'Аня'})-[:KNOWS*1..3]->(x)
RETURN x.name, length(p) AS hops
ORDER BY hops, x.name;

+----------------+
| x.name  | hops |
+----------------+
| "Борис" | 1    |
| "Глеб"  | 1    |
| "Вера"  | 2    |
| "Глеб"  | 2    |
| "Дина"  | 2    |
| "Аня"   | 3    |
| "Дина"  | 3    |
| "Егор"  | 3    |
+----------------+

8 rows

Функция length(p) возвращает число связей в пути. Глеб встречается дважды: к нему ведут путь в один шаг и путь в два через Бориса. Сама Аня тоже в ответе, круг Аня, Борис, Вера замыкается на третьем шаге.

Ровно два шага:

MATCH (:Person {name: 'Аня'})-[:KNOWS*2]->(x)
RETURN x.name
ORDER BY x.name;

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

3 rows

Что внутри пути

Путь хранит все свои узлы и связи. Функции nodes(p) и relationships(p) достают их списками, а генератор списка [n IN nodes(p) | n.name] превращает узлы в имена. Цепочки знакомств от Дины без ограничения длины:

MATCH p = (:Person {name: 'Дина'})-[:KNOWS*]->(x)
RETURN [n IN nodes(p) | n.name] AS chain, length(p) AS hops
ORDER BY hops;

+-------------------------------------------------+
| chain                                    | hops |
+-------------------------------------------------+
| ["Дина", "Егор"]                         | 1    |
| ["Дина", "Егор", "Жанна"]                | 2    |
| ["Дина", "Егор", "Жанна", "Зоя"]         | 3    |
| ["Дина", "Егор", "Жанна", "Зоя", "Илья"] | 4    |
+-------------------------------------------------+

4 rows

У каждой связи в пути можно спросить свойства. Годы знакомств вдоль каждой цепочки от Ани длиной до двух шагов:

MATCH p = (:Person {name: 'Аня'})-[:KNOWS*1..2]->(x)
RETURN x.name, [r IN relationships(p) | r.since] AS years
ORDER BY x.name, years;

+------------------------+
| x.name  | years        |
+------------------------+
| "Борис" | [2015]       |
| "Вера"  | [2015, 2018] |
| "Глеб"  | [2015, 2019] |
| "Глеб"  | [2020]       |
| "Дина"  | [2020, 2021] |
+------------------------+

5 rows

Без направления и без повторов

Звёздочка работает и со связями без стрелки. Сколько участников вообще достижимо от Ани за шесть шагов в любую сторону:

MATCH (:Person {name: 'Аня'})-[:KNOWS*1..6]-(x:Person)
RETURN count(DISTINCT x) AS reachable;

+-----------+
| reachable |
+-----------+
| 9         |
+-----------+

1 row

Девять из десяти, вместе с самой Аней, до которой путь тоже дотягивается по кругу. Не хватает только Яны, у неё нет ни одной связи.

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

Почему нужна верхняя граница

Число путей растёт очень быстро. У каждого участника большой соцсети сотни знакомых. Один шаг это сотни путей, два шага десятки тысяч, пять шагов уже триллионы. База честно попробует перебрать их все, и запрос «повиснет».

Поэтому у пути переменной длины почти всегда ставят верхнюю границу, например *1..4. Звёздочку без границы пиши только на маленьком графе или там, где путь по смыслу короткий: дерево категорий, цепочка версий документа. Песочница уроков тоже следит за этим и прерывает слишком дорогой перебор строкой sandbox: ....

Если нужен один кратчайший путь, а не все пути, для этого есть отдельный инструмент shortestPath, о нём урок про типовые задачи.

Новая запись с фигурными скобками

В Cypher 25 есть и запись из стандарта GQL: количество повторов пишут после связи в фигурных скобках, как в регулярных выражениях. {1,3} значит то же, что *1..3, а + после связи значит «один и больше».

MATCH (:Person {name: 'Аня'})-[:KNOWS]->{1,3}(x)
RETURN DISTINCT x.name
ORDER BY x.name;

+---------+
| x.name  |
+---------+
| "Аня"   |
| "Борис" |
| "Вера"  |
| "Глеб"  |
| "Дина"  |
| "Егор"  |
+---------+

6 rows

Обе записи работают, в уроках раздела мы чаще используем звёздочку: она короче и встречается в большинстве примеров в сети.

Попробуй сам

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

Сожми диапазон до *1..2 и посмотри, какая часть клуба пропала. Потом верни имена и длину пути вместо самих путей.

Проверь себя

Задание

Дальше

Мы научились находить много строк. Пора научиться сворачивать их в итоги: сколько книг у каждого, средняя оценка, список знакомых одним значением. В следующем уроке разбираем count, collect и неявную группировку.