浙江省计算机三级数据库复习资料

浙江省计算机三级数据库复习资料数据结构基础数据结构的基本概念及有关术语：数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。表示一个事物的一组数据称为一个数据元素，数据元素是数据的基本单位。它可以是一个不可分割的原子项，也可以由多个数据项组成。

数据类型是指一个类型和定义在这个类型上的操作集合。数据结构（datastructure）指数据元素之间存在的关系数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常被称为数据结构。根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构和图，其中树结构和图又称为非线性结构。P2数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立与计算机的。而数据的存储结构是逻辑结构在计算机内存中的实现，是依赖于计算机的。数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法分析主要包含时间代价和空间代价两个方面。时间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。空间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。算法的时间及空间复杂性度量算法的时间效率算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。T(n)=O(f(n))度量算法的空间效率空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用的存储空间。S(n)=O(f(n))基本数据结构及其操作：线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,a(n-1)组成的有限序列。P36线性表的逻辑结构：其中，元素ai的数据类型可以是整数、浮点数、字符或类；n是线性表的元素个数，称为线性长度。若n=0,则为空表；若n>0,ai(0<i<n-1)有且仅有一个前驱元素a(i-1),没有后继元素a(i+1),a0没有前驱元素，a(n-1)没有后继元素线性表的存储结构（顺序存储、链式存储）线性表的顺序存储结构使用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。顺序存储的线性表也称为顺序表。线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。插入、删除操作单链表的插入操作：空表插入/头插入if(head==null)head=newNode<T>(x,null);//空表插入else{Node<T>q=newNode<T>(x,null);//头插入q.next=head;head=q;}中间插入/尾插入Node<T>q=newNode<T>(x,null);次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。孩子优先：先根次序：访问根结点，遍历左子树，遍历右子树。中根次序：遍历左子树，访问根结点，遍历右子树。后根次序：遍历左子树，遍历右子树，访问根结点二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树。哈夫曼树定义为带权外路径长度最短的二叉树路径长度：从根结点到所有结点的路径长度之和(a)、(b)、（c）、(d)的路径长度为1x2+2x2+3x2=12外路径长度：从根结点到所有叶子结点的路径长度之和(a)、(b)、（c）、(d)的外路径长度为2+3x2+1=9从根到X结点的带权路径长度是X结点的权值与从根到X结点路径长度的乘积。所有叶子结点的带权路径长度之和称为二叉树的带权外路径长度。二叉树的带权外路径长度检索方法：（P259）顺序查找算法描述为：从线性表的一端开始，依次将每个元素的关键字与给定值进行比较，若有相等者，则查找成功；否则比较继续，直到比较完所有元素，仍未有相等者，则查找不成功，给出结果信息。平均查找长度为（n+1）/2,查找一个元素的平均比较次数为n，查找失败需比较n+1次，时间复杂度为O(n)。查找成功的平均查找长度：查找失败的平均查找长度：（P262）二分查找又叫折半查找，时间复杂度为O(log2n)。折半查找算法分析排序方法：直接插入排序总的关键码比较次数为n^2/4，总的记录移动个数也约为n^2/4；二分法插入排序关键码比较次数为O(nlog2n),记录移动个数为O(n^2)；shell排序法的关键码比较次数和记录移动个数均为n^1.3左右。冒泡排序的最坏时间复杂度为O(n2),最好的时间复杂度为O(n)，算法的平均时间复杂度为O(n2)。快速排序的最坏时间为O(n^2)，平均时间复杂度为(nlgn)。插入排序：每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，依此重复，直到全部元素插入完毕。直接插入排序数据序列已排序（最好情况）的时间复杂度为O（n）数据序列反序排列（最坏情况）的时间复杂度为O（n的平方）数据序列随机排列的时间复杂度为O（n的平方）折半插入排序希尔排序交换排序冒泡排序的基本思想是：比较相邻两个元素的关键字值，如果反序，则交换。若按升序排序，每趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出来一样。快速排序是一种分区交换排序算法。快速排序的基本思想是;在数据序列中选择一个值作为比较的基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，见大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。同时，序列被划分成两个子序列，再用同样的方法分别对两个子序列进行排序，直到子序列的长度为1，则完成排序。选择排序直接选择排序的基本思想是：第一趟从n个元素的数据序列中选出关键字最小（或最大）的元素并放到最前（或最后）位置，下一趟再从n-1个元素中选出最小（大）的元素并放到次前（后）位置。以此类推，经过n-1趟完成排序堆排序（1）创建最小堆（2）堆排序归并排序数据库系统数据库的基本概念：信息是经过加工处理并对人类社会实践和生产活动产生决策影响的数据。数据是人们用于记录事物情况的物理符号。为了描述客观事物而用到的数字、字符以及所有能输入到计算机中并能被计算机处理的符号都可以看作是数据。数据处理是指将数据转换成信息的过程。它包括对数据的收集、存储、分类、计算、加工、检索和传输等一系列活动。数据库系统的组成与结构数据库系统是由计算机系统、数据库及其描述机构、数据库管理系统和有关人员组成。考察数据库系统的结构可以有多种不同的层次或不同的角度。从数据管理系统的角度看，数据库通常采用三级模式结构，这是数据库管理系统的内部结构；从数据库最终用户的角度看，数据库系统的结构可分为集中式结构、分布式结构、客户/服务器结构、并型结构，这是数据库系统的外部的体系结构。这里主要介绍数据库系统的内部结构——当前大部分数据库系统采用的三级模式结构。数据库系统三级模式结构的概念和原理及其数据独立性它包括外模式、模式和内模式。模式：是整个数据库当中所有实体和关系的集合，是所有用户的公共数据视图，与应用无关。每个数据库中只有一个模式，也称逻辑模式。外模式：是模式的一个子集，或是模式的一个局部表现形态。内模式：也叫存储模式，是对模式的数据及数据的定义内容进行组织、存储的表达形式，在什么地方存储、如何存储是内模式要解决的内容根据各类人员与数据库的不同关系，可把视图（所谓视图是指观察、认识和理解数据的范围、角度和方法）分为三种：对应于用户的外部视图对应于应用程序员的概念视图对应于系统程序员的内部视图数据库系统的数据模型：常见的数据模型：层次数据模型、网状数据模型、关系数据模型。层次：通过树形结构表示实体及联系。如描述学校管理机构。每个结点表示一个实体（型），箭头表示实体（型）间的联系（由父到子）。层次数据模型主要特点：有且仅有一个根结点；每个非根结点有且仅有一个父(直接上层)结点。它最适合表示实体的一对多联系。网状：通过网状结构表示实体及联系。“网”中每个结点表示一个实体(型)，结点之间箭头表示实体(型)间的联系。网状数据模型主要特点：网状数据模型可能有多个根结点，某些非根结点可能有多个父结点，适合表示实体的多对多联系。层次与网状模型优缺点:优点:能直观、形象地描述实体及其联系，易于被人们所理解和掌握。缺点:数据结构较复杂，存储数据需要更多的链接指针；在检索数据时，需要考虑数据的存储路径；在插入或删除数据时，涉及到调整链接指针。关系关系模型与层次模型和网状模型相比有着本质的差别，它是用二维表格来表示实体及其相互之间的联系。一个关系就是没有重复行和重复列的二维表，二维表的每一行在关系中称为元组，每一列在关系中称为属性。学生关系的每一行代表一个学生的记录，每一列代表学生记录的一个字段。属性个数（n）称为关系的元。关系、关系模式、关系数据库模式、关系数据库的定义（关系、元组、属性、域、关键字、数据项）关系：关系的描述称为关系模式，可以表示为R(U,D,DOM,F)R为关系名，U为属性名集合，D为域集合，DOM为属性向域的映像集合，F为属性间的依赖关系集合关系模式是型，关系是值例：学生选修课成绩登记表，定义关系模式SC如下：SC（{sno,cno,grade},{N(6),N(3)},{(sno,N(6)),(cno,N(3)),(grade,N(3))},{(sno,cno)→grade}）关系模式：关系的描述称为关系模式，可以表示为R(U,D,DOM,F)R为关系名，U为属性名集合，D为域集合，DOM为属性向域的映像集合，F为属性间的依赖关系集合关系模式是型，关系是值例：学生选修课成绩登记表，定义关系模式SC如下：SC（{sno,cno,grade},{N(6),N(3)},{(sno,N(6)),(cno,N(3)),(grade,N(3))},{(sno,cno)→grade}）关系数据库：关系数据库基本概念关系数据库就是一些相关的二维表和其他数据库对象的集合。关系数据库中的所有信息都存储在二维表格中；一个关系数据库可能包含多个表；除了这种二维表外，关系数据库还包含一些其他对象，如视图等。1．关系一个关系就是一张二维表，通常将一个没有重复行、重复列的二维表看成一个关系，每个关系都有一个关系名。2．元组二维表的每一行在关系中称为元组(Tuple)。一行描述了现实世界中的一个实体，或者描述了不同实体间的一种联系。3．属性二维表的每一列在关系中称为属性(Attribute)，每个属性都有一个属性名，各个属性的取值称为属性值。每个属性有一定的取值范围，称为值域。4．关键字关系中能惟一区分、确定不同元组的属性或属性组合，称为该关系的一个关键字。关键字又称为键或码(Key)。码候选码能唯一标示一个元组的属性组主码多个候选码中的主要应用属性组，其中的每个属性都称为主属性，不属于任何候选码的属性称为非码属性合成码码含有多个属性外码不是当前关系的码，但是其他关系中的主码全码所有属性共同组成关系模式的候选码5．域（集合）域是一组具有相同数据类型的值的集合。6.主属性和非主属性定义5设Ai是关系模式R的一个属性，若Ai属于R的某个候选关键属性，称Ai是R的主属性，否则，称Ai为非主属性。关系运算：选择、投影、集合并运算、集合差运算、笛卡儿积、连接运算符含义运算符含义集合运算符∪－∩并差交逻辑运算符┐Λν非与或专门的关系运算符×σ∏∞%广义笛卡尔积选择投影连接除比较运算符≥>≤<=≠大于等于大于小于等于小于等于不等于1.选择（selection）:对关系而言，选择是从行的角度取关系的子集公式表示:R[F]或σF(R)={t|t∈RΛF(t)=True}公式的含义：R中使布尔函数为真的元组集，F为布尔函数，即限定条件F的基本形式为：x1θy1[Φx2θy2……],其中θ为比较运算符，Φ为逻辑运算符，x1,y1是属性名或常量，属性名也可用序号表示例：σ5=‘IS’(student)或student[5=‘IS’]σSage<19(student)或student[Sage<19]2.投影（projection）:对关系而言，投影是从列的角度取关系的子集公式表示:R[A]或∏A(R)={t[A]|t∈R}公式的含义：包含A中各属性组的元组集投影之后不仅取消了某些属性列，而且还可能取消某些元组例：∏Sname,Sdept(student)或student[Sname,Sdept]∏2,5(student)或student[2,5]3.集合并（union）R∪S={t|t∈Rνt∈S}R、S为同类关系（关系的度相同，且相应属性都来自相同的域），并的结果与R、S也是同类关系R和S具有相同的目n相应的属性取自同一个域R-S仍为n目关系，由属于R而不属于S的所有元组组成

R-S={t|tR∧tS}4.集合差（difference）R－S={t|t∈RΛ┐t∈S}={t|t∈RΛt∈S}R、S为同类关系，差的结果与R、S也是同类关系R和S具有相同的目n相应的属性取自同一个域R-S仍为n目关系，由属于R而不属于S的所有元组组成

R-S={t|tR∧tS}5．笛卡尔积给定一组域D1,D2，...，Dn，这些域可以完全不同，也可以部分或全部相同，D1、D2、…、Dn的笛卡尔积为：D1×D2×…×Dn={(d1，d2，…，dn)|di∈Di，i=1，2，…，n}，其中每一个元素(d1，d2，…，dn)称作一个n元组（n-tuple）或简称元组，它的每个元素di取自对应的集合Di。元组中的每一个值di称作一个分量（component）若di为有限集，其基数为mi(i=1,2,3…n),则D1×D2×…×Dn的基数为m=∏mi例如，设A={1，2}，B={a，b}，则A×B={(1，a)，(1，b)，(2，a)，(2，b)}。6.连接（join）:公式表示:R∞FS或R[F]S={trts|tr∈RΛts∈SΛF(tr,ts)=True}或表示为：R∞AθBS或R[F]S={trts|tr∈RΛts∈SΛtr[A]θts[B])=True}公式的含义：从两个关系的笛卡尔积中选取属性间满足一定条件的元组关系数据库基本概念：函数依赖的基本概念定义1对于R中属性X的任何一个具体值，Y仅有唯一的具体值与之对应，则称R的属性Y函数依赖于属性X。记为：X→Y，X称为决定因素。完全函数依赖、部分函数依赖定义2在R中，如果属性集Y函数依赖于属性集X，且不函数依赖于X的任意真子集，则称Y完全函数依赖于X，记做：XY，否则，称Y部分函数依赖于X，记做：XY。例：关系SC(Sno,Cno,Grade)中，由于SnoGrade,CnoGrade，所以有(Sno,Cno)Grade传递函数依赖定义3设X，Y，Z是关系模式R的不同属性集，若XY(并且Y∈X)，YZ，称X传递决定Z，或称Z传递函数依赖于X，记做XZ。例：如关系Std(Sno,Sdept,Mname)中，有Sno→Sdept，Sdept