datalog_ir

Intermediate Representation (IR) types for Datalog query plans.

This library provides a canonical IR definition for representing Datalog query execution plans, suitable for use in query optimizers and execution engines.

Features

IRNode - Query plan operators (Scan, Map, Filter, Join, Distinct, Union)
Predicate - Filter conditions with support for comparisons and logical operators
Schema tracking - Automatic schema propagation through the query tree
Predicate utilities - Column reference tracking, simplification, and projection adjustment

Installation

Add this to your Cargo.toml:

[dependencies]
datalog_ir = "0.1"

Quick Start

use datalog_ir::{IRNode, Predicate};

// Create a scan of the "edge" relation
let scan = IRNode::Scan {
    relation: "edge".to_string(),
    schema: vec!["x".to_string(), "y".to_string()],
};

// Add a filter: x > 5
let filtered = IRNode::Filter {
    input: Box::new(scan),
    predicate: Predicate::ColumnGtConst(0, 5),
};

// Project to just the "y" column
let projected = IRNode::Map {
    input: Box::new(filtered),
    projection: vec![1],
    output_schema: vec!["y".to_string()],
};

// Get the output schema
assert_eq!(projected.output_schema(), vec!["y"]);

// Pretty print for debugging
println!("{}", projected.pretty_print(0));

IR Node Types

Node	Description
`Scan`	Read from a relation (EDB or IDB)
`Map`	Project/transform columns
`Filter`	Select rows matching a predicate
`Join`	Multi-column equi-join of two inputs
`Distinct`	Remove duplicate rows
`Union`	Combine multiple inputs

Predicate Types

Predicate	Description
`ColumnEqConst`	Column equals constant
`ColumnNeConst`	Column not equals constant
`ColumnGtConst`	Column greater than constant
`ColumnLtConst`	Column less than constant
`ColumnGeConst`	Column greater or equal
`ColumnLeConst`	Column less or equal
`ColumnsEq`	Two columns are equal
`ColumnsNe`	Two columns are not equal
`And`	Logical AND
`Or`	Logical OR
`True`	Always true (optimization)
`False`	Always false (optimization)

Example: Building a Join Query

use datalog_ir::IRNode;

// Scan two relations
let edges = IRNode::Scan {
    relation: "edge".to_string(),
    schema: vec!["a".to_string(), "b".to_string()],
};

let nodes = IRNode::Scan {
    relation: "node".to_string(),
    schema: vec!["id".to_string(), "label".to_string()],
};

// Join edge.b = node.id
let joined = IRNode::Join {
    left: Box::new(edges),
    right: Box::new(nodes),
    left_keys: vec![1],   // edge.b
    right_keys: vec![0],  // node.id
    output_schema: vec![
        "a".to_string(),
        "b".to_string(),
        "id".to_string(),
        "label".to_string(),
    ],
};

Example: Predicate Manipulation

use datalog_ir::Predicate;

// Build a compound predicate: (x > 5) AND (y = z)
let predicate = Predicate::And(
    Box::new(Predicate::ColumnGtConst(0, 5)),
    Box::new(Predicate::ColumnsEq(1, 2)),
);

// Find referenced columns
let columns = predicate.referenced_columns();
assert!(columns.contains(&0));
assert!(columns.contains(&1));
assert!(columns.contains(&2));

// Simplify predicates with constant folding
let with_true = Predicate::And(
    Box::new(Predicate::True),
    Box::new(Predicate::ColumnGtConst(0, 5)),
);
let simplified = with_true.simplify();
assert_eq!(simplified, Predicate::ColumnGtConst(0, 5));

License

Licensed under either of:

Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

datalog_ir 0.1.2