《评测师考试知识点整理》由会员分享，可在线阅读，更多相关《评测师考试知识点整理（25页珍藏版）》请在金锄头文库上搜索。
1、一、 数据库范式范式：英文名称是 Normal Form，它是英国人 E.F.Codd（关系数据库的老祖宗）在上个世纪70年代提出关系数据库模型后总结出来的，范式是关系数据库理论的基础，也是我们在设计数据库结构过程中所要遵循的规则和指导方法。目前有迹可寻的共有8种范式，依次是：1NF，2NF，3NF，BCNF，4NF，5NF，DKNF，6NF。通常所用到的只是前三个范式，即：第一范式（1NF），第二范式（2NF），第三范式（3NF）。下面就简单介绍下这三个范式。 第一范式（1NF）：强调的是列的原子性，即列不能够再分成其他几列。 考虑这样一个表：【联系人】（姓名，性别，电话） 如果在实际场景中
2、，一个联系人有家庭电话和公司电话，那么这种表结构设计就没有达到 1NF。要符合 1NF 我们只需把列（电话）拆分，即：【联系人】（姓名，性别，家庭电话，公司电话）。1NF 很好辨别，但是 2NF 和 3NF 就容易搞混淆。 第二范式（2NF）：首先是 1NF，另外包含两部分内容，一是表必须有一个主键；二是没有包含在主键中的列必须完全依赖于主键，而不能只依赖于主键的一部分。 考虑一个订单明细表：【OrderDetail】（OrderID，ProductID，UnitPrice，Discount，Quantity，ProductName）。 因为我们知道在一个订单中可以订购多种产品，所以单单一个
3、OrderID 是不足以成为主键的，主键应该是（OrderID，ProductID）。显而易见 Discount（折扣），Quantity（数量）完全依赖（取决）于主键（OderID，ProductID），而 UnitPrice，ProductName 只依赖于 ProductID。所以 OrderDetail 表不符合 2NF。不符合 2NF 的设计容易产生冗余数据。 可以把【OrderDetail】表拆分为【OrderDetail】（OrderID，ProductID，Discount，Quantity）和【Product】（ProductID，UnitPrice，ProductName）
4、来消除原订单表中UnitPrice，ProductName多次重复的情况。 第三范式（3NF）：首先是 2NF，另外非主键列必须直接依赖于主键，不能存在传递依赖。即不能存在：非主键列 A 依赖于非主键列 B，非主键列 B 依赖于主键的情况。 考虑一个订单表【Order】（OrderID，OrderDate，CustomerID，CustomerName，CustomerAddr，CustomerCity）主键是（OrderID）。 其中 OrderDate，CustomerID，CustomerName，CustomerAddr，CustomerCity 等非主键列都完全依赖于主键（Order
5、ID），所以符合 2NF。不过问题是 CustomerName，CustomerAddr，CustomerCity 直接依赖的是 CustomerID（非主键列），而不是直接依赖于主键，它是通过传递才依赖于主键，所以不符合 3NF。 通过拆分【Order】为【Order】（OrderID，OrderDate，CustomerID）和【Customer】（CustomerID，CustomerName，CustomerAddr，CustomerCity）从而达到 3NF。 第二范式（2NF）和第三范式（3NF）的概念很容易混淆，区分它们的关键点在于，2NF：非主键列是否完全依赖于主键，还是依赖于
6、主键的一部分；3NF：非主键列是直接依赖于主键，还是直接依赖于非主键列。 BCNF是比第三范式更严格一个范式。它要求关系模型中所有的属性（包括主属性和非主属性）都不传递依赖于任何候选关键字。也就是说，当关系型表中功能上互相依赖的那些列的每一列都是一个候选关键字时候，该满足BCNF。BCNF实际上是在第三范式的基础上，进一步消除了主属性的传递依赖。3举例有这样一个配件管理表WPE(WNO,PNO,ENO,QNT),其中WNO表示仓库号，PNO表示配件号，ENO表示职工号，QNT表示数量。有以下约束要求：（1）一个仓库有多名职工；（2）一个职工仅在一个仓库工作；（3）每个仓库里一种型号的配件由专人
7、负责，但一个人可以管理几种配件；（4）同一种型号的配件可以分放在几个仓库中。分析表中的函数依赖关系，可以得到：（1）ENO-WNO;（2）（WNO，PNO）-QNT（3）（WNO，PNO）-ENO（4）（ENO，PNO）-QNT可以看到，候选键有：（ENO,PNO）;(WNO,PNO)。所以，ENO,PNO,WNO均为主属性，QNT为非主属性。显然，非主属性是直接依赖于候选键的。所以此表满足第三范式。而我们观察一下主属性：（WNO,PNO）-ENO;ENO-WNO。显然WNO对于候选键（WNO,PNO）存在传递依赖，所以不符合BCNF.解决这个问题的办法是分拆为两个表：管理表EP（ENO，PN
8、O，QNT）；工作表EW（ENO，WNO）。但这样做会导致函数依赖（WNO,PNO）-ENO丢失。4应用虽然，不满足BCNF，也会导致一些冗余和一致性的问题。但是，将表分解成满足BCNF的表又可能丢失一些函数依赖。所以，一般情况下不会强制要求关系表要满足BCNF。第四范式（4NF）1定义第四范式需要满足以下要求：（1）必须满足第三范式（2）表中不能包含一个实体的两个或多个互相独立的多值因子。2说明显然，第四范式也是一个比第三范式严格的范式。第四范式的意思是：当一个表中的非主属性互相独立时（3NF），这些非主属性不应该有多值。若有多值就违反了第四范式。定义比较抽象，可以参照下面的例子理解。3举例
9、有这样一个用户联系方式表TELEPHONE(CUSTOMERID,PHONE,CELL)。CUSTOMERID为用户ID,PHONE为用户的固定电话,CELL为用户的移动电话。本来，这是一个非常简单的第3范式表。主键为CUSTOMERID，不存在传递依赖。但在某些情况下，这样的表还是不合理的。比如说，用户有两个固定电话，两个移动电话。这时，表的具体表示如下：CUSTOMERIDPHONECELL10008828-123414908888888810008838-1234149099999999由于PHONE和CELL是互相独立的，而有些用户又有两个和多个值。这时此表就违反第四范式。在这种情况下
10、，此表的设计就会带来很多维护上的麻烦。例如，如果用户放弃第一行的固定电话和第二行的移动电话，那么这两行会合并吗？等等解决问题的方法为，设计一个新表NEW_PHONE(CUSTOMERID,NUMBER,TYPE).这样就可以对每个用户处理不同类型的多个电话号码，而不会违反第四范式。4应用显然，第四范式的应用范围比较小，因为只有在某些特殊情况下，要考虑将表规范到第四范式。所以在实际应用中，一般不要求表满足第四范式。第五范式（5NF）1定义第五范式有以下要求：（1）必须满足第四范式（2）表必须可以分解为较小的表，除非那些表在逻辑上拥有与原始表相同的主键。2说明第五范式是在第四范式的基础上做的进一步
11、规范化。第四范式处理的是相互独立的多值情况，而第五范式则处理相互依赖的多值情况。3举例有一个销售信息表SALES（SALEPERSON，VENDOR，PRODUCT）。SALEPERSON代表销售人员，VENDOR代表供和商，PRODUCT则代表产品。在某些情况下，这个表中会产生一些冗余。可以将表分解为PERSON_VENDOR表（SALEPERSON，VENDOR）；PERSON_PRODUCT表（SALEPERSON，PRODUCT）；VENDOR_PRODICT表（VENDOR，PRODUCT）。二、 分布式数据库系统的透明性1.分片透明性：用户不必关心数据是如何分片，他们对数据的操作在
12、全局关系上进行的，即关心如何分片对用户是透明的，因此，当分片改变时应用程序可以不变。*分片透明性是最高层次的透明性，如果用户能在全局关系一级操作，则数据如何分布，如何存储等细节不必关心，其应用程序的编写与集中式数据库相同。2.复制透明性：用户不用关心数据库在网络中的各个节点的复制情况，被复制的数据的更新都由系统自动完成。*在分布式数据库系统中，可以把一个场地的数据复制到其他场地存放，应用程序可以使用复制到本地的数据在本地完成分布式操作，避免通过网络传输数据，提高了系统的运行和查询效率。但是对于复制数据的更新操作，就要涉及到对所有复制数据的更新。3.位置透明性：用户不必知道所操作的数据放在何处，
13、即数据分配到哪个或哪些站点存储对用户是透明的。因此，数据分片模式的改变，如把数据从一个站点转移到另一个站点将不会影响应用程序，因而应用程序不必改写。4.逻辑透明性（局部映像透明性）：它是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关心局部DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，局部映像透明性对异构型和同构异质的分布式数据库系统时非常重要的。三、 堆得简单介绍以及堆排序首先看一下堆的定义：对于n个元素的序列k1,k2,k3,kn，当且仅当满足下列关系时，称之为堆：K(i) = K(2*i) & K(i) = K(2*i)
14、& K(i) = K(2*i+1) 此时的堆为大顶堆（i = 1,2,，n/2(下取整)）注意：堆得存储是用一维数组来存储的。若将堆对应的序列看成是一个完全二叉树，则堆得含义表明：完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值。因此，若序列K1,K2,Kn 是大顶堆，则堆顶元素必为序列中n个元素的最大值；反之，若序列是小顶堆，则堆顶元素必为序列中n个元素的最小值。堆排序就是利用的这个性质。堆排序的过程如下：假设要从小到大排序，我们构建一个大顶堆，则堆顶元素是最大值。将堆顶元素和最后一个元素互换，则最后一个元素变成了n个元素中的最大值。之后再将剩下的 n-1 个元素调整成为
15、大顶堆，将堆顶元素和第n-1 个元素互换，则第n-1 个元素变成了n个元素中的次大值循环这个过程，不断调整堆，最后得到一个有序的序列。在上面堆排序的过程中，有两个问题需要解决：（1）如何将一个初始的序列构建成一个大顶堆？（2）再得到最大元素后，剩下的n-1个元素如何再次调整成为一个大顶堆？实际上，初始序列构建大顶堆也是一个不断调整堆得过程。因此，只要解决第二个问题就可以。下图是一个大顶堆：当把堆顶元素20和最后一个元素互换之后，最后一个元素变成了序列中的最大值。如下图：但是，此时堆顶元素违反了大顶堆的性质，堆顶元素的左右孩子仍旧满足大顶堆的性质。因此，此时需要对堆进行调整。因为左子树的值大于右子树的值，所以将3和17互换，如下图：此时，左子树又违反了大顶堆得性质，所以需要调整左子树，如下图：至此，一次调整完毕，堆顶元素成为了次大元素
