# Technical Specification: ZPARQL Indexed Secondary Query Planner & Traversal Contract

**Document ID:** `SPEC-ZPARQL-INDEXED-QUERY-PLANNER`  
**Status:** Approved Architectural Specification  

---

## 1. Executive Summary & Vision

As the ZQK Knowledge Kernel scales to tens of thousands of objects (requirements, backlog items, test cases, criteria, telemetry runs), unindexed graph traversals and naive Breadth-First / Depth-First Searches incur $O(N)$ execution cost across the entire graph space $N$.

The **ZPARQL Query Planner and Traversal Engine** provides:
1. **Logical to Physical Plan Optimization**: Translates declarative pattern queries into optimized physical execution plans incorporating predicate pushdown and index seeks.
2. **$O(K)$ Subgraph Traversal Complexity**: Bounded complexity proportional to matched subgraph cardinality $K$ rather than total graph space $N$ via inverted edge indexes and kind indexes.
3. **Cycle-Safe and Depth-Bounded Traversal**: Strict cycle detection using visited-node bitsets and configurable maximum recursion depth limits ($D_{\max}$) to prevent infinite loops and stack exhaustion in cyclic graph topologies.

---

## 2. Query Planner Execution Contract (`CRIT-ZPARQL-PLANNER-CONTRACT-SPEC`)

### 2.1 Logical & Physical Plan Representation
The planner translates high-level ZPARQL AST queries into a directed pipeline of physical operators:
- **IndexSeek**: Resolves seed nodes in $O(1)$ time via unique identifier or indexed property.
- **KindScan**: Scans only entities of the target kind via the inverted kind index.
- **EdgeExpand**: Navigates forward or backward relationships using adjacency indexes without scanning non-adjacent nodes.
- **Filter**: Evaluates predicate expressions pushed down as close as possible to the scan/expand operators.
- **Project**: Extracts and transforms returned properties.

### 2.2 Predicate Pushdown & Index Selection Contract
1. If a node pattern specifies a concrete `id` (`(n {id: "..."})`), the planner selects an `IndexSeek` operation with cost 1.
2. If a node pattern specifies a `kind` and property filters, property predicates are pushed down into the initial scan operator rather than evaluated post-join.
3. Edge traversals leverage directed index structures (`SourceID -> Relation -> TargetIDs`), avoiding graph-wide edge table scans.

---

## 3. $O(K)$ Complexity Bound via Secondary Indexes (`CRIT-ZPARQL-INDEX-SCAN-COMPLEXITY-PROOF`)

In a graph $G = (V, E)$ with $|V| = N$ nodes and $|E| = M$ edges:
- **Naive Traversal**: Traverses all $N$ nodes and inspects all edges, yielding $O(N + M)$ complexity.
- **Indexed Traversal**: Given starting node $s$ and a traversal depth $d$ matching $K$ connected entities:
  $$\text{Complexity} = O(K) \quad \text{where } K \ll N$$
- The traversal engine tracks inspection operations. In an indexed lookup of $K$ records within a graph of $N = 10,000$ nodes, total operations executed MUST NOT exceed $C \times K$ (where constant $C < 10$), completely decoupling latency from total graph size $N$.

---

## 4. Cycle Safety & Negative Recursion Limits (`CRIT-ZPARQL-CYCLIC-TRAVERSAL-RECURSION-NEGATIVE`)

### 4.1 Visited Set Tracking
To guarantee termination on cyclic graphs ($A \to B \to C \to A$):
1. The traversal engine maintains a `VisitedSet` tracking traversed node identifiers along each evaluation path.
2. If an edge expansion encounters an already visited node along the current branch:
   - In acyclic traversal mode: The edge is skipped without re-visiting the node.
   - In cyclic path query mode: The cycle is recorded and terminated.

### 4.2 Depth-Bounded Recursion & Fail-Closed Guard
1. **Maximum Recursion Depth ($D_{\max}$)**: Queries specify a maximum traversal hop limit (default: 16; configurable up to 64).
2. **Fail-Closed Abortion**: If a traversal branch attempts to exceed $D_{\max}$, the engine halts traversal immediately and raises `ERR_ZPARQL_CYCLIC_RECURSION_LIMIT`.
3. Stack exhaustion and infinite loops are strictly prohibited.