Зачем graph в курсе для data engineer

В первых десяти модулях вы строили структуры, в которых данные либо лежат в ряд (массив, список), либо в иерархии (дерево, куча), либо адресуются ключом (hash map). Граф — это обобщение всех трёх. Дерево — это связный ациклический граф. Hash map — это, по сути, отображение, которое тоже можно описать графом из двух колонок. Любые таблицы БД, соединённые foreign-key, образуют ориентированный граф.

В реальной работе data engineer граф встречается каждый день — иногда явно, иногда нет:

• DAG в Airflow — расписание задач, направленный ациклический граф; задача B запускается, когда A завершилась.
• Lineage таблиц — какие таблицы породили какие. Это направленный граф, из которого нужно уметь искать «всё, что зависит от raw.orders».
• Foreign-key схема БД — таблицы как вершины, FK как рёбра. Обычно ациклический, но возможны циклы (self-referencing FK).
• Dependency graph моделей dbt — каждая SELECT-модель зависит от других. dbt компилирует это в DAG и решает порядок исполнения.
• Social/event graph — пользователи и их взаимодействия. Колоночные хранилища тут проигрывают графовым.

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

Vertex, edge и формальное определение

V = {A, B, C, D}
E = {(A, B), (B, C), (A, C), (C, D)}

Это всё. Никакой магии — пара множеств. Но из этой пары вырастают десятки разновидностей, и важно различать.

Размер графа описывают двумя числами: |V| = n (количество вершин) и |E| = m (количество рёбер). Big-O оценки в графовых алгоритмах почти всегда формулируются в этих двух буквах: O(V + E), O(V * E), O(V^2). Запомните: V и E — это про размер, не про конкретные вершины.

Directed vs undirected

Главное первое разделение:

В неориентированном ребро между A и B — это просто «они связаны». В ориентированном (digraph) ребро от A к B — это «из A можно попасть в B». От B к A — отдельное ребро, и оно может не существовать.

Undirected:   A —— B    (A и B знают друг о друге)

Directed:     A ——> B    (из A в B стрелка; из B в A — отдельный вопрос)

В DE 90% графов — ориентированные. Lineage: «таблица fact_orders построена из stg_orders». Это стрелка в одну сторону. У dbt: «модель A зависит от модели B». Стрелка из A в B. У Airflow: «task B следует после task A». Стрелка из A в B.

В коде разница в одном: для неориентированного, добавляя ребро (A, B), вы добавляете и (B, A) тоже. Для ориентированного — только то, что добавили.

Weighted vs unweighted

A —(5)—> B
A —(2)—> C
B —(7)—> C

В DE это:

• стоимость операции SQL-плана (cost),
• размер таблицы в байтах при оценке join-плана,
• сетевая задержка между нодами кластера,
• цена транспорта в logistics-данных.

Алгоритмы поиска кратчайшего пути в weighted и unweighted графах — РАЗНЫЕ. На неутяжелённом работает BFS (см. модуль 13). На утяжелённом — Dijkstra, Bellman-Ford, A*. На графе с отрицательными весами BFS вообще даёт неправильный ответ. Если вы кодите без понимания, какой у вас граф — алгоритм будет лгать молча.

Cyclic vs acyclic. Что такое DAG

A —> B —> C —> A     цикл: A->B->C->A
A —> B —> C          цикла нет: до A никак не вернуться

DAG — фундамент data engineering:

• Airflow называется так: «Apache Airflow is a platform to programmatically author, schedule and monitor workflows», но внутри — DAG. Каждый pipeline = один DAG.
• dbt строит DAG моделей; если вы случайно создали цикл (модель A ссылается на модель B, которая ссылается на A), dbt run ляжет с ошибкой «Found a cycle».
• Spark physical plan — тоже DAG операций.
• Git commit history — DAG (если без force-push: merge-коммиты могут иметь больше одного родителя, но цикла никогда).

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

Степени вершин и плотность графа

• in-degree(v) — число рёбер, входящих в v,
• out-degree(v) — число рёбер, выходящих из v.

A —> B —> C
A —> C

in-degree(A) = 0   out-degree(A) = 2
in-degree(B) = 1   out-degree(B) = 1
in-degree(C) = 2   out-degree(C) = 0

Сумма всех out-degree всегда равна |E|. И сумма всех in-degree тоже равна |E| (каждое ребро добавляет ровно 1 куда-то и 1 откуда-то).

