Directed Acyclic Graph (DAG)

Every connection in a DAG represents a one-way dependency from one node to another. If Task B depends on Task A, the edge points A → B, establishing an unambiguous execution order.

• Parent node must complete before child node can begin
• Enables clear dependency resolution in tools like Apache Airflow and Prefect
• Contrasts with undirected graphs where relationships are bidirectional
• Forms the basis for topological sorting algorithms

The 'acyclic' property guarantees that no path exists that starts and ends at the same node. This is the critical safeguard that prevents infinite loops in data pipelines.

• A cycle would mean Task A depends on Task B, which depends on Task A — a deadlock
• DAG validators reject any graph containing a back-edge during construction
• Enables deterministic termination: every DAG execution has a finite endpoint
• Cycle detection is typically O(V+E) using depth-first search algorithms

Every DAG admits at least one topological ordering — a linear sequence of nodes where every directed edge goes from an earlier node to a later node. This ordering is the execution plan.

• Multiple valid orderings may exist for the same DAG
• Schedulers use Kahn's algorithm or DFS-based methods to compute the order
• Forms the basis for parallel execution: independent nodes at the same depth can run concurrently
• Critical path length determines the minimum possible execution time

DAGs model partial orders rather than total orders. Two nodes with no directed path between them are considered concurrent — they have no dependency relationship and can execute in parallel.

• Enables horizontal scaling: independent tasks fan out across workers
• MapReduce and Spark DAGs exploit this for distributed computation
• The transitive reduction of a DAG removes redundant edges while preserving reachability
• Contrasts with sequential scripts that enforce unnecessary ordering constraints

In event sourcing and data lineage systems, DAGs represent an append-only sequence of transformations. New nodes and edges are added, but existing structure is never modified retroactively.

• Each node represents a discrete transformation or event
• Enables time travel queries: replay the DAG from any historical point
• Used in Git commit histories, blockchain ledgers, and Delta Lake transaction logs
• The Merkle DAG variant adds cryptographic hashing for tamper detection

The transitive closure of a DAG captures all indirect dependencies. If A → B → C, then A transitively depends on C. This is essential for impact analysis in data pipelines.

• Changing node A requires re-evaluating all nodes in its downstream closure
• Used in build systems like Bazel and Make to determine minimal rebuild sets
• Transitive reduction is the inverse operation: removing redundant edges
• Computed using Floyd-Warshall or repeated depth-first traversal