| dc.description.abstract | In relational database theory, a class of dependencies that includes functional dependencies (FDs), multivalued dependencies (MVDs), and join dependencies (JDs) has been found to play an important role in the process of designing relational database schemas. The utilization of this class of dependencies in schema design requires what are known as membership algorithms.
In a membership algorithm, usually a set of dependencies, say ?\Sigma?, is specified that includes either FDs (F), MVDs (M), JDs (J), or a combination of these dependencies - i.e., FUM, FUJ, MUJ, or FUMUJ. The algorithm then solves the implication of some additional dependencies from ?\Sigma?. The additional FDs inferred are denoted by F(?)F(\Sigma)F(?), the MVDs by M(?)M(\Sigma)M(?), and the JDs by J(?)J(\Sigma)J(?). For example, an MVD membership algorithm infers all M(?)M(\Sigma)M(?) from a given set ?\Sigma?, and an FD-MVD membership algorithm infers all F(?)F(\Sigma)F(?) and M(?)M(\Sigma)M(?).
There are also FD, JD, FD-JD, MVD-JD, and FD-MVD-JD membership algorithms. Two membership algorithms of the same type can also be different if their methodologies or the sets ?\Sigma? used are different.
This thesis presents altogether ten different membership algorithms. Among these algorithms, three are simpler than the existing similar algorithms and six of them are new. All the algorithms deal with FDs, total MVDs and total JDs only, but not with embedded MVDs and partial JDs. For convenience, total MVDs or total JDs are simply referred to as MVDs or JDs. Each of the algorithms uses a particular set of dependencies and infers certain additional dependencies. The details of these algorithms are shown in the following table:
[Table]
The correctness of the first three algorithms has been proved in this thesis. The fourth algorithm is presented for reasons more academic rather than any practical significance. Algorithms 5 and 7 are non-tableaux type and algorithms 6 and 8 are semi-tableaux type. As far as known to the author, until recently there has been only one algorithm that is referred to as the tableaux method or chase process for inferring a JD from a given set of dependencies. Very recently, a non-tableaux type algorithm has been proposed in the literature that infers an acyclic JD from a given FUMUJ. This algorithm is similar to the seventh algorithm.
The last two algorithms, i.e., ninth and tenth, are entirely new in the sense that there exist no similar algorithms in the literature. These two last algorithms are of semi-tableaux type.
Two new basic results have also been expounded in this thesis.
• The first basic result is with regard to representing a JD equivalently in two ways, referred to as ?-representation and ?-representation.
• The second basic result is about the concept of a branch-stem basis, which has helped in inferring all JDs.
These two new basic results, along with some other existing preliminary results, have enabled the development of the above ten membership algorithms. | |
