A mechanism of updating query results for a graph linking data in a computer system is disclosed. Results of the query on the graph linking data are received along with a change to the graph. The change to the graph is determined to be localizable or relatively bounded. Based on the determination of the localizable or relatively bounded change to the graph, the results of the query are updated based on the change to the graph without determining updated results of the query over the graph. This is accomplished by discovering nodes that are affected by the change to the graph, updating data associated with the affected nodes, and applying the updated data to the results of the query.