Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/25932

Title: On Tarski’s Relation Algebra: Querying trees and chains, and the semi-join algebra
Authors: Hellings, Jelle
Advisors: Gyssens, Marc
Van den Bussche, Jan
Kuijpers, Bart
Issue Date: 2018
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.
URI: http://hdl.handle.net/1942/25932
Category: T1
Type: Theses and Dissertations
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
-1.42 MBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.