Embedded Graph Databases

Building the SQLite of Graph Data

Introduction: Why the SQLite of Graph Data Does Not Yet Exist

1. What You Will Build
2. Why Graph Data Needs Its Own Embedded Engine
3. What This Book Is Not
4. How to Read This Book
5. Prerequisites
6. The Journey Ahead

Chapter 1: The Embedded Graph Database Thesis

1. What “Embedded” Means: No Server, No Daemon, No Network
2. The Graph Workload Gap in Existing Embedded Systems
3. Why SQLite Is Our North Star (And Where We Must Depart)
4. Target Deployment Models and Realistic Use Cases
5. Design Goals: Correctness, Durability, Locality, Small Footprint
6. Non-Goals: Distributed Consensus, ML Integration, Cloud-Native Abstractions

Chapter 2: Graph Foundations for Storage Engineers

1. Vertices, Edges, Directions, and the Property Graph Model
2. Labels, Types, Properties: And Why They Matter for Indexing
3. Multigraphs, Self-Loops, and Duplicate Semantics
4. Paths, Walks, Cycles, Neighborhoods, and Reachability
5. Degree Distributions and the Supernode Problem
6. Graph Schemas: Enforced vs. Optional vs. Hybrid

Chapter 3: Database Internals from First Principles

1. Pages, Blocks, Records, and Slots: The Vocabulary of Storage
2. Fixed vs. Variable-Length Records and Slotted Page Design
3. File Formats: Headers, Metadata, and Self-Description
4. The Memory Stack: Application Heap, OS Cache, Database Buffer Pool
5. Disk, SSD, NVMe Characteristics and I/O Patterns That Matter
6. Checksums, Corruption Detection, and the Cost of Trust

Chapter 4: Architecting Graph Storage on Disk

1. Adjacency Lists vs. Matrices vs. Edge Tables: The Fundamental Trade-offs
2. Node-Centric Layouts: Clustering Relationships Near Their Source
3. CSR/CSC-Inspired Structures for Traversal Locality
4. Pointer Chasing, Offsets, and the Cost of Indirection
5. Update Patterns: Appends, Deletes, Fragmentation, and Compaction
6. The Reference Architecture: Why We Choose What We Choose

Chapter 5: The Binary Database File Format

1. Magic Values, Version Numbers, and Byte Ordering
2. Page Size Selection and Global Header Layout
3. Node Records: IDs, Labels, Property Pointers, Degree Counters
4. Edge Records: Source/Target References, Types, Properties
5. Variable-Length Properties and Overflow Page Handling
6. Free-Page Tracking, Checksums, and Corruption Invariants

Chapter 6: Identifiers, References, and Relocation

1. Physical Record IDs vs. Logical Stable Identifiers
2. Page/Slot Addressing and Generation Counters
3. Deleted Object Reuse Without Tombstone Explosion
4. Stale Reference Detection and Safe Indirection Layers
5. Relocation During Compaction and Vacuum Operations
6. Trade-off Analysis: Compactness vs. Durability vs. Simplicity

Chapter 7: Memory Management and Page Caching

1. Page Allocation, Free Lists, and Persistent Freelist Tracking
2. Buffer Pool Architecture: Pinning, Dirty Pages, Eviction
3. LRU vs. Clock Algorithms: Measured, Not Assumed
4. Memory Mapping: When mmap Helps and When It Hurts
5. Prefetching Strategies for Traversal Locality
6. Bounded Memory Usage and Graceful Degradation

Chapter 8: Indexing for Graph Data

1. B+ Trees from Scratch: Pages, Splits, Merges, Search
2. Hash Indexes for Equality Lookups and Constraints
3. Property Indexes: Single-Key, Composite, and Inverted Structures
4. Adjacency Indexes: Accelerating Neighbor Expansion
5. Index Maintenance Under Transactional Updates
6. Statistics, Selectivity, and Query Planner Integration

Chapter 9: Core Graph Operations and Semantics

1. Node Creation, Reading, Update, and Deletion Semantics
2. Edge Creation with Duplicate and Self-Loop Policies
3. Property Operations: Sets, Nulls, Missing vs. Explicit Absence
4. Cascading Deletes, Dangling Edges, and Referential Behavior
5. Schema Constraints: Uniqueness, Type Enforcement, Validation
6. Transactional Visibility of Graph Mutations

Chapter 10: Transactions from First Principles

1. ACID in the Embedded Context: What It Actually Guarantees
2. Transaction States: Active, Prepared, Committed, Aborted
3. Lock-Based Concurrency: Granularity, Deadlocks, Starvation
4. Optimistic Concurrency and Timestamp-Based MVCC
5. Read Sets, Write Sets, Conflict Detection at Commit Time
6. The Reference Choice: Why We Implement What We Implement

Chapter 11: Durability, Logging, and Crash Recovery

1. Write-Ahead Logging vs. Rollback Journals vs. Copy-on-Write
2. WAL Design: Log Records, Transaction Boundaries, Group Commit
3. fsync Semantics, Durability Primitives, and OS Buffering Hazards
4. Checkpoints: Materializing WAL State to the Main Database File
5. Recovery Procedure: Redo of Committed, Undo of Uncommitted
6. Crash Testing Infrastructure: Fault Injection and Invariant Verification

Chapter 12: Graph Traversal Primitives

1. Neighbor Expansion: The Atomic Unit of Graph Traversal
2. Breadth-First Search with Frontier Management and Visited Sets
3. Depth-First Search, Cycle Handling, and Path Reconstruction
4. Directional Filtering, Type Filtering, Property Predicates
5. Memory-Efficient Traversal Over Graphs Larger Than RAM
6. Distinguishing Traversal Primitives from Analytical Algorithms

Chapter 13: Query Language and Frontend

1. Language Design Goals: Expressiveness vs. Simplicity vs. Familiarity
2. Lexical Structure: Tokens, Keywords, Literals, Identifiers
3. Grammar: Patterns, Predicates, Projections, Traversals, Mutations
4. Parser Implementation: Recursive Descent with Error Recovery
5. Semantic Analysis: Name Resolution, Type Checking, Validation
6. Logical Query Representation and Plan Input

Chapter 14: Query Planning, Optimization, and Execution

1. Logical vs. Physical Plans: Operators and Their Costs
2. Cardinality and Selectivity Estimation from Statistics
3. Index Selection: Scan vs. Seek Decisions for Graph Patterns
4. Traversal Order Planning: Avoiding Intermediate Result Explosion
5. Rule-Based and Cost-Based Optimization Rules
6. Iterator Execution Engine: Volcano Model, Memory, Spilling

Chapter 15: APIs, Bindings, Tools, and Production Readiness

1. Embedded API Design: Lifecycle, Transactions, Prepared Statements
2. Rust Implementation and Python Bindings via FFI
3. Database Shell and CLI: Querying, Inspection, Maintenance
4. Security: Untrusted Files, Parser Attacks, Resource Exhaustion
5. Error Model, Observability, and Tuning Guidance
6. Backup, Restore, Integrity Checks, and Production Deployment

Conclusion: The Cohesive Engine

References