В DE in-degree = 0 обычно означает «raw-источник» (никакая другая таблица его не порождает). Out-degree = 0 — «конечная витрина», от неё никто не зависит.

Плотность графа — отношение |E| / |E_max|. Максимально возможное число рёбер в простом directed графе — V * (V - 1) (без петель). Если |E| близко к V^2 — граф плотный (dense). Если |E| близко к V — разреженный (sparse).

В реальности почти все DE-графы разреженные. Lineage из 1000 таблиц редко имеет миллион рёбер — скорее 3000-5000 рёбер (каждая таблица зависит от 3-5 источников). Это решает, как вы будете хранить граф (см. урок 04).

Реальные графы в DE: размеры и характер

Пара примеров с реальными числами, чтобы было с чем сравнивать.

dbt-проект средней компании:

• |V| = 800 моделей,
• |E| = 2400 ref-связей,
• средняя in-degree = 3 (каждая модель зависит в среднем от 3 других),
• DAG, обязательно. dbt не позволит запустить с циклом.

Lineage всего DWH с включёнными сырыми таблицами:

• |V| = 5000-50 000,
• |E| = в 3-10 раз больше,
• разреженный, DAG. Один обход BFS — порядка миллисекунд.

Airflow staging-инсталляция:

• |V| = 50-200 задач в одном DAG,
• |E| = 100-400,
• маленький DAG, можно держать в RAM одной строкой.

Foreign key схема Postgres крупного приложения:

• |V| = 300 таблиц,
• |E| = 600-1000 FK,
• обычно DAG, но иногда self-referencing FK (комментарий ссылается на родительский комментарий) — это циклы длины 1 (петли).

Социальный граф пользователей:

• |V| = миллион,
• |E| = десятки миллионов,
• неориентированный, средне-плотный, обычно содержит огромную связную компоненту. Уже не помещается в простой Python-структуре, нужен Neo4j / igraph / специальный движок.

Для junior DE задачи на графах = первые четыре случая. Размер от десятков до десятков тысяч вершин — комфортный диапазон для встроенных структур Python и networkx.

DE-кейс: проверка корректности dbt-проекта

Допустим, вы пишете утилиту, проверяющую целостность dbt-проекта перед коммитом. Что вы должны проверить графовыми инструментами?

1. Нет циклов. dbt сам кричит, но раннее обнаружение в pre-commit hook — это +5 минут жизни.
2. Нет изолированных моделей. Модель без ref() и без потребителей — кандидат на удаление.
3. Глубина DAG (longest path). Если самая длинная цепочка > 10 уровней — это пахнет архитектурной проблемой.
4. Высокая in-degree. Если модель mart_master_table имеет in-degree = 50 — это монолит, надо разбивать.

Все 4 проверки — стандартные графовые операции, которые мы разберём в модулях 11-12. Если вы прошли мимо темы «граф = (V, E)», ни одну из этих утилит вы не напишете.

Попробуй сам

Вот dbt-подобный список зависимостей. Изобразите граф на бумаге и ответьте на вопросы.

deps = {
    "stg_users": [],
    "stg_orders": [],
    "stg_products": [],
    "int_user_orders": ["stg_users", "stg_orders"],
    "int_order_items": ["stg_orders", "stg_products"],
    "mart_user_revenue": ["int_user_orders", "int_order_items"],
    "mart_top_products": ["int_order_items"],
}

1. Сколько вершин и сколько рёбер в этом графе?
2. Какие вершины имеют in-degree = 0? Что они означают на языке DE?
3. Какие имеют out-degree = 0? Что они означают?
4. Это DAG или нет?
5. Если в int_order_items добавить зависимость от mart_top_products, что произойдёт? Почему dbt этого не позволит?

Решение:

1. |V| = 7, |E| = 7 (считаем количество элементов в списках значений).
2. in-degree = 0 у stg_users, stg_orders, stg_products — это источники (raw / staging-таблицы), ни одна модель в них не направляет.
3. out-degree = 0 у mart_user_revenue и mart_top_products — это витрины (data marts), от них уже никто не зависит.
4. Да, DAG. Все рёбра идут «снизу-вверх» от stg к mart, без обратных стрелок.
5. Цикл int_order_items -> mart_top_products -> int_order_items. Это сделает невозможным topological sort: непонятно, что строить первым. dbt откажется компилировать.

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