ETD

• constraint systems
• differential privacy
• relational algebra

Differential privacy is a modern approach in privacy-preserving data analysis to control the amount of information that can be inferred about an individual by querying a database. The most common techniques are based on the introduction of probabilistic noise, often defined as a Laplacian parametric on the sensitivity of the query. In order to maximize the utility of the query, it is crucial to estimate the sensitivity as precisely as possible.
In this thesis relational algebra is considered, the classical language for queries in relational databases, and a method is proposed for computing a bound on the sensitivity of queries in an intuitive and compositional way. Constraint-based techniques are used to accumulate the information on the possible values for attributes provided by the various components of the query, thus making it possible to compute tight bounds on the sensitivity.