Skip to content
An incremental implementation of the Functional Aggregate Query (FAQ) framework in Differential Dataflow
Rust
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
examples
src
.gitignore
Cargo.lock
Cargo.toml
README.md

README.md

Differential Aggregate Query

An incremental implementation of the Functional Aggregate Query (FAQ) framework in Rust using Differential Dataflow.

This is a research project and currently does only provide a naive implementation of the insideOut algorithm to compute FAQ Queries.

Currently not concerned with optimal variable order.

Research

The FAQ framework is discussed in this paper FAQ: Questions Asked Frequently

Implementation

FAQ generalizes a bunch of different, on first glance unconnected problems by expressing them as aggregates over hypergraphs.

Factors are Differential Dataflow collections with generic datatype representing the input and output in listing format. That means every tuple in the collection has a support and a factor value. The factor value resides in the diff.

Currently we only support the SumProd semi-ring as differential dataflows join represents the product and consolidate the sum.

More semi-ring aggregates will be added by implementing the correct diff trait.

Running

cargo run --example graph will kick off a very small triangle counting computation expressed as a FAQ.

You can’t perform that action at this time.