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 | |
| Publication status | Published - 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
}
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 journal › Article › Academic › peer-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 -