uqa_graph/persistent_store/
trait_impl.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Graph operations over indexed durable records and storage checkpoints.
8
9use super::{
10    BTreeMap, BTreeSet, Direction, Edge, GraphEntityFilter, GraphEntityKind, GraphLabelRegistry,
11    GraphStore, GraphStoreError, GraphStoreResult, LabelKind, PersistentGraphStore, Vertex,
12};
13
14impl GraphStore for PersistentGraphStore {
15    fn vertex_id_page(
16        &self,
17        graph: &str,
18        after: Option<u64>,
19        limit: usize,
20    ) -> GraphStoreResult<Vec<u64>> {
21        self.require_graph(graph)?;
22        self.storage.ids(
23            GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
24            after,
25            limit,
26        )
27    }
28    fn edge_id_page(
29        &self,
30        graph: &str,
31        after: Option<u64>,
32        limit: usize,
33    ) -> GraphStoreResult<Vec<u64>> {
34        self.require_graph(graph)?;
35        self.storage.ids(
36            GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph)),
37            after,
38            limit,
39        )
40    }
41    fn transaction<T>(
42        &mut self,
43        operation: impl FnOnce(&mut Self) -> GraphStoreResult<T>,
44    ) -> GraphStoreResult<T> {
45        self.transaction_mapped(operation, std::convert::identity)
46    }
47
48    fn create_graph(&mut self, name: &str) -> GraphStoreResult<()> {
49        self.transaction(|store| {
50            if !store.storage.has_graph(name)? {
51                store.storage.create_graph(name)?;
52                store
53                    .storage
54                    .save_registry(name, &GraphLabelRegistry::default())?;
55            }
56            Ok(())
57        })
58    }
59    fn drop_graph(&mut self, name: &str) -> GraphStoreResult<()> {
60        self.transaction(|store| {
61            if !store.storage.has_graph(name)? {
62                return Ok(());
63            }
64            for kind in [GraphEntityKind::Edge, GraphEntityKind::Vertex] {
65                store.for_each_id(GraphEntityFilter::new(kind, Some(name)), |id| {
66                    store.detach_entity(kind, id, name)
67                })?;
68            }
69            store.storage.delete_graph(name)
70        })
71    }
72    fn graph_names(&self) -> GraphStoreResult<Vec<String>> {
73        self.storage.graph_names()
74    }
75    fn has_graph(&self, name: &str) -> GraphStoreResult<bool> {
76        self.storage.has_graph(name)
77    }
78    fn union_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
79        self.algebra(g1, Some(g2), target, |_| true, true)
80    }
81    fn intersect_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
82        self.algebra(g1, Some(g2), target, |common| common, false)
83    }
84    fn difference_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
85        self.algebra(g1, Some(g2), target, |common| !common, false)
86    }
87    fn copy_graph(&mut self, source: &str, target: &str) -> GraphStoreResult<()> {
88        self.algebra(source, None, target, |_| true, false)
89    }
90
91    fn add_vertex(&mut self, vertex: Vertex, graph: &str) -> GraphStoreResult<()> {
92        self.transaction(|store| {
93            store.require_graph(graph)?;
94            store.reserve_id(GraphEntityKind::Vertex, vertex.vertex_id)?;
95            store.storage.save_vertex(&vertex)?;
96            store
97                .storage
98                .attach(GraphEntityKind::Vertex, vertex.vertex_id, graph)?;
99            for owner in store
100                .storage
101                .memberships(GraphEntityKind::Vertex, vertex.vertex_id)?
102            {
103                let mut registry = store.label_registry(&owner)?;
104                registry.observe(&vertex.label, vertex.vertex_id, LabelKind::Vertex);
105                store.storage.save_registry(&owner, &registry)?;
106            }
107            Ok(())
108        })
109    }
110    fn add_edge(&mut self, edge: Edge, graph: &str) -> GraphStoreResult<()> {
111        self.transaction(|store| {
112            store.require_graph(graph)?;
113            let mut owners = store
114                .storage
115                .memberships(GraphEntityKind::Edge, edge.edge_id)?;
116            if !owners.iter().any(|owner| owner == graph) {
117                owners.push(graph.to_owned());
118            }
119            for owner in &owners {
120                for id in [edge.source_id, edge.target_id] {
121                    if !store
122                        .storage
123                        .has_membership(GraphEntityKind::Vertex, id, owner)?
124                    {
125                        return Err(GraphStoreError::InvalidMutation(format!(
126                            "edge {} references endpoint outside graph {owner:?}: {} -> {}",
127                            edge.edge_id, edge.source_id, edge.target_id
128                        )));
129                    }
130                    store.require_vertex(id)?;
131                }
132            }
133            store.reserve_id(GraphEntityKind::Edge, edge.edge_id)?;
134            store.storage.save_edge(&edge)?;
135            store
136                .storage
137                .attach(GraphEntityKind::Edge, edge.edge_id, graph)?;
138            for owner in owners {
139                let mut registry = store.label_registry(&owner)?;
140                registry.observe(&edge.label, edge.edge_id, LabelKind::Edge);
141                store.storage.save_registry(&owner, &registry)?;
142            }
143            Ok(())
144        })
145    }
146    fn remove_vertex(&mut self, vertex_id: u64, graph: &str) -> GraphStoreResult<()> {
147        self.transaction(|store| {
148            store.require_graph(graph)?;
149            if !store
150                .storage
151                .has_membership(GraphEntityKind::Vertex, vertex_id, graph)?
152            {
153                return Ok(());
154            }
155            for outgoing in [true, false] {
156                let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
157                if outgoing {
158                    filter.source = Some(vertex_id);
159                } else {
160                    filter.target = Some(vertex_id);
161                }
162                store.for_each_id(filter, |id| {
163                    store.detach_entity(GraphEntityKind::Edge, id, graph)
164                })?;
165            }
166            store.detach_entity(GraphEntityKind::Vertex, vertex_id, graph)
167        })
168    }
169    fn remove_edge(&mut self, edge_id: u64, graph: &str) -> GraphStoreResult<()> {
170        self.transaction(|store| {
171            store.require_graph(graph)?;
172            store.detach_entity(GraphEntityKind::Edge, edge_id, graph)
173        })
174    }
175
176    fn neighbors(
177        &self,
178        vertex_id: u64,
179        label: Option<&str>,
180        direction: Direction,
181        graph: &str,
182    ) -> GraphStoreResult<Vec<u64>> {
183        self.require_vertex_in_graph(vertex_id, graph)?;
184        let mut neighbors = Vec::new();
185        for outgoing in [true, false] {
186            if (outgoing && direction == Direction::In)
187                || (!outgoing && direction == Direction::Out)
188            {
189                continue;
190            }
191            let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
192            filter.label = label;
193            if outgoing {
194                filter.source = Some(vertex_id);
195            } else {
196                filter.target = Some(vertex_id);
197            }
198            self.for_each_id(filter, |id| {
199                let edge = self.require_edge(id, graph)?;
200                neighbors.push(if outgoing {
201                    edge.target_id
202                } else {
203                    edge.source_id
204                });
205                Ok(())
206            })?;
207        }
208        if direction == Direction::Both {
209            neighbors.sort_unstable();
210            neighbors.dedup();
211        }
212        Ok(neighbors)
213    }
214    fn vertices_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Vertex>> {
215        self.require_graph(graph)?;
216        let mut filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
217        filter.label = Some(label);
218        let mut result = Vec::new();
219        self.for_each_id(filter, |id| {
220            result.push(self.require_vertex(id)?);
221            Ok(())
222        })?;
223        Ok(result)
224    }
225    fn vertex_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<u64>> {
226        self.require_graph(graph)?;
227        let mut filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
228        filter.label = Some(label);
229        Ok(self.collect_ids(filter)?.into_iter().collect())
230    }
231    fn vertices_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Vertex>> {
232        self.require_graph(graph)?;
233        let mut result = Vec::new();
234        self.for_each_id(
235            GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
236            |id| {
237                result.push(self.require_vertex(id)?);
238                Ok(())
239            },
240        )?;
241        Ok(result)
242    }
243    fn edges_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Edge>> {
244        self.require_graph(graph)?;
245        let mut result = Vec::new();
246        self.for_each_id(
247            GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph)),
248            |id| {
249                result.push(self.require_edge(id, graph)?);
250                Ok(())
251            },
252        )?;
253        Ok(result)
254    }
255    fn vertex_graphs(&self, id: u64) -> GraphStoreResult<BTreeSet<String>> {
256        Ok(self
257            .storage
258            .memberships(GraphEntityKind::Vertex, id)?
259            .into_iter()
260            .collect())
261    }
262    fn edges_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Edge>> {
263        self.require_graph(graph)?;
264        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
265        filter.label = Some(label);
266        let mut edges = Vec::new();
267        self.for_each_id(filter, |id| {
268            edges.push(self.require_edge(id, graph)?);
269            Ok(())
270        })?;
271        Ok(edges)
272    }
273
274    fn edge_graphs(&self, id: u64) -> GraphStoreResult<BTreeSet<String>> {
275        Ok(self
276            .storage
277            .memberships(GraphEntityKind::Edge, id)?
278            .into_iter()
279            .collect())
280    }
281    fn out_edge_ids(&self, id: u64, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
282        self.require_vertex_in_graph(id, graph)?;
283        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
284        filter.source = Some(id);
285        let ids = self.collect_ids(filter)?;
286        for id in &ids {
287            self.require_edge(*id, graph)?;
288        }
289        Ok(ids)
290    }
291    fn in_edge_ids(&self, id: u64, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
292        self.require_vertex_in_graph(id, graph)?;
293        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
294        filter.target = Some(id);
295        let ids = self.collect_ids(filter)?;
296        for id in &ids {
297            self.require_edge(*id, graph)?;
298        }
299        Ok(ids)
300    }
301    fn edge_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
302        self.require_graph(graph)?;
303        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
304        filter.label = Some(label);
305        let ids = self.collect_ids(filter)?;
306        for id in &ids {
307            self.require_edge(*id, graph)?;
308        }
309        Ok(ids)
310    }
311    fn vertex_ids_in_graph(&self, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
312        self.require_graph(graph)?;
313        self.collect_ids(GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)))
314    }
315    fn require_vertex_in_graph(&self, id: u64, graph: &str) -> GraphStoreResult<()> {
316        self.require_graph(graph)?;
317        if !self
318            .storage
319            .has_membership(GraphEntityKind::Vertex, id, graph)?
320        {
321            return Err(GraphStoreError::InvalidQuery(format!(
322                "vertex {id} is not a member of graph {graph:?}"
323            )));
324        }
325        self.require_vertex(id)?;
326        Ok(())
327    }
328
329    fn degree_distribution(&self, graph: &str) -> GraphStoreResult<BTreeMap<u64, u64>> {
330        self.require_graph(graph)?;
331        let mut result = BTreeMap::new();
332        self.for_each_id(
333            GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
334            |id| {
335                let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
336                filter.source = Some(id);
337                result.insert(id, self.storage.count(filter)?);
338                Ok(())
339            },
340        )?;
341        Ok(result)
342    }
343    fn label_degree(&self, label: &str, graph: &str) -> GraphStoreResult<f64> {
344        self.require_graph(graph)?;
345        let mut sources = BTreeSet::new();
346        let mut count = 0_usize;
347        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
348        filter.label = Some(label);
349        self.for_each_id(filter, |id| {
350            sources.insert(self.require_edge(id, graph)?.source_id);
351            count += 1;
352            Ok(())
353        })?;
354        if sources.is_empty() {
355            return Ok(0.0);
356        }
357        Ok(
358            crate::memory_store::usize_to_f64_exact(count, "edge label count")?
359                / crate::memory_store::usize_to_f64_exact(
360                    sources.len(),
361                    "edge label source count",
362                )?,
363        )
364    }
365    fn vertex_label_counts(&self, graph: &str) -> GraphStoreResult<BTreeMap<String, u64>> {
366        self.require_graph(graph)?;
367        let mut result = BTreeMap::new();
368        self.for_each_id(
369            GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
370            |id| {
371                *result.entry(self.require_vertex(id)?.label).or_default() += 1;
372                Ok(())
373            },
374        )?;
375        Ok(result)
376    }
377    fn get_vertex(&self, id: u64) -> GraphStoreResult<Option<Vertex>> {
378        self.storage.vertex(id)
379    }
380    fn get_edge(&self, id: u64) -> GraphStoreResult<Option<Edge>> {
381        self.storage.edge(id)
382    }
383    fn next_vertex_id(&mut self) -> GraphStoreResult<u64> {
384        self.allocate_counter(GraphEntityKind::Vertex)
385    }
386    fn next_edge_id(&mut self) -> GraphStoreResult<u64> {
387        self.allocate_counter(GraphEntityKind::Edge)
388    }
389    fn allocate_vertex_id(&mut self, label: &str, graph: &str) -> GraphStoreResult<u64> {
390        self.allocate_label_id(label, graph, LabelKind::Vertex)
391    }
392    fn allocate_edge_id(&mut self, label: &str, graph: &str) -> GraphStoreResult<u64> {
393        self.allocate_label_id(label, graph, LabelKind::Edge)
394    }
395    fn clear(&mut self) -> GraphStoreResult<()> {
396        self.transaction(|store| {
397            for graph in store.graph_names()? {
398                store.drop_graph(&graph)?;
399            }
400            for kind in [GraphEntityKind::Vertex, GraphEntityKind::Edge] {
401                // Also release global records left without any membership.
402                store.for_each_id(GraphEntityFilter::new(kind, None), |id| match kind {
403                    GraphEntityKind::Vertex => store.storage.delete_vertex(id),
404                    GraphEntityKind::Edge => store.storage.delete_edge(id),
405                })?;
406                store.storage.save_counter(kind, 1)?;
407            }
408            Ok(())
409        })
410    }
411    fn vertices(&self) -> GraphStoreResult<BTreeMap<u64, Vertex>> {
412        let mut result = BTreeMap::new();
413        self.for_each_id(
414            GraphEntityFilter::new(GraphEntityKind::Vertex, None),
415            |id| {
416                result.insert(id, self.require_vertex(id)?);
417                Ok(())
418            },
419        )?;
420        Ok(result)
421    }
422    fn edges(&self) -> GraphStoreResult<BTreeMap<u64, Edge>> {
423        let mut result = BTreeMap::new();
424        self.for_each_id(GraphEntityFilter::new(GraphEntityKind::Edge, None), |id| {
425            let edge = self
426                .storage
427                .edge(id)?
428                .ok_or_else(|| GraphStoreError::CorruptGraph(format!("missing edge {id}")))?;
429            result.insert(id, edge);
430            Ok(())
431        })?;
432        Ok(result)
433    }
434}
uqa_graph/persistent_store/trait_impl.rs

uqa_graph/persistent_store/
trait_impl.rs
