Techniques for storing and querying graph data in a key-value store are provided. A graph statement (e.g., an RDF graph statement) includes a plurality of values, at least two of which correspond to nodes in a graph. A key is generated based on the graph statement. The key may be generated based on concatenating hash values that are generated based on the plurality of values. The key-value store stores the key. The value that corresponds to the key may be a null or empty value. In response to a graph query (e.g., in SPARQL) that includes one or more query patterns, each of which includes one or more values, a key is generated based on the one or more values and sent to the key-value store, which returns one or more other keys, each of which is a superset of the generated key.