前言

晚上床上玩手机有点上头，导致一整天下午之前都没怎么精神刷课，于是调整了下学这套课程的排期，多排了一天嘻嘻，这下轻松多了。

本文是学习standford CS145 Introduction to Databases系列视频的第三篇笔记，主要包括第七章到第九章的内容：

  1. 关系型数据库设计
  2. XML的查询
  3. 统一建模语言(Unified Modeling Language， or UML)

相关参考资料：

视频链接：Introduction to Databases - Jennifer Widom - Stanford

函数依赖、部分依赖、传递依赖等准备知识：范式通俗理解：1NF、2NF、3NF和BNCF-CSDN博客

关系模式的分解原则：【数据库原理】（18）关系模式的分解 - 知乎 (zhihu.com)

三范式和BCNF的举例：数据库三范式和BCNF范式的理解：生动举例-CSDN博客

3NF和BCNF的区别：Difference Between 3NF and BCNF (with Comparison Chart) - Tech Differences

组合和聚合：UML一一 类图关系 (泛化、实现、依赖、关联、聚合、组合)_uml类图关系-CSDN博客

一、关系型数据库设计

1. 基本概念

现有关系表$R$，关系表的所有属性的集合为$U$

设$X$、$Y$和$Z$皆为$R$上的一组属性，即$ X, Y, Z \subseteq U$

1.1 函数依赖(Functional Dependencies)

(1) 定义

对 $ \forall t, u \in R$，如果 $t[X] = u[X]$，则有 $ t[Y] = u[Y]$，其中$ t[X]$代表取元组$t$所有$X$中的属性

则称，$Y$依赖于$X$，记为$X \rightarrow Y$

讲人话就是确定了$X$就确定了$Y$，称$Y$依赖于$X$

(2) Trivial or Nontrivial

trivial意为平常的、琐碎的、不重要的，所以trivial的Functional Dependency（以下简称FD）就是在讲废话，不能传递更多信息。

Trivial FD：当$ Y \subseteq X$，我们称$X \rightarrow Y$是 Trivial FD。因为确定了$X$肯定就确定了它的子集$Y$（讲废话

Nontivial FD：相对地，当$Y \nsubseteq X$，我们称 $ X \rightarrow Y$是 Nontrivial FD。

Complete nontrivial FD：当$X$和$Y$完全不重合时，即$ Y \cap X = \varnothing $，我们称$X \rightarrow Y$是 Complete nontrivial FD

(3) 属性的闭包(Closure of Attributes)

给定许多依赖$S$，和属性集$X$

设集合 $set = X$

重复以下步骤直到$set$不发生改变:

如果有$A \rightarrow B$并且$A$在$set$当中，那么$ set = set \cup B$

最后得到的$set$成为$X$在$S$上的闭包(Closure)，记作$X^+$

讲人话，闭包就是已知许多依赖$S$，确定了$X$后，能够确定的所有属性

1.2 部分依赖

当$ X \rightarrow Y$，取$X$的一子集$X’$，若$X’ \rightarrow Y$，则称$Y$部分依赖于$X$

讲人话就是确定了$X$中一部分值就能确定了$Y$，称$Y$部分依赖于$X$

1.3 传递依赖

当$X \rightarrow Y$，并且$ Y \rightarrow Z$，并且$ Y \nrightarrow X$，则称$Z$传递依赖于$X$

讲人话就是确定了$X$能确定$Y$，确定了$Y$又能确定$Z$，并且确定了$Y$不能确定$X$（在范式比较中会提到为什么这么定义），就说$Z$传递依赖于$X$

1.4 多值依赖(Multivalued Dependencies, or MVD)

设$Z = U - X - Y$，即$Z$为属性集$U$中除了$X$和$Y$的剩余所有属性

(1) 定义

对 $ \forall t_1, t_2 \in R$，如果 $t_1[X] = t_2[X]$，则$\exists v \in R$，使得$v[X] = t_1[X] = t_2[X]$，并且$v[Y] = t_1[Y]$，并且$ v[Z] = t_2[Z]$，则称$Y$多值依赖$X$

