Skip to main content

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