When a dependency graph is incomplete, widen the test plan

A missing dependency edge makes a reduced test plan hard to trust. It also leaves a practical decision unresolved: should the team add a consumer test, run a whole domain, or expand across the system?

The stopping boundary needs evidence. A graph with an unobserved billing consumer can justify a billing-wide fallback only if possible influence is contained there. An unresolved export to analytics invalidates that boundary. A complete test run inside billing cannot answer for the omitted analytics consumer.

This article works through that choice with an executable selector over multiple plausible graphs. It quantifies the resulting test inventories and illustrative costs while keeping completeness assumptions visible. The quantities describe a synthetic planning problem, not discovery accuracy or a probability that production is safe.

A graph assembled from runtime traces records relationships observed under particular traffic, instrumentation, environments, and collection settings. That is useful positive evidence. It is not automatically a complete inventory of relationships that can matter to a release.

OpenTelemetry’s sampling documentation defines an unsampled trace or span as one that is not processed or exported. It also explains that head sampling decides without inspecting the whole trace. Those are documented collection properties. The implication for test selection is ours: a relationship absent from exported traces may still exist.

Even recording every instrumented request during an observation window does not exercise every possible behavior. A monthly invoice job may never run during the window. A tenant flag can activate a different consumer. A recovery path can read shared state only after a failure. Complete collection of exercised paths and complete inventory of possible paths are different obligations.

Declared dependencies have their own completeness problem. Bazel’s dependency documentation distinguishes actual from declared dependencies and requires declared edges to overapproximate actual edges. It also warns that redundant declarations can slow builds and enlarge binaries. That is a build-system requirement, not a guarantee about distributed services. It illustrates why an inventory must account for both missing relationships and unnecessary ones.

Before using a graph to narrow validation, identify what its edges mean. Calls, imports, data dependencies, queue subscriptions, and configuration relationships describe different kinds of influence. A call graph alone cannot justify exclusions involving an unrepresented shared database.

For one candidate revision and a declared environment scope, let G* = (V, E*) represent the true impact relationships. Orient an edge a → b to mean that a change in a can affect b. A caller-to-callee inventory must therefore be traversed in the appropriate reverse direction when looking for affected callers.

Let Go = (V, Eo) contain the observed relationships, and let C contain the changed nodes. In the simple case where observations contain only real edges, Eo ⊆ E*. Reachability is monotone:

Reach(Go, C) ⊆ Reach(G*, C)

The observed reachable set is a lower bound. It can identify consumers to include. An empty path to another consumer cannot establish that the consumer is unaffected.

Define M(v) as the existing tests mapped to node v. A basic selector returns the union of M(v) over reachable nodes, including the changed nodes themselves. Its adequacy as a selection mechanism requires several explicit assumptions:

These conditions concern selecting relevant existing tests. They do not establish that those tests have adequate assertions or cover every failure mode.

Global graph completeness is stronger than necessary. A team may justify completeness for the affected region and its outward influence paths. But a familiar service boundary is insufficient if an unknown relationship can cross it.

Where possible, represent uncertainty explicitly. One useful model is a set Ω of plausible completed graphs consistent with available evidence. Conservative selection takes the union of tests reachable across those graphs:

Sconservative = union(select(G, C) for G in Ω)

This is a definition of the obligation, not a practical discovery algorithm. Its conservatism requires the true scoped graph to be included in Ω; overlooking a possible relationship defeats that assumption. If plausible missing edges could reach any component, the union can become the full existing inventory. If evidence confines them to billing, a billing-wide fallback may suffice. An arbitrary confidence score does not establish either boundary.

The standard-library fixture supplies five nodes, five test mappings and a known edge serializer → api. Billing contains serializer, API and invoice; analytics and health are outside it. A baseline serializer returns {"amount": "10.00"}; the candidate returns {"amount": 10.0}. The API accepts a numeric conversion, but invoice requires a decimal string.

serializer ──→ api          # observed
     └───────→ invoice      # possible unobserved billing influence
                   └──→ analytics   # possible cross-domain influence
health                     # excluded only with a justified boundary

*Figure: Impact edges point from dependency to consumer. Possible edges are planning inputs; the fixture does not discover them.*

The billing scenario admits two uncertain edges: serializer → invoice and api → invoice. Each may be absent or present. The script enumerates all four combinations, selects tests in each graph, and takes their union. Every combination's affected nodes stay inside billing. The resulting fallback has three tests, including invoice, and excludes analytics and health.

The next scenario admits invoice → analytics as well, yielding eight combinations. In this installation analytics consumes the invoice amount and requires its string representation. The union now includes four tests. Billing-only execution catches the invoice failure but omits the separate analytics obligation; the expanded plan catches both. The billing assumption failed because the actual cross-domain graph was outside its allowed completions.

Finally, allow a possible serializer → health relationship. The sixteen combinations collectively reach every known node, so no test can be excluded. This is full-inventory fallback within the supplied universe. It is not a claim that arbitrary enterprise uncertainty can be reduced to four optional edges.

The implementation is small:

for every permitted completion:
    collect reachable nodes
union the mapped tests for those nodes
report reachable nodes with no test mapping separately

For fixed mappings, the union is the smallest plan containing every test selected in any allowed completion. Omitting one of those tests contradicts at least one permitted graph. This is a selection guarantee conditional on the completion set; it does not certify assertion quality. Enumerating all subsets costs exponentially many graphs. For this unconstrained edge model, traversing the union of all possible edges gives the same reachable union; mutually exclusive edges require more care because their union can invent impossible paths.

The fixture assigns invented cost weights: serializer 1, API 2, invoice 5, analytics 8 and health 1. They are planning units, not measured duration or money. Its observed two-test plan costs 3 units.

The fourth case deliberately removes invoice from the mapping that supplies the planner's inventory. Conservative selection then runs two passing tests while reporting invoice as an unmapped affected node. Even running every test in that incomplete mapped inventory yields passes and leaves invoice untested. An independently enumerated test registry could restore the missing test; expanding the same incomplete inventory cannot.

Run from this directory:

python3 fixture.py
python3 -O fixture.py

The receipt contains both commands and an environment-enabled optimization run, interpreter details, source hashes and actual output. Both baseline installations pass all five tests. Incomplete targeting passes two. Billing fallback and repaired targeting reveal the invoice failure; cross-domain fallback reveals invoice and analytics failures. Explicit test conditions and demonstration expectations remain active under optimization. Process exit zero means those expected outcomes held, including intentional failures and the mapping gap.

These are author-supplied worlds and inventories. No application source, telemetry, hosted Zof process or discovery mechanism is exercised. A real team must justify its possible-edge boundary through reviewed configuration, subscriptions, schemas, shared-state relationships and owners' inventories. The fixture computes the consequence of that boundary; it cannot establish its truth.

Broader execution has a real cost: runner capacity, queue delay, environment setup, and failure triage. Unnecessary scope can also bury a useful signal in unrelated failures. Graph quality matters because it can reduce that cost while preserving relevant tests.

In the fixture's invented weights, billing fallback adds 5 units to the observed plan. Admitting analytics doubles fallback cost from 8 to 16; including health adds one more. These exact differences expose the price of each uncertainty boundary without pretending to estimate how likely a missing edge is.

For a real economic comparison, let ΔC include added execution, queue time and investigation; let Δp be the reduction in escape probability and L its consequence. Expected cost favors broadening when Δp × L > ΔC. The graph-completion counts do not supply Δp: four completions are not four equally likely worlds. If assertions miss the affected behavior, broader execution can provide zero reduction. Severe contractual or safety constraints may rule out this optimization altogether.

Measure selection misses by periodically comparing targeted plans with broader execution on the same candidate. Investigate relevant failures found only by the broader run. Include queue time and triage cost in the comparison. Historical results can improve planning, but a new architecture or configuration invalidates old assumptions.

For the next release that uses graph-based selection, keep a short decision record alongside the test results:

Zof’s System Graph documentation assigns topology accuracy to platform teams and service owners, calls for missing components to be added, and discusses sparse metadata and incorrect edge direction. Those are documented maintenance responsibilities. This article’s fallback procedure is a vendor-neutral recommendation; it does not establish automatic hosted fallback behavior.

Two counterexamples limit the recommendation. First, a complete graph with an incomplete test mapping still omits relevant tests. Repairing edges alone cannot fix that. Second, every selected test may pass because its assertions accept the regression. Running the full inventory then produces more execution without stronger evidence about the violated requirement.

Other limits include candidate-only feature flags, incompatible environments, and nodes absent from both topology and inventory. A broader pass supports the behaviors actually asserted under the conditions actually executed. It cannot certify the unknown remainder.

Try the fixture, then review one proposed targeted plan in your own system. Write down the missing relationships you can name, the ones you cannot bound, and the broader inventory you will run. A graph earns narrower testing through supported exclusions. Until those exclusions hold, spend the extra validation effort and carry the remaining gaps into the release decision.

Download the complete Python example. Extract the archive and follow its README. The examples are synthetic demonstrations, not production benchmarks.