Decompositions of join dependencies in the relational database model

The decomposition of a relational database has been studied extensively during the last fifteen years. The reasons for decomposing a relation are obvious: smaller relations are easier to understand, independent data should not be stored in the same relation and in distributed databases, different components can be stored in different sites. The main tool for decomposing a relational database is the specification of semantic constraints. The study of these constraints has started about 1970 with the introduction of functional dependencies by Codd. Many other types were proposed afterwards. This work is mainly concerned with joint dependencies, since they are a necessary and sufficient condition for a relation to be decomposable. Moreover, many authors believe that the structure of a real-world database can be expressed by one join dependency and some functional dependencies. Unfortunately, the join-operator is very expensive. Therefore we devise an algorithm to decompose a join dependency into a set of smaller join dependencies as to make integrity checking more efficient. It is shown that this algorithm generates final non-redundant decompositions satisfying several favorable properties. As said before, a join dependency can be used to decompose a database. If this approach is followed, we need to check the consistency of the database after each update. Until recently it was believed that this could only be done efficiently for acyclic join dependencies and hence all research efforts were concentrated on how to modify the structure of a database so that it can be described by an acyclic join dependency. As an important side-effect of the decomposition algorithm mentioned above, a hierarchical classification of join dependencies is established according to their degree of cyclicity n, for which acyclicity corresponds to n = 2. It turns out that most problems concerning join dependencies remain tractable if the degree of cyclicity is restricted, but not necessarily to acyclicity. Hence the major conclusion is that in order to design the structure of a database, one must first decide which level of cyclicity one considers acceptable and then use only join dependencies whose degree of cyclicity does not supersede this level.