Abstract

The transmission of own and partly confidential data to another agent comes along with the risk of enabling the receiver to infer information he is not entitled to learn. We consider a specific countermeasure against unwanted inferences about associations between data values whose combination of attributes are declared to be sensitive. This countermeasure fragments a relation instance into attribute-disjoint and duplicate-preserving projections such that no sensitive attribute combination is contained in any projection. Unfortunately, the intended goal of inference-proofness will not always be accomplished. Inferences might be based on combinatorial reasoning, since duplicate-preservation implies that the frequencies of value associations in visible fragments equals those in the original relation instance. In addition, the receiver might exploit entailment reasoning about functional dependencies, numerical dependencies and tuple-generating dependencies, as presumably known from the underlying database schema. We investigate possible interferences of combinatorial reasoning and entailment reasoning and identify basic conditions for a fragmentation to violate inference-proofness. Moreover, we outline a comprehensive method to effectively check the inference-proofness of a given fragmentation and we experimentally evaluate the computational efficiency of a partial prototype implementation.