---
phase: 26-pk-fk-join-resolution
plan: 01
type: execute
wave: 1
depends_on: []
files_modified:
  - src/graph.rs
  - src/lib.rs
  - src/ddl/define.rs
autonomous: true
requirements:
  - EXP-06
  - EXP-03

must_haves:
  truths:
    - "A semantic view with a cyclic relationship graph is rejected at CREATE time with a path-naming error"
    - "A semantic view with a diamond relationship graph is rejected at CREATE time with a path-naming error"
    - "A self-referencing relationship (from_alias == to_alias) is rejected with a specific self-reference error"
    - "Orphan tables (declared but not connected by any relationship) are rejected at CREATE time"
    - "Dim/metric source_table aliases unreachable from the base table are rejected at CREATE time"
    - "FK column count mismatching PK column count on the referenced table is rejected at CREATE time"
    - "Topological sort produces deterministic join ordering regardless of declaration order"
    - "Legacy definitions (empty fk_columns) skip graph validation entirely"
  artifacts:
    - path: "src/graph.rs"
      provides: "RelationshipGraph struct, validate_graph(), toposort(), all validation functions"
      exports: ["RelationshipGraph", "validate_graph"]
    - path: "src/lib.rs"
      provides: "pub mod graph declaration"
      contains: "pub mod graph"
    - path: "src/ddl/define.rs"
      provides: "validate_graph() call before persisting in both DefineSemanticViewVTab and DefineFromJsonVTab"
      contains: "validate_graph"
  key_links:
    - from: "src/ddl/define.rs"
      to: "src/graph.rs"
      via: "validate_graph() call in both bind() functions"
      pattern: "graph::validate_graph"
    - from: "src/graph.rs"
      to: "src/model.rs"
      via: "reads SemanticViewDefinition.tables, .joins, .dimensions, .metrics"
      pattern: "SemanticViewDefinition"
---

<objective>
Create the relationship graph module and wire define-time validation into both DDL paths.

Purpose: EXP-06 requires that invalid relationship graphs (cycles, diamonds, self-references, orphans, unreachable tables) are caught at CREATE time with descriptive errors. EXP-03 requires topological sort for deterministic join ordering. This plan builds the graph infrastructure that Plan 02 will use for query expansion.

Output: `src/graph.rs` module with `RelationshipGraph`, all validation functions, topological sort via Kahn's algorithm, and integration into `define.rs`.
</objective>

<execution_context>
@/Users/paul/.claude/get-shit-done/workflows/execute-plan.md
@/Users/paul/.claude/get-shit-done/templates/summary.md
</execution_context>

<context>
@.planning/PROJECT.md
@.planning/ROADMAP.md
@.planning/STATE.md
@.planning/phases/26-pk-fk-join-resolution/26-CONTEXT.md
@.planning/phases/26-pk-fk-join-resolution/26-RESEARCH.md

<interfaces>
<!-- Key types and contracts the executor needs. Extracted from codebase. -->

From src/model.rs:
```rust
pub struct TableRef {
    pub alias: String,
    pub table: String,
    pub pk_columns: Vec<String>,  // Phase 24 field
}

pub struct Join {
    pub table: String,
    pub on: String,                // Legacy Phase 10
    pub from_cols: Vec<String>,    // Phase 11
    pub join_columns: Vec<JoinColumn>, // Phase 11.1
    pub from_alias: String,        // Phase 24
    pub fk_columns: Vec<String>,   // Phase 24
    pub name: Option<String>,      // Phase 24
}

pub struct Dimension {
    pub name: String,
    pub expr: String,
    pub source_table: Option<String>,
    pub output_type: Option<String>,
}

pub struct Metric {
    pub name: String,
    pub expr: String,
    pub source_table: Option<String>,
    pub output_type: Option<String>,
}

pub struct SemanticViewDefinition {
    pub base_table: String,
    pub tables: Vec<TableRef>,
    pub dimensions: Vec<Dimension>,
    pub metrics: Vec<Metric>,
    pub filters: Vec<String>,
    pub joins: Vec<Join>,
    pub facts: Vec<Fact>,
    pub column_type_names: Vec<String>,
    pub column_types_inferred: Vec<u32>,
}
```

