rust-kgdb

Production-ready RDF/hypergraph database with 100% W3C SPARQL 1.1 + RDF 1.2 compliance, worst-case optimal joins (WCOJ), and pluggable storage backends.

This npm package provides the high-performance in-memory database. For distributed cluster deployment (1B+ triples, horizontal scaling), contact: gonnect.uk@gmail.com

Deployment Modes

rust-kgdb supports three deployment modes:

Distributed Cluster Mode (Enterprise)

For enterprise deployments requiring 1B+ triples and horizontal scaling:

Key Features:

• Subject-Anchored Partitioning: All triples for a subject are guaranteed on the same partition for optimal locality
• Arrow-Powered OLAP: High-performance analytical queries executed as optimized SQL at scale
• Automatic Query Routing: The coordinator intelligently routes queries to the right executors
• Kubernetes-Native: StatefulSet-based executors with automatic failover
• Linear Horizontal Scaling: Add more executor pods to scale throughput

How It Works:

Your SPARQL queries work unchanged. For large-scale aggregations, the cluster automatically optimizes execution:

-- Your SPARQL query
SELECT (COUNT(*) AS ?count) (AVG(?salary) AS ?avgSalary)
WHERE {
  ?employee <http://ex/type> <http://ex/Employee> .
  ?employee <http://ex/salary> ?salary .
}

-- Cluster executes as optimized SQL internally
-- Results aggregated across all partitions automatically

Request a demo: gonnect.uk@gmail.com

Why rust-kgdb?

Core Technical Innovations

1. Worst-Case Optimal Joins (WCOJ)

Traditional databases use nested-loop joins with O(n²) to O(n⁴) complexity. rust-kgdb implements the LeapFrog TrieJoin algorithm—a worst-case optimal join that achieves O(n log n) for multi-way joins.

How it works:

• Trie Data Structure: Triples indexed hierarchically (S→P→O) using BTreeMap for sorted access
• Variable Ordering: Frequency-based analysis orders variables for optimal intersection
• LeapFrog Iterator: Binary search across sorted iterators finds intersections without materializing intermediate results

Query: SELECT ?x ?y ?z WHERE { ?x :p ?y . ?y :q ?z . ?x :r ?z }

Nested Loop: O(n³) - examines every combination
WCOJ:        O(n log n) - iterates in sorted order, seeks forward on mismatch

2. Sparse Matrix Engine (CSR Format)

Binary relations (e.g., foaf:knows, rdfs:subClassOf) are converted to Compressed Sparse Row (CSR) matrices for cache-efficient join evaluation:

• Memory: O(nnz) where nnz = number of edges (not O(n²))
• Matrix Multiplication: Replaces nested-loop joins
• Transitive Closure: Semi-naive Δ-matrix evaluation (not iterated powers)

// Traditional: O(n²) nested loops
for (s, p, o) in triples { ... }

// CSR Matrix: O(nnz) cache-friendly iteration
row_ptr[i] → col_indices[j] → values[j]

Used for: RDFS/OWL reasoning, transitive closure, Datalog evaluation.

3. SIMD + PGO Compiler Optimizations

Zero code changes—pure compiler-level performance gains.

Benchmark Results (LUBM, Intel Skylake):

Average speedup: 44.5% across all queries.

4. Quad Indexing (SPOC)

Four complementary indexes enable O(1) pattern matching regardless of query shape:

Storage Backends

rust-kgdb uses a pluggable storage architecture. Default is in-memory (zero configuration). For persistence, enable RocksDB.

InMemory (Default)

Zero configuration, maximum performance. Data is volatile (lost on process exit).

High-Performance Data Structures:

Why these structures enable sub-microsecond performance:

• DashMap: Sharded locks (16 shards default) → near-linear scaling on multi-core
• FxHashMap: Rust compiler's hash function → 30% faster than std HashMap
• BTreeMap: O(log n) ordered iteration → enables binary search in LeapFrog
• Pre-allocation: 100K capacity avoids rehashing during bulk inserts

use storage::{QuadStore, InMemoryBackend};

let store = QuadStore::new(InMemoryBackend::new());
// Ultra-fast: 2.78 µs lookups, zero disk I/O

RocksDB (Persistent)

LSM-tree based storage with ACID transactions. Tested with 61 comprehensive tests.

# Cargo.toml - Enable RocksDB backend
[dependencies]
storage = { version = "0.1.10", features = ["rocksdb-backend"] }

use storage::{QuadStore, RocksDbBackend};

// Create persistent database
let backend = RocksDbBackend::new("/path/to/data")?;
let store = QuadStore::new(backend);

