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 feeding the clean bruteforce program the following script.
This project is related to the following publications and presentations
- PhD dissertation (dissertation, local version, defense slides, project page)
- On Tarski's Relation Algebra: querying trees and chains and the semi-join algebra. Hasselt University and transnational University of Limburg. Adviser: Marc Gyssens of the Databases and Theoretical Computer Science Research Group at Hasselt University.
- CJ 2020 (local version; see also: DBPL 2017)
- Jelle Hellings, Catherine L. Pilachowski, Dirk Van Gucht, Marc Gyssens, Yuqing Wu. From relation algebra to semi-join algebra: an approach for graph query optimization. In: The Computer Journal, Oxford University Press, 2020. DOI: doi:10.1093/comjnl/bxaa031
- IS 2019 (local version; see also: DBPL 2015)
- Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, George H. L. Fletcher. Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees. In: Information Systems, volume 89. Elsevier, 2019. DOI: doi:10.1016/j.is.2019.101467
- FoIKS 2018a (local version, slides, project page)
Jelle Hellings, Yuqing Wu, Marc Gyssens, Dirk Van Gucht. The power of Tarski's relation algebra on trees. In: 10th International Symposium on Foundations of Information and Knowledge Systems, pages 244--264. Springer, 2018. DOI: doi:10.1007/978-3-319-90050-6_14
- FoIKS 2018b (local version, slides; see also: AMAI 2019)
Jelle Hellings, Catherine L. Pilachowski, Dirk Van Gucht, Marc Gyssens, Yuqing Wu. From relation algebra to semi-join algebra: an approach for graph query optimization. In: Proceedings of the 16th International Symposium on Database Programming Languages, article 5. ACM, 2017. DOI: doi:10.1145/3122831.3122833
- DBPL 2015 (local version, slides)
Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, George H. L. Fletcher. Relative expressive power of downward fragments of navigational query languages on trees and chains. In: Proceedings of the 15th Symposium on Database Programming Languages, pages 59--68. ACM, 2015. DOI: doi:10.1145/2815072.2815081