Market Data Dependency Resolution
Table of Contents
Summary
A single market data
identifier rarely stands alone: a curve is typically built from other
market data (the instrument quotes used to bootstrap it, or, for a
cross-currency curve, another currency's own discount curve and an FX
spot rate), and that market data may itself depend on further data,
recursively. Dependency resolution is the process of expanding a set
of identifiers into its full transitive closure under this "depends
on" relation, so that every item genuinely needed to build every item in
the original set is accounted for before construction begins, and of
determining a valid order in which to build them. This document defines
that closure formally, and grounds it in two independently engineered
implementations — ORE's DependencyGraph and OpenGamma Strata's
MarketDataNode — that agree closely on both the underlying
graph-theoretic model and the reason it is needed.
Layperson's mental model
Building a complex software project cannot proceed in arbitrary order. A compiled program cannot be linked until every library it uses has been compiled; each of those libraries may itself depend on further libraries; and so on recursively, until every item in the chain has been accounted for. The full set of things that must be built before any given target can be built is exactly the dependency closure of that target: the smallest set containing the target itself and everything — directly or indirectly — that the target depends on. A build system such as Make or Bazel computes this closure automatically, then determines a valid order in which to build everything within it — leaves first, roots last. The two structural risks any build system must handle are a missing dependency (a library that is referenced but not available — the build fails on the item that needs it) and a cycle (library A depends on B, and B depends on A — no valid build order exists, and the system must detect this and fail cleanly rather than loop).
Market data dependency resolution is the same process applied to a different domain. A curve cannot be built until every instrument quote used to bootstrap it is available; that quote may itself be derived from further market data; and so on. The dependency closure of a set of market data identifiers is the smallest superset containing everything each identifier directly or transitively depends on — computed before any item in the set is actually built, and from which a valid construction order is then derived. Missing dependencies and cycles carry over as failure modes with the same structure, made precise by the formal definition below.
Aside: for readers who know how browsers work
A browser loading a web page illustrates the same closure structure. The
page itself is one resource: it references a stylesheet at a second
location, the stylesheet references a web font at a third, and an
<img> tag references an image at a fourth. The browser cannot correctly
render the original page having fetched only its own URL; it must
recursively discover and fetch every resource the page — and everything
the page references — depends on, before rendering can be considered
complete.
The two failure modes map directly: if the font server is down, the browser renders the page without the intended font — a partial, degraded result. A missing rate quote is harder: unlike text falling back to a default typeface, there is no safe default value for a missing rate. And if page A's stylesheet somehow referenced page A itself as a dependency, naive recursive fetching would loop forever — exactly the cycle failure mode, and exactly why real dependency-resolution systems must detect it and stop.
State of the art
ORE's DependencyGraph
ORE's own implementation, ore::data::DependencyGraph
(OREData/ored/marketdata/dependencygraph.hpp), is built directly as a
graph structure and is used, in TodaysMarket construction
(OREData/ored/marketdata/todaysmarket.cpp), exactly as this document
describes: the code comment at the point of use reads "build the
dependency graph for all configurations," and the graph is then processed
with boost::topological_sort — the standard graph algorithm for
producing a build order consistent with a dependency relation, provided
the graph is acyclic. ORE's own comment at that call site notes
explicitly that "topological_sort() might have produced partial
results, that we have to discard" when the sort fails, and treats a
failed topological sort as reportable evidence of a cyclic dependency
graph.
OpenGamma Strata's MarketDataNode
OpenGamma Strata's com.opengamma.strata.calc.marketdata.MarketDataNode
class, package-private within Strata's calculation-runner module, is
documented as "a node in a tree of dependencies of market data required
by a set of calculations… used to determine the order in which market
data is built. The leaves of the tree represent market data with no
dependencies." Strata's own worked example in that Javadoc could be
transcribed almost unchanged into this cluster's own vocabulary: "if a
function requests a curve, there will be a node below the root
representing the curve. The curve's node will have a child node
representing the curve group containing the curve… It might also have
a child node representing another curve, or possibly an FX rate" — a
direct, independent restatement of exactly the cross-currency-curve
dependency example given in this document's introduction.
Why the convergence matters
ORE models the dependency structure as a general graph processed with a standard library topological sort; Strata models it as a tree (a graph restricted so that no node has more than one parent), walked to determine build order. The difference between "general graph" and "tree" is a genuine implementation choice — not every real market data dependency structure is guaranteed to be a tree, since two different curves can share a common underlying dependency (both a USD swap curve and a USD-denominated cross-currency curve might depend on the very same USD OIS discount curve, which is a shared dependency, not a tree-structured one) — but both systems agree completely on the governing abstraction underneath: a directed "depends on" relation over market data items, expanded transitively, with build order determined by that expansion, and cycles treated as an error condition rather than silently tolerated. This is the strongest possible confirmation available from two production systems that this document's formal closure definition describes something real, not an invented abstraction.
Formal definition
Let \(\mathrm{deps}: U \to \mathcal{P}(U)\) be a function giving each member of the market data universe \(U\) the (possibly empty) set of other members of \(U\) it directly depends on. For a set \(S \subseteq U\), the dependency closure of \(S\) is the smallest superset of \(S\) that is closed under \(\mathrm{deps}\) — formally, the smallest \(\overline{S} \supseteq S\) such that
\[x \in \overline{S} \implies \mathrm{deps}(x) \subseteq \overline{S}\]
Read in words: if something is in the closure, then everything it directly depends on must also be in the closure — recursively, until nothing new is added. This is precisely the \(\mathrm{closure}(\cdot)\) step in Market Data Universe's pipeline formula, given its own full treatment here.
Discussion
Two failure modes, made precise by the closure definition
The formal definition makes both failure modes precise rather than merely descriptive:
- A missing dependency is the case where \(\mathrm{deps}(x)\), for some \(x \in \overline{S}\), contains an element that is not a member of the market data universe \(U\) at all — exactly the situation the universe document's \(\cap\, U\) step is designed to surface, rather than silently discard.
- A cycle is the case where \(\mathrm{deps}\) contains a chain \(x_1 \to x_2 \to \cdots \to x_n \to x_1\) — a case in which the "smallest closed superset" the formal definition asks for does not exist: the construction of \(\overline{S}\) by naive recursive expansion does not terminate. This is exactly why both ORE and Strata compute \(\overline{S}\) via an explicit graph algorithm with cycle detection rather than by naive unbounded recursion — a topological sort is defined if and only if the graph is acyclic, and its failure is precisely a cycle-detection mechanism, not an unrelated add-on.
See also
- Market Data Requirements and Resolution — the hub; a reading-order guide for the full cluster.
- Market Data Universe — where the closure defined here fits into the full valuation-scoped set derivation.
- Market Data Identifier — the elements the "depends on" relation is defined over.
- Market Data Configuration — the resolution step immediately preceding dependency expansion.