sqlite-graph

The extension supports a subset of the Cypher query language for pattern matching and graph manipulation.

Common Operations:

• MATCH: Find patterns (nodes, relationships, or both).
• CREATE: Create nodes and relationships.
• MERGE: Ensure a pattern exists (create if missing).
• SET: Update properties or labels.
• DETACH DELETE: Delete a node and all its connected relationships.
• WHERE: Filter results based on properties or pattern existence.

-- Pattern matching
MATCH (a:Person)-[:KNOWS]->(b:Person) 
RETURN a.name, b.name;

-- Create nodes and relationships
CREATE (a:Person {name: 'Alice'}),
       (b:Person {name: 'Bob'}),
       (a)-[:KNOWS {since: 2020}]->(b);

-- Merge with lifecycle hooks
MERGE (n:Person {name: 'David'})
ON CREATE SET n.created = timestamp()
ON MATCH SET n.updated = timestamp();

-- Delete a node and its relationships
MATCH (n:Person {name: 'Old User'})
DETACH DELETE n;

The SQLite Graph Database Extension is a loadable extension that integrates graph capabilities into SQLite via the Virtual Table interface. It allows users to execute openCypher queries alongside standard SQL while maintaining SQLite's ACID properties.

Core Architecture Layers

1. SQLite Core: The host environment providing the Virtual Table interface.
2. Graph Extension Entry Point: Handles initialization (sqlite3_graph_init), registration of virtual tables, and SQL functions.
3. Virtual Table Manager: Bridges SQLite and the graph engine by implementing methods like graphCreate(), graphBestIndex(), graphOpen(), and graphFilter().
4. Cypher Query Engine: A multi-stage pipeline that processes openCypher queries:
   • Lexer/Parser: Tokenizes strings and builds an Abstract Syntax Tree (AST).
   • Logical Planner: Optimizes the query (e.g., predicate pushdown) and creates a logical plan.
   • Physical Planner: Selects execution strategies (e.g., index scans) and generates iterators.
   • Executor: Runs the physical plan and materializes results.
5. Graph Storage Layer: Manages in-memory data structures including hash tables for lookups, B-trees for property indexes, and adjacency lists for traversals.
6. Graph Algorithms: Provides built-in implementations for shortest path (Dijkstra, BFS), centrality (PageRank), and traversals (DFS, BFS).

The extension uses a hybrid storage model combining hash tables, adjacency lists, and B-trees to manage graph data:

Node and Edge Storage

• Nodes: Stored in a hash table for $O(1)$ lookup by ID, with a linked list to allow for iteration.
• Edges: Stored in hash tables with adjacency lists to facilitate graph traversal. The system maintains both node_outgoing (edges leaving a node) and node_incoming (edges entering a node) lists.

Indexing

• Label Index: A B-tree mapping labels to lists of node IDs, optimized for MATCH (n:Label) queries.
• Property Index: A B-tree mapping (property_key, property_value) pairs to lists of node/edge IDs. These are created automatically for frequently accessed properties.

Property Storage

Properties are stored as JSON strings using SQLite's native JSON functions. This allows for:

• Flexible schemas.
• Complex nested data structures.
• Efficient serialization/deserialization.

When a Cypher query is executed, it passes through a structured pipeline to transform high-level syntax into low-level data retrieval:

Example Pipeline for: MATCH (p:Person {age: 30}) RETURN p.name

1. Lexer: Converts the query string into a stream of tokens (e.g., MATCH, LPAREN, IDENT("p")).
2. Parser: Consumes tokens to build an Abstract Syntax Tree (AST) representing the query structure.
3. Logical Planner: Analyzes the AST to create an optimized logical plan. For the example above, it might decide to use a label index for Person and push down the age=30 filter.
4. Physical Planner: Translates the logical plan into specific execution strategies, such as IndexScan $\rightarrow$ FilterIterator $\rightarrow$ ProjectIterator.
5. Executor: Executes the iterators, applying filters and projecting properties to produce the final result set.
6. Virtual Table Interface: The results are handed back to SQLite via standard virtual table methods like graphOpen(), graphFilter(), and graphNext().

1. Lexer
   Input: "MATCH (p:Person {age: 30}) RETURN p.name"
   Output: [MATCH, LPAREN, IDENT("p"), COLON, IDENT("Person"), ...]

2. Parser
   Input: Token stream
   Output: AST with MATCH clause, pattern, RETURN clause

3. Logical Planner
   - Identify pattern: node with label "Person" and property filter
   - Optimization: use label index for "Person"
   - Optimization: push down property filter
   - Generate logical plan: LabelScan(Person) -> Filter(age=30) -> Return(name)

4. Physical Planner
   - Choose index scan strategy
   - Generate iterators: IndexScan -> FilterIterator -> ProjectIterator

5. Executor
   - Open index scan on "Person" label
   - For each matching node:
     - Apply filter: age = 30
     - Project property: name
   - Add to result set
   - Return results to SQLite

6. Virtual Table Interface
   - SQLite calls graphOpen() to create cursor
   - SQLite calls graphFilter() to start iteration
   - SQLite calls graphNext() for each row
   - Results returned via graphColumn()