Decisional BCNF

Decisional BCNF is the problem of deciding whether or not a relation schema can be turned 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