Relative Expressive Power of Navigational Querying on Graphs

Motivated by both established and new applications, the authors study navigational query languages for graphs (binary relations). The simplest language has only the two operators union and composition, together with the identity relation. They make more powerful languages by adding any of the following operators: intersection; set difference; projection; co-projection; converse; transitive closure; and the diversity relation. All these operators map binary relations to binary relations. They compare the expressive power of all resulting languages.