On finding a worst-case optimal Fourth Normal Form database decomposition

G Loizou, P Thanisch

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Although several Fourth Normal Form (4NF) decomposition algorithms have been published, the problem's computational complexity remains an open question. Part of the difficulty is that no one has established an upper bound on the size of a 4NF decomposition scheme for a given number of attributes. We prove such an upper bound and we present an algorithm which is worst-case optimal: it never produces a 4NF decomposition scheme that is larger than the upper bound. © 1987 BIT Foundations.

Original languageEnglish
Pages (from-to)157-162
Number of pages6
JournalBIT Numerical Mathematics
Issue number2
Publication statusPublished - Jun 1987


  • F.2
  • H.2.1


Dive into the research topics of 'On finding a worst-case optimal Fourth Normal Form database decomposition'. Together they form a unique fingerprint.

Cite this