Inference control of open relational queries under closed-world semantics based on theorem proving

摘要

Relational database systems may serve to evaluate an open query under closed-world semantics. The evaluation returns an explicit output relation complemented with an often implicit statement about the completeness of that relation. The output relation is formed from all those tuples that both fit the format and satisfy the properties expressed in the query. Using first-order logic for specifying formal semantics, the output relation can be seen as a set of (ground) sentences obtained from the query formula by suitable substitutions of free variables by constants. A statement about the completeness of a relation can also explicitly be formalized as a sentence of first-order logic. Inference control for enforcing a confidentiality policy has to inspect and to possibly distort not only the sentences representing the tuples of the output relation but also the completeness sentences. Previously designed and formally verified control procedures employ theorem-proving for such inspections while iteratively considering candidates for those sentences and determining termination conditions, respectively. In this article, we outline an implementation of these control procedures and treat improvements of their runtime efficiency, in particular to overcome shortcomings of the underlying theorem prover, which is repeatedly called with an input comprising a completeness sentence of increasing size. The improvements are obtained by an equivalent rewriting of completeness sentences, exploiting the active domain or introducing new constants for combinations of the original constants, respectively, as well as by optimizing the number of such calls. Besides theoretical complexity considerations, we also present practical evaluations for some examples. These examples include queries that without control would return the whole underlying database relations and with control can be used for confidentiality-preserving data publishing. (C) 2016 Elsevier Ltd. All rights reserved.