search

rust-lang / datafrog

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

Datafrog does not support early termination #47

Closed Cypher1 closed 2 years ago

Cypher1 commented 2 years ago

It seems that the following assertions ensure that datafrog will not give partial results.

https://github.com/rust-lang/datafrog/blob/5455139ef26ee36acf229eb8abf45b1dfa453774/src/variable.rs#L307

This is often useful for completeness, but unproductive in real world situations where the are often unbounded numbers solutions to problems and 'good enough' is fine (e.g. estimation, path finding etc.).

Are patches accepted here? I'd like to add an incomplete method which would just be the 'complete' method without the assertions, and then replace the body of complete with just the assertions and the result of incomplete.

ecstatic-morse commented 2 years ago

@Cypher1 I'm happy to review patches.

The approach you described seems fine. A minor nit, "complete" is a verb in this context, which makes it incompatible with "incomplete".

Cypher1 commented 2 years ago

Thanks, inspect might be a better form. I think I might need some hand holding / information about the algorithm used before I can make progress, as I'm getting empty partial results (from .stable) until my test problem is fully solved.

Is there a) a canonical algorithm used in datafrog b) an easy [low effort for you] way to bring me up to speed?

ecstatic-morse commented 2 years ago

datafrog is a bottom-up, semi-naive solver that uses sorted data structures to hold the relations. Frank's blog post (linked on the README) has more information. Notably, stable is stored as a "leveled", sorted set, where each level is a) sorted and b) approximately twice as big as the previous level (kind of like an in-memory log-structured merge tree).

datafrog performs quite well, but it's not very user friendly. It does pretty much exactly what is needed for Polonius, nothing more. crepe or DDLog might be better choices if you are getting your feet wet with datalog programming.

Cypher1 commented 2 years ago

I'll read the blog post. I've played with crepe a little but hadn't found DDLog yet.

Thanks @ecstatic-morse for the help!

Cypher1 commented 2 years ago

Thanks @ecstatic-morse I'm mostly looking for a datalog engine for prototyping, looks like you're right and Crepe is a better fit for now. I'll close this for now but if I come back to datafrog will try to work out how to add this and submit a PR (as 'watching' partial results would be useful for our use case). Cheers