TY - JOUR
T1 - Relative expressive power of navigational querying on graphs using transitive closure
AU - Surinx, D.
AU - Fletcher, G.H.L.
AU - Gyssens, M.
AU - Leinders, D.
AU - Van den Bussche, J.
AU - Van Gucht, D.
AU - Vansummeren, S.
AU - Wu, Y.
PY - 2015
Y1 - 2015
N2 - Motivated by both established and new applications, we study navigational query languages for graphs (binary relations). The simplest language has only the two operators union and composition, together with the identity relation. We make more powerful languages by adding any of the following operators: intersection; set difference; projection; coprojection; converse; transitive closure; and the diversity relation. All these operators map binary relations to binary relations. We compare the expressive power of all resulting languages, both for binary-relation queries as well as for boolean queries. In the absence of transitive closure, a complete Hasse diagram of relative expressiveness has already been established [8]. Moreover, it has already been shown that for boolean queries over a single edge label, transitive closure does not add any expressive power when only projection and diversity may be present [11]. In the present article, we now complete the Hasse diagram in the presence of transitive closure, both for the case of a single edge label, as well as for the case of at least two edge labels.
The main technical results are the following:
(1) In contrast to the above-stated result [11] transitive closure does add expressive power when coprojection is present.
(2) Transitive closure also adds expressive power as soon as converse is present.
(3) Conversely, converse adds expressive power in the presence of transitive closure. In particular, the converse elimination result from [8] no longer works in the presence of transitive closure.
(4) As a corollary, we show that the converse elimination result from [8] necessitates an exponential blow-up in the degree of the expressions.
Keywords: Databases; relational algebra; query languages
AB - Motivated by both established and new applications, we study navigational query languages for graphs (binary relations). The simplest language has only the two operators union and composition, together with the identity relation. We make more powerful languages by adding any of the following operators: intersection; set difference; projection; coprojection; converse; transitive closure; and the diversity relation. All these operators map binary relations to binary relations. We compare the expressive power of all resulting languages, both for binary-relation queries as well as for boolean queries. In the absence of transitive closure, a complete Hasse diagram of relative expressiveness has already been established [8]. Moreover, it has already been shown that for boolean queries over a single edge label, transitive closure does not add any expressive power when only projection and diversity may be present [11]. In the present article, we now complete the Hasse diagram in the presence of transitive closure, both for the case of a single edge label, as well as for the case of at least two edge labels.
The main technical results are the following:
(1) In contrast to the above-stated result [11] transitive closure does add expressive power when coprojection is present.
(2) Transitive closure also adds expressive power as soon as converse is present.
(3) Conversely, converse adds expressive power in the presence of transitive closure. In particular, the converse elimination result from [8] no longer works in the presence of transitive closure.
(4) As a corollary, we show that the converse elimination result from [8] necessitates an exponential blow-up in the degree of the expressions.
Keywords: Databases; relational algebra; query languages
U2 - 10.1093/jigpal/jzv028
DO - 10.1093/jigpal/jzv028
M3 - Article
VL - 23
SP - 759
EP - 788
JO - Logic Journal of the IGPL
JF - Logic Journal of the IGPL
SN - 1367-0751
IS - 5
ER -