讲人话就是，如果有$(x, y_1, z_1)$和$(x, y_1, z_2)$，则必有$(x, y_1, z_2)$和$(x, y_2, z_1)$（Y和Z是对称的），则称$Y$多值依赖$X$，记作$ Y \twoheadrightarrow X$

也就是说，确定了$X$为$x$时，$Y$和$Z$会有很多种取值$y_1, y_2, …, y_m$和$z_1, z_2, …, z_n$，$Y$和$Z$的取值的所有组合都会出现

从定义中，我们可以看出，判断$Y$是否多值依赖$X$，还需要考虑全属性集$U$。也就是说，同样的属性集$Y$和$X$，在不同的全属性集$U$中，它们可能多值依赖的关系不同。

(2) Trivial or Nontrivial

  1. Trivial MVD：当$X \cup Y = U$或$Y \subseteq X$时，称$ X \twoheadrightarrow Y$为 Trivial MVD。

如果有$(x, y_1, z_1)$和$(x, y_2, z_2)$

当$X \cup Y = U$时，$Z = \varnothing$，得$z_1 = z_2 = NULL$。那么$(x, y_1, z_2) = (x, y_1, NULL)$，$(x, y_2, z_1) = (x, y_2, NULL)$已经在表中，自行满足了多值依赖的条件，

当$Y \subseteq X$时，有$X \rightarrow Y$，得$y_1 = y_2$。那么$(x, y_1, z_2) = (x, y_2, z_2)$，$(x, y_2, z_1) = (x, y_1, z_1)$已经在表中自行满足了多值依赖的条件

所以满足以上其中一种条件的多值依赖不能传递更多的信息，可称为Trivial MVD

  1. Nontrivial MVD：当$Y$和$X$不满足以上条件，则称$X \twoheadrightarrow Y$为Nontrivial MVD

2. 分解关系模式(Decompostion of Relational Schema)

2.1 分解的原则

将关系$R(U)$分解为$R_1(U_1)$和$R_2(U_2)$后，应当满足：

  1. $U_1 \cup U_2 = U$
  2. $R_1 \bowtie R_2 = R$ （无损连接性）

实际上满足第二条就会满足第一条（小声

“Good” Decomposition，也就是一个好的分解，应当满足无损连接性（能通过自然连接得到原始表）和依赖保留性（能在每个表中直接得到原来的所有依赖），详见前言中的参考资料

2.2 BCNF分解

(1) BCNF的定义

注意：在实际情况中，可能不止有一组元素能够作为主键，比如$X^+ = U$，$Y^+ = U$，那么称$X$和$Y$都为超键，去掉超键中任意属性会使其不再为超键的，叫做候选键，我们可以在多个候选键中选一个叫主键。

假设$X$和$Y$都是候选键，$X \cup Y$也就是$X$和$Y$中的所有元素都称作主属性。而不是只有我们选定的主键中的元素才叫做主属性

对$R$中任一nontrivial FD$X \rightarrow Y$，$X$都是候选键的超集，那么就称$R$满足 鲍依斯-科得范式(Boyce Codd Normal Form, or BCNF)

(2) BCNF分解算法

找到$R$中的候选键

重复以下步骤直到所有的关系都满足BCNF:

  1. 关系$R’$的依赖$A \rightarrow B$不满足BCNF
  2. 将$R’$ 分解为 $R_1 = (A, B)$和$ R_2(A, rest)$，$rest$为$A$和$B$之外的剩余部分
  3. 找到$R_1$和$R_2$中的FD和候选键

2.3 4NF分解

(1) 4NF的定义

对$R$中任一nontrivial MVD$X \twoheadrightarrow Y$，$X$都是候选键的超集，那么就称$R$满足4NF

(2) 4NF分解算法

找到$R$中的候选键

重复以下步骤直到所有的关系都满足4NF:

  1. 关系$R’$的依赖$A \twoheadrightarrow B$不满足4NF
  2. 将$R’$ 分解为 $R_1 = (A, B)$和$ R_2(A, rest)$，$rest$为$A$和$B$之外的剩余部分
  3. 找到$R_1$和$R_2$中的MVD和候选键