From src/expand.rs:
```rust
pub fn suggest_closest(name: &str, available: &[String]) -> Option<String>;
pub fn quote_ident(ident: &str) -> String;
pub fn quote_table_ref(table: &str) -> String;
```

From src/ddl/define.rs — both bind() functions follow the same pattern:
```rust
// DefineSemanticViewVTab::bind() — parse args, infer types, persist, catalog_insert
// DefineFromJsonVTab::bind() — deserialize JSON, infer types, persist, catalog_insert
// Both need graph validation AFTER parsing/deserializing but BEFORE persisting.
```
</interfaces>
</context>

<tasks>

<task type="auto" tdd="true">
  <name>Task 1: Create src/graph.rs with RelationshipGraph, validation, and topological sort</name>
  <files>src/graph.rs, src/lib.rs</files>
  <behavior>
    - Self-reference: `from_alias == to_alias` returns Err containing "cannot reference itself"
    - Cycle detection: A->B->C->A returns Err containing "cycle detected in relationships" with path
    - Diamond detection: A->B, A->C, B->D, C->D returns Err containing "diamond" and "two paths to"
    - Orphan table: declared in tables but not in any relationship and not base table returns Err containing "orphan"
    - FK/PK count mismatch: join with 2 fk_columns referencing table with 1 pk_column returns Err with count mismatch
    - Unreachable source_table: dim with source_table="x" where "x" is not reachable from root returns Err
    - Toposort of valid tree A->B->C returns [A, B, C] (root first)
    - Toposort deterministic: same graph with different declaration order produces same output
    - Legacy defs (all joins have empty fk_columns): validate_graph returns Ok and skips validation
    - Single-table defs (no joins at all): validate_graph returns Ok
    - Error messages include fuzzy "did you mean?" suggestions using suggest_closest from expand.rs
  </behavior>
  <action>
Create `src/graph.rs` with:

1. `RelationshipGraph` struct with:
   - `edges: HashMap<String, Vec<String>>` — adjacency list (from_alias -> to_alias)
   - `reverse: HashMap<String, Vec<String>>` — reverse adjacency (to_alias -> from_aliases)
   - `all_nodes: HashSet<String>` — all declared table aliases (lowercased)
   - `root: String` — base table alias (first table in TABLES clause, lowercased)

2. `RelationshipGraph::from_definition(def: &SemanticViewDefinition) -> Result<Self, String>`:
   - Extract root from `def.tables.first()` (lowercased)
   - Build all_nodes from `def.tables` aliases (lowercased)
   - Iterate `def.joins` where `!join.fk_columns.is_empty()`:
     - Self-reference check: `from_alias == to_alias` (case-insensitive) -> immediate Err
     - Add edge from_alias -> to_alias (both lowercased)
     - Add reverse edge to_alias -> from_alias

3. `toposort(&self) -> Result<Vec<String>, String>` — Kahn's algorithm:
   - Compute in-degree for each node
   - Seed queue with root first (in-degree 0), then other zero-in-degree nodes in sorted order for determinism
   - BFS: pop node, decrement in-degree of neighbors, enqueue when in-degree reaches 0
   - If order.len() != all_nodes.len(), remaining nodes form a cycle -> format error with path naming: "cycle detected in relationships: X -> Y -> Z -> X"
   - To find cycle path: from any unvisited node, follow edges until revisiting a node

4. `check_no_diamonds(&self) -> Result<(), String>`:
   - For each node in `reverse`, if node != root and parents.len() > 1 -> Err with "diamond: two paths to 'X' via 'Y' and 'Z'"

5. `check_no_orphans(&self) -> Result<(), String>`:
   - An orphan is a non-root node with in-degree 0 AND out-degree 0 (not in edges keys, not in reverse keys)
   - Err with "orphan table 'X' is not connected by any relationship" plus fuzzy suggestion

6. `check_fk_pk_counts(def: &SemanticViewDefinition) -> Result<(), String>`:
   - For each join with non-empty fk_columns, find referenced table (join.table) in def.tables
   - If referenced table has non-empty pk_columns and fk_columns.len() != pk_columns.len() -> Err

