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
Relative expressive power of navigational querying on graphs. . (2011). In: Proceedings of the 14th International Conference on Database Theory, 197-207. ACM. DOI: 10.1145/1938551.1938578.
Relative expressive power of navigational querying on graphs. . (2015). In: Information Sciences, 298, 390-406. Elsevier. DOI: 10.1016/j.ins.2014.11.031.
Relative expressive power of navigational querying on graphs using transitive closure. . (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).
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.
Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees. . (2020). In: Information Systems, 89. Elsevier. DOI: 10.1016/j.is.2019.101467.
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.
The power of tarski's relation algebra on trees. . (2018). In: Foundations of Information and Knowledge Systems, 244-264. Springer. DOI: 10.1007/978-3-319-90050-6_14. author copy, slides.
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?
Relative expressive power of downward fragments of navigational query languages on trees and chains. . (2015). In: Proceedings of the 15th Symposium on Database Programming Languages, 59-68. ACM. DOI: 10.1145/2815072.2815081. author copy, slides.
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.
On tarski's relation algebra: Querying trees and chains and the semi-join algebra. . (2018). Hasselt University and transnational University of Limburg. Adviser: Marc Gyssens.
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.