3. 范式之间的比较

3.1 每一层范式解决的问题

  • 1NF：每个元组的每个属性的值不能是集合，不可再分关系。1NF是$R$作为关系模型的最基本的条件
  • 2NF：在1NF的基础上消除了非主属性对候选键的部分依赖，也就是非主属性不能只依赖于一部分主属性，应该完全依赖于所有主属性。
  • 3NF：在2NF的基础上消除了非主属性对候选键的传递依赖。也就是非主属性不能依赖于其他非主属性，应该直接完全依赖于所有主属性。

前面我们讲到了传递依赖的定义：

当$X \rightarrow Y$，并且$ Y \rightarrow Z$，并且$ Y \nrightarrow X$，则称$Z$传递依赖于$X$

这里要求$ Y \nrightarrow X$是因为，如果$ Y \rightarrow X$，那么$Z$部分依赖于$Y$，而部分依赖已经在2NF中消除了。

3NF究竟还遗留了哪些问题？

我们现在只解决了主属性和非主属性之间的冗余，而BCNF希望解决多个候选键之间，也就是主属性之间的冗余。

当然，如果关系中只有一个候选键，那么3NF和BCNF其实没什么区别。要举出有多个后续键的例子比较困难，所以很难区分喵qwq

  • BCNF：在3NF的基础上消除了候选键之间的部分依赖和传递依赖。

至此，我们已经解决的冗余都是针对依赖关系而言，而依赖是一对一的。

倘若我们有$X \twoheadrightarrow Y$，剩余部分为$Z$，其中$X$对$Y$是1对m，$X$对$Z$是1对n，他们的组合就有$m \times n$个元组，而实际上用两个表$R_1$和$R_2$共$m + n$个元组就能表示这两个一对多的关系，而且$R_1 \bowtie R_2 = R$也符合分解的原则。

  • 4NF：在BCNF的基础上消除了nontrivial MVD。

3.2 BCNF和4NF的不足

BCNF和4NF会对所有FD和MVD做检查和分解，当分解出来的表的属性过少时，我们需要对多个表做自然连接才能验证我们原来的FD和MVD，对查询不是很友好，所以应该尽量先选择能保留更多属性的分解。然后具体问题具体分析，权衡好查询负载(Query Workload)和过分解(Over Decomposition)之间的关系。

二、XML的查询

1. XPath

视频中关于XPath的语法都能在这里找到：XPath 教程 | 菜鸟教程 (runoob.com)

主要列举一些示例方便快速复习：

1
2
3
4
5
// 谓语(Predicates)：将用于查找某些特定节点的条件嵌入到方括号[]中，将其称之为谓语
// 查询价格小于90且存在作者的姓是Ullman的一本书
// 注意：[]中的条件只针对存在
doc("BookstoreQ.xml")/Bookstore/Book[@Price < 90 and
    Authors/Author/Last_Name ="Ullman" ]/Title  
1
2
3
// 内置函数(Built-in Functions)
// 查询Remark属性中包含"great"的书
doc("BookstoreQ.xml")//Book[contains(Remark, "great" )]/Title
1
2
3
// self join
doc("BookstoreQ.xml")//Magazine[Title = 
    doc("BookstoreQ.xml")//Book/Title]
1
2
3
4
5
6
7
// axes(轴)
// 查询所有父节点不为Bookstore和不为Book的节点
doc("BookstoreQ.xml")/Bookstore//*[name(parent::*)!="Bookstore"
    and name(parent::*)!="Book"]
// 查询所有跟同层级节点有相同Title的Book或Magzine
doc("BookstoreQ.xml")/Bookstore/(Book|Magazine)[Title = 
    following-sibling::*/Title or Title = preceding-sibling::*/Title]
