A graph database is described. The graph database includes one or more symbolic data stores and one or more key-value data stores. Each symbolic data store is configured to symbolically store sets of multiple hyper-graph nodes. Each key-value data store is configured to store attribute information for hyper-graph nodes and hyper-graph edges.