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(transparent)]
31    InvalidPostingList(#[from] GraphPostingListError),
32}
33
34pub type GraphStoreResult<T> = Result<T, GraphStoreError>;
35
36/// Storage interface for named property graphs.
37///
38/// Each store hosts zero or more named graphs that share a single
39/// vertex / edge id space (a vertex can belong to multiple graphs).
40/// Mutations are scoped to a target graph by name.
41pub trait GraphStore {
42    // --- Lifecycle ---
43
44    /// Create a new named graph. No-op if it already exists.
45    fn create_graph(&mut self, name: &str);
46
47    /// Drop a named graph and all of its membership entries. Vertex /
48    /// edge records that aren't referenced by any other graph become
49    /// unreachable and are released.
50    fn drop_graph(&mut self, name: &str);
51
52    /// Return all graph names sorted ascending.
53    fn graph_names(&self) -> Vec<String>;
54
55    fn has_graph(&self, name: &str) -> bool;
56
57    // --- Algebra ---
58
59    /// `target := g1 union g2` over vertex and edge sets.
60    fn union_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
61
62    /// `target := g1 intersect g2`.
63    fn intersect_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
64
65    /// `target := g1 \ g2`.
66    fn difference_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
67
68    fn copy_graph(&mut self, source: &str, target: &str) -> GraphStoreResult<()>;
69
70    // --- Mutations ---
71
72    fn add_vertex(&mut self, vertex: Vertex, graph: &str) -> GraphStoreResult<()>;
73
74    fn add_edge(&mut self, edge: Edge, graph: &str) -> GraphStoreResult<()>;
75
76    fn remove_vertex(&mut self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<()>;
77
78    fn remove_edge(&mut self, edge_id: EdgeId, graph: &str) -> GraphStoreResult<()>;
79
80    // --- Queries ---
81
82    /// Neighbor vertex ids reached from `vertex_id` along edges with the
83    /// given label (or any label when `label` is `None`) in the given
84    /// direction.
85    fn neighbors(
86        &self,
87        vertex_id: VertexId,
88        label: Option<&str>,
89        direction: Direction,
90        graph: &str,
91    ) -> GraphStoreResult<Vec<VertexId>>;
92
93    fn vertices_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Vertex>>;
94
95    /// Return only the vertex ids for a label. Stores with a label index should override this to avoid materializing full vertices.
96    fn vertex_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<VertexId>> {
97        Ok(self
98            .vertices_by_label(label, graph)?
99            .into_iter()
100            .map(|vertex| vertex.vertex_id)
101            .collect())
102    }
103
104    fn vertices_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Vertex>>;
105
106    fn edges_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Edge>>;
107
108    fn vertex_graphs(&self, vertex_id: VertexId) -> BTreeSet<String>;
109
110    // --- Adjacency accessors ---
111
112    fn out_edge_ids(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
113
114    fn in_edge_ids(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
115
116    fn edge_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
117
118    fn vertex_ids_in_graph(&self, graph: &str) -> GraphStoreResult<BTreeSet<VertexId>>;
119
120    /// Require an explicit query vertex to be a live member of `graph`.
121    /// Implementations may override this with a cheaper membership lookup.
122    /// Missing query input is distinct from a valid vertex with no edges and
123    /// must not be reported as an empty neighborhood/path result.
124    fn require_vertex_in_graph(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<()> {
125        if !self.vertex_ids_in_graph(graph)?.contains(&vertex_id) {
126            return Err(GraphStoreError::InvalidQuery(format!(
127                "vertex {vertex_id} is not a member of graph {graph:?}"
128            )));
129        }
130        if self.get_vertex(vertex_id).is_none() {
131            return Err(GraphStoreError::CorruptGraph(format!(
132                "graph {graph:?} references missing vertex {vertex_id}"
133            )));
134        }
135        Ok(())
136    }
137
138    // --- Statistics ---
139
140    fn degree_distribution(&self, graph: &str) -> GraphStoreResult<BTreeMap<VertexId, u64>>;
141
142    fn label_degree(&self, label: &str, graph: &str) -> GraphStoreResult<f64>;
143
144    fn vertex_label_counts(&self, graph: &str) -> GraphStoreResult<BTreeMap<String, u64>>;
145
146    // --- Global accessors ---
147
148    fn get_vertex(&self, vertex_id: VertexId) -> Option<&Vertex>;
149
150    fn get_edge(&self, edge_id: EdgeId) -> Option<&Edge>;
151
152    /// Returns and advances the next available vertex id.
153    fn next_vertex_id(&mut self) -> GraphStoreResult<VertexId>;
154
155    /// Returns and advances the next available edge id.
156    fn next_edge_id(&mut self) -> GraphStoreResult<EdgeId>;
157
158    /// Allocate a vertex id for a new entity with `label` inside
159    /// `graph`. Stores that implement the Apache AGE `graphid` scheme
160    /// override this to return `(label_id << 48) | sequence`; the
161    /// default falls back to the store-wide counter.
162    fn allocate_vertex_id(&mut self, _label: &str, _graph: &str) -> GraphStoreResult<VertexId> {
163        self.next_vertex_id()
164    }
165
166    /// Allocate an edge id for a new entity with `label` inside
167    /// `graph`. See [`GraphStore::allocate_vertex_id`].
168    fn allocate_edge_id(&mut self, _label: &str, _graph: &str) -> GraphStoreResult<EdgeId> {
169        self.next_edge_id()
170    }
171
172    fn clear(&mut self);
173
174    // --- Bulk accessors ---
175
176    /// Snapshot every vertex in the store, keyed by id. Mirrors the
177    /// `vertices` property on the current abstract `GraphStore`.
178    fn vertices(&self) -> BTreeMap<VertexId, Vertex>;
179
180    /// Snapshot every edge in the store, keyed by id. Mirrors the
181    /// `edges` property on the current abstract `GraphStore`.
182    fn edges(&self) -> BTreeMap<EdgeId, Edge>;
183}
uqa_graph/store.rs

uqa_graph/
store.rs
