Budget tracking in a differentially private database system

A non-transitory computer-readable storage medium storing executable instructions that, when executed by a computer system, cause the computer system to perform steps comprising:

• receiving a request from a client device to perform a query of a private database system, the request associated with a level of differential privacy;
• accessing a privacy budget corresponding to the received request, the privacy budget including a cumulative privacy spend and a maximum privacy spend, wherein the cumulative privacy spend represents previous queries of the private database system;
• determining a privacy spend associated with the received request based at least in part on the level of differential privacy associated with the received request and on a sensitivity factor associated with the query, wherein the sensitivity factor is based on one or more relational operators included in the query, wherein the one or more relational operators include a ‘select’ relational operator;
• and
• in response to the sum of the cumulative privacy spend and the determined privacy spend being less than the maximum privacy spend:
• providing a set of results to the client device in response to the performed query;
• and
• updating the cumulative privacy spend by incrementing the cumulative privacy spend by an amount equal to the determined privacy spend.

A method comprising:

• receiving, by a privacy device, a request from a client device to perform a query of a private database system, the request associated with a level of differential privacy;
• accessing, by the privacy device, a privacy budget corresponding to the received request, the privacy budget including a cumulative privacy spend and a maximum privacy spend, wherein the cumulative privacy spend represents previous queries of the private database system;
• determining, by the privacy device, a privacy spend associated with the received request based at least in part on the level of differential privacy associated with the received request and on a sensitivity factor associated with the query, wherein the sensitivity factor is based on one or more relational operators included in the query, wherein the one or more relational operators include a ‘select’ relational operator;
• and
• in response to the sum of the cumulative privacy spend and the determined privacy spend being less than the maximum privacy spend:
• providing a set of results to the client device in response to the performed query;
• and
• updating the cumulative privacy spend by incrementing the cumulative privacy spend by an amount equal to the determined privacy spend.