Data Dependencies and Inference Control in Multilevel Relational Database Systems

We investigate the inference problems due to functional dependencies (FD) and multi-valued dependencies (hND) in a multilevel relational database (MDB) with attribute and record classification schemes, respectively. For FDs, we show that, to prevent compromise, the security levels of attributes must be assigned by using the knowledge of functional dependencies. Under the assumption that all the attributes in the database have been assigned classification levels according to real world requirements, we first determine the set of functional dependencies to be taken into account. Then, we prove that changing the minimum number of attribute levels to prevent compromise is an NP-complete problem. However, assuming that the number of functional dependencies involved in inference is low, we give an exact algorithm to adjust the minimum number of attribute levels so that no compromise due to functional dependencies occurs. For NfVDs, we give a necessary and sufficient condition for compromise due to a single MVD, and then propose an algorithm to prevent single MVD inferences.