翻译 《Database.System.Concepts》的8.3 Decomposition Using Functional Dependencies

8.3 分解使用函数依赖

在8.1节中， 我们注意到有一种正规的方法来评估一个关系模式是否应该被分解，这种方法是基于码和函数依赖的概念来实行的。

      在讨论关系型数据库设计的算法时，我们需要讨论任意关系和它们的模式，而不是只讨论示例。回顾我们在第二章中对于关系模型的介绍，在这里我们对记号进行总结：

•通常，我们用希腊字母来表示属性集（例如α）。我们用小写的罗马字母后面跟上个用括号括起来的大写的罗马字母来表示一个关系模式（例如r（R））。我们用记号r（R）表示这个模式是用R表示属性集的关系r，但是有时当关系名对我们来说不那么重要时，我们用R来表示以简化记号。

      当然，一个关系模式是一个属性集，但不是所有的属性集都是模式。当我们用小写希腊字母时，我们表示的是一个可能是或者可能不是模式的属性集。当我们希望表明某一个属性集绝对是一个模式时，我们用一个罗马字母来表示。

•当一个属性集是超码时，我们用K来表示。超码有一种特殊的关系模式，所以我们用术语“K是r(R)的超码”来表示。

•我们用小写名称来表示关系。在我们的示例中，这些名称是要现实的（例如instructor），而在我们的定义和算法中，我们用单个字母来表示，如r。

•当然，一个关系在任何给定的时间里都有一个特值；我们称之为实例并用术语“r的实例”来表示。当清楚地知道我们正在讨论一个实例时，我们可能会简单地用关系名来表示这个实例（例如r）。

 

8.3.1 码和函数依赖

数据库模拟现实世界中的实体集和关系，在现实世界中，数据通常有各种各样的约束（规则）。例如，在大学数据库中被期望拥有的一些约束有:

1.学生和讲师可以通过他们的ID被唯一识别。

2.每个学生和讲师只有一个名字。

3.每个讲师和学生都只与一个部门有（主要的）关联。

4.每个部门的预算都只有一个值，并且只有一个相关建筑。

      将一个满足这些所有现实世界约束的关系的实例称为关系的合法实例;数据库中的一个合法实例在所有关系实例中都是合法实例。在现实世界约束中一些最常用的类型可以用码（超码、候选码、主码）或者用我们下面定义的函数依赖来表示。

    在2.3节中，我们将超码的概念定义为一个或多个完全集合在一起的属性集，使我们能够唯一识别关系中的一个元组。我们重申这一定义如下：用r（R）表示一个关系模式，在r（R）的任意一个合法实例中，如果R的一个子集K是r（R）的一个超码，对于实例r的元组中的所有成对的t1和t2来说，如果t1不等于t2，那么t1[K]不等于t2[K]。也就是说，在关系r（R）的任意合法实例中没有两个元组在属性集K中可能有相同的值。显然，如果r中没有两个元组在K上具有相同的值，那么一个K值在r中能够唯一标识一个元组。

    鉴于超码是一个能够唯一识别整个元组的属性集，而函数依赖允许我们表达约束来唯一地识别某些属性的值。思考关系模式r（R），并使α⊆R且β⊆R。

•给定一个r（R）的实例，我们定义这个实例满足函数依赖α→β，如果对于实例中的所有成对元组t1和t2来说，t1[α] = t2[α]，这也是t1[β] = t2[β]的情况。

•我们定义如果函数依赖α→β建立在模式r（R）上，r（R）的每个合法实例都满足函数依赖。

    使用函数依赖的概念，我们定义如果函数依赖K→R建立在r（R）上，那么K是r（R）的一个超码。换句话说，如果K是一个超码，那么对于r（R）中的每个合法实例和实例中的每个成对的t1和t2来说，每当t1[K] = t2[K]时,也会导致 t1[R] = t2[R] （也就是t1=t2）。

    函数依赖允许我们表达我们无法用超码表达的约束。在8.1.2小节中，我们思考了模式：

