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.

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)

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

No compilation required—pre-built native binaries included.

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
db.updateInsert(`
  INSERT DATA { <http://ex/new> <http://ex/prop> "value" }
`)

// DELETE WHERE
db.updateDelete(`
  DELETE WHERE { ?s <http://ex/deprecated> ?o }
`)

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

Version History

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