KEY-BASED DELETION ANOMALIES IN RELATIONAL
DATABASES

MILLIST W. VINCENT
School of Computer and Information Science, University of South Australia, Adelaide 5095

1. INTRODUCTION

Although normalisation [1, 2] is one of the oldest topics in relational database theory and several normal forms have been defined [1-6], most of these works in which normal forms were defined emphasised the syntactic properties of the normal forms and didn't provide any justification for their use. By this, we mean that the normal form conditions were not formally shown to be either necessary or sufficient conditions for ensuring desirable processing properties in relations. In the case where the only constraints are functional dependencies (FDs), other researchers [5, 7-13] have provided a formal justification for normal forms [2] but, apart from some older work by Fagin [5, 10] and our own recent work [14-16], little work has been done on the justification of normal forms when the types of constraints permitted are generalised to include multivalued dependencies (MVDs). The purpose of this paper is to further the investigation of this issue.
The approach used in this paper to justifying the use of normalisation is based on the key-based interpretation, due to Fagin [5, 10], which we now briefly describe. According to Fagin, a relation scheme has a key-based update anomaly if an update to a legal relation (satisfies the constraints) defined over the scheme results in a new relation that satisfies key uniqueness, i.e. no two tuples in the relation have the same value for