inst dept (ID, name, salary, dept_name, building, budget)

      在这个模式中，因为对于每个部门（由dept_name鉴别）都有唯一的预算值，所以函数依赖dept_name → budget 建立。

      我们用下面的文字表示这两个属性（ID, dept_name）对inst_dept形成一个超码：

ID, dept_name→name, salary, building, budget

      我们用两种方式来使用函数依赖：

1. 测试关系实例，看它们是否满足函数依赖的给定集F。

2. 明确对合法关系集的约束。因此，我们只需要关心满足函数依赖中给定集合的那些关系实例。如果我们想要约束我们自己与满足函数依赖的集合F的模式r（R）之间的关系，我们称F建立在r（R）中。

    让我们思考图8.4关系r中的实例，可以看出这个实例是满足函数依赖的。可以注意到A→C是满足的函数依赖的。两个元组a1有A值。这些元组有相同的C值——也就是c1。类似地，有A值的两个元组a2有相同的C值，即c2。没有其他两个不同的元组具有相同的A值。然而，函数依赖C→A并不满足。为了证明它是不满足的，思考元组t1 =(a2,b3,c2,d3)和t2 =(a3,b3,c2,d4)。这两个元组有相同的C值，即c2，但是它们有不同的A值，分别为a2和a3。因此，我们发现了在这一对元组t1和t2中，t1[C]= t2[C],但是t1[A]≠t2[A]。

    一些函数依赖被认为是不重要的，因为它们满足所有关系。例如，A→A满足属性A中所涉及的所有关系。从字面上理解函数依赖的定义，我们可以看到，对于所有元组t1和t2，有 t1[A] = t2[A]，这是t1[A] = t2[A]的情况。同样的，AB→A满足属性A中涉及的所有关系。总的来说，如果β⊆α，那么表格α→β的函数依赖是微不足道的。

    认识到关系中的一个实例可能满足一些不要求我们建立关系模式的函数依赖是很重要的。在图8.5的classroom关系的实例中，我们看到room_number→capacity是满足函数依赖的。然而我们相信在现实世界中，两个在不同楼的教室可以有相同的教室号码但是它们的容量是不同的。因此，在有些时候当room_number→capacity不满足函数依赖时，关系classroom有一个实例也是有可能的。所以，我们不会把room_number→capacity包含于建立在classroom关系中的模式的函数依赖集中。然而，我们应该期望函数依赖building，room_number→capacity 建立在classroom模式中。

    给定一个建立在关系r（R）的函数依赖集F，可以推断出可能其他确定的函数依赖必须也建立在关系中。例如，给定一个模式r（A,B,C），如果函数依赖A→B和B→C建立在r中，我们可以推断出函数依赖A→C也必须建立在r中。这是因为给定任何A值都有唯一一应的值给B，并且对于B的值，都有唯一一个相应的值给C。我们之后在8.4.1小节中将会学习如何做出这样的推断。

    我们将使用记号F+ 来表示函数依赖集F的闭包，也就是给定函数依赖集F可以推断出函数依赖集中的所有函数依赖。显然，函数依赖集F+包含了所有F中的函数依赖。

8.3.2 BCNF

　　我们能得到的较理想的正常形式之一是BCNF。它消除了基于函数依赖可以发现的所有冗余，但是，正如我们将在第8.6节中看到的，可能还有其他类型的冗余。一个关系模式R在BCNF中，对于函数依赖关系的集合F，如果在形式的F +中，所有的函数依赖项α→β,，且α⊆ R和⊆R中，至少有一个如下所述:

　　•α→β是平常的函数依赖(也就是β ⊆α)

　　•α是模式R的一个超码

　　如果构成一个关系模式集中的每个模式都属于BCNF,那么这个数据库设计属于BCNF。我们已经在8.1节中见过见过了不属于BCNF的关系模式的例子:

　　Ins_ dept(ID,name,salary, dept_name,buiIding,budget)

　　函数依赖dept_name→budget 在 inst_dept上成立,但是dept name 不是一个超码(因为一个系中可以有很多不同的教师) ,在8.1.2小节中，我们看到把inst_dept 拆分为 instructor 和d epartment 是一个更好的设计。模式instructor 属于BCNF。所有的成立的非平凡函数依赖,例如:

