Correspondence:
[**]
Corresponding author: Pierangela Samarati, DTI, Università degli Studi di Milano, Via Bramante 65, 26013 Crema, Italy. Tel.: +39 0373 898061; Fax: +39 0373 898074; E-mail: pierangela.samarati@unimi.it.
Note: [*] A preliminary version of this paper appeared under the title “Enforcing confidentiality and data visibility constraints: An OBDD approach”, in: Proceedings of the 25th Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy (DBSec 2011), Richmond, VA, USA, July 2011 [13].
Abstract: With the growing needs for data sharing and dissemination, privacy-preserving data publishing is becoming an important issue that still requires further investigation. In this paper, we make a step towards private data publication by proposing a solution based on the release of vertical views (fragments) over a relational table that satisfy confidentiality and visibility constraints expressing requirements for information protection and release, respectively. We translate the problem of computing a fragmentation composed of the minimum number of fragments into the problem of computing a maximum weighted clique over a fragmentation graph. The fragmentation graph models fragments, efficiently computed using Ordered Binary Decision Diagrams (OBDDs), that satisfy all the confidentiality constraints and a subset of the visibility constraints defined in the system. We then show an exact and a heuristic algorithm for computing a minimal and a locally minimal fragmentation, respectively. Finally, we provide experimental results comparing the execution time and the fragmentations returned by the exact and heuristic algorithms. The experiments show that the heuristic algorithm has low computation cost and computes a fragmentation close to optimum.
Keywords: Privacy, fragmentation, confidentiality and visibility constraints, OBDDs, maximum weighted clique
