Chapter 7 Relational Database Design¶

文本统计：约 1900 个字 • 6 行代码

Info

参考 Lecture 7 ｜ Relational Database Design - Yaoyaoling's notebook

7.1 Introduction¶

Example

对于一个高校的数据库关系模式，我们能不能将instructor和department进行合并

Pitfalls of the “bad” relations

Information repetition (信息重复)
Insertion anomalies (插入异常)
Update difficulty (更新困难)

数据之间存在着隐含的函数约束关系，知道了 id 就可以决定其他元素。比如说 id →→ name, salary, dept_name; dept_name →→ building, budget

产生冗余的原因是 dept_name 决定了部分属性，但他却不是这个表的 primary key。我们希望的关系是只有 candidate key 能决定其他属性。

拆表后要有重叠的属性，否则无法拼接回去。这里的公共属性必须是分拆出一个关系模式的 primary key, 这是无损（没有信息损失）连接。

A Lossy Decomposition

由于Kim 并不是primary key，所以拼接回去的结果与原来并不相同

Lossless-join Decomposition

Let $R$ be a relation schema and let $R_1$ and $R_2$ form a decomposition of $R$. That is $R=R1∪R2$.

We say that the decomposition is a lossless decomposition if there is no loss of information by replacing $R$ with the two relation schemas $R=R_1∪R_2$. Formally, $r=∏_{R_1}(r)⋈∏_{R_2}(r)$.

And, conversely a decomposition is lossy if $r⊂∏_{R_1}(r)⋈∏_{R_2}(r)$

Note: more tuples implies more uncertainty (less information).

A decomposition of $R$ into $R_1$ and $R_2$ is lossless join if at least one of the following dependencies holds: (充分条件)

$R_1∩R_2→R_1$
$R_1∩R_2→R_2$

即公共属性是其中一个关系的 Key.

Lossless-Join Decomposition

Decide whether a particular relation $R$ is in “good” form.

In the case that a relation $R$ is not in “good” form, decompose it into a set of relations $\{R_1, R_2, ..., R_n\}$ such that

each relation is in good form
the decomposition is a lossless-join decomposition

Our theory is based on:

functional dependencies
multivalued dependencies

Normal Forms(NF): $1NF \rightarrow 2NF \rightarrow 3NF\rightarrow BCNF\rightarrow 4NF$

有些函数依赖，不能在 BCNF 中得到体现，需要把几个表拼在一起才能体现，叫依赖保持。这时我们需要从 BCNF 回到 3NF.

1NF

A relational schema R is in first normal form if the domains of all attributes of R are atomic.

Domain is atomic if its elements are considered to be indivisible units

e.g. Suppose that students are given roll numbers which are strings of the form CS0012 or EE1127 If the first two characters are extracted to find the department, the domain of roll numbers is not atomic.

7.2 Functional Dependencies¶

Functional Dependencies are constraints on the set of legal relations.

Require that the value for a certain set of attributes determines uniquely the value for another set of attributes. e.g. $\text{dept\_name}\rightarrow \text{building}$

A functional dependency is a generalization of the notion of a key.

Let $R$ be a relation schema $α⊆R$ and $β⊆R$ ($α,β$ 是属性的集合)

The functional dependency

\[ α→β \]

holds on $R$ if and only if for any legal relations $r(R)$, whenever any two tuples $t_1$ and $t_2$ of $r$ agree on the attributes $α$, they also agree on the attributes $β$. That is, $$ t_1[α]=t_2[α]⇒t_1[β]=t_2[β] $$ 通过数据库实例可以证伪函数依赖，但不能证实。（依赖是来自应用层面的规定，先有函数依赖，再有数据库中的数据）

Example

$A→B$ 可以证伪，但也不能因此就说 $B→A$

这样 super-key 和 candidate key 的定义可以如下定义

(1) K is a super-key for relation schema RR if and only if $K→R$

(2) K is a candidate key for $R$ if and only if

$K→R$, and
for no $α⊂K$, $α→R$

A functional dependency is trivial (平凡的) if it is satisfied by all relations, e.g. ID,name $\rightarrow$ ID

In general, $\alpha \rightarrow \beta$ is trivial if $\beta ⊆ \alpha$

7.2.1 Closure of Functional Dependencies¶

Given a set $F$ of functional dependencies, there are certain other functional dependencies that are logically implied by $F$. e.g. if $A\rightarrow B$ and $B\rightarrow C$ then we can infer $A\rightarrow C$

The set of all functional dependencies logically implied by $F$ is the closure of $F$. We denote the closure of $F$ by $F^+$

e.g. $F=\{A→B,B→C\} \text{ then } F^+=\{A→B,B→C,A→C,AB→B,AB→C,…\}$

We can find $F^+$, the closure of $F$, by repeatedly applying Armstrong’s Axioms:

if $β⊆α$ then $α→β$ (reflexivity, 自反律)
if $α→β$ then $γα→γβ$ (augmentation, 增补律)
if $α→β$ and $β→γ$ then $α→γ$ (transitivity, 传递律)

These rules are

Sound（正确有效的） generate only functional dependencies that actually hold
Complete（完备的） generate all functional dependencies that hold

Example

Additional rules:

If $α→β$ holds and $α→γ$ holds, then $α→βγ$ holds (union, 合并)
If $α→βγ$ holds, then $α→β$ holds and $α→γ$ holds (decomposition, 分解)
If $α→β$ holds and $γβ→δ$ holds, then $αγ→δ$ holds (pseudo-transitivity，伪传递)

7.2.2 Closure of Attribute Sets¶

Given a set of attributes a, define the closure of a under $F$ (denoted by $a^+$) as the set of attributes that are functionally determined by a under $F$

Algorithm to compute $a^+$, the closure of a under $F$

result := a;
while (changes to result) do
    for each b -> c in F do
        begin
            if b in result then  result := result and c         
        end

Example

Uses of Attribute Closure¶

Testing for superkey: To test if $α$ is a superkey, we compute $α^+$, and check if $α^+$ contains all attributes of $R$.

Testing functional dependencies

To check if a functional dependency $α→β$ holds (or, in other words, is in $F^+$), just check if $β⊆α^+$.
That is, we compute $α^+$ by using attribute closure, and then check if it contains $β$.

Computing closure of $F$ For each $γ⊆R$, we find the closure $γ^+$, and for each $S⊆γ^+$, we output a functional dependency $γ→S$.

Example

7.2.3 Canonical Cover（正则覆盖）¶

Sets of functional dependencies may have redundant dependencies that can be inferred from the others, For example: $A \rightarrow C$ is redundant in: $\{A \rightarrow B, B \rightarrow C, A \rightarrow C\}$

Example

Intuitively, a canonical cover of F is a “minimal” set of functional dependencies equivalent to F, having no redundant dependencies or redundant parts of dependencies

Extraneous Attributes(无关属性)

Consider a set $F$ of functional dependencies and the functional dependency $\alpha\rightarrow \beta$ in $F$.

Attribute A is extraneous in $\alpha$ if $A\in \alpha$ and $F$ logically implies $(F – \{\alpha \rightarrow \beta\}) \cup \{(\alpha – A) \rightarrow \beta\}$.
Attribute A is extraneous in $\alpha$ if $A\in \beta$ and the set of functional dependencies $(F – \{\alpha \rightarrow \beta\}) \cup \{\alpha \rightarrow(\beta – A)\}$ logically implies $F$.

A canonical cover for $F$ is a set of dependencies $F_c$ such that

$F$ logically implies all dependencies in $F_c$
$F_c$ logically implies all dependencies in $F$ 两者是等价的
No functional dependency in $F_c$ contains an extraneous attribute
Each left side of functional dependency in $F_c$ is unique.

To compute a canonical cover for $F$

重复以下步骤 - 使用合并规则替换$ F $中的任何依赖关系：将 $\alpha_1 \rightarrow \beta_1$ 和 $\alpha_1 \rightarrow \beta_2$ 替换为 $\alpha_1 \rightarrow \beta_1\beta_2$。 - 在 $\alpha \rightarrow \beta$ 中寻找一个具有冗余属性的功能依赖，该冗余属性可能在 $\alpha$ 或 $\beta$ 中。 - 如果找到冗余属性，则从 $\alpha \rightarrow \beta$ 中删除它。

直到 $F$ 不再改变。

Note: Union rule may become applicable after some extraneous attributes have been deleted, so it has to be re-applied

Computing a Canonical Cover

7.2.4 Boyce-Codd Normal Form¶

A relation schema $R$ is in BCNF with respect to a set $F$ of functional dependencies if for all functional dependencies in $F^+$ of the form where $α⊆R$ and $β⊆R$, at least one of the following holds

$α→β$ is trivial
$α$ is a super-key for $R$.

Decomposing a Schema into BCNF

Suppose we have a schema $R$ and a non-trivial dependency $α→β$ causes a violation of BCNF. We decompose $R$ into: $(α∪β)$ and $(R−(β−α))$

Example

Constraints, including functional dependencies, are costly to check in practice unless they pertain to only one relation.

If it is sufficient to test only those dependencies on each individual relation of a decomposition in order to ensure that all functional dependencies hold, then that decomposition is dependency preserving (保持依赖). （如果通过检验单一关系上的函数依赖，就能确保所有的函数依赖成立，那么这样的分解是依赖保持的）（或者，原来关系R上的每一个函数依赖，都可以在分解后的单一关系上得到检验或者推导得到。）

Because it is not always possible to achieve both BCNF and dependency preservation, we consider a weaker normal form, known as third normal form.

Let $F_i$ be the set of all functional dependencies in $F^+$ that include only attributes in $R_i$. ($F_i$: the restriction of $F$ on $R_i$)

A decomposition is dependency preserving, if $(F_1∪F_2∪…∪F_n)^+=F^+$
If it is not, then checking updates for violation of functional dependencies may require computing joins, which is expensive.

Example

It is not always possible to get a BCNF decomposition that is dependency preserving

7.2.5 Third Normal Form¶

任何一个非平凡函数依赖，如果左边不是一个 super key, 那么右边必须包含在一个 candidate key 里面。

A relation schema $R$ is in third normal form (3NF) if for all: $α→β$ in $F^+$ at least one of the following holds:

$α→β$ is trivial (i.e., $β∈α$)
$α$ is a super-key for $R$
Each attribute A in $β−α$ is contained in a candidate key for $R$. (NOTE: each attribute may be in a different candidate key)

Example