// Features:
// - ACID transactions
// - Snappy compression (automatic)
// - Crash recovery
// - Range & prefix scanning
// - 1MB+ value support

// Force sync to disk
store.flush()?;

RocksDB Test Coverage:

• Basic CRUD operations (14 tests)
• Range scanning (8 tests)
• Prefix scanning (6 tests)
• Batch operations (8 tests)
• Transactions (8 tests)
• Concurrent access (5 tests)
• Unicode & binary data (4 tests)
• Large key/value handling (8 tests)

LMDB (Memory-Mapped Persistent)

B+tree based storage with memory-mapped I/O (via heed crate). Optimized for read-heavy workloads with MVCC (Multi-Version Concurrency Control). Tested with 31 comprehensive tests.

# Cargo.toml - Enable LMDB backend
[dependencies]
storage = { version = "0.1.12", features = ["lmdb-backend"] }

use storage::{QuadStore, LmdbBackend};

// Create persistent database (default 10GB map size)
let backend = LmdbBackend::new("/path/to/data")?;
let store = QuadStore::new(backend);

// Or with custom map size (1GB)
let backend = LmdbBackend::with_map_size("/path/to/data", 1024 * 1024 * 1024)?;

// Features:
// - Memory-mapped I/O (zero-copy reads)
// - MVCC for concurrent readers
// - Crash-safe ACID transactions
// - Range & prefix scanning
// - Excellent for read-heavy workloads

// Sync to disk
store.flush()?;

When to use LMDB vs RocksDB:

LMDB Test Coverage:

• Basic CRUD operations (8 tests)
• Range scanning (4 tests)
• Prefix scanning (3 tests)
• Batch operations (3 tests)
• Large key/value handling (4 tests)
• Concurrent access (4 tests)
• Statistics & flush (3 tests)
• Edge cases (2 tests)

TypeScript SDK

The npm package uses the in-memory backend—ideal for:

• Knowledge graph queries
• SPARQL execution
• Data transformation pipelines
• Embedded applications

import { GraphDB } from 'rust-kgdb'

// In-memory database (default, no configuration needed)
const db = new GraphDB('http://example.org/app')

// For persistence, export via CONSTRUCT:
const ntriples = db.queryConstruct('CONSTRUCT { ?s ?p ?o } WHERE { ?s ?p ?o }')
fs.writeFileSync('backup.nt', ntriples)

Installation

npm install rust-kgdb

Platform Support (v0.2.1)

This release (v0.2.1) includes pre-built binary for macOS x64 only. Other platforms will be added in the next release.

Quick Start

Complete Working Example

import { GraphDB } from 'rust-kgdb'

// 1. Create database
const db = new GraphDB('http://example.org/myapp')

// 2. Load data (Turtle format)
db.loadTtl(`
  @prefix foaf: <http://xmlns.com/foaf/0.1/> .
  @prefix ex: <http://example.org/> .

  ex:alice a foaf:Person ;
           foaf:name "Alice" ;
           foaf:age 30 ;
           foaf:knows ex:bob, ex:charlie .

  ex:bob a foaf:Person ;
         foaf:name "Bob" ;
         foaf:age 25 ;
         foaf:knows ex:charlie .

  ex:charlie a foaf:Person ;
             foaf:name "Charlie" ;
             foaf:age 35 .
`, null)

// 3. Query: Find friends-of-friends (WCOJ optimized!)
const fof = db.querySelect(`
  PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  PREFIX ex: <http://example.org/>

  SELECT ?person ?friend ?fof WHERE {
    ?person foaf:knows ?friend .
    ?friend foaf:knows ?fof .
    FILTER(?person != ?fof)
  }
`)
console.log('Friends of Friends:', fof)
// [{ person: 'ex:alice', friend: 'ex:bob', fof: 'ex:charlie' }]

// 4. Aggregation: Average age
const stats = db.querySelect(`
  PREFIX foaf: <http://xmlns.com/foaf/0.1/>

  SELECT (COUNT(?p) AS ?count) (AVG(?age) AS ?avgAge) WHERE {
    ?p a foaf:Person ; foaf:age ?age .
  }
`)
console.log('Stats:', stats)
// [{ count: '3', avgAge: '30.0' }]

// 5. ASK query
const hasAlice = db.queryAsk(`
  PREFIX ex: <http://example.org/>
  ASK { ex:alice a <http://xmlns.com/foaf/0.1/Person> }
`)
console.log('Has Alice?', hasAlice)  // true

// 6. CONSTRUCT query
const graph = db.queryConstruct(`
  PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  PREFIX ex: <http://example.org/>

  CONSTRUCT { ?p foaf:knows ?f }
  WHERE { ?p foaf:knows ?f }
`)
console.log('Extracted graph:', graph)

