by query shape · graph

Graph traversal on OriginChain.

OriginChain runs a managed graph database on the same hash-keyed substrate that powers SQL, vector, and full-text. A graph is a pair of relation keys written atomically when you put a row. Forward and reverse edges live under direction-tagged shapes — self-relations (a "follows" edge from users back to users) don't collide. Traversal is a set of helpers on top: one-hop, BFS, reachability, weighted shortest path.

# forward edge (the one written when you put a row with declared relations)
h(tenant · "rel" · from_table · rel_name · "→" · from_pk) ‖ to_pk

# reverse edge (written atomically alongside if bidirectional = true)
h(tenant · "rel" · target_table · rel_name · "←" · to_pk) ‖ from_pk

Declare the relation.

A row write that includes a declared relation atomically writes the forward and (if bidirectional = true) reverse edge in the same WAL frame. Overwriting a relation retires the stale edges in the same batch — no orphans.

# manifest.toml — declare a relation
[[relations]]
name          = "follows"
from_table    = "users"
to_table      = "users"           # self-relation; direction tags resolve the collision
bidirectional = true              # default; both keys written atomically

[[relations]]
name          = "placed_by"
from_table    = "orders"
to_table      = "clients"
bidirectional = true

Five operations.

opendpointnote

neighbors GET /graph/:t/:rel/neighbors?from=PK One-hop forward. Lexicographic order. O(degree).

reverse_neighbors GET /graph/:t/:rel/reverse?to=PK One-hop inbound. Works on self-relations now (direction tags).

bfs GET /graph/:t/:rel/bfs?from=PK&max_depth=N Breadth-first frontier up to depth N. Returns (dst, depth)[].

path_exists GET /graph/:t/:rel/path?from=PK&to=PK&max_depth=N Reachability. Short-circuits on first match.

dijkstra POST /graph/:t/:rel/dijkstra { weights_json } Weighted shortest path. Caller-supplied weight map.

One-hop forward & reverse.

neighbors — who does u_42 follow?

curl "https://acme.ap-south-1.db.originchain.ai/v1/tenants/$T/graph/users/follows/neighbors?from=u_42" \
  -H "Authorization: Bearer $OC_TOKEN"

following = oc.graph("users", "follows").neighbors(src="u_42")

reverse_neighbors — who follows u_42?

curl "https://acme.ap-south-1.db.originchain.ai/v1/tenants/$T/graph/users/follows/reverse?to=u_42" \
  -H "Authorization: Bearer $OC_TOKEN"

followers = oc.graph("users", "follows").reverse_neighbors(dst="u_42")

Reverse traversal works on self-relations — the direction tag in the key resolves the forward/reverse collision.

BFS & reachability.

bfs — frontier up to depth 3

curl "https://acme.ap-south-1.db.originchain.ai/v1/tenants/$T/graph/users/follows/bfs?from=u_42&max_depth=3" \
  -H "Authorization: Bearer $OC_TOKEN"

frontier = oc.graph("users", "follows").bfs(
    src="u_42",
    max_depth=3,
)
for hop in frontier:
    print(hop.dst, hop.depth)

path_exists — short-circuits on first match

curl "https://acme.ap-south-1.db.originchain.ai/v1/tenants/$T/graph/users/follows/path?from=u_42&to=u_99&max_depth=4" \
  -H "Authorization: Bearer $OC_TOKEN"

reachable = oc.graph("users", "follows").path_exists(
    src="u_42", dst="u_99", max_depth=4,
)

Weighted shortest path (Dijkstra).

The walker takes a caller-supplied weights_json map keyed by "from→to" (literal arrow, U+2192). Edges absent from the map are pruned. Negative weights are rejected.

POST /graph/:t/:rel/dijkstra

# weights_json maps "from→to" → numeric cost. Edges absent from the
# map are ignored by the walker (effectively pruned).
curl -X POST "https://acme.ap-south-1.db.originchain.ai/v1/tenants/$T/graph/cities/connects/dijkstra" \
  -H "Authorization: Bearer $OC_TOKEN" \
  -H "Content-Type: application/json" \
  -d '{
    "from":          "BLR",
    "to":            "FRA",
    "weights_json":  {
      "BLR→DEL": 2.5,
      "DEL→FRA": 7.4,
      "BLR→DXB": 4.1,
      "DXB→FRA": 6.0
    }
  }'

import urllib.request, json, os

req = urllib.request.Request(
    f"{os.environ['OC_ENDPOINT']}/v1/tenants/{os.environ['T']}/graph/cities/connects/dijkstra",
    method="POST",
    headers={
        "Authorization": f"Bearer {os.environ['OC_TOKEN']}",
        "Content-Type":  "application/json",
    },
    data=json.dumps({
        "from": "BLR",
        "to":   "FRA",
        "weights_json": {
            "BLR\u2192DEL": 2.5,    # → as the literal arrow
            "DEL\u2192FRA": 7.4,
            "BLR\u2192DXB": 4.1,
            "DXB\u2192FRA": 6.0,
        },
    }).encode(),
)
with urllib.request.urlopen(req) as r:
    print(json.loads(r.read()))

{
  "src":   "BLR",
  "dst":   "FRA",
  "cost":  9.9,
  "path":  ["BLR", "DEL", "FRA"],
  "hops":  2
}

Composition with SQL and vector.

Edges are visible to SQL JOINs the moment the WAL fsyncs — declare the relation in the manifest and JOIN on the column. Combine vector topk with a graph hop in two calls (topk on embeddings, then neighbors against the resulting ids) for retrieval-augmented walks across documents and entities.