In an example embodiment, data in a multi-tenant database is organized as a graph representing the relationships among all documents and tenants. Specifically, each document is represented as a node in the graph and each tenant also is represented as a node. The relationships between the documents themselves, or between a document and a graph, are then represented as edges in the graph. A list of tenants whose data should be marked for deletion (e.g., former customers who no longer have a relationship with the entity maintaining the database) may be maintained. Periodically (e.g., once a week), this list of tenants and the relationship graph are fed as input into a graph search algorithm that generates smaller relationship graphs comprised only of documents associated with those accounts.