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

G Loizou; P Thanisch

doi:10.1007/BF01934180

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

G Loizou, P Thanisch

School of Engineering & Physical Sciences

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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 language	English
Pages (from-to)	157-162
Number of pages	6
Journal	BIT Numerical Mathematics
Volume	27
Issue number	2
DOIs	https://doi.org/10.1007/BF01934180
Publication status	Published - Jun 1987

Keywords

F.2
H.2.1

Access to Document

10.1007/BF01934180

Cite this

@article{89e393c39080448da7e85bf80cd8358c,

title = "On finding a worst-case optimal Fourth Normal Form database decomposition",

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. {\textcopyright} 1987 BIT Foundations.",

keywords = "F.2, H.2.1",

author = "G Loizou and P Thanisch",

year = "1987",

month = jun,

doi = "10.1007/BF01934180",

language = "English",

volume = "27",

pages = "157--162",

journal = "BIT Numerical Mathematics",

issn = "0006-3835",

publisher = "Springer",

number = "2",

}

TY - JOUR

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

AU - Loizou, G

AU - Thanisch, P

PY - 1987/6

Y1 - 1987/6

N2 - 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.

AB - 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.

KW - F.2

KW - H.2.1

UR - http://www.scopus.com/inward/record.url?scp=0023253431&partnerID=8YFLogxK

U2 - 10.1007/BF01934180

DO - 10.1007/BF01934180

M3 - Article

SN - 0006-3835

VL - 27

SP - 157

EP - 162

JO - BIT Numerical Mathematics

JF - BIT Numerical Mathematics

IS - 2

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this