Requirements

Requirements

Numbered requirements for mGraphDB. Each is verified by a method on the Test Plan page. Status: Done, Design, or Planned.

Requirement IDs are stable; if a requirement is dropped it is marked obsolete rather than reused.

1. Graph model

ID	Requirement	Status
REQ-01	The model represents Nodes, Edges, and Properties.	Done
REQ-02	Edges and Properties are specialisations of Node ("everything is a node").	Done
REQ-03	Every element is addressable by a compact integer ID.	Done
REQ-04	A node may carry a type reference to a "class" node. The reference is optional; no type is required.	Design
REQ-05	The database is schema-less: no schema or type definition is required before writing data; the storage engine enforces no structural constraints. Types, classes, and ontologies are represented as nodes and edges within the graph itself and constitute a descriptive viewpoint, not a write gate.	Design

2. String Store

ID	Requirement	Status
REQ-10	Strings are interned and deduplicated; identical content is stored once.	Done
REQ-11	Each string is addressable by a compact StrId (u64).	Done
REQ-12	Each string has a 128-bit content hash for dedup and cross-segment identity.	Done
REQ-13	Storage is append-only: existing entries are never mutated.	Done
REQ-14	An entry is encoded as [hash128][varint len][utf8][crc32].	Done
REQ-15	Entries are grouped into blocks (~64 KiB) with an entry-offset trailer.	Done
REQ-16	A store can be saved to and re-opened from a single segment file. Format v1 (uncompressed) and v2 (compression-capable) are both readable.	Done
REQ-17	On open, every entry's CRC32 and UTF-8 validity are verified.	Done
REQ-18	On open, a corrupt header/footer/directory is rejected with an error.	Done
REQ-19	API: intern, resolve_id, resolve_hash, id_of, hash_of.	Done
REQ-20	Block payload compression is optional and signalled by header flags. Supported algorithms: None (default), LZ4 (lz4_flex, pure Rust), Zstd (level 3). Selected at store-creation time via Compression enum.	Done
REQ-21	A per-segment Bloom filter is optional and signalled by footer flags.	Planned
REQ-22	Long values may be routed to a more space-efficient store. Implemented in Graph::set_str: strings > 14 bytes are interned into the String Store and referenced by StrId.	Done
REQ-23	Incremental on-disk append (without rewriting the whole segment).	Planned
REQ-24	Lazy decompression: blocks remain compressed on disk; individual entries are decompressed on demand by resolve_id/resolve_hash without loading or decompressing the full block.	Planned
REQ-25	FSST compression as an optional third algorithm (after REQ-24); enables random-access decompression of single entries via a per-block symbol table. Depends on a production-ready, Arrow-free Rust implementation.	Planned

3. Persistent layer (Small Profile)

ID	Requirement	Status
REQ-30	Records are fixed length, giving direct access by ID (offset = id × record_size).	Done
REQ-31	Reference (ID) size is configurable at creation. Current: u32 (NodeId); NodeId::MAX is the null sentinel.	Done
REQ-32	Node storage has three options: not stored, dedicated file, or inline-with-data. Option 2 (dedicated file) implemented.	Done
REQ-33	Node flags encode subtype (4 bits) plus tombstone, HAS_IN, HAS_OUT, HAS_PROP.	Done
REQ-34	Edges and Properties share a fixed 16-byte record in the property store.	Done
REQ-35	An edge stores start/end node references; properties store a typed value.	Done
REQ-36	The 16-byte buffer supports a range of value types (see §4).	Done
REQ-37	Values too large for 16 bytes are referenced into the String Store.	Done
REQ-38	A node's owned edges/properties are resolved through a separate CSR adjacency index (offsets + neighbors), built from explicit owner→record associations. The index is a derived view: rebuildable, memory-only, or droppable.	Done

4. Value types (property buffer)

ID	Requirement	Status
REQ-40	STRING: short UTF-8 inline — up to INLINE_STR_MAX (10) bytes; longer strings via String Store.	Done
REQ-41	BOOL, INTEGER (i128), DECIMAL (f64/f128).	Done
REQ-42	DATE / TIME / DATETIME / DURATION.	Done
REQ-43	UUID (16 bytes), HASH, GEO (lat/long).	Done
REQ-44	URL / TEXT / FILE referenced into a backing store.	Done
REQ-45	VECTOR referenced into an optional vector store.	Planned
REQ-46	The value type is encoded in the record flags.	Done

4b. Graph API

ID	Requirement	Status
REQ-60	A single Graph facade owns the node, property/edge, string, and index layers and exposes node/property/edge creation.	Done
REQ-61	Edges are created as Edge-valued property records owned by the start node; the start gains HAS_OUT and the end gains HAS_IN.	Done
REQ-62	Traversal accessors return a node's owned records, outgoing edges, and properties; string values resolve transparently across inline / String-Store storage.	Done
REQ-63	The whole graph can be persisted to and reloaded from a directory of segment files, rebuilding adjacency from the CSR index on load.	Done
REQ-64	Incoming-edge traversal is O(1) via a reverse adjacency (in_edges / in_neighbors / in_degree), maintained on edge creation and rebuilt from the edges on load in insertion order.	Done
REQ-65	A node can be soft-deleted (tombstoned, id never reused) and is detached symmetrically: its outgoing and incoming edges are removed from the respective peers, and its records are orphaned. Writes targeting a deleted node are rejected. Deletion state persists.	Done
REQ-66	Each property and edge carries a key: a NodeId naming the property or labelling the edge (RDF-predicate style; NO_KEY = unkeyed). It is stored in-record (bytes 2–5). Lookups by key (get_property, edges_of_type) resolve by name, not position.	Done
REQ-67	Nodes can be found by property value: find_by_property(key, value), find_by_str(key, s) (resolves inline/String-Store storage), and find_by_key(key). Results are ascending node order, each node once, excluding edges and deleted nodes. Currently a full scan; a secondary inverted index is a planned optimisation.	Done
REQ-68	A graph can be imported from a SNAP-style edge list (from/to integer pairs, # comments skipped) via from_edge_list; sparse source ids are remapped to contiguous NodeIds, each line becoming one directed edge.	Done

5. Non-functional

ID	Requirement	Status
REQ-50	Minimal footprint, embeddable like SQLite.	Design
REQ-51	No unsafe in the project's own crates.	Done
REQ-52	Zero compiler and Clippy warnings.	Done
REQ-53	Little-endian on-disk encoding across platforms.	Done
REQ-54	MIT licensed.	Done
REQ-55	Full ACID support is not required for now.	N/A