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 = "crate::serde_map")]
228    roles: BTreeMap<RoleId, RoleDefinition>,
229    /// Role IDs by name.
230    role_names: BTreeMap<String, RoleId>,
231    /// Labels by stable ID.
232    #[serde(with = "crate::serde_map")]
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 = "crate::serde_map")]
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 = "crate::serde_map")]
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 = "crate::serde_map")]
248    projections: BTreeMap<ProjectionId, ProjectionEntry>,
249    /// Projection IDs by name.
250    projection_names: BTreeMap<String, ProjectionId>,
251    /// Indexes by stable ID.
252    #[serde(with = "crate::serde_map")]
253    indexes: BTreeMap<IndexId, IndexEntry>,
254    /// Index IDs by name.
255    index_names: BTreeMap<String, IndexId>,
256}
257
258impl Catalog {
259    /// Creates an empty catalog.
260    ///
261    /// # Performance
262    ///
263    /// This function is `O(1)`.
264    #[must_use]
265    pub(crate) const fn empty() -> Self {
266        Self {
267            roles: BTreeMap::new(),
268            role_names: BTreeMap::new(),
269            labels: BTreeMap::new(),
270            label_names: BTreeMap::new(),
271            relation_types: BTreeMap::new(),
272            relation_type_names: BTreeMap::new(),
273            property_keys: BTreeMap::new(),
274            property_key_names: BTreeMap::new(),
275            projections: BTreeMap::new(),
276            projection_names: BTreeMap::new(),
277            indexes: BTreeMap::new(),
278            index_names: BTreeMap::new(),
279        }
280    }
281
282    /// Returns a role definition.
283    ///
284    /// # Performance
285    ///
286    /// This method is `O(log r)`.
287    #[must_use]
288    pub fn role(&self, id: RoleId) -> Option<&RoleDefinition> {
289        self.roles.get(&id)
290    }
291
292    /// Returns a label definition.
293    ///
294    /// # Performance
295    ///
296    /// This method is `O(log l)`.
297    #[must_use]
298    pub fn label(&self, id: LabelId) -> Option<&LabelDefinition> {
299        self.labels.get(&id)
300    }
301
302    /// Returns a relation type definition.
303    ///
304    /// # Performance
305    ///
306    /// This method is `O(log t)`.
307    #[must_use]
308    pub fn relation_type(&self, id: RelationTypeId) -> Option<&RelationTypeDefinition> {
309        self.relation_types.get(&id)
310    }
311
312    /// Returns a property key definition.
313    ///
314    /// # Performance
315    ///
316    /// This method is `O(log p)`.
317    #[must_use]
318    pub fn property_key(&self, id: PropertyKeyId) -> Option<&PropertyKeyDefinition> {
319        self.property_keys.get(&id)
320    }
321
322    /// Returns a projection entry.
323    ///
324    /// # Performance
325    ///
326    /// This method is `O(log p)`.
327    #[must_use]
328    pub fn projection(&self, id: ProjectionId) -> Option<&ProjectionEntry> {
329        self.projections.get(&id)
330    }
331
332    /// Returns an index entry.
333    ///
334    /// # Performance
335    ///
336    /// This method is `O(log i)`.
337    #[must_use]
338    pub fn index(&self, id: IndexId) -> Option<&IndexEntry> {
339        self.indexes.get(&id)
340    }
341
342    /// Resolves a role name.
343    ///
344    /// # Performance
345    ///
346    /// This method is `O(log r + name length)`.
347    #[must_use]
348    pub fn role_id(&self, name: &str) -> Option<RoleId> {
349        self.role_names.get(name).copied()
350    }
351
352    /// Resolves a label name.
353    ///
354    /// # Performance
355    ///
356    /// This method is `O(log l + name length)`.
357    #[must_use]
358    pub fn label_id(&self, name: &str) -> Option<LabelId> {
359        self.label_names.get(name).copied()
360    }
361
362    /// Resolves a relation type name.
363    ///
364    /// # Performance
365    ///
366    /// This method is `O(log t + name length)`.
367    #[must_use]
368    pub fn relation_type_id(&self, name: &str) -> Option<RelationTypeId> {
369        self.relation_type_names.get(name).copied()
370    }
371
372    /// Resolves a property key name.
373    ///
374    /// # Performance
375    ///
376    /// This method is `O(log p + name length)`.
377    #[must_use]
378    pub fn property_key_id(&self, name: &str) -> Option<PropertyKeyId> {
379        self.property_key_names.get(name).copied()
380    }
381
382    /// Resolves a projection name.
383    ///
384    /// # Performance
385    ///
386    /// This method is `O(log p + name length)`.
387    #[must_use]
388    pub fn projection_id(&self, name: &str) -> Option<ProjectionId> {
389        self.projection_names.get(name).copied()
390    }
391
392    /// Resolves an index name.
393    ///
394    /// # Performance
395    ///
396    /// This method is `O(log i + name length)`.
397    #[must_use]
398    pub fn index_id(&self, name: &str) -> Option<IndexId> {
399        self.index_names.get(name).copied()
400    }
401
402    /// Iterates role definitions in ID order.
403    ///
404    /// # Performance
405    ///
406    /// Creating the iterator is `O(1)`.
407    pub fn roles(&self) -> impl Iterator<Item = &RoleDefinition> {
408        self.roles.values()
409    }
410
411    /// Iterates label definitions in ID order.
412    ///
413    /// # Performance
414    ///
415    /// Creating the iterator is `O(1)`.
416    pub fn labels(&self) -> impl Iterator<Item = &LabelDefinition> {
417        self.labels.values()
418    }
419
420    /// Iterates relation type definitions in ID order.
421    ///
422    /// # Performance
423    ///
424    /// Creating the iterator is `O(1)`.
425    pub fn relation_types(&self) -> impl Iterator<Item = &RelationTypeDefinition> {
426        self.relation_types.values()
427    }
428
429    /// Iterates property key definitions in ID order.
430    ///
431    /// # Performance
432    ///
433    /// Creating the iterator is `O(1)`.
434    pub fn property_keys(&self) -> impl Iterator<Item = &PropertyKeyDefinition> {
435        self.property_keys.values()
436    }
437
438    /// Iterates projection entries in ID order.
439    ///
440    /// # Performance
441    ///
442    /// Creating the iterator is `O(1)`.
443    pub fn projections(&self) -> impl Iterator<Item = &ProjectionEntry> {
444        self.projections.values()
445    }
446
447    /// Iterates index entries in ID order.
448    ///
449    /// # Performance
450    ///
451    /// Creating the iterator is `O(1)`.
452    pub fn indexes(&self) -> impl Iterator<Item = &IndexEntry> {
453        self.indexes.values()
454    }
455
456    /// Registers a structural role.
457    pub(crate) fn insert_role(&mut self, id: RoleId, name: String) -> Result<(), DbError> {
458        insert_named(&mut self.role_names, &name, id)?;
459        self.roles.insert(id, RoleDefinition { id, name });
460        Ok(())
461    }
462
463    /// Registers a label.
464    pub(crate) fn insert_label(&mut self, id: LabelId, name: String) -> Result<(), DbError> {
465        insert_named(&mut self.label_names, &name, id)?;
466        self.labels.insert(id, LabelDefinition { id, name });
467        Ok(())
468    }
469
470    /// Registers a relation type.
471    pub(crate) fn insert_relation_type(
472        &mut self,
473        id: RelationTypeId,
474        name: String,
475    ) -> Result<(), DbError> {
476        insert_named(&mut self.relation_type_names, &name, id)?;
477        self.relation_types
478            .insert(id, RelationTypeDefinition { id, name });
479        Ok(())
480    }
481
482    /// Registers a typed property key.
483    pub(crate) fn insert_property_key(
484        &mut self,
485        definition: PropertyKeyDefinition,
486    ) -> Result<(), DbError> {
487        insert_named(
488            &mut self.property_key_names,
489            &definition.name,
490            definition.id,
491        )?;
492        self.property_keys.insert(definition.id, definition);
493        Ok(())
494    }
495
496    /// Registers a projection definition.
497    pub(crate) fn insert_projection(
498        &mut self,
499        id: ProjectionId,
500        definition: ProjectionDefinition,
501    ) -> Result<(), DbError> {
502        insert_named(&mut self.projection_names, definition.name(), id)?;
503        self.projections
504            .insert(id, ProjectionEntry { id, definition });
505        Ok(())
506    }
507
508    /// Registers an index definition.
509    pub(crate) fn insert_index(
510        &mut self,
511        id: IndexId,
512        name: String,
513        definition: IndexDefinition,
514    ) -> Result<(), DbError> {
515        insert_named(&mut self.index_names, &name, id)?;
516        self.indexes.insert(
517            id,
518            IndexEntry {
519                id,
520                name,
521                definition,
522            },
523        );
524        Ok(())
525    }
526}
527
528/// Inserts one unique name into a catalog name map.
529fn insert_named<Id: Copy>(
530    names: &mut BTreeMap<String, Id>,
531    name: &str,
532    id: Id,
533) -> Result<(), DbError> {
534    if names.contains_key(name) {
535        return Err(DbError::DuplicateCatalogName);
536    }
537    names.insert(name.to_owned(), id);
538    Ok(())
539}
oxgraph_db/catalog.rs

oxgraph_db/
catalog.rs
