Publishing Inference-Proof Relational Data: Design, Implementation, Optimization and Experiments

Talk by Prof. Joachim Biskup - Technische Universität Dortmund (Based on joint theoretical work with Lena Wiese and on joint practical work with Christine Dahn, Katharina Diekmann, Ralf Menzel, Dirk Schalge and Lena Wiese)

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. We have designed 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. Conceptually, the generation procedure performs a depth-first search for satisfying the constraints and follows a branch-and-bound strategy for minimizing distortions.

We briefly outline the basic view generation procedure, and then discuss various implemented optimization efforts. Among others, we present the design and experimental results of (i) exploiting sophisticated local lower bounds on the number of additional distortions in subtrees, (ii) coordinated parallelization for searching in many subtrees concurrently, and (iii) priority searching.

The talk will take place on Wednesday, April 25th at 13:15h-15:00h in room Alan Turing (00.09.038).