In order to facilitate the requesting of desired information from a graph database that stores a graph, a system may translate an initial query into a query that can be executed against the graph database. In particular, using primitives, the system may translate a query associated with a type of database (such as a relational database) into the query. The graph may include nodes, edges between the nodes, and predicates to represent and store data with index-free adjacency. Moreover, the primitives may include: a rule based on edges in the graph that expresses a relational schema in the type of database, and information associated with a compound key that specifies a relationship between nodes, edges and predicates in the graph corresponding to a table in the type of database. Then, the system may execute the query against the graph database, and may receive a result that includes a subset of the graph.