Relative expressive power of navigational querying on graphs

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

25 Citaten (Scopus)
254 Downloads (Pure)


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; and the diversity relation. All these operators map binary relations to binary relations. We compare the expressive power of all resulting languages. We do this not only for general path queries (queries where the result may be any binary relation) but also for boolean or yes/no queries (expressed by the nonemptiness of an expression). For both cases, we present the complete Hasse diagram of relative expressiveness. In particular the Hasse diagram for boolean queries contains some nontrivial separations and a few surprising collapses. Keywords: Graph databases; Query languages; Expressive power
Originele taal-2Engels
Pagina's (van-tot)390-406
TijdschriftInformation Sciences
StatusGepubliceerd - 2015


Duik in de onderzoeksthema's van 'Relative expressive power of navigational querying on graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit