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）和【 Pro
4、duct】（ ProductID， UnitPrice， ProductName）来消除原订单表中 UnitPrice， ProductName多次重复的情况。 第三范式（ 3NF）：首先是 2NF，另外非主键列必须直接依赖于主键，不能存在传递依赖。即不能存在：非主键列 A 依赖于非主键列 B，非主键列 B 依赖于主键的情况。 考虑一个订单表【 Order】（ OrderID， OrderDate， CustomerID， CustomerName， CustomerAddr，CustomerCity）主键是（ OrderID）。 其中 OrderDate， CustomerID， Custo
5、merName， CustomerAddr， CustomerCity 等非主键列都完全依赖于主键（ OrderID），所以符合 2NF。不过问题是 CustomerName， CustomerAddr，CustomerCity 直接依赖的是 CustomerID（非主键列），而不是直接依赖于主键，它是通过传递才依赖于主键，所以不符合 3NF。 通过拆分【 Order】为【 Order】（ OrderID， OrderDate， CustomerID）和【 Customer】（ CustomerID，CustomerName， CustomerAddr， CustomerCity）从而达到 3
6、NF。 第二范式（ 2NF）和第三范式（ 3NF）的概念很容易混淆，区分它们的关键点在于， 2NF：非主键列是否完全依赖于主键，还是依赖于主键的一部分； 3NF：非主键列是直接依赖于主键，还是直接依赖于非主键列。 BCNF 是比第三范式更严格一个范式。它要求关系模型中所有的属性（包括主属性和非主属性）都不传递依赖于任何候选关键字。也就是说，当关系型表中功能上互相依赖的那些列的每一列都是一个候选关键字时候，该满足 BCNF。 BCNF 实际上是在第三范式的基础上，进一步消除了主属性的传递依赖。 3 举例 有这样一个配 件管理表 WPE(WNO,PNO,ENO,QNT),其中 WNO 表示仓库号，
7、 PNO 表示配件号， ENO 表示职工号， QNT 表示数量。 有以下约束要求： （ 1） 一个仓库有多名职工； （ 2） 一个职工仅在一个仓库工作； （ 3） 每个仓库里一种型号的配件由专人负责，但一个人可以管理几种配件； （ 4） 同一种型号的配件可以分放在几个仓库中。 分析表中的函数依赖关系，可以得到： （ 1） ENO-WNO; （ 2） （ WNO， PNO） -QNT （ 3） （ WNO， PNO） -ENO （ 4） （ ENO， PNO） -QNT 可以看到，候选键有：（ ENO,PNO） ;(WNO,PNO)。所以， ENO,PNO,WNO 均为主属性， QNT为非主属性
8、。显然，非主属性是直接依赖于候选键的。所以此表满足第三范式。 而我们观察一下主属性：（ WNO,PNO） -ENO;ENO-WNO。显然 WNO 对于候选键（ WNO,PNO）存在传递依赖，所以不符合 BCNF. 解决这个问题的办法是分拆为两个表：管理表 EP（ ENO， PNO， QNT）；工作表 EW（ ENO，WNO）。但这样做会导致函数依赖（ WNO,PNO） -ENO 丢失。 4 应用 虽然，不满足 BCNF，也会导致一些冗余和一致性的问题。但是，将表分解成满足 BCNF的表又可能丢失一些函数依赖。所以，一般情况下不会强制要求关系表要满足 BCNF。 第四范式（ 4NF） 1 定义
9、第四范式需要满足以下要求： （ 1） 必须满足第三范式 （ 2） 表中不能包含一个实体的两个或多个互相独立的多值因子。 2 说明 显然，第四范式也是一个比第三范式严格的范式。 第四范式的意思是：当一个 表中的非主属性互相独立时（ 3NF），这些非主属性不应该有多值。若有多值就违反了第四范式。定义比较抽象，可以参照下面的例子理解。 3 举例 有这样一个用户联系方式表 TELEPHONE(CUSTOMERID,PHONE,CELL)。 CUSTOMERID 为用户ID,PHONE 为用户的固定电话 ,CELL 为用户的移动电话。 本来，这是一个非常简单的第 3 范式表。主键为 CUSTOMERID
10、，不存在传递依赖。但在某些情况下，这样的表还是不合理的。比如说，用户有两个固定电话，两个移动电话。这时，表的具体表示如 下： CUSTOMERID PHONE CELL 1000 8828-1234 149088888888 1000 8838-1234 149099999999 由于 PHONE 和 CELL 是互相独立的，而有些用户又有两个和多个值。这时此表就违反第四范式。 在这种情况下，此表的设计就会带来很多维护上的麻烦。例如，如果用户放弃第一行的固定电话和第二行的移动电话，那么这两行会合并吗？等等 解决问题的方法为，设计一个新表 NEW_PHONE(CUSTOMERID,NUMBER,
11、TYPE).这样就可以对每个用户处理不同类型的多个电话号码，而不会违反第四范式。 4 应用 显然，第四范式的应用范围比较小，因为只有在某些特殊情况下，要考虑将表规范到第四范式。所以在实际应用中，一般不要求表满足第四范式。 第五范式（ 5NF） 1 定义 第五范式有以下要求： （ 1） 必须满足第四范式 （ 2） 表必须可以分解为较小的表，除非那些表在逻辑上拥有与原始表相同的主键。 2 说明 第五范式是在第四范式的基础上做的进一步规范化。 第四范式处理的是相互独立的多值情况，而第五范式则处理相互依赖的多值情况。 3 举例 有一个销售信息表 SALES（ SALEPERSON， VENDOR， P
12、RODUCT）。 SALEPERSON 代表销售人员， VENDOR 代表供和商， PRODUCT 则代表产品。 在某些情况下，这个表中会产生一些冗余。可以将表分解为 PERSON_VENDOR 表（ SALEPERSON， VENDOR）； PERSON_PRODUCT 表（ SALEPERSON， PRODUCT）； VENDOR-_PRODICT 表（ VENDOR， PRODUCT）。 二、 分布式数据库系统的透明性 1.分片透明性 ：用户不必关心数据是如何分片，他们对数据的操作在全局关系上进行的，即关心如何分片对用户是透明的，因此，当分片改变时应用程序可以不变。 *分片透明性是最高层
13、次的透明性，如果用户能在全局关系一级操作，则数据如何分布，如何存储等细节不必关心，其应用程序的编写与集中式 数据库 相同。 2.复制透明性 ：用户不用关心数据库在网络中的各个节点的复制情况，被复制的数据的更新都由系统自动完成。 *在分布式数据库系统中，可以把一个 场地的数据复制到其他场地存放，应用程序可以使用复制到本地的数据在本地完成分布式操作，避免通过网络传输数据，提高了系统的运行和查询效率。但是对于复制数据的更新操作，就要涉及到对所有复制数据的更新。 3.位置透明性 ：用户不必知道所操作的数据放在何处，即数据分配到哪个或哪些站点存储对用户是透明的。因此，数据分片模式的改变，如把数据从一个站
14、点转移到另一个站点将不会影响应用程序，因而应用程序不必改写。 4.逻辑透明性 （局部映像透明性）：它是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关心局部 DBMS 支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，局部映像透明性对异构型和同构异质的分布式数据库系统时非常重要的。 三、 堆得简单介绍以及堆排序 首先看一下堆的定义： 对于 n 个元素的序列 k1,k2,k3,kn，当且仅当满足下列关系时，称之为堆： K(i) = K(2*i) int numN = -1,49,38,65,97,76,13,27; /从第一个元素开始存储 /
15、调整堆的函数 void heapAdjust(int pos,int total) int temp = numpos; for(int j = 2 * pos; j = numj) /不需要再继续向下调整了 break; numpos = numj; pos = j; numpos = temp; void heapSort() /首先将数组构建成一个大顶堆 for(int i = (N-1) / 2;i =1;-i) heapAdjust(i,N - 1); /开始堆排序 for(int i = N-1; i 1; -i) int temp = numi; /交换第一个元素和最后一个元素
16、numi = num1; num1 = temp; heapAdjust(1,i - 1); /交换完之后，重新调整堆 四、 UML 类图 类图（ Class Diagram） : 类图是面向对象系统建模中最常用和最重要的图，是定义其它图的基础。类图主要是用来显示系统中的类、接口以及它们之间的静态结构和关系的一种静态模型。 类图的 3 个基本组件：类名、属性、方法。 泛化 (generalization)：表示 is-a 的关系，是对象之间耦合度最大的一种关系，子类继承父类的所有细节。直接使用语言中的继承表达。在类图中使用带三角箭头的实线表示，箭头从子类指向父类。 实现（ Realization） :在类图中就是接口和实现的关系。这个没什么好讲的。在类图中使用带三角箭头的虚线表示，箭头从实现类指向接口。 依赖 (Dependency)：对象之间最弱的一种关联方式，是临时性的关联。代码中一般指由局部变量、函数参数、返回值建立的 对于其他对象的调用关系。一个类调用被依赖类中的某些方法而得以完成这个类的一些职责。在类图使用带箭头的虚线表示，箭头从使用类指向被依赖的类。
