rust-lang / datafrog

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

Allow the output of a join to be filtered by an arbitrary predicate #37

Closed ecstatic-morse closed 3 years ago

ecstatic-morse commented 3 years ago

The purpose is to eliminate reflexive subset relations in Polonius. Currently, we do this by manually filtering the subset relation at each stage, but this is inefficient and makes things a bit harder to reason about. This change allows us to write the equivalent of the following rule.

subset(o1, o3, p) :-
    subset(o1, o2, p),
    subset(o2, o3, p),
    o1 != o3.

The signature for from_join_filtered is maximally expressive, allowing the user to inspect the shared key and both values when deciding whether to filter. I think this is good, but it's possible there's a more restrictive API that would achieve the same thing?

lqd commented 3 years ago

This is exactly what I had in mind when I added the hacky symmetry filtering to polonius: a way to filter_map the emitted tuples for these cases. So this looks good to me as well, and I personally don't mind the maximally expressive vs restricted API (but that's an interesting question indeed).

lqd commented 3 years ago

thanks a bunch!