　　ID→ name, dept _name,  salary

　　在箭头的在侧包含ID,并且ID是一个超码(实际上，在这个例子中它是一个主码)(换句话来说，在不包含ID的另一侧上,对于 name，dept _name，和salary的任意组合不存在非平凡的函数依赖)，因此,教师属于BCNF。

　　相同的,department模式属子BCNF因为所有成立的非平凡函数依赖,例如:

　　dept _name → building, budget

　　在箭头的左侧包含部门名称，并且部门名称对于系来说是一个超码(并且是一个主码) 因此department属于BCNF。

     我们现在来讲述分解不属于BCNF模式的一般规则,让R成为一个不属于BCNF的一个模式。那么这里就至少有一个非平凡函数依赖α→β,比如α不是R的一个超码。我们在我们的设计中用两种模式来替代R:

　　• ( α∪β )

　　• (R − ( β− α))

　　在这个例子中,  α= dept _name,  = {building, budget}, 并且inst_dept 被替代为

　　• ( α∪ β)=(dept _name,building,budget)

　　• (R − ( α−β )) = (ID, name, dept_name, salary)

　　在这个例子中，结果是β-α=β。我们需要像上面一样表达规则，然后正确处理箭头两边都有出现的属性的函数依赖。我们将会在8.5.1小节中介绍专门的原因。

　　当我们分解一个不属于BCNF的模式时,可能有一个或多个产生的模式是不属于BCNF的。在这种情况中，需要进一步的分解，最终结果是一个BCNF模式集。

8.3.3 BCNF和依赖保持

　　我们看到了表达数据库一致性约束的几种方法：主键约束、函数依赖、检查约束、断言和触发器。每次更新数据库时都测试这些约束是花费很大的，因此，设计数据库时使用一种约束可以被有效测试的方法是很有用的。特别是，如果只考虑一种关系就可以测试一个函数依赖，那么测试该约束的成本就会很低。我们将看到，在某些情况下，分解为BCNF可以防止确定的函数依赖的有效测试。

　　为了说明这一点，假设我们对我们的大学组织做了一个小小的改变。在图7.15的设计中，一个学生可能只有一个导师。这是因为关系集advisor是从student到advisor的多对一关系。我们要做的“小”改变是，一名教师只能与一个单独的系联系，一个学生可能有一个以上的导师，但最多只能有一个来自一个确定的系的导师。

　　使用E-R设计实现此更改的一种方法是将advisor关系集替换为一个三元关系集，dept_advisor，如图8.6所示，涉及实体集instructor, student,和department，从一对{student, instructor}到department是多对一的。E-R图说明了该约束，即“一个学生可能有多个导师，但最多有一个对应于给定的部门”。

　　使用这个新的E-R图，instructor,department, 和 student的架构不变。然而，从dept_advisor派生的架构现在是：dept_advisor (s_ID, i_ID,dept_name)

　　虽然E-R图中没有指定，但假设我们有一个附加约束，即“一个教师只能担任单个部门的导师”。

　　然后，以下函数依赖将保留在dept_advisor上：

　　I_ID→dept_name

　　s_ID, dept_name→i_ID

　　第一个函数依赖遵循我们的要求，即“一个教师只能担任一个部门的导师”。 第二个函数依赖是根据我们的要求，“一个学生最多可以有一个来自一个给定部门导师。”

　　请注意，使用此设计，在dept_advisor关系中每次讲师参与时我们被迫重复一次部门名称。

　　我们看到dept_advisor不在BCNF中，因为i_ID不是一个超码。按照我们的BCNF分解规则，我们得到：

　　(s_ID, i_ID)

　　(i_ID, dept_name)

　　以上两种模式都是BCNF。(实际上，你可以通过定义验证任何只有两个属性的模式是在BCNF中。) 但是注意，在我们的BCNF设计中，没有包含出现在函数依赖s_ID, dept_name→i_ID中所有属性的模式。

