LA'n'EGG RPQ

Linear Algebra & E-Graphs for Regular Path Queries is a project focusing on applying equality saturation via E-graphs to optimize regular path queries evaluation expressed in terms of sparse linear algebra.

Dependencies

This project uses the following dependencies.

• Rust compiler (2021 edition).
• LAGraph and GraphBLAS libraries (packed as submodules in vendor/).

Building

Start from installing LAGraph using the QUICK START instructions from its repository.

You might not install LAGraph on a system level and simply use local build as a submodule by running.

git submodule update --init --recursive

To build the project itself after installing the dependencies, clone the repository and execute the following commands.

cargo build --release

The binary will be available in the target/release/ directory

Usage

Basically, the binary can be used as follows.

la-n-egg-rpq <path-to-graph-as-matrix-market-files> <queries-file>

To convert the graph, please, use our tools for converting them into the MatrixMarket format. You might start from one of the prepared datasets.

The queries should be expressed in the SPARQL format. They should use <query-number>,<Simplified SPARQL format>. Here is an example.

1,<Radosha_Ferioli> (<coauthor>)* ?obj
2,<Mikolas_Sirman> (<coauthor>)* ?obj
3,<Bruna_Nervis> (<coauthor>)* ?obj
4,<Amishi_Masgalas> (<coauthor>)* ?obj
5,<Socorro_Mcsorley> (<coauthor>)* ?obj

By default the binary executes randomly generated query plans for each query from the plan and printing best/worst/mean time for each query kind.

Authors

• Georgiy Belyanin (mail: belyaningeorge@ya.ru).
• Rodion Suvorov (mail: rodion.suvorov.94@mail.ru).
• Semyon Grigorev (mail: s.v.grigoriev@mail.spbu.ru).

Acknowledgments & copyright notices

LA'n'EGG RPQ is licensed under the Apache 2.0 License.

Thank you for you interest in the la-n-egg-rpq project.