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

Jelle Hellings; Marc Gyssens; Yuqing Wu; Dirk van Gucht; Jan van den Bussche; Stijn Vansummeren; George H.L. Fletcher

doi:10.1016/j.is.2019.101467

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 journal › Article › Academic › peer-review

2 Citations (Scopus)

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 language	English
Article number	101467
Number of pages	16
Journal	Information Systems
Volume	89
DOIs	https://doi.org/10.1016/j.is.2019.101467
Publication status	Published - Mar 2020

Funding

Yuqing Wu carried out part of her work during a sabbatical visit to Hasselt University with a Senior Visiting Postdoctoral Fellowship of the Research Foundation Flanders (FWO).

Keywords

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

Access to Document

10.1016/j.is.2019.101467

Cite this

@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 = mar,

doi = "10.1016/j.is.2019.101467",

language = "English",

volume = "89",

journal = "Information Systems",

issn = "0306-4379",

publisher = "Elsevier",

}

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 - https://www.scopus.com/pages/publications/85074827543

U2 - 10.1016/j.is.2019.101467

DO - 10.1016/j.is.2019.101467

M3 - Article

AN - SCOPUS:85074827543

SN - 0306-4379

VL - 89

JO - Information Systems

JF - Information Systems

M1 - 101467

ER -

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

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this