An OBDD approach to enforce confidentiality and visibility constraints in data publishing*

• DOI: 10.3233/jcs-2012-0449
• Publication Date: 2016-05-18T07:44:05Z
• Authors: Valentina Ciriani; Sabrina De Capita...; Sara Foresti; Giovanni Livraga; Pierangela Samarati
• Keywords: confidentiality and visibility constraints; fragmentation; maximum weighted clique; OBDDs; Privacy; 0102 computer and information sciences; 01 natural sciences

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.