Querying Lineage Across Two Stores

Part of: Lineage Query Patterns and Graph Traversal

Many organisations end up with lineage in two places: the spatial database that holds the datasets and their extents, and a graph store that holds the derivation relationships. Neither arrangement is wrong, and the split is usually the right engineering answer, because each store indexes what the other cannot. What it costs is that every interesting question needs both, and this how-to makes that federation reliable rather than merely possible.

The rule that keeps it manageable: one store is authoritative for each fact, and the other holds a projection. A split where both stores are authoritative for overlapping facts produces disagreements nobody can adjudicate, and adjudicating them is far more expensive than avoiding them.

Prerequisites

  • A traversal store and a spatial store, per Lineage Query Patterns and Graph Traversal.
  • A shared entity identifier scheme with the same value in both.
  • An agreed authority assignment per fact class.
  • A way to detect and report drift between them.

Assign Authority Fact by Fact

Every fact class needs exactly one home, and writing the assignment down is what makes the design reviewable.

Authority assignment across two stores Extents, attributes and quality metrics are authoritative in the spatial store; derivation edges and agents in the graph store; each holds a read-only projection of the other's identifiers. FACT CLASS AUTHORITATIVE IN PROJECTED AS dataset extent, geometry spatial store nothing — do not copy quality metrics, versions spatial store nothing — fetch on demand derivation edges graph store nothing — traverse there agents, activities graph store nothing The right-hand column being empty everywhere is the goal: identifiers cross, facts do not.

The caption states the discipline that makes the whole thing work. If only identifiers cross the boundary, there is nothing to drift, and the reconciliation problem disappears rather than being managed.

The temptation to project — to copy extents into the graph so that a spatial filter can happen there, or to copy edges into the database so a join works — is strong and it is where every federated design goes wrong. Each copy becomes a second source of truth that will disagree, and the disagreement will be discovered during an incident.

Where a projection is genuinely unavoidable, mark it read-only, stamp it with the source version, and never let anything write to it directly. A projection that can be edited has stopped being a projection.

The Query Shape: Filter, Seed, Traverse, Enrich

Federated lineage questions decompose into the same four steps, and following them in order keeps both stores doing only what they are good at.

Filter in the spatial store to get a bounded set of identifiers. Seed the graph traversal with those identifiers as a parameter. Traverse in the graph store to get the reachable identifier set. Enrich by fetching the display attributes for the result back from the spatial store.

The two round trips are the cost, and they are almost always worth it. Each store answers with an index; the alternative is one store doing a scan, which is slower by more than the network hop even on small data.

Bound the intermediate sets explicitly at both hand-offs. An unbounded seed list turns the traversal into a full walk, and an unbounded traversal result turns the enrichment into a query with ten thousand identifiers in it. Cap both and report when a cap bites.

Batch the enrichment. Fetching attributes one identifier at a time is the classic mistake in this shape, and it turns a two-round-trip design into an N-round-trip one that looks fine in testing and collapses on a real result set.

Consistency Between the Stores Is Eventual

Two stores written separately are never simultaneously current, and the design has to say what that means for an answer.

The inconsistency window between two writes A dataset exists in the spatial store before its edge lands in the graph store; a query in that window sees a dataset with no ancestry. dataset written (spatial store) edge written (graph store) inconsistency window A query here returns "dataset exists, no ancestry" — indistinguishable from a real source. Fix by writing the graph edge first, so the window shows an edge to a not-yet-visible node instead.

The ordering fix in the caption is the cheap mitigation and it is worth taking. An edge referencing a node the enrichment step cannot find is obviously anomalous and can be reported as pending; a node with no edges looks exactly like a legitimate terminal source and will be believed.

Where the window must be closed rather than mitigated, use an outbox: write both facts into one store transactionally, and have a relay move one of them across. It is more machinery, and it is the only approach that gives a real guarantee without distributed transactions.

