oxgraph_db/
catalog.rs

1//! Catalog metadata for names, projections, property keys, and indexes.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5use serde::{Deserialize, Serialize};
6
7use crate::{
8    DbError, IndexId, LabelId, ProjectionId, PropertyKeyId, RelationTypeId, RoleId,
9    value::PropertyType,
10};
11
12/// Catalog entry for one structural incidence role.
13///
14/// # Performance
15///
16/// Cloning is `O(name length)`.
17#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
18pub struct RoleDefinition {
19    /// Stable role identifier.
20    pub id: RoleId,
21    /// Human-readable unique role name.
22    pub name: String,
23}
24
25/// Catalog entry for one element or relation label.
26///
27/// # Performance
28///
29/// Cloning is `O(name length)`.
30#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
31pub struct LabelDefinition {
32    /// Stable label identifier.
33    pub id: LabelId,
34    /// Human-readable unique label name.
35    pub name: String,
36}
37
38/// Catalog entry for one relation type.
39///
40/// # Performance
41///
42/// Cloning is `O(name length)`.
43#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
44pub struct RelationTypeDefinition {
45    /// Stable relation type identifier.
46    pub id: RelationTypeId,
47    /// Human-readable unique relation type name.
48    pub name: String,
49}
50
51/// Subject family accepted by a property key.
52///
53/// # Performance
54///
55/// Copying and comparing are `O(1)`.
56#[derive(Clone, Copy, Debug, Deserialize, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize)]
57pub enum PropertyFamily {
58    /// Property applies to canonical elements.
59    Element,
60    /// Property applies to canonical relations.
61    Relation,
62    /// Property applies to canonical incidences.
63    Incidence,
64}
65
66/// Catalog entry for one typed property key.
67///
68/// # Performance
69///
70/// Cloning is `O(name length)`.
71#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
72pub struct PropertyKeyDefinition {
73    /// Stable property key identifier.
74    pub id: PropertyKeyId,
75    /// Human-readable unique key name.
76    pub name: String,
77    /// Subject family this key can be attached to.
78    pub family: PropertyFamily,
79    /// Required scalar value type.
80    pub value_type: PropertyType,
81}
82
83/// Graph projection definition.
84///
85/// Graph projections materialize binary relations as CSR outgoing and CSC
86/// incoming arrays over canonical topology IDs.
87///
88/// # Performance
89///
90/// Cloning is `O(r)` for `r` selected relation types plus the name length.
91#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
92pub struct GraphProjectionDefinition {
93    /// Unique projection name.
94    pub name: String,
95    /// Relation types visible as binary graph edges.
96    pub relation_types: BTreeSet<RelationTypeId>,
97    /// Role identifying the source endpoint.
98    pub source_role: RoleId,
99    /// Role identifying the target endpoint.
100    pub target_role: RoleId,
101}
102
103/// Hypergraph projection definition.
104///
105/// Hypergraph projections materialize many-participant directed relations as
106/// BCSR-style relation-major and vertex-major arrays.
107///
108/// # Performance
109///
110/// Cloning is `O(r + s + t)` for relation type and role set sizes plus the
111/// name length.
112#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
113pub struct HypergraphProjectionDefinition {
114    /// Unique projection name.
115    pub name: String,
116    /// Relation types visible as hyperedges.
117    pub relation_types: BTreeSet<RelationTypeId>,
118    /// Roles treated as source-side participants.
119    pub source_roles: BTreeSet<RoleId>,
120    /// Roles treated as target-side participants.
121    pub target_roles: BTreeSet<RoleId>,
122}
123
124/// Physical projection definition stored in the catalog.
125///
126/// # Performance
127///
128/// Cloning is `O(definition size)`.
129#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
130pub enum ProjectionDefinition {
131    /// Binary graph projection.
132    Graph(GraphProjectionDefinition),
133    /// Directed hypergraph projection.
134    Hypergraph(HypergraphProjectionDefinition),
135}
136
137impl ProjectionDefinition {
138    /// Returns the unique projection name.
139    ///
140    /// # Performance
141    ///
142    /// This method is `O(1)`.
143    #[must_use]
144    pub fn name(&self) -> &str {
145        match self {
146            Self::Graph(definition) => &definition.name,
147            Self::Hypergraph(definition) => &definition.name,
148        }
149    }
150}
151
152/// Index definition stored in the catalog.
153///
154/// # Performance
155///
156/// Cloning is `O(key count)` for composite indexes and `O(1)` otherwise.
157#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
158pub enum IndexDefinition {
159    /// Element label membership index.
160    Label {
161        /// Indexed label.
162        label: LabelId,
163    },
164    /// Relation type membership index.
165    RelationType {
166        /// Indexed relation type.
167        relation_type: RelationTypeId,
168    },
169    /// Equality index over one property key.
170    PropertyEquality {
171        /// Indexed property key.
172        key: PropertyKeyId,
173    },
174    /// Range index over one ordered property key.
175    PropertyRange {
176        /// Indexed property key.
177        key: PropertyKeyId,
178    },
179    /// Composite equality index over ordered property keys.
180    CompositeEquality {
181        /// Indexed property keys in tuple order.
182        keys: Vec<PropertyKeyId>,
183    },
184    /// Projection-materialization index metadata.
185    Projection {
186        /// Indexed projection.
187        projection: ProjectionId,
188    },
189}
190
191/// Catalog entry for one index.
192///
193/// # Performance
194///
195/// Cloning is `O(name length + definition size)`.
196#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
197pub struct IndexEntry {
198    /// Stable index identifier.
199    pub id: IndexId,
200    /// Human-readable unique index name.
201    pub name: String,
202    /// Logical index definition.
203    pub definition: IndexDefinition,
204}
205
206/// Catalog entry for one projection.
207///
208/// # Performance
209///
210/// Cloning is `O(name length + definition size)`.
211#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
212pub struct ProjectionEntry {
213    /// Stable projection identifier.
214    pub id: ProjectionId,
215    /// Physical projection definition.
216    pub definition: ProjectionDefinition,
217}
218
219/// Database catalog for names, schemas, projections, and indexes.
220///
221/// # Performance
222///
223/// Cloning is `O(catalog entries + string bytes)`.
224#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
225pub struct Catalog {
226    /// Roles by stable ID.
227    #[serde(with = "serde_btree_map_vec")]
228    roles: BTreeMap<RoleId, RoleDefinition>,
229    /// Role IDs by name.
230    role_names: BTreeMap<String, RoleId>,
231    /// Labels by stable ID.
232    #[serde(with = "serde_btree_map_vec")]
233    labels: BTreeMap<LabelId, LabelDefinition>,
234    /// Label IDs by name.
235    label_names: BTreeMap<String, LabelId>,
236    /// Relation types by stable ID.
237    #[serde(with = "serde_btree_map_vec")]
238    relation_types: BTreeMap<RelationTypeId, RelationTypeDefinition>,
239    /// Relation type IDs by name.
240    relation_type_names: BTreeMap<String, RelationTypeId>,
241    /// Property keys by stable ID.
242    #[serde(with = "serde_btree_map_vec")]
243    property_keys: BTreeMap<PropertyKeyId, PropertyKeyDefinition>,
244    /// Property key IDs by name.
245    property_key_names: BTreeMap<String, PropertyKeyId>,
246    /// Projections by stable ID.
247    #[serde(with = "serde_btree_map_vec")]
248    projections: BTreeMap<ProjectionId, ProjectionEntry>,
249    /// Projection IDs by name.
250    projection_names: BTreeMap<String, ProjectionId>,
251    /// Indexes by stable ID.
252    #[serde(with = "serde_btree_map_vec")]
253    indexes: BTreeMap<IndexId, IndexEntry>,
254    /// Index IDs by name.
255    index_names: BTreeMap<String, IndexId>,
256}
257
258/// Serde helper for `BTreeMap` values keyed by non-string IDs.
259mod serde_btree_map_vec {
260    /// Serializes a map as an ordered entry array.
261    pub(super) fn serialize<S, K, V>(
262        map: &std::collections::BTreeMap<K, V>,
263        serializer: S,
264    ) -> Result<S::Ok, S::Error>
265    where
266        S: serde::Serializer,
267        K: serde::Serialize,
268        V: serde::Serialize,
269    {
270        serde::Serialize::serialize(&map.iter().collect::<Vec<_>>(), serializer)
271    }
272
273    /// Deserializes a map from an ordered entry array.
274    pub(super) fn deserialize<'de, D, K, V>(
275        deserializer: D,
276    ) -> Result<std::collections::BTreeMap<K, V>, D::Error>
277    where
278        D: serde::Deserializer<'de>,
279        K: Ord + serde::de::DeserializeOwned,
280        V: serde::de::DeserializeOwned,
281    {
282        <Vec<(K, V)> as serde::Deserialize>::deserialize(deserializer)
283            .map(|entries| entries.into_iter().collect())
284    }
285}
286
287impl Catalog {
288    /// Creates an empty catalog.
289    ///
290    /// # Performance
291    ///
292    /// This function is `O(1)`.
293    #[must_use]
294    pub(crate) const fn empty() -> Self {
295        Self {
296            roles: BTreeMap::new(),
297            role_names: BTreeMap::new(),
298            labels: BTreeMap::new(),
299            label_names: BTreeMap::new(),
300            relation_types: BTreeMap::new(),
301            relation_type_names: BTreeMap::new(),
302            property_keys: BTreeMap::new(),
303            property_key_names: BTreeMap::new(),
304            projections: BTreeMap::new(),
305            projection_names: BTreeMap::new(),
306            indexes: BTreeMap::new(),
307            index_names: BTreeMap::new(),
308        }
309    }
310
311    /// Returns a role definition.
312    ///
313    /// # Performance
314    ///
315    /// This method is `O(log r)`.
316    #[must_use]
317    pub fn role(&self, id: RoleId) -> Option<&RoleDefinition> {
318        self.roles.get(&id)
319    }
320
321    /// Returns a label definition.
322    ///
323    /// # Performance
324    ///
325    /// This method is `O(log l)`.
326    #[must_use]
327    pub fn label(&self, id: LabelId) -> Option<&LabelDefinition> {
328        self.labels.get(&id)
329    }
330
331    /// Returns a relation type definition.
332    ///
333    /// # Performance
334    ///
335    /// This method is `O(log t)`.
336    #[must_use]
337    pub fn relation_type(&self, id: RelationTypeId) -> Option<&RelationTypeDefinition> {
338        self.relation_types.get(&id)
339    }
340
341    /// Returns a property key definition.
342    ///
343    /// # Performance
344    ///
345    /// This method is `O(log p)`.
346    #[must_use]
347    pub fn property_key(&self, id: PropertyKeyId) -> Option<&PropertyKeyDefinition> {
348        self.property_keys.get(&id)
349    }
350
351    /// Returns a projection entry.
352    ///
353    /// # Performance
354    ///
355    /// This method is `O(log p)`.
356    #[must_use]
357    pub fn projection(&self, id: ProjectionId) -> Option<&ProjectionEntry> {
358        self.projections.get(&id)
359    }
360
361    /// Returns an index entry.
362    ///
363    /// # Performance
364    ///
365    /// This method is `O(log i)`.
366    #[must_use]
367    pub fn index(&self, id: IndexId) -> Option<&IndexEntry> {
368        self.indexes.get(&id)
369    }
370
371    /// Resolves a role name.
372    ///
373    /// # Performance
374    ///
375    /// This method is `O(log r + name length)`.
376    #[must_use]
377    pub fn role_id(&self, name: &str) -> Option<RoleId> {
378        self.role_names.get(name).copied()
379    }
380
381    /// Resolves a label name.
382    ///
383    /// # Performance
384    ///
385    /// This method is `O(log l + name length)`.
386    #[must_use]
387    pub fn label_id(&self, name: &str) -> Option<LabelId> {
388        self.label_names.get(name).copied()
389    }
390
391    /// Resolves a relation type name.
392    ///
393    /// # Performance
394    ///
395    /// This method is `O(log t + name length)`.
396    #[must_use]
397    pub fn relation_type_id(&self, name: &str) -> Option<RelationTypeId> {
398        self.relation_type_names.get(name).copied()
399    }
400
401    /// Resolves a property key name.
402    ///
403    /// # Performance
404    ///
405    /// This method is `O(log p + name length)`.
406    #[must_use]
407    pub fn property_key_id(&self, name: &str) -> Option<PropertyKeyId> {
408        self.property_key_names.get(name).copied()
409    }
410
411    /// Resolves a projection name.
412    ///
413    /// # Performance
414    ///
415    /// This method is `O(log p + name length)`.
416    #[must_use]
417    pub fn projection_id(&self, name: &str) -> Option<ProjectionId> {
418        self.projection_names.get(name).copied()
419    }
420
421    /// Resolves an index name.
422    ///
423    /// # Performance
424    ///
425    /// This method is `O(log i + name length)`.
426    #[must_use]
427    pub fn index_id(&self, name: &str) -> Option<IndexId> {
428        self.index_names.get(name).copied()
429    }
430
431    /// Iterates role definitions in ID order.
432    ///
433    /// # Performance
434    ///
435    /// Creating the iterator is `O(1)`.
436    pub fn roles(&self) -> impl Iterator<Item = &RoleDefinition> {
437        self.roles.values()
438    }
439
440    /// Iterates label definitions in ID order.
441    ///
442    /// # Performance
443    ///
444    /// Creating the iterator is `O(1)`.
445    pub fn labels(&self) -> impl Iterator<Item = &LabelDefinition> {
446        self.labels.values()
447    }
448
449    /// Iterates relation type definitions in ID order.
450    ///
451    /// # Performance
452    ///
453    /// Creating the iterator is `O(1)`.
454    pub fn relation_types(&self) -> impl Iterator<Item = &RelationTypeDefinition> {
455        self.relation_types.values()
456    }
457
458    /// Iterates property key definitions in ID order.
459    ///
460    /// # Performance
461    ///
462    /// Creating the iterator is `O(1)`.
463    pub fn property_keys(&self) -> impl Iterator<Item = &PropertyKeyDefinition> {
464        self.property_keys.values()
465    }
466
467    /// Iterates projection entries in ID order.
468    ///
469    /// # Performance
470    ///
471    /// Creating the iterator is `O(1)`.
472    pub fn projections(&self) -> impl Iterator<Item = &ProjectionEntry> {
473        self.projections.values()
474    }
475
476    /// Iterates index entries in ID order.
477    ///
478    /// # Performance
479    ///
480    /// Creating the iterator is `O(1)`.
481    pub fn indexes(&self) -> impl Iterator<Item = &IndexEntry> {
482        self.indexes.values()
483    }
484
485    /// Registers a structural role.
486    pub(crate) fn insert_role(&mut self, id: RoleId, name: String) -> Result<(), DbError> {
487        insert_named(&mut self.role_names, &name, id)?;
488        self.roles.insert(id, RoleDefinition { id, name });
489        Ok(())
490    }
491
492    /// Registers a label.
493    pub(crate) fn insert_label(&mut self, id: LabelId, name: String) -> Result<(), DbError> {
494        insert_named(&mut self.label_names, &name, id)?;
495        self.labels.insert(id, LabelDefinition { id, name });
496        Ok(())
497    }
498
499    /// Registers a relation type.
500    pub(crate) fn insert_relation_type(
501        &mut self,
502        id: RelationTypeId,
503        name: String,
504    ) -> Result<(), DbError> {
505        insert_named(&mut self.relation_type_names, &name, id)?;
506        self.relation_types
507            .insert(id, RelationTypeDefinition { id, name });
508        Ok(())
509    }
510
511    /// Registers a typed property key.
512    pub(crate) fn insert_property_key(
513        &mut self,
514        definition: PropertyKeyDefinition,
515    ) -> Result<(), DbError> {
516        insert_named(
517            &mut self.property_key_names,
518            &definition.name,
519            definition.id,
520        )?;
521        self.property_keys.insert(definition.id, definition);
522        Ok(())
523    }
524
525    /// Registers a projection definition.
526    pub(crate) fn insert_projection(
527        &mut self,
528        id: ProjectionId,
529        definition: ProjectionDefinition,
530    ) -> Result<(), DbError> {
531        insert_named(&mut self.projection_names, definition.name(), id)?;
532        self.projections
533            .insert(id, ProjectionEntry { id, definition });
534        Ok(())
535    }
536
537    /// Registers an index definition.
538    pub(crate) fn insert_index(
539        &mut self,
540        id: IndexId,
541        name: String,
542        definition: IndexDefinition,
543    ) -> Result<(), DbError> {
544        insert_named(&mut self.index_names, &name, id)?;
545        self.indexes.insert(
546            id,
547            IndexEntry {
548                id,
549                name,
550                definition,
551            },
552        );
553        Ok(())
554    }
555}
556
557/// Inserts one unique name into a catalog name map.
558fn insert_named<Id: Copy>(
559    names: &mut BTreeMap<String, Id>,
560    name: &str,
561    id: Id,
562) -> Result<(), DbError> {
563    if names.contains_key(name) {
564        return Err(DbError::DuplicateCatalogName);
565    }
566    names.insert(name.to_owned(), id);
567    Ok(())
568}
oxgraph_db/catalog.rs

oxgraph_db/
catalog.rs
