Normal form relation schemes : a new characterization

Demetrovics János and Hencsey Gusztáv and Libkin Leonid O. and Muchnik Ilya: Normal form relation schemes : a new characterization. In: Acta cybernetica, (10) 3. pp. 141-153. (1992)

[thumbnail of cybernetica_010_numb_003_141-153.pdf]
Cikk, tanulmány, mű

Download (862kB) | Preview


A new characterization of relational database schemes in normal forms is given. This characterization is based on the properties of the semilattice of closed sets of attributes. For the problems testing third and Boyce-Codd normal forma, which are known to be ^//'-complete for relation schemes, this new characterization helps establish polynomial algorithms if the input is a relation (matrix) rather than a relation scheme. The problem of approximation of an arbitrary family of functional dependencies by one in a normal form is also addressed.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1992
Volume: 10
Number: 3
ISSN: 0324-721X
Page Range: pp. 141-153
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 151-153. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 09:19

Actions (login required)

View Item View Item