IEEE Transactions on Knowledge and Data Engineering · 1991 · 71 citations · 16 references
ComputingComputer ScienceAlgorithmsData ManagementDatabasesClassification SchemesDatabase DesignDatabase ManagementRelational AlgebraRelational Data ModelRelational DatabasesFunctional Dependency InferenceFunctional Dependency TheoryInformation Loss AnalysisMultivalued DependenciesNp-complete ProblemsNp-completenessRecord ClassificationRelational Database Systems
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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
16
The theory of relational databases
Michel Adiba · Science of Computer Programming · 1984 · 969 citations
Principles of Database Systems
John Kandiri · 2018 · 892 citations
Dependency Structures of Data Base Relationships.
William W. Armstrong · IFIP Congress · 1974 · 739 citations
On the Equivalence of Database Models
Y. Edmund Lien · Journal of the ACM · 1982 · 227 citations · Full text