Bruteforce Methods for Tarski's Relation Algebra

One of the tools in our research on the expressive power of (fragments of) Tarski's relation algebra is a our 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

  1. ICDT 2011.
    Relative expressive power of navigational querying on graphs. George H. L. Fletcher, Marc Gyssens, Dirk Leinders, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, and Yuqing Wu. (2011). In: Proceedings of the 14th International Conference on Database Theory, 197-207. ACM. DOI: 10.1145/1938551.1938578.
  2. IS 2015.
    Relative expressive power of navigational querying on graphs. George H.L. Fletcher, Marc Gyssens, Dirk Leinders, Dimitri Surinx, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, and Yuqing Wu. (2015). In: Information Sciences, 298, 390-406. Elsevier. DOI: 10.1016/j.ins.2014.11.031.
  3. LJIGPL 2015.
    Relative expressive power of navigational querying on graphs using transitive closure. Dimitri Surinx, George H. L. Fletcher, Marc Gyssens, Dirk Leinders, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, and Yuqing Wu. (2015). In: Logic Journal of the IGPL, 23(5), 759-788. Oxford University Press. DOI: 10.1093/jigpal/jzv028.

The version I used for my PhD thesis and for several papers started as a 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).

  1. The clean bruteforce tool. source code (.zip).
    A full implementation of a clean well-performing bruteforce tool which was used during research.
  2. The third bruteforce tool. source code (.zip).
    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 that describe the basic working of the bruteforce technique used in these bruteforce tools and how these techniques can be used to prove results on the expressive power of query languages. The note also describes some of the implementation details in the above two bruteforce tools. These notes where originally planned to be part of another new version of the bruteforce tool that improved on the tools 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 tool the following script.

Related Publications

  1. IS 2020.
    Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees. Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, and George H. L. Fletcher. (2020). In: Information Systems, 89. Elsevier. DOI: 10.1016/j.is.2019.101467.
    author copy, technical report.
    Abstract

    Motivated by the continuing interest in the tree data model, we study the expressive power of downward navigational query languages on trees and chains. Basic navigational queries are built from the identity relation and edge relations using composition and union. We study the effects on relative expressiveness when we add transitive closure, projections, coprojections, intersection, and difference; this for boolean queries and path queries on labeled and unlabeled structures. In all cases, we present the complete Hasse diagram. In particular, we establish, for each query language fragment that we study on trees, whether it is closed under difference and intersection.

  2. FoIKS 2018a.
    The power of tarski's relation algebra on trees. Jelle Hellings, Yuqing Wu, Marc Gyssens, and Dirk Van Gucht. (2018). In: Foundations of Information and Knowledge Systems, 244-264. Springer. DOI: 10.1007/978-3-319-90050-6_14. author copy, slides.
    Abstract

    Fragments of Tarski's relation algebra form the basis of many versatile graph and tree query languages including the regular path queries, XPath, and SPARQL. Surprisingly, however, a systematic study of the relative expressive power of relation algebra fragments on trees has not yet been undertaken. Our approach is to start from a basic fragment which only allows composition and union. We then study how the expressive power of the query language changes if we add diversity, converse, projections, coprojections, intersections, and/or difference, both for path queries and Boolean queries. For path queries, we found that adding intersection and difference yields more expressive power for some fragments, while adding one of the other operators always yields more expressive power. For Boolean queries, we obtain a similar picture for the relative expressive power, except for a few fragments where adding converse or projection yields no more expressive power. One challenging problem remains open, however, for both path and Boolean queries: does adding difference yields more expressive power to fragments containing at least diversity, coprojections, and intersection?

  3. DBPL 2015.
    Relative expressive power of downward fragments of navigational query languages on trees and chains. Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, and George H. L. Fletcher. (2015). In: Proceedings of the 15th Symposium on Database Programming Languages, 59-68. ACM. DOI: 10.1145/2815072.2815081. author copy, slides.
    Abstract

    Motivated by the continuing interest in the tree data model, we study the expressive power of downward fragments of navigational query languages on trees. The basic navigational query language we consider expresses queries by building binary relations from the edge relations and the identity relation, using composition and union. We study the effects on the expressive power when we add transitive closure, projections, coprojections, intersection, and difference. We study expressiveness at the level of boolean queries and path queries, on labeled and unlabeled trees, and on labeled and unlabeled chains. In all these cases, we are able to present the complete Hasse diagram of relative expressiveness. In particular, we were able to decide, for each fragment of the navigational query languages that we study, whether it is closed under difference and intersection when applied on trees.

  4. PhD thesis.
    On tarski's relation algebra: Querying trees and chains and the semi-join algebra. Jelle Hellings. (2018). Hasselt University and transnational University of Limburg. Adviser: Marc Gyssens.
    author copy, thesis, slides.
    Abstract

    Many practical query languages for graph data are based on fragments of Tarski's relation algebra which, optionally, is augmented with the Kleene-star operator. Examples include XPath, SPARQL, the RPQs, and GXPath. Because of this central role of (fragments of) the relation algebra, we study two aspects in more detail. Combined, these two studies give a detailed picture of the expressive power of the fragments of the relation algebra. Moreover, our results provide several opportunities for the development of new techniques for the efficient evaluation of graph queries.