Publishing inference–proof relational data: An implementation and experiments

摘要

An agent might want to share information maintained by a relational database by means of data publishing, i.e., by generating a view customized for the further unrestricted usage by the anticipated clients. Often, however, the usability of the view has to be confined to ensure the confidentiality of particular pieces of information in need of being excluded from sharing. Previous work on Controlled Interaction Execution provides a sound and complete generation procedure for an inference–proof (i.e., consistent and confidentiality-preserving) view that has minimal distortion distance to the original database instance. Confidentiality is achieved regarding a policy declared in terms of first-order logic sentences to be kept hidden. Consistency ensures the compliance with postulated a priori knowledge of the clients, expressed as first-order logic sentences, too. The generation procedure has been designed to perform a depth-first search for satisfying the constraints and follows a branch-and-bound strategy for minimizing distortions. In this work we present an actual implementation of the generation procedure together with several optimizations. We exploit sophisticated local lower bounds on the number of additional distortions in subtrees to be explored to prune them early, and we employ coordinated parallelization for searching in many subtrees concurrently. Moreover, we describe an experimental evaluation in terms of runtime behavior. Finally, we also explore replacing depth-first searching by priority searching, exhibit special cases that can be handled more efficiently, present heuristics for only approximating distortion minimality, and discuss options of refined mechanisms to employ and invent constants to resolve current violations of constraints.