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. | Document URI: | http://hdl.handle.net/1942/25932 | Category: | T1 | Type: | Theses and Dissertations |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
thesis.pdf | 1.42 MB | Adobe PDF | View/Open |
Page view(s)
208
checked on Sep 7, 2022
Download(s)
66
checked on Sep 7, 2022
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.