BCNF Decomposition

BCNF Decomposition is the problem of decomposing a relation schema into Boyce-Codd normal form (BCNF). A relation schema RR is in Boyce Codd Normal Form (abbr. BCNF) if for all non-trivial FDs XYX \rightarrow Y in F+F^+, XX is a superkey. In extending this notion to database schemas, we must be conscious of the UR-assumption. We say that Ri=<ATTRi,Fi>R_i = <ATTR_i,F_i> is in BCNF if the schema <ATTRi,F+[ATTRi]><ATTR_i, F^+[ATTR_i]> is in BCNF, and DD is in BCNF if each RiR_i is.

Parameters

  • nn: size of database
  • kk: number of functional dependencies

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table