Report the freshness of each store with every federated answer. A caller who knows the graph projection is four seconds behind can interpret an odd result; one who assumes both are current will file a bug.

Detecting Drift Before It Matters

Even with identifiers-only crossing, referential drift accumulates — entities deleted in one store and still referenced in the other.

Run a periodic reconciliation in both directions: graph nodes whose identifiers do not resolve in the spatial store, and spatial datasets absent from the graph. Both are real problems and they have different causes, so count them separately.

Expect a small steady population of the second kind. A dataset created and not yet processed legitimately has no graph presence, so the reconciliation should compare against an age threshold rather than reporting every one.

Treat the first kind as an error rather than a metric. A graph node referencing a dataset that does not exist means either a deletion that skipped the graph or an identifier that was never valid, and both need fixing rather than counting.

Alert on the rate of change rather than the absolute count. A reconciliation that has shown eleven orphans for six months is describing a known backlog; one that shows four hundred today is describing something that broke last night.

Degrade Predictably When One Store Is Down

Two stores means two independent failure modes, and the useful design decision is what a federated query returns when only half of it works.

Partial answers under partial availability Each store's outage still permits a useful partial answer, provided the missing half is labelled rather than silently omitted. both up the full answer extent + ancestry no caveat needed graph store down datasets and extents still answerable "ancestry unavailable" spatial store down traversal by id still works; no extents "ids only, no names" The forbidden behaviour: returning the partial answer with no label. An empty ancestry from an outage reads exactly like a dataset with no ancestry.

The bottom row is the rule the whole section exists for. An unlabelled partial answer is worse than an error, because the caller acts on it. A dataset shown as having no upstream sources during a graph-store outage will be described as original data by whoever reads the screen.

Decide per call site whether a partial answer is acceptable at all. An interactive lineage panel is better with half an answer clearly labelled; a compliance export must fail rather than emit an incomplete record that will be filed as complete.

Set independent timeouts and surface which one fired. “The graph store did not respond in two seconds” is diagnosable; “the lineage query failed” sends someone to read logs in both systems.

Test the degraded paths deliberately. They are the paths that run during an incident, which is the worst time to discover that the label was never wired up.

Verification

Assert the four-step shape end to end against fixtures in both stores, confirming the result matches what a single-store implementation over the same data would give. Keep a small single-store reference implementation for exactly this comparison.

Assert both caps fire, at the seed hand-off and at the enrichment hand-off, and that each is reported distinguishably. A truncated result attributed to the wrong stage sends the investigation to the wrong place.

Assert enrichment batching by counting queries issued for a hundred-identifier result. It must be a small constant, not a hundred.

Assert drift detection by deleting a dataset from the spatial store without touching the graph, and confirming the reconciliation reports the orphaned node.

Gotchas & edge cases

  • Identifier formats diverge quietly. One store lower-cases, the other preserves case; one trims whitespace. The join silently returns nothing for affected rows. Normalise at the boundary and assert the normalisation.
  • Partial failure has no rollback. A federated write that succeeded in one store and failed in the other leaves inconsistency with no transaction to undo it. Make the second write idempotent and retried rather than assuming it succeeded.
  • Read replicas add a third clock. Querying a replica for enrichment while writing to the primary widens the inconsistency window unpredictably. Pin federated reads to one endpoint per request.
  • Two timeouts, two failure modes. A slow spatial filter and a slow traversal need different handling and different messages. A single generic timeout tells the operator nothing.
  • Test environments drift apart independently. A federated system needs both stores restored from the same point; restoring them from different snapshots produces test failures that look like code bugs.
  • Backups must be coordinated. Two stores backed up independently restore to two different moments, and the restored pair will disagree about edges the graph has and datasets the spatial store does not. Snapshot both together, or accept a reconciliation pass as part of every restore.
  • The network hop is not free at high query rates. A per-user lineage panel issuing two federated calls per page view is a load pattern worth measuring before it ships.