Directed Acyclic Graph

The Directed Acyclic Graph (DAG) module allows entities to represent a directed acyclic graph. One type is the DAG, one or more types are vertices, and directed edge types connect vertices. A vertex points to its DAG with in. An edge points to its DAG and declares its source and target vertex types.

YAML model

quent: '0.1.0'
model: query_plan

entities:
  Plan:
    dag: true
    events:
      created: {}

  Operator:
    dag: vertex
    events:
      declared:
        attributes:
          plan:
            dag: { in: Plan }

  PlanEdge:
    dag: edge
    events:
      connected:
        attributes:
          plan:
            dag: { in: Plan }
          source:
            dag: { source: Operator }
          target:
            dag: { target: Operator }

The plan, source, and target attributes are typed entity references. Each vertex and edge must point to its DAG exactly once, using one membership field in a once-event. An edge must declare its DAG, source, and target in that same once-event. Its source and target types must be vertices of the same DAG type.

The rules above describe the graph’s types, not its individual instances. That instance-level work belongs to analysis, which reconstructs the event data and checks that edges belong to one DAG instance and form no cycles.

Instrumentation API

Each generated API accepts typed entity references. DAGs use the usual event methods.

use instrumentation::{Context, Noop, Operator, Plan, PlanEdge, QueryPlan};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let context = Context::<QueryPlan>::try_new(Noop)?;

    let mut plan = context.observer::<Plan>().handle();
    plan.created()?;

    let mut source = context.observer::<Operator>().handle();
    source.declared(plan.as_entity_ref())?;

    let mut target = context.observer::<Operator>().handle();
    target.declared(plan.as_entity_ref())?;

    let mut edge = context.observer::<PlanEdge>().handle();
    edge.connected(
        plan.as_entity_ref(),
        source.as_entity_ref(),
        target.as_entity_ref(),
    )?;

    Ok(())
}

#include "quent-tutorial-dag-cpp-bridge/gen/quent.hpp"

int main() {
  auto context = quent::Context::none();

  auto plan = context.plan_observer()->handle();
  plan.created();

  auto source = context.operator_observer()->handle();
  source.declared(quent::operator_::Declared{.plan = plan.id()});

  auto target = context.operator_observer()->handle();
  target.declared(quent::operator_::Declared{.plan = plan.id()});

  auto edge = context.plan_edge_observer()->handle();
  edge.connected(quent::plan_edge::Connected{
      .plan = plan.id(),
      .source = source.id(),
      .target = target.id(),
  });

  return 0;
}

import quent_tutorial_dag as quent


def main() -> None:
    with quent.Context() as context:
        plan = context.plan_observer().handle()
        plan.created()

        source = context.operator_observer().handle()
        source.declared(plan=plan)

        target = context.operator_observer().handle()
        target.declared(plan=plan)

        edge = context.plan_edge_observer().handle()
        edge.connected(plan=plan, source=source, target=target)


if __name__ == "__main__":
    main()

Full code

• Rust source
• C++ source
• Python source

Future work

The supported representation records vertices and edges as separate entities. Another possible representation is to carry the full topology in one event on the DAG entity; that representation is not currently supported by this module.