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

G Loizou, P Thanisch

Research output: Contribution to journalArticle

Abstract

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
Volume27
Issue number2
DOIs
Publication statusPublished - Jun 1987

Keywords

  • F.2
  • H.2.1

Fingerprint 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