Controlling FD and MVD inferences in multilevel relational database systems

Author

Su, Tzong-An ; Ozsoyoglu, Gultekin

Author_Institution

Dept. of Comput. Sci. & Eng., Toledo Univ., OH, USA

Volume

3

Issue

4

fYear

1991

fDate

12/1/1991 12:00:00 AM

Firstpage

474

Lastpage

485

Abstract

The authors investigate the inference problems due to functional dependencies (FD) and multivalued dependencies (MVD) in a multilevel relational database (MDB) with attribute and record classification schemes, respectively. The set of functional dependencies to be taken into account in order to prevent FD-compromises is determined. It is proven that incurring minimum information loss to prevent compromises is an NP-complete problem. An exact algorithm to adjust the attribute levels so that no compromise due to functional dependencies occurs is given. Some necessary and sufficient conditions for MVD-compromises are presented. The set of MVDs to be taken into account for controlling inferences is determined. An algorithm to prevent MVD-compromises in a relation with conflict-free MVDs is given

Keywords

computational complexity; database theory; inference mechanisms; relational databases; FD inferences; FD-compromises; MVD inferences; MVD-compromises; NP-complete problem; attribute classification; conflict-free MVDs; exact algorithm; functional dependencies; minimum information loss; multilevel relational database; multivalued dependencies; necessary and sufficient conditions; record classification; Control systems; Data security; Database systems; Inference algorithms; Information security; NP-complete problem; National security; Relational databases; Remuneration; Sufficient conditions;

fLanguage

English

Journal_Title

Knowledge and Data Engineering, IEEE Transactions on

Publisher

ieee

ISSN

1041-4347

Type

jour

DOI

10.1109/69.109108

Filename

109108