|
|
|
     |
                                     |
Return to Award Winning Papers
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 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-theoreticcriteria for justifying normalization algorithms.
@inproceedings {DBLP:conf/pods/ArenasL03, author = {Marcelo Arenas and Leonid Libkin}, booktitle = {PODS}, title = {An information-theoretic approach to normal forms for relational and XML data.}, pages = {15-26}, year = {2003}, url = {db/conf/pods/pods2003.html#ArenasL03}, ee = {http://doi.acm.org/10.1145/773153.773155}, crossref = {conf/pods/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
