Задачи, рождённые для графа

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

Слова-подсказки

Представь, что задачу тебе диктуют по телефону. Если в ней звучат слова «через кого», «связан ли», «кратчайший путь», «кто ещё», «общий», «цепочка», «зависит от», это почти наверняка граф. Если звучат «сколько всего», «в среднем за месяц», «топ по выручке», это таблицы и агрегаты.

Дальше пять семейств задач, которые чаще всего решают на графах.

Рекомендации

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

В книжном клубе Аня читала «Мастера и Маргариту» и «Пикник на обочине». Посмотрим, что ещё читали те, у кого с ней совпали книги, и чего Аня ещё не открывала:

MATCH (a:Person {name: 'Аня'})-[:READ]->(:Book)<-[:READ]-(other)-[:READ]->(rec:Book)
WHERE NOT (a)-[:READ]->(rec)
RETURN rec.title AS book, count(*) AS votes
ORDER BY votes DESC, book;

+--------------------------------------------+
| book                               | votes |
+--------------------------------------------+
| "Понедельник начинается в субботу" | 2     |
| "Двенадцать стульев"               | 1     |
+--------------------------------------------+

2 rows

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

Маршруты и пути

Метро, дороги, перелёты с пересадками, доставка между складами. Вопрос «как добраться быстрее всего» это поиск кратчайшего пути. Станции это узлы, перегоны это связи, а время в пути хранится свойством связи. Тот же поиск подходит и для людей: через скольких знакомых Аня может выйти на Илью.

Мошенничество

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

Зависимости

Пакет A зависит от B, B от C, C от уязвимой версии D. Какие сервисы пострадают, если D сломать? Это обход по связям «зависит от» на любую глубину. Та же задача у сетевых инженеров («что отвалится, если выключить этот коммутатор») и у тех, кто считает права доступа через вложенные группы.

Графы знаний

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

Как отличить графовую задачу

Задай себе три вопроса:

1. Важны ли связи сами по себе? Если у связи есть свойства (дата знакомства, цена перевода, время перегона), это сигнал в пользу графа.
2. Неизвестна ли глубина? «Найди все зависимости», «есть ли хоть какой-то путь» плохо выражаются фиксированным числом соединений.
3. Меняется ли форма данных? Новые типы связей в графе добавляются без перестройки таблиц.

Три «да» и граф почти наверняка подойдёт. Три «нет» и обычная таблица будет проще. Честный разговор о том, когда граф лишний, ждёт тебя в последнем уроке раздела.

Попробуй сам

Песочница показывает, через какие книги Аня связана с другими читателями. Под ответом будет картинка: Аня в центре, книги вокруг, другие читатели по краям.

Замени 'Аня' на 'Жанна' и сравни картинки: у кого из них больше общих книг с клубом? Потом попробуй запрос рекомендаций из урока для Жанны.

Проверь себя

Задание

Дальше

Мы говорили «узлы», «связи» и «свойства» на бытовом уровне. В следующем уроке дадим им точные определения: из чего состоит модель property graph и чем она отличается от таблиц.