{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T03:14:32Z","timestamp":1770520472273,"version":"3.49.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,2,15]],"date-time":"2008-02-15T00:00:00Z","timestamp":1203033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP7-ICT-233599"],"award-info":[{"award-number":["FP7-ICT-233599"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["E005039G049165"],"award-info":[{"award-number":["E005039G049165"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>Normal forms that guide the process of database schema design have several key goals such as elimination of redundancies and preservation of integrity constraints, such as functional dependencies. It has long been known that complete elimination of redundancies and complete preservation of constraints cannot be achieved simultaneously. In this article, we use a recently introduced information-theoretic framework, and provide a quantitative analysis of the redundancy\/integrity preservation trade-off, and give techniques for comparing different schema designs in terms of the amount of redundancy they carry.<\/jats:p>\n          <jats:p>The main notion of the information-theoretic framework is that of an information content of each datum in an instance (which is a number in [0,1]): the closer to 1, the less redundancy it carries. We start by providing a combinatorial criterion that lets us calculate, for a relational schema with functional dependencies, the lowest information content in its instances. This indicates how good the schema design is in terms of allowing redundant information. We then study the normal form 3NF, which tolerates some redundancy to guarantee preservation of functional dependencies. The main result provides a formal justification for normal form 3NF by showing that this normal form pays the smallest possible price, in terms of redundancy, for achieving dependency preservation. We also give techniques for quantitative comparison of different normal forms based on the redundancy they tolerate.<\/jats:p>","DOI":"10.1145\/1670243.1670248","type":"journal-article","created":{"date-parts":[[2010,2,16]],"date-time":"2010-02-16T20:51:06Z","timestamp":1266353466000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["An information-theoretic analysis of worst-case redundancy in database design"],"prefix":"10.1145","volume":"35","author":[{"given":"Solmaz","family":"Kolahi","sequence":"first","affiliation":[{"name":"University of British Columbia, Canada"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]}],"member":"320","published-online":{"date-parts":[[2008,2,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974757"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059519"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 4th International Conference on Very Large Data Bases. 113--124","author":"Beeri C."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322414"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/320493.320489"},{"key":"e_1_2_1_8_1","unstructured":"Bernstein P. A. and Goodman N. 1980. What does boyce-codd normal form do&quest; In Proceedings of the 6th International Conference on Very Large Data Bases. IEEE Computer Society 245--259.   Bernstein P. A. and Goodman N. 1980. What does boyce-codd normal form do&quest; In Proceedings of the 6th International Conference on Very Large Data Bases. IEEE Computer Society 245--259."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Biskup J. 1995. Achievements of relational database schema design theory revisited. In Semantics in Databases. 29--54.   Biskup J. 1995. Achievements of relational database schema design theory revisited. In Semantics in Databases. 29--54.","DOI":"10.1007\/BFb0035004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582118"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90034-1"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 13th International Conference on Very Large Data Bases. 71--81","author":"Cavallo R."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. John Wiley and Sons.   Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. John Wiley and Sons.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.336059"},{"key":"e_1_2_1_15_1","first-page":"35","article-title":"Keys, antikeys and prime attributes. Annales","volume":"8","author":"Demetrovics J.","year":"1987","journal-title":"Univ. Sci., Sect. Comp., Budapest"},{"key":"e_1_2_1_16_1","volume-title":"Beginning SQL Server 2005 for Developers: From Novice to Professional","author":"Dewson R."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582120"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/319587.319592"},{"key":"e_1_2_1_19_1","volume-title":"Oracle Essentials: Oracle Database 11g","author":"Greenwald R.","year":"2007","edition":"4"},{"key":"e_1_2_1_20_1","volume-title":"Handbook of Theoretical Computer Science","author":"Kanellakis P. C."},{"key":"e_1_2_1_21_1","volume-title":"Database Systems: An Application-Oriented Approach","author":"Kifer M.","year":"2006"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.014"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142369"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 8th International Conference on Very Large Data Bases. Morgan Kaufmann, 131--141","author":"LeDoux C. H."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1987.232847"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Levene M. Levene M. and Loizou G. 1999. A Guided Tour of Relational Databases and Beyond. Springer.   Levene M. Levene M. and Loizou G. 1999. A Guided Tour of Relational Databases and Beyond. Springer.","DOI":"10.1007\/978-0-85729-349-7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(02)00021-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842267"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319583"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90015-2"},{"key":"e_1_2_1_31_1","unstructured":"Stephens R. K. and Plew R. R. 2002. Sams Teach Yourself SQL in 21 Days 4th Ed. Sams.   Stephens R. K. and Plew R. R. 2002. Sams Teach Yourself SQL in 21 Days 4th Ed. Sams."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050157"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319749"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670248","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1670243.1670248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:58Z","timestamp":1750250458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,15]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1670243.1670248"],"URL":"https:\/\/doi.org\/10.1145\/1670243.1670248","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,15]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}