Techniques are described for generating and re-using reachability graphs for efficient execution of queries. In an embodiment, a query is received for execution on a data graph. Such a query may include one or more expressions for edges in the data graph, which when executed select one or more paths in the data graph to generate results for the query. The system uses a repository to store reachability graphs and may determine whether a reachability graph for an expression of the query for the data graph is stored in a repository. Such a reachability graph is generated by applying the expression on the data graph to qualify or disqualify the edges in the data graph to be included as part of edges of the reachability graph. For example, an edge in a reachability graph exists between two vertices when at least one edge of the data graph has qualified between two vertices of the data graph that correspond to the two vertices of the reachability graph. Based on determining that the reachability graph for the expression is stored in the repository, the system executes the query on the reachability graph without re-applying the expression on the data graph and generates the results for the query.