Document Server@UHasselt >
Research >
Research publications >

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

Title: Relative expressive power of downward fragments of navigational query languages on trees and chains
Authors: Hellings, Jelle
Gyssens, Marc
Wu, Yuqing
Van Gucht, Dirk
Van den Bussche, Jan
Vansummeren, Stijn
Fletcher, George H. L.
Issue Date: 2015
Publisher: ACM
Citation: Cheney, James; Neumann, Thomas (Ed.). Proceedings of the 15th Symposium on Database Programming Languages, p. 59-68
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.
URI: http://hdl.handle.net/1942/21032
Link to publication: http://jhellings.nl/files/dbpl2015_paper.pdf
DOI: 10.1145/2815072.2815081
ISBN: 978-1-4503-3902-5
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version425.41 kBAdobe PDF
author version394.09 kBAdobe PDF

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