Computer Science Colloquium

Joachim Biskup
Technische Universität Dortmund

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

Fri 03.06.2016, 15:00, 90 minutes
S3 048, Informatikgebäude (Science Park 3)

Abstract

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. Within the framework of Controlled Interaction Execution, 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 have further provided an actual implementation of the generation procedure together with several optimizations. In particular, we exploited sophisticated local lower bounds on the number of additional distortions in subtrees to be explored to prune them early, and we employed coordinated parallelization for searching in many subtrees concurrently. Moreover, we have performed an experimental evaluation in terms of runtime behavior. Finally, we have also explored to replace depth-first searching by priority searching, exhibited special cases that can be handled more efficiently, considered heuristics for only approximating distortion minimality, and explored options of refined mechanisms to employ and invent constants to resolve current violations of constraints.

Bio

Joachim Biskup received his Diploma degree in mathematics from Technical University of Hannover and his Ph.D. in computer science from RWTH Aachen, Germany. He has been Professor of Computer Science at the University of Dortmund, University of Hildesheim and University of Dortmund again. He has performed research in recursion and complexity theory, information systems with an emphasis on schema design, query optimization and mediation, and various aspects of security, in particular access control and inference control

Invited by Prof. Dr. Klaus-Dieter Schewe, Institut für anwendungsorientierte Wissensverarbeitung

---

The Computer Science Colloquium is organized by the Department of Coputer Science at JKU, the Österreichische Gesellschaft für Informatik (ÖGI) and the Österreichische Computergesellschaft (OCG).

List of all talks