DAGs in Data Pipelines

• A directed acyclic graph is the minimum structure that can express "after" without expressing "when". That distinction is the whole point: dependency is a statement about correctness, scheduling is a statement about time, and conflating them is what makes cron-driven pipelines fragile (Scheduler vs Orchestrator).
• Acyclicity is what makes the graph *executable*. A cycle means there is no order in which every node runs after its dependencies, because each is waiting on the other. Detection is the same traversal that produces the ordering — a topological sort that cannot consume every node has found a cycle (Topological Sort).
• The standard algorithms map directly onto operational questions. Kahn's algorithm, repeatedly taking nodes with no unmet dependencies, gives both a valid execution order and the natural parallel batches. A depth-first traversal with a colouring scheme detects cycles and yields the reverse-postorder ordering (DFS Topological Sort).
• Forward reachability from a node is its blast radius; reverse reachability is its provenance. These are the same traversal on the same graph with the edges flipped, which is why a platform that can answer one can always answer the other (Depth-First Search (DFS)).
• Longest-path reasoning over the DAG — the critical path — is what determines end-to-end build time, and it is the only quantity that adding workers cannot improve. This is a dynamic-programming computation over the topological order, not a search (DP on DAGs).

        raw_orders          raw_refunds        raw_customers
             |                   |                   |
        stg_orders           stg_refunds         stg_customers
             \                  /                   /
              \                /                   /
               int_orders_enriched  <-------------'
                        |
                    fct_orders
                    /         \
        customer_metrics    revenue_daily
                    \         /
                     dashboards

  in-degree 0  -> sources: nothing upstream, must be ingested
  out-degree 0 -> leaves: consumed directly, or dead work
  longest path -> critical path: the floor on end-to-end freshness
  width        -> the most nodes that can ever run at once

• Model dependency as data reads, not as timing. "This runs after that" invites a cycle; "this reads that" cannot produce one unless the data model genuinely has one (Dependency Graphs: The Real Shape of Your Code).
• Let the graph be derived from the code wherever possible. A hand-declared graph is a second source of truth, and second sources of truth drift (dbt Concepts).
• Fail the build on a cycle rather than resolving it automatically. A cycle is information — it says the model is wrong — and silently breaking it with a stale read hides the finding.
• Keep nodes at the granularity you would want to retry. Too coarse and a retry redoes correct work; too fine and the graph is larger than the problem (Retries in Pipelines).
• Represent cross-system dependencies explicitly — an ingestion job, an external file arriving — rather than approximating them with a start time. A schedule that "usually runs late enough" is a dependency with no edge (Orchestration).

• The graph guarantees that a valid execution order exists and that any topological order is as correct as any other. Which one you get is not specified and must not matter.
• It guarantees that a cycle is detectable before anything runs, which is the cheapest possible moment to find one.
• It guarantees nothing about time. There is no promise that a node runs at a particular hour, within a duration, or after an external system has finished — those are scheduling and sensing concerns layered on top (Task Dependencies).
• It guarantees nothing about data. A perfectly ordered traversal over stale, empty or duplicated inputs completes successfully and reports success (The Pipeline Succeeded. The Data Is Wrong.).