　　因为我们的设计在计算上很难强制执行这种函数依赖，所以我们说我们的设计不是保持依赖关系。由于依赖保持通常被认为是可取的，所以我们考虑另一种比BCNF更弱的正常形式，这将允许我们保留依赖关系，这种正常形式被称为第三范式。

8.3.4 第三范式

　　BCNF要求所有非平凡的依赖都是α→β形式的，此时α是超码。第三范式(3NF)允许某些左侧非超码的非平凡函数依赖，从而稍微放松了这个约束。在我们明确3NF之前，我们回顾了候选码是一个极小的超码，即一个超码，它的真子集也是一个超码。

　　关系模式R相对于函数依赖集F是第三范式，如果对于表单α→β的F⁺中的所有函数依赖，其中α⊆R和β⊆R，至少有以下一种：

　　α→β是平凡的函数依赖。

　　α对于R是超码。

　　β-α中的每个属性A被包含在R中的候选码。

　　注意上面的第三个条件并不是说单个候选键必须包含β-α中的所有属性；β-α中的每个属性A可能包含在different候选键中。

　　首先两种方案与BCNF的定义中的两种方案相同。3NF 定义的第三种选择似乎是不直观的，也不清楚它为什么有用，在某种意义上，它代表了BCNF条件的最小放松，这有助于确保每个模式都有一个保持依赖分解为3NF。当我们研究分解为3NF时，之后它的作用将变得更加明确。

　　请注意，任何满足BCNF的模式也会满足3NF，因为它的每个函数依赖都将满足首要的两种备选方案之一。因此，BCNF是一种比3NF更具有限制性的正常形式。

　　3NF的定义允许某些在BCNF中是不允许的函数依赖。从属关系。依赖α→β满足只是3NF定义的第三种选择，在BCNF中是不允许的，而在3NF中是允许的。

　　现在，让我们再考虑一下dept_advisor关系集，它具有以下函数依赖：

　　I_ID→dept_name

　　s_ID, dept_name→i_ID

　　在第8.3.3节中，我们认为函数依赖“i_ID→dept_name”。导致dept_advisor模式不在BCNF中。注意在这里α= i_ID，β= dept_name，和β-α= dept_name。因为函数依赖s_ID，dept_name→i_ID保存在dept_advisor上，属性dept_name包含在候选码中，因此，dept_name位于3NF中。

　　我们已经看到了必须在BCNF和3NF之间进行的权衡，当没有保持依赖的BCNF设计时。这些权衡在8.5.4节中有更详细的描述。

8.3.5高级范式

　　在某些情况下，使用函数依赖来分解模式可能并不够避免不必要的信息重复。考虑一下instructor实体集合的一个细微的变化，在这个过程中，我们记录每一位教师的一组孩子的名字和一组电话号码。电话号码可以由多个人共享。因此，phone_number和child_name将是多值属性，按照我们从E-R设计生成模式的规则，我们将有两个模式，一个用于多值属性，phone_number和child_name。

　　(ID, child_name)

　　(ID, phone_number)

　　如果我们结合这些模式来获得：

　　(ID, child_name, phone_number)

　　我们将发现结果放在BCNF中，因为只有非平凡的函数依赖才能保持。结果，我们可能认为这样的组合是个好主意。然而，这样的组合是个坏主意，我们可以通过一个有两个孩子和两个电话号码的教师的例子来看。例如，让ID为99999的教师有两个孩子，名为“David”和“William”，以及两个电话号码，512-555-1234和512-555-4321。在组合模式中，我们必须为每个依赖方重复一次电话号码：

　　(99999, David, 512-555-1234)

　　(99999, David, 512-555-4321)

　　(99999, William, 512-555-1234)

　　(99999, William, 512-555-4321)

　　如果我们不重复电话号码，只存储第一个和最后一个元组，我们就会记录下相关的名称和电话号码，但是所得的元组表示大卫对应于512-555-1234，而威廉对应于512-555-4321。正如我们所知，这是不正确的。

　　由于基于函数依赖的范式并不适合充分地来处理这种情况，所以其他依赖和范式也被定义了。我们在第8.6和8.7节中涉及这些问题。