7. `check_source_tables_reachable(def: &SemanticViewDefinition, graph: &RelationshipGraph) -> Result<(), String>`:
   - Collect all source_table aliases from dims and metrics
   - For each, verify it's in graph.all_nodes
   - If not found, error with "unknown source table 'X'" plus fuzzy suggestion against all_nodes

8. `pub fn validate_graph(def: &SemanticViewDefinition) -> Result<RelationshipGraph, String>`:
   - If no joins have non-empty fk_columns -> return Ok with empty/default graph (legacy skip)
   - If def.tables.is_empty() -> return Ok (legacy path, no tables declared)
   - Build graph via from_definition
   - Run: toposort(), check_no_diamonds(), check_no_orphans(), check_fk_pk_counts(), check_source_tables_reachable()
   - Return Ok(graph) if all pass

Add `pub mod graph;` to `src/lib.rs` (after `pub mod expand;`).

Use `crate::expand::suggest_closest` for fuzzy suggestions in error messages. Normalize all alias comparisons to lowercase using `to_ascii_lowercase()`.

All unit tests go in `#[cfg(test)] mod tests` inside graph.rs.
  </action>
  <verify>
    <automated>cd /Users/paul/Documents/Dev/Personal/duckdb-semantic-views && cargo test --lib graph</automated>
  </verify>
  <done>
    - src/graph.rs exists with RelationshipGraph, validate_graph(), toposort()
    - All validation functions implemented: self-ref, cycles, diamonds, orphans, FK/PK count, unreachable source_table
    - Unit tests cover all error cases and happy paths
    - Legacy definitions (empty fk_columns) gracefully skip validation
    - cargo test passes
  </done>
</task>

<task type="auto">
  <name>Task 2: Wire validate_graph into define.rs for both DDL paths</name>
  <files>src/ddl/define.rs</files>
  <action>
Wire `crate::graph::validate_graph` into both `DefineSemanticViewVTab::bind()` and `DefineFromJsonVTab::bind()`.

In `DefineSemanticViewVTab::bind()` (line ~114):
- After `parse_define_args_from_bind(bind)` succeeds (which produces `parsed.def`)
- BEFORE the DDL-time type inference block
- Add: `crate::graph::validate_graph(&parsed.def).map_err(|e| Box::<dyn std::error::Error>::from(e))?;`

In `DefineFromJsonVTab::bind()` (line ~264):
- After `SemanticViewDefinition::from_json(&name, &json)` succeeds (which produces `def`)
- BEFORE the DDL-time type inference block
- Add: `crate::graph::validate_graph(&def).map_err(|e| Box::<dyn std::error::Error>::from(e))?;`

This ensures:
- Graph validation runs BEFORE type inference (no point inferring types for invalid graphs)
- Graph validation runs BEFORE persisting (invalid definitions never reach the catalog)
- Both the function-based DDL path and the AS-body JSON-bridge DDL path validate identically
- Legacy definitions (no fk_columns) skip validation automatically (handled inside validate_graph)

No changes to existing tests needed -- legacy definitions have empty fk_columns and skip validation.
  </action>
  <verify>
    <automated>cd /Users/paul/Documents/Dev/Personal/duckdb-semantic-views && cargo test</automated>
  </verify>
  <done>
    - validate_graph() called in both DefineSemanticViewVTab::bind() and DefineFromJsonVTab::bind()
    - Validation runs before type inference and before persisting
    - All existing tests pass unchanged (legacy defs skip validation)
    - cargo test green
  </done>
</task>

</tasks>

<verification>
- `cargo test --lib graph` runs all graph module unit tests
- `cargo test` passes (all existing tests unaffected by graph validation wiring)
- `just test-all` passes (sqllogictest + DuckLake CI unaffected)
</verification>

<success_criteria>
- src/graph.rs exists with RelationshipGraph, validate_graph(), toposort(), and all validation functions
- Graph validation is wired into both DDL bind paths (define.rs)
- All 6 validation cases produce descriptive errors with path naming and fuzzy suggestions
- Topological sort is deterministic (sorted queue seed)
- Legacy definitions (empty fk_columns or empty tables) skip validation gracefully
- All existing tests pass unchanged
</success_criteria>

<output>
After completion, create `.planning/phases/26-pk-fk-join-resolution/26-01-SUMMARY.md`
</output>
