< Back to previous page
Publication
Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees
Journal Contribution - Journal Article
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. (C) 2019 Elsevier Ltd. All rights reserved.
Journal: INFORMATION SYSTEMS
ISSN: 0306-4379
Volume: 89
Publication year:2020
Keywords:Tree data model, Relational calculus with transitive closure, Downward query language fragments, Path queries, Boolean queries, Relative expressive power
BOF-keylabel:yes
IOF-keylabel:yes
BOF-publication weight:1
CSS-citation score:2
Authors:International
Authors from:Higher Education
Accessibility:Open