  Regular path queries (RPQ) is a classical navigational query formalism for
graph databases to specify constraints on labeled paths. Recently, RPQs have
been extended by Libkin and Vrgo$\rm \check{c}$ to incorporate data value
comparisons among different nodes on paths, called regular path queries with
data (RDPQ). It has been shown that the evaluation problem of RDPQs is
PSPACE-complete and NLOGSPACE-complete in data complexity. On the other hand,
the containment problem of RDPQs is in general undecidable. In this paper, we
propose a novel approach to extend regular path queries with data value
comparisons, called rigid regular path queries with data (RRDPQ). The main
ingredient of this approach is an automata model called nondeterministic rigid
register automata (NRRA), in which the data value comparisons are \emph{rigid},
in the sense that if the data value in the current position $x$ is compared to
a data value in some other position $y$, then by only using the labels (but not
data values), the position $y$ can be uniquely determined from $x$. We show
that NRRAs are robust in the sense that nondeterministic, deterministic and
two-way variant of NRRAs, as well as an extension of regular expressions, are
all of the same expressivity. We then argue that the expressive power of RDPQs
are reasonable by demonstrating that for every graph database, there is a
localized transformation of the graph database so that every RDPQ in the
original graph database can be turned into an equivalent RRDPQ over the
transformed one. Finally, we investigate the computational properties of RRDPQs
and conjunctive RRDPQs (CRRDPQ). In particular, we show that the containment of
CRRDPQs (and RRDPQs) can be decided in 2EXPSPACE.
