rust-lang / datafrog

A lightweight Datalog engine in Rust
Apache License 2.0
796 stars 43 forks source link

Datalog query with leapjoin #51

Open kelped opened 4 months ago

kelped commented 4 months ago

Hey, I'm just playing around with datafrog and trying to translate some basic datalog queries to the equivalent Rust code. I am wondering what something like the following snippet looks like in datafrog?

node(1, 'A').
node(2, 'B').
node(3, 'C').
node(4, 'D').

edge(1, 2).
edge(2, 3).
edge(3, 1).
edge(1, 4).

depthTwo(W1, W2) :-
    page(T1, W1),
    page(T2, W2),
    link(T1, T2).

I'm mostly interested in leapjoin and have tried something like:

let mut iteration = Iteration::new();

let pages: Relation<_> = vec![
    (1, "super.com"),
    (2, "page.com"),
    (3, "subpage.com"),
    (4, "minpage.com"),
]
.into();
let edges: Relation<(u32, u32)> = vec![(1, 2), (2, 3), (3, 1), (1, 4)].into();
let edges_rev: Relation<_> = edges.iter().map(|&(from, to)| (to, from)).collect();

let var = iteration.variable::<(u32, &str)>("var");
var.insert(pages.clone());

while iteration.changed() {
    var.from_leapjoin(
        &var,
        // So I technically would like to filter by the edges
        // but the nodes i want to filter by are not really there yet?
        // And I can't extend with nodes and filter with the edges
        edges_rev.extend_with(|&(a, _)| a),
        //
        |&(a, b), &c| (a, b),
    );
}

But I can't quite wrap my head around how the leapers work even after reading the comment given in the source code of the repo. Any pointers would be appreciated!