Applying Spanning Tree Graph Theory for Automatic Database Normalization

In Knowledge and Data Engineering field, relational
database is the best repository to store data in a real world. It has
been using around the world more than eight decades. Normalization
is the most important process for the analysis and design of relational
databases. It aims at creating a set of relational tables with minimum
data redundancy that preserve consistency and facilitate correct
insertion, deletion, and modification. Normalization is a major task in
the design of relational databases. Despite its importance, very few
algorithms have been developed to be used in the design of
commercial automatic normalization tools. It is also rare technique to
do it automatically rather manually. Moreover, for a large and
complex database as of now, it make even harder to do it manually.
This paper presents a new complete automated relational database
normalization method. It produces the directed graph and spanning
tree, first. It then proceeds with generating the 2NF, 3NF and also
BCNF normal forms. The benefit of this new algorithm is that it can
cope with a large set of complex function dependencies.

• Chetneti Srisa-an

• Relational Database
• Functional Dependency
• Automatic Normalization
• Primary Key
• Spanning tree.

[1] Connoly, Thomas, Carolyn Begg: Database Systems. A Practical
Approach to Design, Implementation, and Management , Pearson
Education, Third edition, 2005.Relational and XML Data, Journal of
Computer System Science, Vol. 73(4): pp. 636-647, 2007..
[2] Date, C.J., An Introduction to Database Systems, Addison-Wesley,
Seventh Edition 2000.
[3] Mora, A., M. Enciso, P. Cordero, IP de Guzman, An Efficient
Preprocessing Transformation for Functional Dependencies Sets Based
on the Substitution Paradigm, CAEPIA2003, pp.136-146, 2003.
[4] Du H., and L. Wery, A Normalization Tool for Relational Database
Designers, Journal of Network and Computer Applications, Volume 22,
No. 4, pp. 215-232, October 1999.
[5] Yazici, A., and Z. Karakaya, Normalizing Relational Database Schemas
Using Mathematica, LNCS, Springer-Verlag, Vol.3992, pp. 375-382,
2006.
[6] Kung, H. and T. Case, Traditional and Alternative Database
Normalization Techniques: Their Impacts on IS/IT Students’
Perceptions and Performance, International Journal of Information
Technology Education, Vol.1, No.1 pp. 53-76, 2004.
[7] Kolahi, S., Dependency-Preserving Normalization of Relational and
XML Data, Journal of Computer System Science, Vol. 73(4): pp. 636-
647, 2007.
[8] M Arenas, L Libkin, An Information-Theoretic Approach to Normal
Forms for Relational and XML Data, Journal of the ACM (JACM), Vol.
52(2), pp. 246-283, 2005