  Testing containment of queries is a fundamental reasoning task in knowledge
representation. We study here the containment problem for Conjunctive Regular
Path Queries (CRPQs), a navigational query language extensively used in
ontology and graph database querying. While it is known that containment of
CRPQs is expspace-complete in general, we focus here on severely restricted
fragments, which are known to be highly relevant in practice according to
several recent studies. We obtain a detailed overview of the complexity of the
containment problem, depending on the features used in the regular expressions
of the queries, with completeness results for np, pitwo, pspace or expspace.