// 7. Count and cleanup
console.log('Triple count:', db.count())  // 11
db.clear()

Save to File

import { writeFileSync } from 'fs'

// Save as N-Triples
const db = new GraphDB('http://example.org/export')
db.loadTtl(`<http://example.org/s> <http://example.org/p> "value" .`, null)

const ntriples = db.queryConstruct(`CONSTRUCT { ?s ?p ?o } WHERE { ?s ?p ?o }`)
writeFileSync('output.nt', ntriples)

SPARQL 1.1 Features (100% W3C Compliant)

Query Forms

// SELECT - return bindings
db.querySelect('SELECT ?s ?p ?o WHERE { ?s ?p ?o } LIMIT 10')

// ASK - boolean existence check
db.queryAsk('ASK { <http://example.org/x> ?p ?o }')

// CONSTRUCT - build new graph
db.queryConstruct('CONSTRUCT { ?s <http://new/prop> ?o } WHERE { ?s ?p ?o }')

Aggregates

db.querySelect(`
  SELECT ?type (COUNT(*) AS ?count) (AVG(?value) AS ?avg)
  WHERE { ?s a ?type ; <http://ex/value> ?value }
  GROUP BY ?type
  HAVING (COUNT(*) > 5)
  ORDER BY DESC(?count)
`)

Property Paths

// Transitive closure (rdfs:subClassOf*)
db.querySelect('SELECT ?class WHERE { ?class rdfs:subClassOf* <http://top/Class> }')

// Alternative paths
db.querySelect('SELECT ?name WHERE { ?x (foaf:name|rdfs:label) ?name }')

// Sequence paths
db.querySelect('SELECT ?grandparent WHERE { ?x foaf:parent/foaf:parent ?grandparent }')

Named Graphs

// Load into named graph
db.loadTtl('<http://s> <http://p> "o" .', 'http://example.org/graph1')

// Query specific graph
db.querySelect(`
  SELECT ?s ?p ?o WHERE {
    GRAPH <http://example.org/graph1> { ?s ?p ?o }
  }
`)

UPDATE Operations

// INSERT DATA - Add new triples
db.updateInsert(`
  PREFIX ex: <http://example.org/>
  PREFIX foaf: <http://xmlns.com/foaf/0.1/>

  INSERT DATA {
    ex:david a foaf:Person ;
             foaf:name "David" ;
             foaf:age 28 ;
             foaf:email "david@example.org" .

    ex:project1 ex:hasLead ex:david ;
                ex:budget 50000 ;
                ex:status "active" .
  }
`)

// Verify insert
const count = db.count()
console.log(`Total triples after insert: ${count}`)

// DELETE WHERE - Remove matching triples
db.updateDelete(`
  PREFIX ex: <http://example.org/>
  DELETE WHERE { ?s ex:status "completed" }
`)

Bulk Data Loading Example

import { GraphDB } from 'rust-kgdb'
import { readFileSync } from 'fs'

const db = new GraphDB('http://example.org/bulk-load')

// Load Turtle file
const ttlData = readFileSync('data/knowledge-graph.ttl', 'utf-8')
db.loadTtl(ttlData, null)  // null = default graph

// Load into named graph
const orgData = readFileSync('data/organization.ttl', 'utf-8')
db.loadTtl(orgData, 'http://example.org/graphs/org')

// Load N-Triples format
const ntData = readFileSync('data/triples.nt', 'utf-8')
db.loadNTriples(ntData, null)

console.log(`Loaded ${db.count()} triples`)

// Query across all graphs
const results = db.querySelect(`
  SELECT ?g (COUNT(*) AS ?count) WHERE {
    GRAPH ?g { ?s ?p ?o }
  }
  GROUP BY ?g
`)
console.log('Triples per graph:', results)

Sample Application

Knowledge Graph Demo

A complete, production-ready sample application demonstrating enterprise knowledge graph capabilities is available in the repository.

Location: examples/knowledge-graph-demo/

Features Demonstrated:

• Complete organizational knowledge graph (employees, departments, projects, skills)
• SPARQL SELECT queries with star and chain patterns (WCOJ-optimized)
• Aggregations (COUNT, AVG, GROUP BY, HAVING)
• Property paths for transitive closure (organizational hierarchy)
• SPARQL ASK and CONSTRUCT queries
• Named graphs for multi-tenant data isolation
• Data export to Turtle format

Run the Demo:

cd examples/knowledge-graph-demo
npm install
npm start

Sample Output:

