In this paper, we propose a novel, exact border-based approach that provides an optimal solution for the hiding of sensitive frequent itemsets by (i) minimally extending the original database by a synthetically generated database part - the database extension, (ii) formulating the creation of the database extension as a constraint satisfaction prob- lem that is solved by using binary integer programming, and (iii) providing an approximate solution close to the optimal one when an ideal solution does not exist. Extending the original database for sensitive itemset hiding is proved to provide optimal solutions to an extended set of hiding prob- lems compared to previous approaches and to provide solu- tions of higher quality.