Can I read An Information-theoretic Analysis of Worst-case Redundancy in Database Design on EtoBox?

An Information-theoretic Analysis of Worst-case Redundancy in Database Design by Solmaz Kolahi; Leonid Libkin is a Computer Science article available to read on EtoBox.

What is An Information-theoretic Analysis of Worst-case Redundancy in Database Design about?

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

Who reads An Information-theoretic Analysis of Worst-case Redundancy in Database Design?

Author

Solmaz Kolahi; Leonid Libkin

Publisher

ACM

Published

2008

Language

EN

Field

Computer Science (Physical Sciences)