On Tarski’s Relation Algebra: Querying trees and chains, and the semi-join algebra

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. First, we study the expressive power the relation algebra when querying tree and chain structures. Next, we study the relationships between the expressive power of the relation algebra and the semi-join algebra. 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.