  We introduce the class CXRPQ of conjunctive xregex path queries, which are
obtained from conjunctive regular path queries (CRPQs) by adding string
variables (also called backreferences) as found in practical implementations of
regular expressions. CXRPQs can be considered user-friendly, since they combine
two concepts that are well-established in practice: pattern-based graph queries
and regular expressions with backreferences. Due to the string variables,
CXRPQs can express inter-path dependencies, which are not expressible by CRPQs.
The evaluation complexity of CXRPQs, if not further restricted, is PSPACE-hard
in data-complexity. We identify three natural fragments with more acceptable
evaluation complexity: their data-complexity is in NL, while their combined
complexity varies between EXPSPACE, PSPACE and NP. In terms of expressive
power, we compare the CXRPQ-fragments with CRPQs and unions of CRPQs, and with
extended conjunctive regular path queries (ECRPQs) and unions of ECRPQs.
