Applications of graph databases are prone to inconsistency due to
interoperability issues. This raises the need for studying query answering over
inconsistent graph databases in a simple but general framework. We follow the
approach of consistent query answering (CQA), and study its data complexity
over graph databases for conjunctive regular-path queries (CRPQs) and
conjunctive regular-path constraints (CRPCs). We deal with subset, superset and
symmetric-difference repairs. Without restrictions, CQA is undecidable for the
semantics of superset- and symmetric-difference repairs, and Pi_2^P-complete
for subset-repairs. However, we identify restrictions on CRPCs and databases
that lead to decidability, and even tractability of CQA.