A sound and complete model-generation procedure for consistent and confidentiality-preserving databases (Q549726)

The paper is devoted to the very important problem of ensuring sensitive data confidentiality while maintaining maximum availability of querying the permissible data. An algorithm is presented realizing a method called ``lying'' (additions and/or removal of database entries) based on definitions produced by a database administrator (initial database instance), a security administrator (secret data) and a user administrator (user's prior knowledge). The algorithm creates a new database instance that does not allow retrieval and/or inference of classified facts. This property is here called the inference-proofness. The second desirable property mentioned above is studied as well (called distortion minimality) using a cardinality-based distortion distance -- the choice of this measure and some other possibilities are discussed in detail. The paper forms a part of the work on controlled query evaluation (CQE) but differs from previous approaches in using the non-interactive setting. The presented algorithm named preCQE is used as a preprocessor and all querying is then performed with the resulting database instance. That has a great impact on the runtime performance of query answering. The algorithm is defined for a subset of first-order logic databases. It uses weakly acyclic constraints comprising tuple-generating dependencies accompanied by existential and denial formulas. All formulas are in the prenex literal normal form. The preCQE algorithm effectively implements a Branch-and-Bound end depth-first search approach. It treats violated constraints step by step. Quantified variables in such a constraint are handled from left to right by the order of their quantifiers. Relevant instantiations are determined. Whenever a ground atom is reached by such instantiations, addition or removal of this atom is tried. The detailed listing and discussion of the algorithm is given in the paper as well as the proofs of its termination, soundness and completeness. In the conclusion, the authors mention that a thorough complexity analysis of the algorithm is still to be performed, a preCQE implementation for propositional logic showed a good runtime performance, and a prototype system using a Oracle-SQL DBMS in connection with a Java interface is currently being implemented. More information and references to a series of related papers can be found, e.g., on \url{http://wiese.free.fr/}.