ONE ALGORITHM FOR OPTIMIZING RELATIONAL DATABASE SCHEMAS

This article presents an exhaustive-search algorithm for finding 3NF schemas for relational databases; the schema are minimal in the class of all equivalent schemas that are synthesized by the Ling - Tompa - Kameda algorithm. The search size is reduced by eliminating nonkey attributes that appear in subschemas of each of the equivalent schemas. The search is accomplished in polynomial time.