  A graph database is a digraph whose arcs are labeled with symbols from a
fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are
labeled with regular expressions over the alphabet. RGPs model navigational
queries for graph databases called conjunctive regular path queries (CRPQs). A
match of a CRPQ in the database is witnessed by a special navigational
homomorphism of the corresponding RGP to the database. We study the complexity
of deciding the existence of a homomorphism between two RGPs. Such
homomorphisms model a strong type of containment between the two corresponding
CRPQs. We show that this problem can be solved by an EXPTIME algorithm (while
general query containmement in this context is EXPSPACE-complete). We also
study the problem for restricted RGPs over a unary alphabet, that arise from
some applications like XPath or SPARQL. For this case, homomorphism-based CRPQ
containment is in NP. We prove that certain interesting cases are in fact
polynomial-time solvable.
