1. A computer-implemented process for responding to graph queries, comprising: using a hardware computer comprising one or more processors and memory to perform the following process actions: receiving a graph query that is submitted to a graph database which is modeled by an attributed graph comprising a plurality of nodes each of which is labeled with one or more attributes, and a plurality of edges each of which is labeled with another one or more attributes, each of the nodes representing a different entity instance, each of the edges connecting a different pair of nodes, the attributes of each of the edges specifying the type of relationship that exists between the pair of nodes connected by the edge, the graph query comprising predicates based on one or more of, the topology of the attributed graph, or the attributes of the nodes and edges therein; decomposing the graph query into a plurality of query components; for each of the query components, identifying a one of a plurality of independent query execution engines that is available to process the query component, generating a sub-query that represents the query component, sending the sub-query to the identified query execution engine for processing, and receiving results for the sub-query from the identified query execution engine; and combining the results received to generate a response to the graph query.