Querying knowledge bases is one of the most important and fundamental tasks in knowledge representation. Although much of the work on querying knowledge bases is focused on conjunctive queries, there is often the need to use a simple form of recursion, such as the one provided by regular path queries (RPQ), which ask for paths defined by a given regular language. Conjunctive RPQs (CRPQs) can then be understood as the generalization of conjunctive queries with this form of recursion. CRPQs are part of SPARQL, the W3C standard for querying RDF data, including well known knowledge bases such as DBpedia and Wikidata. In particular, RPQs are quite popular for querying Wikidata. They are used in over 24% of the queries (and over 38% of the unique queries), according to recent studies (Malyshev et al., 2018; Bonifati et al., 2019). More generally, CRPQs are basic building blocks for querying graph-structured databases (Barceló, 2013). As knowledge bases become larger, reasoning about queries (e.g. for optimization) becomes increasingly important.