1
2
3
4
5
由于谓语只能表示"存在"(exists)关系，当我们想表示"任意"(forall)时，需要使用内置函数count
// 查询所有作者的First_Name都包含'J'的书
doc("BookstoreQ.xml")//Book[
    count(Authors/Author[contains(First_Name,"J”)]) = 
    count(Authors/Author/First_Name)]

2. XQuery

视频中大多数的语法能在这里找到：XQuery 教程 | 菜鸟教程 (runoob.com)

内置函数需要在XPath中查询：XPath、XQuery 以及 XSLT 函数 | 菜鸟教程 (runoob.com)

限定表达式等在上述链接找不到，可以在这里看：限定表达式 (XQuery) - SQL Server | Microsoft Learn

2.1 FLWOR表达式

1
2
3
4
5
For $var in expr
Let $var := expr
Where condition
Order by expr
Return expr

2.2 代码示例

1
2
3
4
5
// 查询价格小于90且存在作者的姓是Ullman的一本书
for $b in doc("BookstoreQ.xml")/Bookstore/Book
where $b/@Price < 90 
 and $b/Authors/Author/Last_Name = "Ullman"
return $b/Title
1
2
3
4
5
6
7
8
9
10
11
12
13
for $b in doc("BookstoreQ.xml")/Bookstore/Book

// 限定表达式 ( some | every ) <variable> in <Expression> (,...) satisfies <Expression>  
// some表示"存在"  every表示"任意"
// 查询Title中存在作者的First_Name的Book
where some $fn in $b/Authors/Author/First_Name satisfies
    contains($b/Title, $fn)
    
// 构造返回结果    
return <Book>
        { $b/Title }
        { $b/Authors/Author/First_Name }
    </Book>
1
2
3
4
5
6
// 聚合函数
// 查询所有Book的Price的平均值
<Average>
{ let $plist := doc("BookstoreQ.xml")/Bookstore/Book/@Price
    return avg($plist)}
</Average>
1
2
3
4
5
6
for $b in doc("BookstoreQ.xml")/Bookstore/Book
order by $b/@Price
return <Book>
         { $b/Title }
         <Price>{ $b/data(@Price))</Price>
       </Book>
1
2
3
4
// 过滤重复值
// distinct-values返回 值的列表，而不是 节点的列表
for $n in distinct-values(doc("Bookstore0.xml" )//Last_Name)
return <Last_Name> {$n} </Last_Name>

3. XSLT(EXtensible Stylesheet Language)

XSLT支持将XML转换为其他文档，比如XHTML。对XML的转换也可以看作是查询和构造结果

示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<xsl:stylesheet version="2.0" xmins:xsl="http://mmr.w3.org/1999/XSl/Transform"
<xsl:output method="xml" indent="yes" onit-xml-declaration-"yes" />
//外层是基本格式

// template + match匹配特定节点
<xsl:template match="Book">
<BookTitle>
    // 选择特定节点中的子节点并构造返回结果
    <xsl:value-of select="Title"/></BookTitle>
</xsl:template>

<xsl:template match="Magazine">
    <MagazineTitle> <xsl:value-of select="Title" /> </MagazineTitle>
</xsl:template>

</xsl:stylesheet>
1
2
3
4
5
6
7
8
9
10
11
// 不等号需要使用转义 小于号：$lt;  大于号$gt;
// copy-of + select返回选择到的节点
<xsl:template match="Book[@Price &lt; 90]">
    <xsl:copy-of select="." />
<xsl:template>

// 不满足所有匹配的节点和属性会成串返回，因此得作以下处理
<xsl:template match="text()" />

// 更加具体的限定条件所构造的匹配，优先度更高
// 当节点同时满足两个优先度相同的匹配规则时（最好不要，会报错），以最后一个匹配规则为结果
1
2
3
4
5
6
// apply-templates + select 将 template + select 的结果嵌入其中
<xsl:template match="*|@*|text()"
    <xsl:copy>
        <xsl:apply-templates select="*|@*|text()/>
    </xsl:copy>
</xsl:template>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<xsl:template match="/"> 
<html> 
    <body> 
    <h2>My CD Collection</h2> 
    <table border="1"> 
        <tr bgcolor="#9acd32"> 
            <th>Title</th> 
            <th>Artist</th>
            <th>Price</th> 
        </tr> 
        // for-each + select 遍历选择到的所有节点
        <xsl:for-each select="catalog/cd"> 
            // if + test 选择满足条件的节点
            <xsl:if test="price &gt; 10"> 
                <tr>
                    <td><xsl:value-of select="title"/></td>
                    <td><xsl:value-of select="artist"/></td>
                    <td><xsl:value-of select="price"/></td> 
                </tr> 
            </xsl:if> 
        </xsl:for-each> 
    </table> 
    </body> 
</html> 
</xsl:template>

三、统一建模语言(UML)

UML用图形化的表示方法描述对数据模型作建模，可以直接翻译为关系模型

1. 类(Classes)

关系模型中的每一个表可以描述为一个了类，如

Student(sID, sName, GPA)

可以与下述模型互相转换：

1
2
3
4
5
6
7
8
9
+-----------+
|  Student  |
+-----------+
|   sID pk  |
|   sName   |
|    GPA    |
+-----------+
| <methods> |     
+-----------+

2. 关联 和 关联类(Associations and Association Classes)

一个类跟另一个类有联系，即有关联，可以有一条线将两个类相连来表示，而关联所产生的附加信息我们可以用一个关联类表示，如：

1
2
3
4
5
6
7
8
9
10
11
+-------+               +-------+  
|   C1  |  Association  |   C2  |
+-------+-------+-------+-------+
|   A1  |       |       |   A2  |
+-------+       |       +-------+
                |
             +--+----+ 
             |  C3   |
             +-------+
             |  A3   | 
             +-------+

其中C1和C2关联到对方的数量可能不同，比如一个学生只能选一个专业，记为1..1，一个专业有至少一个学生修读，记为1..*，如下：

1
2
3
4
5
6
7
8
9
10
11
+-------+               +-------+  
|   C1  |  Association  |   C2  |
+-------+-------+-------+-------+
|   A1  |1..*   |   1..1|   A2  |
+-------+       |       +-------+
                |
             +--+----+ 
             |  C3   |
             +-------+
             |  A3   | 
             +-------+

实际上，如果对应的数量是0..1或者1..1，那么关联表是多余的，可以将关联的属性归到C1中，如下：

1
2
3
4
5
6
+-------+               +-------+  
|   C1  |  Association  |   C2  |
+-------+-------+-------+-------+
|   A1  |1..*       1..1|   A2  |
|   A3  |               +-------+
+-------+

3. 子类(Subclasses)

一个父类可以有很多个子类，子类拥有父类的主键和额外的属性或关联，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
            +------+
            |  C1  |
            +------+
            |  K pk|
            |  A1  |
            +--+---+
               |
 +-------------+------------+
 |             |            |
 |             |            |
+--+--+    +--+--+         +-------+               +-------+  
| C2  |    |  C3 |         |   C4  |  Association  |   C5  |
+-----+    +-----+         +-------+---------------+-------+
| A2  |    |  A3 |         |   A4  |               |   A5  |
+-----+    +-----+         +-------+               +-------+

不完整/完整(incomplete/complete)：

当子类能够表示所有的情况时，我们说这些子类是complete的，否则则是incomplete的

重叠/不相交 (overlapping/disjoint)：

当有对象能够同时属于多个子类时，我们说这些子类是overlapping的，否则则是disjoint的

将带子类的UML翻译为关系模型有多种办法：

  1. 父类建表，每一个子类就是一个表，只包含子类的属性和父类的主键，适用于disjoint + incomplete的情况
  2. 父类可不建表，每一个子类就是一个表，它不仅包含子类的属性和父类的主键，也包含父类的属性，适用于disjoint + complete的情况
  3. 用一个表包含父类和所有子类的属性：适用于heavily overlapping的情况
  1. Subclass relations contain superclass key+ specialized attrs
  2. Subclass relations contain all attributes
  3. One relation containing all superclass + subclass attrs.

4. 组合和聚合(Composition and Aggregation)

组合和聚合都是关联的特例，强调整体和部分的关系，在转换为关系模型时跟关联没有区别，但是在UML中的描述存在语义上的区别。

组合中的整体和部分具有强依赖，整体的对象负责部分的对象的生命周期，如鸟和翅膀

而聚合的整体和部分可以独立存在，如汽车和轮胎，部门和员工

详见前言中的参考资料。