A linear-time algorithm for normalized database design
Ramarathnam Ravichandran, William C. Perkins · 1988
Organizations are increasingly emphasizing effective utilization of information resources in order to meet the challenges presented by today's competitive environment. Given the central role of database systems in information processing in organizations, the underlying structure of the database is of critical importance. This structure, represented in a database schema, should capture data that is of interest for organizational purposes and should ensure that the data provided to the users is correct. Incorrect data or loss of data can result in dysfunctional consequences. Existing algorithms for database schema design assume consistent input from the users and become computationally expensive with exponential run-times for large database design problems. Using semantic constructs and a systematic search of the problem space, an efficient normalization algorithm which addresses input inconsistencies is presented. The concepts of objects and directed relationships are introduced. We illustrate how specifications from semantic data modeling approaches such as the Entity-Relationship model can be translated into objects and directed relationships. Imposing two constraints on the input specifications enables us to detect four possible inconsistencies in the inputs: differing dependency declarations, transitive dependencies, transitive relationships, and circular relationships. Using depth-first search techniques and adjacency list structures, the algorithm detects inconsistencies and resolves them by interacting with the user. The resulting schema is in the fourth normal form and is without interrecord functional dependency redundancies. Given O objects, D directed relationships, and A attributes as inputs, the run-time complexity of the algorithm O(max($O,D,A$)) is linear in its inputs and optimal within a constant factor. The algorithm was implemented in PASCAL to run on both mini and microcomputers and was tested on 450 sample problems of varying sizes. The results indicate that the algorithm can be implemented quite efficiently. For instance, it took 4.4 seconds on the IBM PS/2 Model 80 on a sample problem with 600 objects and 3400 attributes. The algorithm was applied to a large database of NASA with 78 objects and 398 attributes. Inconsistencies were found in the inputs and were resolved successfully, thus providing empirical support for the proposed approach.