Journal
INFORMATION SYSTEMS
Volume 70, Issue -, Pages 32-47Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.is.2016.07.008
Keywords
Active domain; Combined lying and refusal; Confidentiality policy; Completeness sentence; Data publishing; Diagonalization function; Inference control; Lying; Open query; Theorem proving
Categories
Funding
- Deutsche Forschungsgemeinschaft (German Research Council) [BI 311/12-2]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available