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

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

Query languages
Algebra
Data structures
Chemical analysis

Keywords

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

Cite this

Hellings, Jelle ; Gyssens, Marc ; Wu, Yuqing ; van Gucht, Dirk ; van den Bussche, Jan ; Vansummeren, Stijn ; Fletcher, George H.L. / Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees. In: Information Systems. 2020 ; Vol. 89.
@article{1722f68f760942d6891bf300b97c6299,
title = "Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees",
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.",
keywords = "Boolean queries, Downward query language fragments, Path queries, Relational calculus with transitive closure, Relative expressive power, Tree data model",
author = "Jelle Hellings and Marc Gyssens and Yuqing Wu and {van Gucht}, Dirk and {van den Bussche}, Jan and Stijn Vansummeren and Fletcher, {George H.L.}",
year = "2020",
month = "3",
doi = "10.1016/j.is.2019.101467",
language = "English",
volume = "89",
journal = "Information Systems",
issn = "0306-4379",
publisher = "Elsevier",

}

Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees. / Hellings, Jelle; Gyssens, Marc (Corresponding author); Wu, Yuqing; van Gucht, Dirk; van den Bussche, Jan; Vansummeren, Stijn; Fletcher, George H.L.

In: Information Systems, Vol. 89, 101467, 03.2020.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Hellings, Jelle

AU - Gyssens, Marc

AU - Wu, Yuqing

AU - van Gucht, Dirk

AU - van den Bussche, Jan

AU - Vansummeren, Stijn

AU - Fletcher, George H.L.

PY - 2020/3

Y1 - 2020/3

N2 - 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.

AB - 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.

KW - Boolean queries

KW - Downward query language fragments

KW - Path queries

KW - Relational calculus with transitive closure

KW - Relative expressive power

KW - Tree data model

UR - http://www.scopus.com/inward/record.url?scp=85074827543&partnerID=8YFLogxK

U2 - 10.1016/j.is.2019.101467

DO - 10.1016/j.is.2019.101467

M3 - Article

AN - SCOPUS:85074827543

VL - 89

JO - Information Systems

JF - Information Systems

SN - 0306-4379

M1 - 101467

ER -