Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees

Jelle Hellings, Marc Gyssens (Corresponding author), Yuqing Wu, Dirk van Gucht, Jan van den Bussche, Stijn Vansummeren, George H.L. Fletcher

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

Abstract

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.

Original languageEnglish
Article number101467
Number of pages16
JournalInformation Systems
Volume89
DOIs
Publication statusPublished - Mar 2020

    Fingerprint

Keywords

  • Boolean queries
  • Downward query language fragments
  • Path queries
  • Relational calculus with transitive closure
  • Relative expressive power
  • Tree data model

Cite this