Query optimization by decomposition of BCNF / 3NF relations

Abstract

An algorithm was developed for further decomposition of Boyce-Codd Normal Form (BCNF) / Third Normal Form (3NF) relations based on the frequency of use of attributes or groups of attributes identified by the purpose of their use. The properties of the BCNF/3NF relations were kept intact in the decomposed relations. The trade-off between the excess space requirement due to replication of the primary key and query cost reduction was considered while developing the algorithm. It was observed that for more than one frequency occurrences or groups identified by the purpose of use of the attributes in a relation, the algorithm could reduce the query cost significantly. When applied on a branch banking database, it was found that the algorithm was able to reduce the query cost by 55.20% as against an increase of 4.21% of the storage requirement.