The demo creates a realistic knowledge graph with:

• 5 employees across 4 departments
• 13 technical and soft skills
• 2 software projects
• Reporting hierarchies and salary data
• Named graph for sensitive compensation data

Example Query from Demo (finds all direct and indirect reports):

const pathQuery = `
  PREFIX ex: <http://example.org/>
  PREFIX foaf: <http://xmlns.com/foaf/0.1/>

  SELECT ?employee ?name WHERE {
    ?employee ex:reportsTo+ ex:alice .  # Transitive closure
    ?employee foaf:name ?name .
  }
  ORDER BY ?name
`
const results = db.querySelect(pathQuery)

Learn More: See the demo README for full documentation, query examples, and how to customize the knowledge graph.

API Reference

GraphDB Class

class GraphDB {
  constructor(baseUri: string)           // Create with base URI
  static inMemory(): GraphDB             // Create anonymous in-memory DB

  // Data Loading
  loadTtl(data: string, graph: string | null): void
  loadNTriples(data: string, graph: string | null): void

  // SPARQL Queries (WCOJ-optimized)
  querySelect(sparql: string): Array<Record<string, string>>
  queryAsk(sparql: string): boolean
  queryConstruct(sparql: string): string  // Returns N-Triples

  // SPARQL Updates
  updateInsert(sparql: string): void
  updateDelete(sparql: string): void

  // Database Operations
  count(): number
  clear(): void
  getVersion(): string
}

Node Class

class Node {
  static iri(uri: string): Node
  static literal(value: string): Node
  static langLiteral(value: string, lang: string): Node
  static typedLiteral(value: string, datatype: string): Node
  static integer(value: number): Node
  static boolean(value: boolean): Node
  static blank(id: string): Node
}

Performance Characteristics

Complexity Analysis

Memory Layout

Triple: 24 bytes
├── Subject:   8 bytes (dictionary ID)
├── Predicate: 8 bytes (dictionary ID)
└── Object:    8 bytes (dictionary ID)

String Interning: All URIs/literals stored once in Dictionary
Index Overhead: ~4x base triple size (4 indexes)
Total: ~120 bytes/triple including indexes

Performance Benchmarks

By Deployment Mode

*Aggregate throughput across all executors with HDRF partitioning

SIMD + PGO Query Performance (LUBM Benchmark)

Average: 44.5% speedup with zero code changes (compiler optimizations only).

Version History

v0.2.2 (2025-12-08) - Enhanced Documentation

• Added comprehensive INSERT DATA examples with PREFIX syntax
• Added bulk data loading example with named graphs
• Enhanced SPARQL UPDATE section with real-world patterns
• Improved documentation for data import workflows

v0.2.1 (2025-12-08) - npm Platform Fix

• Fixed native module loading for platform-specific binaries
• This release includes pre-built binary for macOS x64 only
• Other platforms coming in next release

v0.2.0 (2025-12-08) - Distributed Cluster Support

• NEW: Distributed cluster architecture with HDRF partitioning
• Subject-Hash Filter for accurate COUNT deduplication across replicas
• Arrow-powered OLAP query path for high-performance analytical queries
• Coordinator-Executor pattern with gRPC communication
• 9-partition default for optimal data distribution
• Contact for cluster deployment: gonnect.uk@gmail.com
• Coming soon: Embedding support for semantic search (v0.3.0)

v0.1.12 (2025-12-01) - LMDB Backend Release

• LMDB storage backend fully implemented (31 tests passing)
• Memory-mapped I/O for optimal read performance
• MVCC concurrency for unlimited concurrent readers
• Complete LMDB vs RocksDB comparison documentation
• Sample application with 87 triples demonstrating all features

v0.1.9 (2025-12-01) - SIMD + PGO Release

• 44.5% average speedup via SIMD + PGO compiler optimizations
• WCOJ execution with LeapFrog TrieJoin
• Release automation infrastructure
• All packages updated to gonnect-uk namespace

v0.1.8 (2025-12-01) - WCOJ Execution

• WCOJ execution path activated
• Variable ordering analysis for optimal joins
• 577 tests passing

v0.1.7 (2025-11-30)

• Query optimizer with automatic strategy selection
• WCOJ algorithm integration (planning phase)

v0.1.3 (2025-11-18)

• Initial TypeScript SDK
• 100% W3C SPARQL 1.1 compliance
• 100% W3C RDF 1.2 compliance

Use Cases

Links

• GitHub Repository
• Documentation
• CHANGELOG
• W3C SPARQL 1.1
• W3C RDF 1.2

License

Apache License 2.0

Built with Rust + NAPI-RS