计算机二级公共基础知识课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机二级公共基础知识,计算机二级公共基础知识,1,数据结构与算法,数据库设计基础,程序设计基础,软件工程基础,公共基础知识,2,数据结构与算法公共基础知识2,第一章 数据结构与算法,1.1,算法,算法：是指解题方案的准确而完整的描述。,算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。,算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：,（,1,）可行性；,（,2,）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；,（,3,）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；,（,4,）输入：一个算法有,0,个或多个输入 ，以刻画运算对象的初始情况 ；,（,5,）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。,3,第一章 数据结构与算法1.1 算法3,1.1,算法,算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。,指令系统：一个计算机系统能执行的所有指令的集合。,基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。,算法的控制结构：顺序结构、选择结构、循环结构。,算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。,算法复杂度：算法时间复杂度和算法空间复杂度。,算法时间复杂度是指执行算法所需要的计算工作量。,算法空间复杂度是指执行这个算法所需要的内存空间。,4,1.1 算法算法的基本要素：一是对数据对象的运算和操作；二是,1.2,数据结构的基本基本概念,数据结构研究的三个方面：,（,1,）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；,（,2,）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；,（,3,）对各种数据结构进行的运算。,数据结构是指相互有关联的数据元素的集合。,5,1.2 数据结构的基本基本概念数据结构研究的三个方面：5,1.2,数据结构的基本基本概念,数据的逻辑结构包含：,（,1,）表示数据元素的信息；,（,2,）表示各数据元素之间的前后件关系。,数据的存储结构有顺序、链接、索引等。,线性结构条件：,（,1,）有且只有一个根结点；,（,2,）每一个结点最多有一个前件，也最多有一个后件。,非线性结构：不满足线性结构条件的数据结构。,6,1.2 数据结构的基本基本概念数据的逻辑结构包含：6,两种最基本的存储结构,顺序存储（数组）,7,两种最基本的存储结构顺序存储（数组）7,两种最基本的存储结构,链表,不是顺序存储，用指针联系,单向链表，双向链表,效率高,单向链表 双向链表,8,两种最基本的存储结构链表8,大家应该也有点累了，稍作休息,大家有疑问的，可以询问和交流,9,大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流9,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,10,大家有疑问的，可以询问和交流可以互相讨论下，但要小声点10,栈与队列,栈与队列,相同点：都是线性结构,不同点：先进先出，后进先出,栈 队列,11,栈与队列栈与队列11,循环队列,为什么需要循环队列？,计算循环队列长度,用一个固定大小为,m,的数组来实现， 那么队列中元素个数,=(rear-front + m)%m,12,循环队列为什么需要循环队列？12,栈,典型应用,逆序输出,10,进制转换,2,进制,13,栈典型应用13,用户名,:jsj,密码,:,无,14,14,非线性结构,根结点，叶子结点,度、深度、结点数,满二叉树，完全二叉树,15,非线性结构根结点，叶子结点15,树,在树结构中，一个结点所拥有的后件的个数称为该,结点的度,所有结点中最大的度称为,树的度,。,树的最大层次称为树的,深度,。,16,树在树结构中，一个结点所拥有的后件的个数称为该结点的度16,非线性结构,树二叉树,17,非线性结构17,二叉树,定义：,二叉树,是另一种树形结构。它与树形结构的区别是：,（,1,）每个结点最多有两棵子树；,（,2,）子树有左右之分。,18,二叉树定义：二叉树是另一种树形结构。它与树形结构的区别是：1,二叉树的,5,种形态：,图,5-7,(a),(b),(c),(d),(e),19,二叉树的5种形态：图 5-7(a)(b)(c)(d)(e),完全二叉树与满二叉树,完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。,在最后一层上与满二叉树相应层次编号为一一对应，则称这棵二叉树为,完全二叉树,。,20,完全二叉树与满二叉树完全二叉树是指除最后一层外，每一层上的结,树的形态,(a),(g),(h),(f),(e),(d),(c),(b),A,A,B,A,B,A,B,B,A,C,B,E,D,A,B,C,A,B,C,Figure 7-6 A collection of binary trees,21,树的形态(a)(g)(h)(f)(e)(d)(c)(b)AA,二叉树的基本性质：,（,1,）在二叉树的第,k,层上，最多有,2,k-1,(k1),个结点；,（,2,）深度为,m,的二叉树最多有,2,m,-1,个结点；,（,3,）度为,0,的结点（即叶子结点）总是比度为,2,的结点多一个；,（,4,）具有,n,个结点的二叉树，其深度至少为,log,2,n+1,其中,log,2,n,表示取,log,2,n,的整数部分；,（,5,）具有,n,个结点的完全二叉树的深度为,log,2,n+1,；,22,二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(,二叉树的基本性质：,（,6,）设完全二叉树共有,n,个结点。如果从根结点开始，按层序（每一层从左到右）用自然数,1,，,2,，,.n,给结点进行编号（,k=1,2,.n,），有以下结论：,若,k=1,，则该结点为根结点，它没有父结点；若,k1,，则该结点的父结点编号为,INT(k/2),；,若,2kn,，则编号为,k,的结点的左子结点编号为,2k,；否则该结点无左子结点（也无右子结点）；,若,2k+1n,，则编号为,k,的结点的右子结点编号为,2k+1,；否则该结点无右子结点。,满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则,k,层上有,2k-1,个结点深度为,m,的满二叉树有,2m-1,个结点。,23,二叉树的基本性质：（6）设完全二叉树共有n个结点。如果从根结,树的遍历,1,2,3,1,2,3,1,2,3,Left subtree,Right subtree,(a),先序遍历,(b),中序遍历,(c),后序遍历,24,树的遍历123123123Left subtreeRight,二叉树的遍历：,（,1,）前序遍历（,DLR,），首先访问根结点，然后前序遍历左子树，最后前序遍历右子树；,（,2,）中序遍历（,LDR,），首先中序遍历左子树，然后访问根结点，最后中序遍历右子树；,（,3,）后序遍历（,LRD,）首先后序遍历左子树，然后后序遍历右子树，最后访问根结点。,25,二叉树的遍历：（1）前序遍历（DLR），首先访问根结点，然后,G H,D E F,B C,A,先序序列：,ABDGCEFH,中序序列：,DGBAECHF,后序序列：,GDBEHFCA,26,G HD,1,7,查找技术,顺序查找的使用情况：,（,1,）线性表为无序表；,（,2,）表采用链式存储结构。,二分法查找只适用于顺序存储的有序表，对于长度为,n,的有序线性表，最坏情况只需比较,log,2,n,次。,27,17 查找技术顺序查找的使用情况：27,1,8,排序技术,排序是指将一个无序序列整理成按值非递减顺序排列的有序序列,。,交换类排序法：（,1,）冒泡排序法，需要比较的次数为,n(n-1)/2,；（,2,）快速排序法需要比较的次数为,n(n-1)/2,。,插入类排序法：（,1,）简单插入排序法，最坏情况需要,n(n-1)/2,次比较；（,2,）希尔排序法，最坏情况需要,O(n,1.5,),次比较。,选择类排序法：,（,1,）简单选择排序法,最坏情况需要,n(n-1)/2,次比较；（,2,）堆排序法，最坏情况需要,O(nlog,2,n),次比较。,28,18 排序技术排序是指将一个无序序列整理成按值非递减顺序排,排序,平均情况下,快速排序速度是最快的,最坏情况下,堆排序法，需要,O(nlog,2,n),次比较,几种简单排序法,最坏情况需要,n(n-1)/2,次比较；如简单选择，冒泡，简单插入,29,排序29,第二章程序设计基础,2,1,程序设计设计方法和风格,如何形成良好的程序设计风格,1,、源程序文档化；,2,、数据说明的方法；,3,、语句的结构；,4,、输入和输出。,注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。,30,第二章程序设计基础21 程序设计设计方法和风格30,2,2,结构化程序设计,结构化程序设计方法的四条原则是：,1.,自顶向下；,2.,逐步求精；,3.,模块化；,4.,限制使用,goto,语句。,结构化程序的基本结构和特点：,（,1,）顺序结构：一种简单的程序设计，最基本、最常用的结构；,（,2,）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；,（,3,）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。,31,22 结构化程序设计结构化程序设计方法的四条原则是：31,2,3,面向对象的程序设计,面向对象的程序设计：以,60,年代末挪威奥斯陆大学和挪威计算机中心研制的,SIMULA,语言为标志。,面向对象方法的优点：,（,1,）与人类习惯的思维方法一致；,（,2,）稳定性好；,（,3,）可重用性好；,（,4,）易于开发大型软件产品；,（,5,）可维护性好。,32,23 面向对象的程序设计面向对象的程序设计：以60年代末挪,对象,对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。,面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。,属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。,33,对象对象是面向对象方法中最基本的概念，可以用来表示客观世界中,对象的基本特点：,（,1,）标识惟一性；,（,2,）分类性；,（,3,）多态性；,（,4,）封装性；,（,5,）模块独立性好,34,对象的基本特点：（1）标识惟一性；34,对象的基本概念,类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。,消息是一个实例与另一个实例之间传递的信息。,消息的组成包括（,1,）接收消息的对象的名称；（,2,）消息标识符，也称消息名；（,3,）零个或多个参数。,继承是指能够直接获得已有的性质和特征，而不必重复定义他们。,继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。,多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,35,对象的基本概念类是指具有共同属性、共同方法的对象的集合。所以,第三章软件工程基础,3,1,软件工程基本概念,计算机软件是包括程序、数据及相关文档的完整集合。,软件的特点包括：,（,1,）软件是一种逻辑实体；,（,2,）软件的生产与硬件不同，它没有明显的制作过程；,（,3,）软件在运行、使用期间不存在磨损、老化问题；,（,4,）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；,（,5,）软件复杂性高，成本昂贵；,（,6,）软件开发涉及诸多的社会因素。,36,第三章软件工程基础31 软件工程基本概念36,软件工程,软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。,软件危机主要表现在成本、质量、生产率等问题。,软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。,软件工程包括,3,个要素：方法、工具和过程。,37,软件工程软件按功能分为应用软件、系统软件、支撑软件（或工具软,软件工程过程,软件工程过程是把软件转化为输出的一组彼此相关的资源和活动，包含,4,种基本活动：,（,1,）,P-,软件规格说明；,（,2,）,D-,软件开发；,（,3,）,C-,软件确认；,（,4,）,A-,软件演进。,38,软件工程过程软件工程过程是把软件转化为输出的一组彼此相关的资,软件周期,软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。,软件生命周期三个阶段,:,软件定义、软件开发、运行维护，主要活动阶段是：,（,1,）可行性研究与计划制定；,（,2,）需求分析；,（,3,）软件设计；,（,4,）软件实现；,（,5,）软件测试；,（,6,）运行和维护。,39,软件周期软件周期：软件产品从提出、实现、使用维护到停止使用退,软件工程相关概念,软件工程的目标和与原则：,目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。,基本目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发软件易于移植；需要较低的费用；能按时完成开发，及时交付使用。,基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性,40,软件工程相关概念软件工程的目标和与原则：40,软件工程相关概念,软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。,软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。,软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容。,软件管理学包括人员组织、进度安排、质量保证、配置管理、项目计划等。,软件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。,41,软件工程相关概念软件工程的理论和技术性研究的内容主要包括：软,3.2,结构化分析方法,结构化方法的核心和基础是结构化程序设计理论。,需求分析方法有（,1,）结构化需求分析方法；（,2,）面向对象的分析的方法。,从需求分析建立的模型的特性来分：静态分析和动态分析。,结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。,结构化分析的常用工具（,1,）数据流图；,（,2,）数据字典；,（,3,）判定树；,（,4,）判定表。,42,3.2 结构化分析方法结构化方法的核心和基础是结构化程序设计,结构化相关概念,数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。,数据字典：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。,判定树：从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。,判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。,数据字典是结构化分析的核心。,43,结构化相关概念数据流图：描述数据处理过程的工具，是需求理解的,软件需求规格说明书的特点：,（,1,）正确性；,（,2,）无岐义性；,（,3,）完整性；,（,4,）可验证性；,（,5,）一致性；,（,6,）可理解性；,（,7,）可追踪性。,44,软件需求规格说明书的特点：（1）正确性；44,3.3,结构化设计方法,软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型。,软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径。,从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。,结构设计：定义软件系统各主要部件之间的关系。,数据设计：将分析时创建的模型转化为数据结构的定义。,接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。,过程设计：把系统结构部件转换成软件的过程描述。,45,3.3 结构化设计方法软件设计的基本目标是用比较抽象概括的方,结构化设计,从工程管理角度来看：概要设计和详细设计。,软件设计的一般过程：软件设计是一个迭代的过程；先进行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。,衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准。,在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。,46,结构化设计从工程管理角度来看：概要设计和详细设计。46,软件概要设计的基本任务是：,（,1,）设计软件系统结构；,（,2,）数据结构及数据库设计；,（,3,）编写概要设计文档；,（,4,）概要设计文档评审。,47,软件概要设计的基本任务是：（1）设计软件系统结构； 47,数据流图,模块用一个矩形表示，箭头表示模块间的调用关系。,在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据。,结构图的基本形式：基本形式、顺序形式、重复形式、选择形式。,结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。,典型的数据流类型有两种：变换型和事务型。,变换型系统结构图由输入、中心变换、输出三部分组成。,48,数据流图模块用一个矩形表示，箭头表示模块间的调用关系。48,详细设计,事务型数据流的特点是：接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元，然后给出结果。,详细设计：是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。,常见的过程设计工具有：图形工具（程序流程图）、表格工具（判定表）、语言工具（,PDL,）。,49,详细设计事务型数据流的特点是：接受一项事务，根据事务处理的特,3.4,软件测试,软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。,软件测试的目的：发现错误而执行程序的过程。,软件测试方法：静态测试和动态测试。,50,3.4 软件测试软件测试定义：使用人工或自动手段来运行或测定,3.4,软件测试,静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。,动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。,白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。主要方法有逻辑覆盖、基本基路径测试。,黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错，用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。,软件测试过程一般按,4,个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。,51,3.4 软件测试静态测试包括代码检查、静态结构分析、代码质量,3,5,程序的调试,程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。,程序调试的基本步骤：,（,1,）错误定位；,（,2,）修改设计和代码，以排除错误；,（,3,）进行回归测试，防止引进新的错误。,软件调试可分表静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试。主要调试方法有：,（,1,）强行排错法；,（,2,）回溯法；,（,3,）原因排除法。,52,35 程序的调试程序调试的任务是诊断和改正程序中的错误，主,第四章 数据库设计基础,4,1,数据库系统的基本概念,数据,：实际上就是描述事物的符号记录。,数据库,：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。,数据库管理系统,：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。,数据库系统,53,第四章 数据库设计基础 41 数据库系统的基本概念53,信息与数据解释,数据是信息的符号表示或载体，信息则是数据的内涵,数据有其特定的含义，称为语义,信息 数据,数据 信息,数据和关于数据的解释是不可分的，数据解释是指对数据含义的说明,特征抽取,语义解释,54,信息与数据解释数据是信息的符号表示或载体，信息则是数据的内涵,数据库（,DataBase,）,存放数据的仓库,数据库的标准定义,所谓数据库是长期存储在计算机内的、有组织、可共享的数据集合。,数据库中的数据按一定的数据模型组织、描述和储存，具有较小的冗余度、较高的数据独立性和易扩展性，并可以为各种用户共享,计算机存储设备,数据按一定格式存放,可共享,冗余度,独立性,易扩展性,55,数据库（DataBase）计算机存储设备数据按一定格式存放可,数据库特点,数据的共享性：数据库中的数据能为多个用户服务。,数据的独立性：用户的应用程序与数据的逻辑组织和物理存储方式均无关。,数据的完整性：数据库中的数据在操作和维护过程中可以保持正确无误。,数据库中的数据冗余（重复）少。,56,数据库特点数据的共享性：数据库中的数据能为多个用户服务。56,数据库管理系统,DBMS,的主要功能,数据定义功能：提供数据定义语言,(DDL),定义数据库中的数据对象,数据操纵功能：提供数据操纵语言,(DML),操纵数据实现对数据库的基本操作,(,查询、插入、删除和修改,),57,数据库管理系统DBMS的主要功能数据定义功能：提供数据定义,DBMS,的主要功能,数据操纵功能：提供数据操纵语言,(DML),数据库的运行管理,保证数据的安全性、完整性、,多用户对数据的并发使用,发生故障后的系统恢复,数据库的建立和维护功能,(,实用程序,),数据库数据批量装载,数据库转储,介质故障恢复,数据库的重组织,性能监视等,58,DBMS的主要功能数据操纵功能：提供数据操纵语言(DML)5,数据库系统的三级模式结构,DBMS,产品种类很多，它们支持不同的数据模型，使用不同的数据库语言，建立在不同的操作系统之上，数据的存储结构也各不相同，但它们的体系结构上通常具有共同的特征：,采用三级模式结构：外模式,(,用户模式,),、模式,(,全局逻辑结构,),和内模式,(,存储模式,),59,数据库系统的三级模式结构DBMS产品种类很多，它们支持不同的,数据库的二级映象功能,数据库系统的三级模式是对数据的三个抽象级别，它使用户能逻辑地抽象地处理数据，而不必关心数据在计算机内部的存储方式，把数据的具体组织交给,DBMS,管理。,为了能够在内部实现这三个抽象层次的联系和转换，,DBMS,在三级模式之间提供了二级映象功能。,60,数据库的二级映象功能数据库系统的三级模式是对数据的三个抽象级,数据库模式映象,外模式,/,模式映象,定义某一个外模式和模式之间的对应关系，映象定义通常包含在各外模式中,当模式改变时，修改外模式,/,模式映象，使外模式保持不变，从而应用程序可以保持不变，称为,数据的逻辑独立性,模式,/,内模式映象,定义数据逻辑结构与存储结构之间的对应关系,存储结构改变时，修改模式,/,内模式映象，使模式保持不变，从而应用程序可以保持不变，称为,数据的物理独立性,61,数据库模式映象外模式/模式映象61,数据库系统构成,数据库,应用系统,应用开发工具,操作系统,数据库管理系统,数据库管理员,用户,用户,用户,62,数据库系统构成 数据库应用系统应用开发工具 操作系统,数据管理的发展阶段,随着计算机硬件和软件的发展，数据管理经历了三个发展阶段。,人工管理,文件系统,数据库系统,63,数据管理的发展阶段随着计算机硬件和软件的发展，数据管理经历了,数据模型的分类,信息世界,概念化,形式化,概念数据模型,结构数据模型,现实世界,计算机世界,面向用户,面向计算机,64,数据模型的分类信息世界概念化形式化概念数据模型结构数据模型现,概念模型,按用户的观点来对数据和信息建模,现实世界到机器世界的一个中间层次,是数据库设计人员和用户直接进行交流的语言,概念模型特点,具有较强的语义表达能力,能够方便、直接地表达应用中的各种语义知识,简单、清晰、易于用户理解,65,概念模型按用户的观点来对数据和信息建模65,E-R,图中的基本概念,实体（,Entity,）,属性（,Attribute,）,码（,Key,）,域（,Domain,）,实体型（,Entity Type,）,实体集（,Entity Set,）,66,E-R图中的基本概念实体（Entity）66,基本概念实体（,Entity,）,客观存在并且可以相互区别的,“,事物,”,称为实体。,实体可以是可触及的对象，如一个学生，一本书，一辆汽车；也可以是抽象的事件，如学生的一次选课、老师与系的工作关系等。,67,基本概念实体（Entity）客观存在并且可以相互区别的“事,基本概念属性（,Attribute,）,实体的某一特性称为属性。一个实体可以由若干个属性来刻画。,如学生实体有学号、姓名、年龄、性别、系等方面的属性。,属性有,“,型,”,和,“,值,”,之分，,“,型,”,即为属性名，如姓名、年龄、性别是属性的型；,“,值,”,即为属性的具体内容，如（,990001,张三，,20,，男，信息系）这些属性值的集合表示了一个学生实体。,68,基本概念属性（Attribute）实体的某一特性称为属性。,联系的分类,实体型之间的联系,一对一联系（,1:1,）,一对多联系（,1:n,）,多对多（,m:n,）,69,联系的分类实体型之间的联系69,一对一联系（,1:1,）,实体集,A,中的一个实体至多与实体集,B,中的一个实体相对应，反之亦然，则称实体集,A,与实体集,B,为一对一的联系。记作,1:1,。,如：班级与班长，观众与座位，病人与床位。,70,一对一联系（1:1）实体集A中的一个实体至多与实体集B中的一,一对多联系（,1:n,）,实体集,A,中的一个实体与实体集,B,中的多个实体相对应，反之，实体集,B,中的一个实体至多与实体集,A,中的一个实体相对应。记作,1:n,。,如：班级与学生、公司与职员、省与市。,71,一对多联系（1:n）实体集A中的一个实体与实体集B中的多个实,多对多（,m:n,）,实体集,A,中的一个实体与实体集,B,中的多个实体相对应，反之，实体集,B,中的一个实体与实体集,A,中的多个实体相对应。记作（,m:n,）。,如：教师与学生,学生与课程，工厂与产品。,72,多对多（m:n）实体集A中的一个实体与实体集B中的多个实体相,学生选修课程,学生,课程,选修,姓名,学号,系别,课程名,先修课,学分,成绩,用矩形表示实体集，在框内写上实体名,用椭圆表示实体的属性,用无向边把实体与其属性连接起来,用菱形表示实体间的联系,将参与联系的实体用线段连接,m,n,联系的,数量,73,学生选修课程学生课程选修姓名学号系别课程名先修课学分成绩用矩,数据模型,数据模型的好坏，直接影响数据库的性能。数据模型的选择，是设计数据库的一项首要任务。,目前最常用的数据模型有,层次模型（,Hierarchical Model,）,网状模型（,Network Model,）,关系模型（,Relational Model,）。,74,数据模型数据模型的好坏，直接影响数据库的性能。数据模型的选择,关系数据模型,用二维表格数据（即集合论中的关系）来表示实体和实体间联系的模型叫关系数据模型。,一般在二维表中存放两类数据：实体本身的数据和实体间的联系。,75,关系数据模型用二维表格数据（即集合论中的关系）来表示实体和实,学生基本信息,76,学生基本信息76,关系数据模型的基本概念,关系（,Relation,）：一个关系对应通常说的一张表。,元组（,Tuple,）：表中的一行即为一个元组。,属性（,Attribute,）：表中的一列即为一个属性，每个属性都有一个属性名。,主码（,Key,）：表中的某个最小属性组，它可以唯一确定一个元组。,外键,(Foreign Key):,如果关系中某个属性或属性组合并非关键字，但却是另一个关系的主关键字，则称此属性或属性组合为本关系的外部关键字。,域（,Domain,）：属性的取值范围。,分量：元组中的一个属性值。,77,关系数据模型的基本概念关系（Relation）：一个关系对应,员工情况表,属性名,元组,关键字,外关键字,78,员工情况表属性名元组关键字外关键字78,部门设置情况表,元组,关键字,79,部门设置情况表元组关键字79,关系代数运算符,集合运算符：,、,专门关系运算符：,（,选择,）、,（,投影,）、 （,连接,） 、,（,除法,）,比较运算符：,、,=,、,逻辑运算符：,，,80,关系代数运算符集合运算符：、 80,关系代数运算分类,传统的集合运算：把关系看成元组的集合，以元组作为集合中元素来进行运算，其运算是从关系的,“,水平,”,方向即行的角度进行的。包括并、差、交和笛卡尔积等运算。,专门的关系运算：不仅涉及行运算，也涉及列运算，这种运算是为数据库的应用而引进的特殊运算。包括选择、投影、连接和除法等运算。,81,关系代数运算分类传统的集合运算：把关系看成元组的集合，以元组,1,并,设,A,、,B,同为,n,元关系，则,A,、,B,的并也是一个,n,元关系，记作,AB,。,2,交,设,A,、,B,同为,n,元关系，则,A,、,B,的交也是一个,n,元关系，记作,AB,。,AB,包含了所有同属于,A,、,B,的元组。,3,差,设,A,、,B,同为,n,元关系，则,A,、,B,的差也是一个,n,元关系，记作,A-B,。,A-B,包含了所有属于,A,但不属于,B,的元组。,传统的集合运算,82,1并传统的集合运算82,4,集合的笛卡尔乘积,设,A1,、,A2,、,、,An,为任意集合，,A1,、,A2,、,、,An,的笛卡尔乘积记做：,A1A2,An,并且定义,D= A1A2,An =(a1,，,a2,，,，,an)|aiAi,，,i=1,，,2,，,，,n,，其中,(a1,，,a2,，,，,an),是一个元组，它的每个元素,ai,取自对应的集合,Ai,。,例如，设,A=1,，,2,，,B=a,，,b,，则,AB=(1,，,a),，,(1,，,b),，,(2,，,a),，,(2,，,b),。,关系是一个集合，其组成元素是元组而不是组成元组的元素。,83,4集合的笛卡尔乘积83,交运算,定义,所有同时出现在两个关系中的元组集合,R,S = r | r,R,r,S ,交运算可以通过差运算来重写,R,S = R,(R,S),R,S,84,交运算定义RS84,交运算,R,S,RS,85,交运算RSRS 85,并运算,定义,所有至少出现在两个关系中之一的元组集合,R,S = r | r,R,r,S ,R,S,两个关系,R,和,S,若进行并运算，则它们必须是相容的：,关系,R,和,S,必须是同元的，即它们的属性数目必须相同,对,i,，,R,的第,i,个属性的域必须和,S,的第,i,个属性的域相同,86,并运算定义RS两个关系R和S若进行并运算，则它们必须是相容,并运算,R,S,RS,87,并运算RSRS 87,差运算,定义,所有出现在一个关系而不在另一关系中的元组集合,R,S = r | r,R,r,S ,R,和,S,必须是相容的,R,S,88,差运算定义RS88,差运算,R,S,R,S,S,R,89,差运算RSRS SR 89,广义笛卡尔积运算,定义,两个关系,R,，,S,，其度分别为,n,，,m,，则它们的笛卡尔积是所有这样的元组集合：元组的前,n,个分量是,R,中的一个元组，后,m,个分量是,S,中的一个元组,R,S,的度为,R,与,S,的度之和，,R,S,的元组个数为,R,和,S,的元组个数的乘积,R,S= rs | r,R,s,S ,90,广义笛卡尔积运算定义RS= rs | rR sS,广义笛卡尔积运算,A,B,1,2,r,C,D,10,10,20,10,E,a,a,b,b,s,A,B,1,1,1,1,2,2,2,2,C,D,10,10,20,10,10,10,20,10,E,a,a,b,b,a,a,b,b,r,x,s,91,广义笛卡尔积运算AB1rCD10EasAB1CD10,专门的关系运算：,连接,投影,选择,除,92,专门的关系运算：连接92,示例数据库,stdent,93,示例数据库stdent 93,示例数据库,Course,(,课程,),94,示例数据库Course (课程)94,示例数据库,SC,95,示例数据库SC 95,选择运算,在关系,R,中选择满足给定条件的元组,F,(R)=t | t R F(t) =,真,F,是选择的条件，,t R,，,F(t),要么为真，要么为假,关系简单说就是根据条件选择内容,F,的形式：由,逻辑运算符（ ，）,连接,关系表达式,而成,关系表达式：,X Y,X,，,Y,是属性名、常量、或简单函数,是比较算符， , , , , , , ,96,选择运算在关系R中选择满足给定条件的元组96,选择运算,(,列数目不变,),R,A5,(R),A5,C=7,(R),97,选择运算(列数目不变)RA5(R) A5 C=7,选择运算示例,找年龄不小于,20,的男学生,查找结果,AGE20 SEX=,男,（,Student,）,98,选择运算示例找年龄不小于20的男学生查找结果 98,选择运算示例,查找信息系（,IS,系）的全体学生,Sdept,IS,（,Student,）,查找结果,99,选择运算示例查找信息系（IS系）的全体学生查找结果 99,投影,从关系,R,中取若干列组成新的关系（从列的角度）,A,(R) = tA | tR , AR,其中,A,为,R,的属性列,从关系,R,中选出若干属性列组成新的关系,投影的结果中要去掉相同的行,c,b,c,f,e,d,c,b,a,C,B,A,R,B , C,(R),100,投影从关系R中取若干列组成新的关系（从列的角度）cbcfed,投影示例,给出所有学生的姓名和年龄,SN, AGE,(S),101,投影示例给出所有学生的姓名和年龄101,投影示例,找,95001,号学生所选修的课程号,C#,( ,S#=001,（,SC,）,102,投影示例找95001号学生所选修的课程号102,连接,连接操作是从两个关系的广义笛卡尔积中选择属性间满足一定条件的元组。通常写为：,A,B,为,R,和,S,上度数相等且可比的属性列，,为关系运算符,A,B,R S =,R.A S.B,(,R,S),103,连接连接操作是从两个关系的广义笛卡尔积中选择属性间满足一定条,连接,(,笛卡尔积的部分,),9,8,7,6,5,4,3,2,1,C,B,A,R S,B D,R,S,104,连接(笛卡尔积的部分)987654321CBA R S B,等值连接,(,条件相等,),9,8,7,6,5,4,3,2,1,C,B,A,R S,C,D,R,S,105,等值连接(条件相等)987654321CBA R S C,自然连接,若,R,和,S,具有相同的属性组（来自相同的域，表示相同的含义），且连接的运算符,为,“,=,”,，并且在连接的结果中去掉重复的属性组，这种连接称为自然连接。,记为：,当,R,与,S,无相同属性时,，,R S,RS,R S,106,自然连接若R和S具有相同的属性组（来自相同的域，表示相同的含,自然连接,A,B,a1,a1,a2,a2,b1,b2,b3,b4,C,5,6,8,12,r,B,b1,b2,b3,b3,b5,E,3,7,10,2,2,s,a1,a1,a2,a2,b1,b2,b3,b3,5,6,8,8,b1,b2,b3,b3,3,7,10,2,A,B,C,B,E,等值连接,a1,a1,a2,a2,b1,b2,b3,b3,5,6,8,8,3,7,10,2,A,B,C,E,自然连接,107,自然连接ABC5rBb1E3sABCBE等值连接ABCE自然,等值连接,当,为,“,”,的连接运算为等值连接,自然连接,要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉。,当两个关系中没有相同的属性组时等同于笛卡尔积,108,等值连接108,关系范式,所谓范式（,Normal Form,NF,）是指规范化的关系模式。由规范化程度不同，就产生了不同的范式。,根据满足条件的不同，经常称某一关系模式为,“,第几范式,”,。,从,1971,年起，,E,F,odd,相继提出了第一范式、第二范式、第三范式，,Codd,与,Boyce,合作提出了,Boyce-Codd,范式。在,1976-1978,年间，,Fagin,、,Delobe,以及,Zaniolo,又定义了第四范式。到目前为止，已经提出了第五范式。每种范式都规定了一些限制约束条件。,109,关系范式所谓范式（Normal Form,NF）是指规范,在任何一个关系数据库中，第一范式（,1NF,）是对关系模式的基本要求，不满足第一范式（,1NF,）的数据库就不是关系数据库,定义,:,在关系模型中的每一个具体关系,R,中，如果每个属性 都是不可再分的，则称,R,属于第一范式（,1NF,），记作,R1NF,。,第一范式（,1NF,）：数据库表中的字段都是单一属性的，不可再分。,第一范式,(1NF),110,在任何一个关系数据库中，第一范式（1NF）是对关系模,第一范式,(1NF),例如，如下的数据库表是符合第一范式的,：,111,第一范式(1NF)例如，如下的数据库表是符合第一范式的：1,第一范式,(1NF),而这样的数据库表是不符合第一范式的：,112,第一范式(1NF)而这样的数据库表是不符合第一范式的：112,第一范式,(1NF),例：如职工号，姓名，电话号码组成一个表（一个人可能有一个办公室电话 和一个家里电话号码） 规范成为,1NF,总结：不能有重复的列,列不可再分,.,不满足第一范式条件的关系为非范式关系,在关系数据库中,凡非范式关系必须要化成范式关系,.,113,第一范式(1NF)例：如职工号，姓名，电话号码组成一个表（一,第二范式,(2NF),第二范式（,2NF,）是在第一范式（,1NF,）的基础上建立起来的，即满足第二范式（,2NF,）必须先满足第一范式（,1NF,）,。,第二范式（,2NF,）说明：,要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系,定义：如果关系模式,R1NF,，且每一个非主属性都完全依赖于主码，则称关系,R,是属于第二范式的，记作,R2NF,114,第二范式(2NF)第二范式（2NF）是在第一范式（1NF）的,第二范式举例,假定选课关系表为,SelectCourse(,学号,姓名,年龄,课程名称,成绩,学分,),，关键字为组合关键字,(,学号,课程名称,),，因为存在如下决定关系：,(,学号,课程名称,) (,姓名,年龄,成绩,学分,),这个数据库表不满足第二范式，因为存在如下决定关系：,(,课程名称,) (,学分,),(,学号,) (,姓名,年龄,),即存在组合关键字中的字段决定非关键字的情况,。,115,第二范式举例假定选课关系表为SelectCourse(学号,第二范式举例,由于不符合,2NF,，这个选课关系表会存在如下问题：,(1),数据冗余：同一门课程由,n,个学生选修，,学分,就重复,n-1,次；同一个学生选修了,m,门课程，姓名和年龄就重复了,m-1,次。,(2),更新异常：若调整了某门课程的学分，数据表中所有行的,学分,值都要更新，否则会出现同一门课程学分不同的情况。,116,第二范式举例由于不符合2NF，这个选课关系表会存在如下问,第二范式举例,(3),插入异常： 假设要开设一门新的课程，暂时还没有人选修。这样，由于还没有,学号,关键字，课程名称和学分也无法记录入数据库。,(4),删除异常：假设一批学生已经完成课程的选修，这些选修记录就应该从数据库表中删除。但是，与此同时，课程名称和学分信息也被删除了。很显然，这也会导致插入异常。,117,第二范式举例(3) 插入异常： 假设要开设一门新的课,第二范式举例,把选课关系表,SelectCourse,改为如下三个表：学生：,Student(,学号,姓名,年龄,),；课程：,Course(,课程名称,学分,),；选课关系：,SelectCourse(,学号,课程名称,成绩,),。这样的数据库表是符合第二范式的，消除了数据冗余、更新异常、插入异常和删除异常。另外，所有单关键字的数据库表都符合第二范式，因为不可能存在组合关键字。,118,第二范式举例把选课关系表SelectCourse改为如下,第三范式（,3NF,）：如果关系模式,R,为,2NF,，并且中的每个非主属性不传递依赖于的主码，则称关系,R,是属于第,3,范式的。,所谓传递依赖，指的是如果存在,A B C,的决定关系，则,C,传递依赖于,A,。,因此，满足第三范式的数据库表应该不存在如下依赖关系：,关键字段 非关键字段,x ,非关键字段,y,第三范式,(3NF),第三范式（,3NF,）要求一个数据库表中不包含其它表中的非主键信息。,119,第三范式（3NF）：如果关系模式R为2NF，并且,