Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:An information-theoretic approach to normal forms for relational and XML data.
Authors: Leonid Libkin ; Marcelo Arenas
Date: 2005
Publication Title:Journal of the ACM
Publication Type:Journal Article Publication Status:Published
Volume No:52 Page Nos:246-283
Normalization as a way of producing good database designs is a well-understood topic. However, the same problem of distinguishing well-designed databases from poorly designed ones arises in other data models, in particular, XML. While in the relational world the criteria for being well-designed are usually very intuitive and clear to state, they become more obscure when one moves to more complex data models. Our goal is to provide a set of tools for testing when a condition on a database design, specified by a {\em normal form}, corresponds to a good design. We use techniques of information theory, and define a measure of information content of elements in a database with respect to a set of constraints. We first test this measure in the relational context, providing information-theoretic justification for familiar normal forms such as BCNF, 4NF, PJ/NF, 5NFR, DK/NF. We then show that the same measure applies in the XML context, which gives us a characterization of a recently introduced XML normal form called XNF. Finally, we look at information-theoretic criteria for justifying normalization algorithms.
Links To Paper
1st Link
Bibtex format
author = { Leonid Libkin and Marcelo Arenas },
title = {An information-theoretic approach to normal forms for relational and XML data.},
journal = {Journal of the ACM},
publisher = {ACM},
year = 2005,
volume = {52},
pages = {246-283},
doi = {10.1145/1059513.1059519},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh