Bruteforce methods for Tarski's relation relation algebra

One of the tools in our research on the expressive power of (fragments of) Tarski's relation algebra is a bruteforce tool. This tool can compute every possible query result one can obtain via queries expressed in a given query language and evaluated on a given graph. Using these computations, we can determine results on the expressive power for Boolean queries and path queries.

The first such tool was developed by Jan Van den Bussche, and was used to help with obtaining the results in

ICDT 2011
George H. L. Fletcher, Marc Gyssens, Dirk Leinders, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, Yuqing Wu. Relative expressive power of navigational querying on graphs. In: Proceedings of the 14th International Conference on Database Theory, pages 197-207. ACM, 2011. DOI: 10.1145/1938551.1938578.

The version I used for my PhD thesis and for several papers started as a clean reimplementation from scratch with the aim of making a high-performance bruteforce tool while, at the same time, playing around with the new features in C++11 (and later C++14).

I have developed two versions of the bruteforce tool, which are available for public use under the BSD-license (license details included in the source files):

The clean bruteforce program
A clean well-performing tool which was used during research.
The third bruteforce program
This versions uses MMX/SSE/AVX instructions to implement part of the bruteforce routines as high-performance Boolean matrix multiplication operations. This tool has not been used for research purposes, but was an interesting prototype. The Boolean matrix multiplication version outperforms the traditional relational version by an order of magnitude.

There is a set of notes. This note should give a clear idea of the basic working of the bruteforce technique to prove results on the expressive power. The note also describes some of the implementation details in the above two bruteforce programs These notes where originally planned to be part of another new version of the bruteforce program that improved on the programs above. Consequently, not all details in the note match the implementations above, but especially the part on Boolean matrix multiplication techniques can prove to be useful.

The bruteforce results in my thesis can be obtained by feedinf the clean bruteforce program the following script.