Handling Time-Variant DAGs with Constraints in Postgres

Managing dynamically changing directed acyclic graphs (DAGs) with constraints in PostgreSQL enables robust tracking of relationships that evolve over time. In our company, this is vital for capturing the status of a vehicle fleet, where vehicles can attach to one another and these connections originate from multiple sources with varying authority. Below, the schema, logic, and query approaches are illustrated using real-world examples and practical procedures.

The full example code is available in our Github repository: traconiq/dags-neon.

In our fleet-management platform at Traconiq, each vehicle is a node in a graph, and every vehicle attachment—where one vehicle pulls another—is a directed edge from the pulling vehicle to the pulled vehicle. Our requirements are:

• Multiple outgoing edges per vehicle (a vehicle can pull many others at the same time).
• Only one incoming edge per vehicle per time interval (a vehicle may only be attached to one pulling vehicle at a time).
• No cycles anywhere in the graph (self-explanatory in the context of chains of attachments).
• Conflicting attachment information (manual entry vs. automated systems) must be resolved by assigning each edge a priority—the higher the value, the more authoritative the information.

To accurately represent vehicle attachment history, each edge stores not only the source and target, but also its validity interval and its priority. The table, named temporal_edges, is defined as follows:

CREATE TABLE dags.temporal_edges (
    id          serial      PRIMARY KEY,
    source      text        NOT NULL,   -- pulling vehicle id
    target      text        NOT NULL,   -- pulled vehicle id
    valid_from  timestamptz NOT NULL,   -- start of attachment
    valid_to    timestamptz,            -- end of attachment, null = ongoing
    priority    int         NOT NULL,   -- source authority for conflict resolution
    constraint vehicle2vehicle_ck
        check (source <> target),
    constraint vehicle2vehicle_valid_ck
        check ((valid_from < valid_to) OR (valid_to IS NULL))
);

This schema utilizes native Postgres temporal types and constraints, leveraging the power of SQL to structure evolving DAGs. The most basic check constraints ensure that no vehicle can attach to itself and that the validity intervals are logically consistent (i.e., valid_from is before valid_to, or valid_to is null for ongoing attachments).

For more details on general data types and constraints, see the official PostgreSQL documentation ¹.

Two strict conditions must always hold for this graph:

1. No cycles: Inserting or updating edges must never create a cycle.²
2. Single incoming edge per node: At any time, a node can have at most one incoming edge.¹

These constraints are enforced using deferred constraint triggers that run after each insert or update, but only at transaction commit (or explicit constraint check):³

-- Trigger to detect and prevent cycles in the graph
CREATE CONSTRAINT TRIGGER trigger_detect_cycle
AFTER INSERT OR UPDATE ON temporal_edges
DEFERRABLE INITIALLY DEFERRED
FOR EACH ROW
EXECUTE PROCEDURE detect_cycle();

-- Trigger to enforce the single incoming edge per node constraint
CREATE CONSTRAINT TRIGGER trigger_check_single_incoming
AFTER INSERT OR UPDATE ON temporal_edges
DEFERRABLE INITIALLY DEFERRED
FOR EACH ROW
EXECUTE PROCEDURE check_single_incoming_edge();

These triggers execute the corresponding functions (detect_cycle() and check_single_incoming_edge()), which raise exceptions if violations are detected. The deferred nature allows complex multi-step updates and batch inserts to proceed within a transaction, ensuring constraints hold before commit.³

To add new edges to the table without manually resolving conflicts, the function add_edge(source varchar, target varchar, valid_from timestamptz, valid_to timestamptz, priority integer) is provided, which takes care of adjusting the validity period of already existing edges as well as the new edge to add. Depending on the priorities, the adjustments can result in adjusting the valid_from or the valid_to column, splitting a validity interval by changing the validity interval and adding a second edge with a different interval, or completely deleting the corresponding edge(s).

The implementation of the database functions themselves are available in the example code repository.

Suppose our table contains a confirmed attachment:

Now, attempting to add:

