  Privacy-preserving data splitting is a technique that aims to protect data
privacy by storing different fragments of data in different locations. In this
work we give a new combinatorial formulation to the data splitting problem. We
see the data splitting problem as a purely combinatorial problem, in which we
have to split data attributes into different fragments in a way that satisfies
certain combinatorial properties derived from processing and privacy
constraints. Using this formulation, we develop new combinatorial and algebraic
techniques to obtain solutions to the data splitting problem. We present an
algebraic method which builds an optimal data splitting solution by using
Gr\"{o}bner bases. Since this method is not efficient in general, we also
develop a greedy algorithm for finding solutions that are not necessarily
minimal sized.
