Skip to main content

Directed Acyclic Graph (DAG)

A Directed Acyclic Graph, or DAG, is a concept from mathematics and computer science that describes a specific type of graph.

  • Directed: This means that the connections between the points in the graph (known as nodes) have a direction. In a directed graph, each connection (edge) points from one node to another, indicating a one-way relationship.
  • Acyclic: This term means that there are no cycles in the graph. A cycle occurs when you can start at one node and follow a path of edges that eventually loops back to the starting node. In a DAG, loops aren't allowed.
  • Graph: In this context, a graph is a collection of nodes (which can represent various objects like tasks, events, or states) and edges (which represent the relationships or connections between these nodes).

Key Characteristics of a DAG​

  • Directionality: Each edge has a direction, showing the relationship from one node to another.
  • No Cycles: Once you have left a node, you can't go back to it again. This prevents the chance of circling back to the node through the edges.
  • Topological Ordering: Since DAGs have directed edges and no cycles, you can list the nodes in a linear order. This order respects the direction of the edges, meaning for every directed edge from node A to node B, A appears before B in order.

Applications of DAGs​

DAGs are incredibly useful in scenarios where you need to represent tasks that must be done in a specific order.

Here are a few areas where DAGs are commonly used:

  • Project Scheduling: In project management, tasks that depend on the completion of other tasks can be represented using a DAG. This helps in planning the order of operations.
  • Data Processing: Many data processing workflows involve steps that depend on the outputs of previous steps. DAGs can help in mapping out these dependencies clearly.
  • Blockchain Technology: Some newer cryptocurrencies use DAGs instead of traditional blockchain structures to record transactions. This can offer improvements in scalability and speed.

Example of a DAG​

When working in Coalesce, you'll use a DAG to build your pipeline. In the graph you have nodes and the connections between them. Each connector is one way, so the first nodes will execute, followed by the next nodes. CUSTOMER > STG_CUSTOMER > DIM_CUSTOMER.

You can change some of the node execution through Ref Functions.