• Conflict Window: 10:00–12:00, V002 would receive two incoming edges if both were left unchanged.
• Priority Decision: The new edge (priority 70) overrides the previous (priority 50) for the overlap.
• Result:
  • V001→V002 is truncated to end at 10:00.
  • V003→V002 is recorded as active from 10:00 to 13:00.

Updated table:

Suppose an additional record is introduced:

• Conflict Window: 11:00–13:00 overlaps with the higher-priority edge V003→V002.¹
• Resolution: The new edge is truncated so it only covers non-conflicting intervals after 13:00.

Final state:

This respects the “one incoming edge per node” rule, with higher-priority data prevailing.

Find current attachments in the fleet at a time:

SELECT source, target
FROM dags.temporal_edges
WHERE valid_from <= '2025-10-06 11:00:00+00'
  AND (valid_to IS NULL OR valid_to > '2025-10-06 11:00:00+00');

Check which vehicles a specific vehicle is pulling at a snapshot time:

SELECT target
FROM dags.temporal_edges
WHERE source = 'V004'
  AND valid_from <= '2025-10-06 11:30:00+00'
  AND (valid_to IS NULL OR valid_to > '2025-10-06 11:30:00+00');

Detect illegal multiple incoming edges (should never exist):

SELECT target, COUNT(*)
FROM dags.temporal_edges
WHERE valid_from <= '2025-10-07 12:00:00+00'
  AND (valid_to IS NULL OR valid_to > '2025-10-06 12:00:00+00')
GROUP BY target
HAVING COUNT(*) > 1;

Recursively fetch the full DAG (all vehicles attached downstream) at a given time from a pulling vehicle:⁴⁵

WITH RECURSIVE fleet_dag AS (
  -- Start with the given pulling vehicle at the reference time
  SELECT source, target
  FROM dags.temporal_edges
  WHERE source = 'V001'
    AND valid_from <= '2025-10-08 12:00:00+00'
    AND (valid_to IS NULL OR valid_to > '2025-10-08 12:00:00+00')

  UNION ALL

  -- Recursively find children attached to each target vehicle in the chain
  SELECT e.source, e.target
  FROM dags.temporal_edges e
         JOIN fleet_dag fd ON e.source = fd.target
  WHERE e.valid_from <= '2025-10-08 12:00:00+00'
    AND (e.valid_to IS NULL OR e.valid_to > '2025-10-08 12:00:00+00')
)
SELECT * FROM fleet_dag;

WITH RECURSIVE fleet_dag AS (
  -- Start with the given pulling vehicle at the reference time
  SELECT source, target
  FROM dags.temporal_edges
  WHERE source = 'V001'
    AND valid_from <= '2025-10-08 13:00:00+00'
    AND (valid_to IS NULL OR valid_to > '2025-10-08 13:00:00+00')

  UNION ALL

  -- Recursively find children attached to each target vehicle in the chain
  SELECT e.source, e.target
  FROM dags.temporal_edges e
         JOIN fleet_dag fd ON e.source = fd.target
  WHERE e.valid_from <= '2025-10-08 13:00:00+00'
    AND (e.valid_to IS NULL OR e.valid_to > '2025-10-08 13:00:00+00')
)
SELECT * FROM fleet_dag;

This recursive CTE starts from a chosen pulling vehicle (e.g., 'V001') and expands downstream, collecting every vehicle attached directly or indirectly at the specified time. It leverages the temporal validity columns to ensure edges are active at that moment, thus reconstructing the fleet’s attachment DAG slice at that point in time.

Such recursive queries showcase PostgreSQL’s power for handling graph-like temporal data in relational schemas efficiently.

• Temporal tracking enables complete historical and real-time analysis of vehicle attachment networks.
• PL/pgSQL logic driven by a function like add_edge ensures data integrity and automates priority-based conflict resolution and interval updates.
• PostgreSQL’s features (range types, recursive queries, transactionality) provide tools for managing acyclic, constrained, time-varying graphs at scale.

This design pattern supports operational requirements in the fleet, making it feasible to trace and analyze changing hierarchies, enforce physical constraints, and always reflect the most trustworthy information—regardless of data source.