  We introduce injective semantics for Conjunctive Regular Path Queries
(CRPQs), and study their fundamental properties. We identify two such
semantics: atom-injective and query-injective semantics, both defined in terms
of injective homomorphisms. These semantics are natural generalizations of the
well-studied class of RPQs under simple-path semantics to the class of CRPQs.
We study their evaluation and containment problems, providing useful
characterizations for them, and we pinpoint the complexities of these problems.
Perhaps surprisingly, we show that containment for CRPQs becomes undecidable
for atom-injective semantics, and PSPACE-complete for query-injective
semantics, in contrast to the known EXPSPACE-completeness result for the
standard semantics. The techniques used differ significantly from the ones
known for the standard semantics, and new tools tailored to injective semantics
are needed. We complete the picture of complexity by investigating, for each
semantics, the containment problem for the main subclasses of CRPQs, namely
Conjunctive Queries and CRPQs with finite languages.
