uqa_graph/
store.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! `GraphStore` trait — the abstract storage interface for named
8//! property graphs. Both an in-memory store and a SQLite-backed store
9//! sit behind it.
10
11use std::collections::{BTreeMap, BTreeSet};
12
13use uqa_core::{Edge, EdgeId, Vertex, VertexId};
14
15use crate::posting_list::GraphPostingListError;
16use crate::types::Direction;
17
18#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
19pub enum GraphStoreError {
20    #[error("graph {0:?} does not exist")]
21    UnknownGraph(String),
22    #[error("graph id space exhausted: {0}")]
23    IdExhausted(String),
24    #[error("invalid graph mutation: {0}")]
25    InvalidMutation(String),
26    #[error("invalid graph query: {0}")]
27    InvalidQuery(String),
28    #[error("corrupt graph state: {0}")]
29    CorruptGraph(String),
30    #[error("graph storage error: {0}")]
31    Storage(String),
32    #[error("graph serialization failure: {0}")]
33    SerializationFailure(String),
34    #[error(transparent)]
35    InvalidPostingList(#[from] GraphPostingListError),
36}
37
38pub type GraphStoreResult<T> = Result<T, GraphStoreError>;
39
40/// Storage interface for named property graphs.
41///
42/// Each store hosts zero or more named graphs that share a single
43/// vertex / edge id space (a vertex can belong to multiple graphs).
44/// Mutations are scoped to a target graph by name.
45pub trait GraphStore {
46    /// Apply a group of mutations atomically. Persistent stores use a storage
47    /// transaction or savepoint, never a cloned graph as a rollback image.
48    /// Both errors and unwinding must restore the pre-operation state.
49    fn transaction<T>(
50        &mut self,
51        operation: impl FnOnce(&mut Self) -> GraphStoreResult<T>,
52    ) -> GraphStoreResult<T>
53    where
54        Self: Sized;
55
56    // --- Lifecycle ---
57
58    /// Create a new named graph. No-op if it already exists.
59    fn create_graph(&mut self, name: &str) -> GraphStoreResult<()>;
60
61    /// Drop a named graph and all of its membership entries. Vertex /
62    /// edge records that aren't referenced by any other graph become
63    /// unreachable and are released.
64    fn drop_graph(&mut self, name: &str) -> GraphStoreResult<()>;
65
66    /// Return all graph names sorted ascending.
67    fn graph_names(&self) -> GraphStoreResult<Vec<String>>;
68
69    fn has_graph(&self, name: &str) -> GraphStoreResult<bool>;
70
71    // --- Algebra ---
72
73    /// `target := g1 union g2` over vertex and edge sets.
74    fn union_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
75
76    /// `target := g1 intersect g2`.
77    fn intersect_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
78
79    /// `target := g1 \ g2`.
80    fn difference_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
81
82    fn copy_graph(&mut self, source: &str, target: &str) -> GraphStoreResult<()>;
83
84    // --- Mutations ---
85
86    fn add_vertex(&mut self, vertex: Vertex, graph: &str) -> GraphStoreResult<()>;
87
88    fn add_edge(&mut self, edge: Edge, graph: &str) -> GraphStoreResult<()>;
89
90    fn remove_vertex(&mut self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<()>;
91
92    fn remove_edge(&mut self, edge_id: EdgeId, graph: &str) -> GraphStoreResult<()>;
93
94    // --- Queries ---
95
96    /// Neighbor vertex ids reached from `vertex_id` along edges with the
97    /// given label (or any label when `label` is `None`) in the given
98    /// direction.
99    fn neighbors(
100        &self,
101        vertex_id: VertexId,
102        label: Option<&str>,
103        direction: Direction,
104        graph: &str,
105    ) -> GraphStoreResult<Vec<VertexId>>;
106
107    fn vertices_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Vertex>>;
108
109    /// Return only the vertex ids for a label. Stores with a label index should override this to avoid materializing full vertices.
110    fn vertex_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<VertexId>> {
111        Ok(self
112            .vertices_by_label(label, graph)?
113            .into_iter()
114            .map(|vertex| vertex.vertex_id)
115            .collect())
116    }
117
118    fn vertices_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Vertex>>;
119
120    fn edges_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Edge>>;
121
122    /// Read only edges carrying a label. Durable stores push this predicate
123    /// into their physical label index before fetching any payloads.
124    fn edges_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Edge>> {
125        self.edge_ids_by_label(label, graph)?
126            .into_iter()
127            .map(|id| {
128                self.get_edge(id)?
129                    .ok_or_else(|| GraphStoreError::CorruptGraph(format!("missing edge {id}")))
130            })
131            .collect()
132    }
133
134    fn vertex_graphs(&self, vertex_id: VertexId) -> GraphStoreResult<BTreeSet<String>>;
135    fn edge_graphs(&self, edge_id: EdgeId) -> GraphStoreResult<BTreeSet<String>>;
136
137    // --- Adjacency accessors ---
138
139    fn out_edge_ids(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
140
141    fn in_edge_ids(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
142
143    fn edge_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
144
145    fn vertex_ids_in_graph(&self, graph: &str) -> GraphStoreResult<BTreeSet<VertexId>>;
146
147    /// Bounded ascending vertex identities, exclusively after the cursor.
148    /// Durable stores override this with an indexed storage cursor.
149    fn vertex_id_page(
150        &self,
151        graph: &str,
152        after: Option<u64>,
153        limit: usize,
154    ) -> GraphStoreResult<Vec<u64>> {
155        if !(1..=uqa_storage::MAX_GRAPH_ID_PAGE).contains(&limit) {
156            return Err(GraphStoreError::InvalidQuery(
157                "invalid graph page size".into(),
158            ));
159        }
160        Ok(self
161            .vertex_ids_in_graph(graph)?
162            .into_iter()
163            .filter(|id| after.is_none_or(|after| *id > after))
164            .take(limit)
165            .collect())
166    }
167
168    /// Bounded ascending edge identities without materializing edge payloads.
169    fn edge_id_page(
170        &self,
171        graph: &str,
172        after: Option<u64>,
173        limit: usize,
174    ) -> GraphStoreResult<Vec<u64>> {
175        if !(1..=uqa_storage::MAX_GRAPH_ID_PAGE).contains(&limit) {
176            return Err(GraphStoreError::InvalidQuery(
177                "invalid graph page size".into(),
178            ));
179        }
180        let mut ids = BTreeSet::new();
181        for vertex in self.vertex_ids_in_graph(graph)? {
182            ids.extend(self.out_edge_ids(vertex, graph)?);
183        }
184        Ok(ids
185            .into_iter()
186            .filter(|id| after.is_none_or(|after| *id > after))
187            .take(limit)
188            .collect())
189    }
190
191    /// Require an explicit query vertex to be a live member of `graph`.
192    /// Implementations may override this with a cheaper membership lookup.
193    /// Missing query input is distinct from a valid vertex with no edges and
194    /// must not be reported as an empty neighborhood/path result.
195    fn require_vertex_in_graph(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<()> {
196        if !self.vertex_ids_in_graph(graph)?.contains(&vertex_id) {
197            return Err(GraphStoreError::InvalidQuery(format!(
198                "vertex {vertex_id} is not a member of graph {graph:?}"
199            )));
200        }
201        if self.get_vertex(vertex_id)?.is_none() {
202            return Err(GraphStoreError::CorruptGraph(format!(
203                "graph {graph:?} references missing vertex {vertex_id}"
204            )));
205        }
206        Ok(())
207    }
208
209    // --- Statistics ---
210
211    fn degree_distribution(&self, graph: &str) -> GraphStoreResult<BTreeMap<VertexId, u64>>;
212
213    fn label_degree(&self, label: &str, graph: &str) -> GraphStoreResult<f64>;
214
215    fn vertex_label_counts(&self, graph: &str) -> GraphStoreResult<BTreeMap<String, u64>>;
216
217    // --- Global accessors ---
218
219    /// Fetch one owned record. A storage implementation must not retain all
220    /// entities merely to return a borrow, and I/O failures are not absence.
221    fn get_vertex(&self, vertex_id: VertexId) -> GraphStoreResult<Option<Vertex>>;
222
223    fn get_edge(&self, edge_id: EdgeId) -> GraphStoreResult<Option<Edge>>;
224
225    /// Returns and advances the next available vertex id.
226    fn next_vertex_id(&mut self) -> GraphStoreResult<VertexId>;
227
228    /// Returns and advances the next available edge id.
229    fn next_edge_id(&mut self) -> GraphStoreResult<EdgeId>;
230
231    /// Allocate a vertex id for a new entity with `label` inside
232    /// `graph`. Stores that implement the Apache AGE `graphid` scheme
233    /// override this to return `(label_id << 48) | sequence`; the
234    /// default falls back to the store-wide counter.
235    fn allocate_vertex_id(&mut self, _label: &str, _graph: &str) -> GraphStoreResult<VertexId> {
236        self.next_vertex_id()
237    }
238
239    /// Allocate an edge id for a new entity with `label` inside
240    /// `graph`. See [`GraphStore::allocate_vertex_id`].
241    fn allocate_edge_id(&mut self, _label: &str, _graph: &str) -> GraphStoreResult<EdgeId> {
242        self.next_edge_id()
243    }
244
245    fn clear(&mut self) -> GraphStoreResult<()>;
246
247    // --- Bulk accessors ---
248
249    /// Snapshot every vertex in the store, keyed by id. Mirrors the
250    /// `vertices` property on the current abstract `GraphStore`.
251    fn vertices(&self) -> GraphStoreResult<BTreeMap<VertexId, Vertex>>;
252
253    /// Snapshot every edge in the store, keyed by id. Mirrors the
254    /// `edges` property on the current abstract `GraphStore`.
255    fn edges(&self) -> GraphStoreResult<BTreeMap<EdgeId, Edge>>;
256}
257
258impl From<uqa_storage::StorageBackendError> for GraphStoreError {
259    fn from(error: uqa_storage::StorageBackendError) -> Self {
260        Self::Storage(error.to_string())
261    }
262}
uqa_graph/store.rs

uqa_graph/
store.rs
