In the current big data era, in which we are overloaded with huge amounts of data, there is a large demand for alternatives to traditional querying systems. In our context, big data refers to the petabyte scale data analysis to which industry and academia are ex- posed today; and, where hundreds or thousands of machines, running in parallel, are required to finish computations in a reasonable amount of time. However, the current data landscape also has a complex and non-traditional structure, which typically fits well into the graph model. In semi-structured data, the traditional relational query languages fall short. Hence, we consider the conjunctive regular path queries (CRPQs); a simple, but reasonably expressive language for querying graph data. This thesis is about the eval- uation of CRPQs in MapReduce, a framework that provides a programming abstraction that enables the design of algorithms that can be executed automatically on a cluster of machines in a fault-tolera