The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs

G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, Y. Wu

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

13 Citaten (Scopus)
146 Downloads (Pure)

Samenvatting

Several established and novel applications motivate us to study the expressive power of navigational query languages on graphs, which represent binary relations. Our basic language has only the operators union and composition, together with the identity relation. Richer languages can be obtained by adding other features such as intersection, difference, projection and coprojection, converse, and the diversity relation. The expressive power of the languages thus obtained cannot only be evaluated at the level of path queries (queries returning binary relations), but also at the level of Boolean or yes/no queries (expressed by the nonemptiness of an expression). For the languages considered above, adding transitive closure augments the expressive power not only at the level of path queries but also at the level of Boolean queries, for the latter provided that multiple input relations are allowed. This is no longer true in the context of unlabeled graphs (i.e., in the case where there is only one input relation), however. In this paper, we prove that this is indeed not the case for the basic language to which none, one, or both of projection and the diversity relation are added, a surprising result given the limited expressive power of these languages. In combination with earlier work (Fletcher et al. 2011, 2012), this result yields a complete understanding of the impact of transitive closure on the languages under consideration. Keywords: Boolean query; Transitive closure; Relation algebra; Unlabeled graph; Expressiveness
Originele taal-2Engels
Pagina's (van-tot)167-203
TijdschriftAnnals of Mathematics and Artificial Intelligence
Volume73
Nummer van het tijdschrift1-2
DOI's
StatusGepubliceerd - 2015

Vingerafdruk

Duik in de onderzoeksthema's van 'The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit