Research Of Schema Decomposition On α-Acycle In The Creation Relation Database

Due to the rapid development of computer technology, to some degree the storage problem of data has been solved. Large-scale and super large-scale databases of the magnanimity data that are widely used in the production field such as CIMS, GIS have presented. The type of the data become more and more complicated, such as the stream media, spacial data, temporal data etc. and many different type of data organization of database such as network, parallel and mobile have been put forward. Design and inquiry become the focus in database research as well as in application. Therefore at present the theory of acyclic database schema design has become a new important branch of database study.Combining the database and graph theory put the theory of acyclic database schema forward. Decomposition of database schema makes the design of database more standard, and reduces the redundance and the abnormality of inquiry and storage. According to the graph theory, relation schemas in database schema can be expressed clearly. This method combines the normalization theory and the semantic description of the variety of data using functional dependency, forms a new technique in complicated database design research. Since acyclic database schema has a lot of fine properties, which has solved the problems that were rather difficult in the past, the acyclicity turns to an important characteristic of judging a database schema.This dissertation studies theα-acyclic decomposition of database schema in the data organization of database systems based on acyclic database theory. Through the discussion of the existence of the conflicts in the merge dependency set of the functional dependency set, the existence of cycles and acyclic database schema decomposition are studied. Moreover, how to add theα-acyclic characteristic into the database schemas of several levels of normal form and whether it has aα-cyclic or has a acyclic decomposition are discussed.Firstly, Based on the types of the cycles in the database hypergraph, the merge dependency set which is defined for examining the conflicts in database schema and its properties are expounded. Through the analysis on the algorithms of calculating the merge dependency set and the minimum merge dependency set, the algorithm of calculating the closure of 2-tuple set of the merge dependency set is put forward. The algorithms to calculate the subset of leftside set of the merge dependency set are systematically sorted out.Secondly, Integrating the characteristics that hypergraph and FD hypergraph discuss the implication of functional dependency set in microscopic view, the different types of inside conflicts in the relation schema according to the merge FD hypergraph are analyzed. Based on the definition of generalized leftside conflict and generalized rightside conflict, the determinant theorems of generalized leftside conflict and generalized rightside conflict and the algorithms of the theorems are presented.Thirdly, When the FD set has inside conflicts, in order to get a decomposition meeting BCNF, the method to decompose a database schema into one only meets keep FD, BCNF andα-acyclic are put forward. Based on the analysis of the functional dependent relation in the merge dependency set with inside conflicts, the sufficient and necessary condition that ensure the database can be decomposed into one meeting P₂ andα-acyclic is given and proved. Finally, the condition examining and schema decomposition algorithm are given.Fourthly, The definitions of elementary merge dependency set and minimum elementary merge dependency set are put forward. The weak leftside conflict and weak rightside conflict in the minimum elementary merge dependency set are defined. The conclusion that when the minimum elementary merge dependency set has weak left side conflicts or weak right side conflict is reached, The decomposition meeting PEK isα-cyclic is given. The algorithms of calculating the minimum elementary merge dependency set and examining the conflicts are given. Finally, the algorithm to decompose a database schema into one meeting PEK andα-acyclic is given.Fifthly, During the research on the decomposition meeting SNF(Simple Normal Form) andα-acyclic, based on the correlation degree of the minimum merge dependency set, the condition which ensures a database schema can be decomposed into one meeting SNF andα-acyclic is given. The sufficient and necessary conclusion that when D has weak left side conflicts or weak right side conflict or not meet the condition above, the decomposition meeting P_s isα-cyclic is proved. The algorithm to examine whether the database schema meeting the condition and the decomposition algorithm of the database schema that meeting P_s andα-acyclic are given.