  The study of graph queries in database theory has spanned more than three
decades, resulting in a multitude of proposals for graph query languages. These
languages differ in the mechanisms. We can identify three main families of
languages, with the canonical representatives being: (1) regular path queries,
(2) walk logic, and (3) first-order logic with transitive closure operators.
This paper provides a complete picture of the expressive power of these
languages in the context of data graphs. Specifically, we consider a graph data
model that supports querying over both data and topology. For example, "Does
there exist a path between two different persons in a social network with the
same last name?". We also show that an extension of (1), augmented with
transitive closure operators, can unify the expressivity of (1)--(3) without
increasing the query evaluation complexity.
