1、计算机等级考试公共基础知识n考试说明n考试大纲n数据结构与算法n数据库设计基础n程序设计基础n软件工程基础公共基础知识第一章 数据结构与算法n1.1 算法n算法：是指解题方案的准确而完整的描述。n算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。n算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：n（1）可行性；n（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；n（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；n（4）输入：
2、一个算法有0个或多个输入 ，以刻画运算对象的初始情况 ；n（5）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。 1.1 算法n算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。n指令系统：一个计算机系统能执行的所有指令的集合。n基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。n算法的控制结构：顺序结构、选择结构、循环结构。n算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。n算法复杂度：算法时间复杂度和算法空间复杂度。n算法时间复杂度是指执行算法所需要的计算工作量。n算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基
3、本基本概念n数据结构研究的三个方面：n（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；n（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；n（3）对各种数据结构进行的运算。n数据结构是指相互有关联的数据元素的集合。 1.2 数据结构的基本基本概念n数据的逻辑结构包含：n（1）表示数据元素的信息；n（2）表示各数据元素之间的前后件关系。n数据的存储结构有顺序、链接、索引等。n线性结构条件：n（1）有且只有一个根结点；n（2）每一个结点最多有一个前件，也最多有一个后件。n非线性结构：不满足线性结构条件的数据结构。两种最基本的存储结构n顺序存储（数组）两种
4、最基本的存储结构n链表n不是顺序存储，用指针联系n单向链表，双向链表n效率高n 单向链表 双向链表 栈与队列n栈与队列n相同点：都是线性结构n不同点：先进先出，后进先出n 栈 队列 循环队列n为什么需要循环队列？n计算循环队列长度n用一个固定大小为m的数组来实现， 那么队列中元素个数=(rear-front + m)%m 栈n典型应用n逆序输出n10进制转换2进制nftp:/172.16.67.134/n用户名:jsjn密码:无非线性结构n根结点，叶子结点n度、深度、结点数n满二叉树，完全二叉树 树n在树结构中，一个结点所拥有的后件的个数称为该结点的度结点的度n所有结点中最大的度称为树的度树的
5、度。n树的最大层次称为树的深度深度。非线性结构 树二叉树 二叉树定义：二叉树是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分。 n二叉树的5种形态：图图 5-7(a)(b)(c)(d)(e)完全二叉树与满二叉树n完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。n在最后一层上与满二叉树相应层次编号为一一对应，则称这棵二叉树为完全二叉树。树的形态(a)(g)(h)(f)(e)(d)(c)(b)AABABABBACBEDABCABCFigure 7-6 A collection of binary trees二
6、叉树的基本性质：n（1）在二叉树的第k层上，最多有2k-1(k1)个结点；n（2）深度为m的二叉树最多有2m-1个结点；n（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；n（4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分；n（5）具有n个结点的完全二叉树的深度为log2n+1；二叉树的基本性质：n（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，.n给结点进行编号（k=1,2.n），有以下结论：n若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)；n若2kn，
7、则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；n若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。n满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。树的遍历123123123Left subtreeRight subtree(a)先序遍历先序遍历(b)中序遍历中序遍历(c)后序遍历后序遍历二叉树的遍历：n（1）前序遍历（DLR），首先访问根结点，然后前序遍历左子树，最后前序遍历右子树；n（2）中序遍历（LDR），首先中序遍历左子树，然后访问根结点，最后中序遍历右子树；
8、n（3）后序遍历（LRD）首先后序遍历左子树，然后后序遍历右子树，最后访问根结点。G HD E FB CA先序序列：先序序列：ABDGCEFH中序序列：中序序列：DGBAECHF后序序列：后序序列：GDBEHFCA17 查找技术n顺序查找的使用情况：n（1）线性表为无序表；n（2）表采用链式存储结构。n二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。18 排序技术n排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。n交换类排序法：（1）冒泡排序法，需要比较的次数为n(n-1)/2；（2）快速排序法需要比较的次数为n(n-1)/2 。n插入类排
9、序法：（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O(n1.5)次比较。n选择类排序法：n（1）简单选择排序法,最坏情况需要n(n-1)/2次比较；（2）堆排序法，最坏情况需要O(nlog2n)次比较。排序n平均情况下,快速排序速度是最快的 n最坏情况下n堆排序法，需要O(nlog2n)次比较n几种简单排序法,最坏情况需要n(n-1)/2次比较；如简单选择，冒泡，简单插入第二章程序设计基础第二章程序设计基础n21 程序设计设计方法和风格n如何形成良好的程序设计风格n1、源程序文档化； 2、数据说明的方法；n3、语句的结构； 4、输入和输出。n注释分序
10、言性注释和功能性注释，语句结构清晰第一、效率第二。22 结构化程序设计n结构化程序设计方法的四条原则是：n1. 自顶向下；n2. 逐步求精；n3.模块化；n4.限制使用goto语句。n结构化程序的基本结构和特点：n（1）顺序结构：一种简单的程序设计，最基本、最常用的结构；n（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；n（3）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。23 面向对象的程序设计n面向对象的程序设计：以60年代末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志。n面向对
11、象方法的优点：n（1）与人类习惯的思维方法一致；n（2）稳定性好；n（3）可重用性好；n（4）易于开发大型软件产品；n（5）可维护性好。对象n对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。n面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。n属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。对象的基本特点：n（1）标识惟一性；n（2）分类性；n（3）多态性；n（4）封装性；n（5）模块独立性好 对象的基本概念n类是指具有共同属性、共同方法的
12、对象的集合。所以类是对象的抽象，对象是对应类的一个实例。n消息是一个实例与另一个实例之间传递的信息。n消息的组成包括（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。n继承是指能够直接获得已有的性质和特征，而不必重复定义他们。n继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。n多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。第三章软件工程基础第三章软件工程基础n31 软件工程基本概念n计算机软件是包括程序、数据及相关文档的完整集合。n软件的特点包括：n（1）软件是一种逻辑实体；n（2）软件的生产与硬件不同，
13、它没有明显的制作过程；n（3）软件在运行、使用期间不存在磨损、老化问题；n（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；n（5）软件复杂性高，成本昂贵；n（6）软件开发涉及诸多的社会因素。软件工程n软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。n软件危机主要表现在成本、质量、生产率等问题。n软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。n软件工程包括3个要素：方法、工具和过程。软件工程过程n软件工程过程是把软件转化为输出的一组彼此相关的资源和活动，包含4种基本活动：n（1）P-软件规格说明；n（2）
14、D-软件开发；n（3）C-软件确认；n（4）A-软件演进。软件周期n软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。n软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是：n（1）可行性研究与计划制定；n（2）需求分析；n（3）软件设计；n（4）软件实现；n（5）软件测试；n（6）运行和维护。软件工程相关概念n软件工程的目标和与原则：n目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。n基本目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发软件易于
15、移植；需要较低的费用；能按时完成开发，及时交付使用。n基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性 软件工程相关概念n软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。n软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。n软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容。n软件管理学包括人员组织、进度安排、质量保证、配置管理、项目计划等。n软件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。3.2 结构化分析方法n结构化方法的核心和基础是结构化程序设计理论。n需求分析方法有（1）结构
16、化需求分析方法；（2）面向对象的分析的方法。n 从需求分析建立的模型的特性来分：静态分析和动态分析。n结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。n结构化分析的常用工具（1）数据流图； （2）数据字典； （3）判定树； （4）判定表。 结构化相关概念n数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。n数据字典：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。n判定树：从问题定义
17、的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。n判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。n数据字典是结构化分析的核心。软件需求规格说明书的特点：n（1）正确性；n（2）无岐义性；n（3）完整性；n（4）可验证性；n（5）一致性；n（6）可理解性；n（7）可追踪性。3.3 结构化设计方法n软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型。n软
18、件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径。n从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。n结构设计：定义软件系统各主要部件之间的关系。n数据设计：将分析时创建的模型转化为数据结构的定义。n接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。n过程设计：把系统结构部件转换成软件的过程描述。结构化设计n从工程管理角度来看：概要设计和详细设计。n软件设计的一般过程：软件设计是一个迭代的过程；先进行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。n衡量软件模块独立性使用耦合性和内聚性两个定性的度量
19、标准。n在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。软件概要设计的基本任务是：n（1）设计软件系统结构； n（2）数据结构及数据库设计；n（3）编写概要设计文档； n（4）概要设计文档评审。数据流图n模块用一个矩形表示，箭头表示模块间的调用关系。n在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据。n结构图的基本形式：基本形式、顺序形式、重复形式、选择形式。n结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。n典型的数据流类型有两种：变换型和事务型。n变换型系统结构图由输入
20、、中心变换、输出三部分组成。详细设计n事务型数据流的特点是：接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元，然后给出结果。n详细设计：是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。n常见的过程设计工具有：图形工具（程序流程图）、表格工具（判定表）、语言工具（PDL）。3.4 软件测试n软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。n软件测试的目的：发现错误而执行程序的过程。n软件测试方法：静态测试和动态测试。3.4 软件测试n静态测试
21、包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。n动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。n白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。主要方法有逻辑覆盖、基本基路径测试。n黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错，用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。n软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。35 程序的调试n程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。n程序调试的基本
22、步骤：n（1）错误定位；n（2）修改设计和代码，以排除错误；n（3）进行回归测试，防止引进新的错误。n软件调试可分表静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试。主要调试方法有：n（1）强行排错法；n（2）回溯法；n（3）原因排除法。第四章第四章 数据库设计基础数据库设计基础 n41 数据库系统的基本概念n数据数据：实际上就是描述事物的符号记录。n数据库数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。n数据库管理系统数据库管理系统：一种系统软件，负责数据库中的数
23、据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。n数据库系统数据库系统信息与数据解释n数据是信息的符号表示或载体，信息则是数据的内涵n数据有其特定的含义，称为语义n信息 数据n数据 信息n数据和关于数据的解释是不可分的，数据解释是指对数据含义的说明特征抽取语义解释数据库（DataBase）n存放数据的仓库n数据库的标准定义n所谓数据库是长期存储在计算机内的、有组织、可共享的数据集合。n数据库中的数据按一定的数据模型组织、描述和储存，具有较小的冗余度、较高的数据独立性和易扩展性，并可以为各种用户共享计算机存储设备数据按一定格式存放可共享冗余度独立性易扩展性数据库特点n数据的共
24、享性：数据库中的数据能为多个用户服务。n数据的独立性：用户的应用程序与数据的逻辑组织和物理存储方式均无关。n数据的完整性：数据库中的数据在操作和维护过程中可以保持正确无误。 n数据库中的数据冗余（重复）少。 数据库管理系统DBMS的主要功能n数据定义功能：提供数据定义语言数据定义功能：提供数据定义语言(DDL) 定义数据库中的数据对象定义数据库中的数据对象n数据操纵功能：提供数据操纵语言数据操纵功能：提供数据操纵语言(DML) 操纵数据实现对数据库的基本操作操纵数据实现对数据库的基本操作 (查询、插入、删除和修改查询、插入、删除和修改)DBMS的主要功能n数据操纵功能：提供数据操纵语言数据操纵
25、功能：提供数据操纵语言(DML)n数据库的运行管理数据库的运行管理 保证数据的安全性、完整性、保证数据的安全性、完整性、 多用户对数据的并发使用多用户对数据的并发使用 发生故障后的系统恢复发生故障后的系统恢复n数据库的建立和维护功能数据库的建立和维护功能(实用程序实用程序) 数据库数据批量装载数据库数据批量装载 数据库转储数据库转储 介质故障恢复介质故障恢复 数据库的重组织数据库的重组织 性能监视等性能监视等数据库系统的三级模式结构nDBMS产品种类很多，它们支持不同的数据模型，使用不同的数据库语言，建立在不同的操作系统之上，数据的存储结构也各不相同，但它们的体系结构上通常具有共同的特征：n采
26、用三级模式结构：外模式(用户模式)、模式(全局逻辑结构)和内模式(存储模式)数据库的二级映象功能n数据库系统的三级模式是对数据的三个抽象级别，它使用户能逻辑地抽象地处理数据，而不必关心数据在计算机内部的存储方式，把数据的具体组织交给 DBMS 管理。n为了能够在内部实现这三个抽象层次的联系和转换，DBMS 在三级模式之间提供了二级映象功能。数据库模式映象数据库模式映象n外模式/模式映象n定义某一个外模式和模式之间的对应关系，映象定义通常包含在各外模式中n当模式改变时，修改外模式/模式映象，使外模式保持不变，从而应用程序可以保持不变，称为数据的逻辑独立性数据的逻辑独立性n模式/内模式映象n定义数
27、据逻辑结构与存储结构之间的对应关系n存储结构改变时，修改模式/内模式映象，使模式保持不变，从而应用程序可以保持不变，称为数据的物理独立性数据的物理独立性数据库系统构成 数据库数据库应用系统应用系统应用开发工具应用开发工具 操作系统操作系统 数据库管理系统数据库管理系统数据库管理员数据库管理员用户用户用户用户用户用户数据管理的发展阶段n随着计算机硬件和软件的发展，数据管理经历了三个发展阶段。n人工管理n文件系统n数据库系统数据模型的分类信息世界信息世界概念化概念化形式化形式化概念数据模型概念数据模型结构数据模型结构数据模型现实世界现实世界计算机世界计算机世界面向用户面向用户面向计算机面向计算机概
28、念模型n按用户的观点来对数据和信息建模n现实世界到机器世界的一个中间层次n是数据库设计人员和用户直接进行交流的语言n概念模型特点n具有较强的语义表达能力n能够方便、直接地表达应用中的各种语义知识n简单、清晰、易于用户理解E-R图中的基本概念n实体（Entity）n属性（Attribute）n码（Key）n域（Domain）n实体型（Entity Type）n实体集（Entity Set）基本概念实体（Entity）n客观存在并且可以相互区别的“事物”称为实体。n实体可以是可触及的对象，如一个学生，一本书，一辆汽车；也可以是抽象的事件，如学生的一次选课、老师与系的工作关系等。基本概念属性（Att
29、ribute）n实体的某一特性称为属性。一个实体可以由若干个属性来刻画。n如学生实体有学号、姓名、年龄、性别、系等方面的属性。n属性有“型”和“值”之分，“型”即为属性名，如姓名、年龄、性别是属性的型；“值”即为属性的具体内容，如（990001,张三，20，男，信息系）这些属性值的集合表示了一个学生实体。联系的分类n实体型之间的联系n一对一联系（1:1）n一对多联系（1:n）n多对多（m:n）一对一联系（1:1）n实体集A中的一个实体至多与实体集B中的一个实体相对应，反之亦然，则称实体集A与实体集B为一对一的联系。记作1:1。n如：班级与班长，观众与座位，病人与床位。一对多联系（1:n）n实体
30、集A中的一个实体与实体集B中的多个实体相对应，反之，实体集B中的一个实体至多与实体集A中的一个实体相对应。记作1:n。n如：班级与学生、公司与职员、省与市。多对多（m:n）n实体集A中的一个实体与实体集B中的多个实体相对应，反之，实体集B中的一个实体与实体集A中的多个实体相对应。记作（m:n）。n如：教师与学生,学生与课程，工厂与产品。学生选修课程学生学生课程课程选修选修姓名姓名学号学号系别系别课程名课程名先修课先修课学分学分成绩成绩用矩形表示实用矩形表示实体集，在框内体集，在框内写上实体名写上实体名用椭圆表示实用椭圆表示实体的属性体的属性用无向边用无向边把实体与把实体与其属性连其属性连接起来
31、接起来用菱形表示实用菱形表示实体间的联系体间的联系将参与联系的实将参与联系的实体用线段连接体用线段连接mn联系的联系的数量数量数据模型n数据模型的好坏，直接影响数据库的性能。数据模型的选择，是设计数据库的一项首要任务。n目前最常用的数据模型有n层次模型（Hierarchical Model）n网状模型（Network Model）n关系模型（Relational Model）。关系数据模型n用二维表格数据（即集合论中的关系）来表示实体和实体间联系的模型叫关系数据模型。n一般在二维表中存放两类数据：实体本身的数据和实体间的联系。 学生基本信息学号学号姓名姓名出生日期出生日期家庭地址家庭地址030
32、02华克1983-7-16海淀区02001李默1983-6-19西城区01002李扬1982-9-10海淀区04002龙翔1982-10-7崇文区02002齐霖1982-10-12门头沟区关系数据模型的基本概念n关系（Relation）：一个关系对应通常说的一张表。n元组（Tuple）：表中的一行即为一个元组。n属性（Attribute）：表中的一列即为一个属性，每个属性都有一个属性名。n主码（Key）：表中的某个最小属性组，它可以唯一确定一个元组。n外键(Foreign Key):如果关系中某个属性或属性组合并非关键字，但却是另一个关系的主关键字，则称此属性或属性组合为本关系的外部关键字。n
33、域（Domain）：属性的取值范围。n分量：元组中的一个属性值。部门编号部门编号部门名称部门名称员工员工编号编号员工姓名员工姓名性性别别住址住址D001总经理办总经理办E001钱达理钱达理男男东风路东风路78号号D001总经理办总经理办E002东方牧东方牧男男五一北路五一北路25号号D002市场部市场部E003郭文斌郭文斌男男公司集体宿舍公司集体宿舍D003销售部销售部E004肖海燕肖海燕女女公司集体宿舍公司集体宿舍D004仓储部仓储部E005张明华张明华男男韶山北路韶山北路55号号属性名元组关键字外关键字部门编号部门编号部门名称部门名称D001总经理办总经理办D002市场部市场部D003销售
34、部销售部D004仓储部仓储部元组关键字关系代数运算符n集合运算符：、 n专门关系运算符：（选择）、（投影）、 （连接） 、（除法）n比较运算符：、=、n逻辑运算符：，关系代数运算分类n传统的集合运算：把关系看成元组的集合，以元组作为集合中元素来进行运算，其运算是从关系的“水平”方向即行的角度进行的。包括并、差、交和笛卡尔积等运算。n专门的关系运算：不仅涉及行运算，也涉及列运算，这种运算是为数据库的应用而引进的特殊运算。包括选择、投影、连接和除法等运算。1并设A、B同为n元关系，则A、B的并也是一个n元关系，记作AB。2交设A、B同为n元关系，则A、B的交也是一个n元关系，记作AB。AB包含了所
35、有同属于A、B的元组。3差设A、B同为n元关系，则A、B的差也是一个n元关系，记作A-B。A-B包含了所有属于A但不属于B的元组。 传统的集合运算4集合的笛卡尔乘积设A1、A2、An为任意集合，A1、A2、An的笛卡尔乘积记做：A1A2An,并且定义D= A1A2An =(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)。关系是一个集合，其组成元素是元组而不是组成元组关系是一个集合，其组成元素是元组而不是组成元组的元素。的元素。 交运算n定
36、义n所有同时出现在两个关系中的元组集合n交运算可以通过差运算来重写RS = R (R S)R S交运算ABC367257723443RABC345723SABC723RS 并运算n定义n所有至少出现在两个关系中之一的元组集合R Sn两个关系R和S若进行并运算，则它们必须是相容的：n关系R和S必须是同元的，即它们的属性数目必须相同n对i，R的第i个属性的域必须和S的第i个属性的域相同并运算ABC367257723443RABC345723SABC367257723443345RS 差运算n定义n所有出现在一个关系而不在另一关系中的元组集合nR和S必须是相容的R S差运算ABC3672577234
37、43RABC345723SABC367257443RS ABC345SR 广义笛卡尔积运算n定义n两个关系R，S，其度分别为n，m，则它们的笛卡尔积是所有这样的元组集合：元组的前n个分量是R中的一个元组，后m个分量是S中的一个元组nRS的度为R与S的度之和， RS的元组个数为R和S的元组个数的乘积广义笛卡尔积运算AB12rCD10102010EaabbsAB11112222CD 1010201010102010Eaabbaabbrxs专门的关系运算：连接连接投影投影选择选择除除示例数据库stdentstdent SnoSnoSnameSnameSsexSsexSageSageSdeptSdep
38、t95001李勇男20 CS95002刘晨女19 IS95003王敏女18 MA95004张立男19 IS示例数据库CourseCourse (课程)CnoCnoCnameCnameCpnoCpnoCcreditCcredit1 数据库5 4 2 数学 3 3 信息系统1 44 操作系统6 35 数据结构7 46 数据处理27 PASCAL语言6 4示例数据库SCSC SnoSnoCnoCnoGradeGrade950011 92950012 85950013 88950022 90950023 80选择运算n在关系R中选择满足给定条件的元组nF是选择的条件，t R， F(t)要么为真，要么为
39、假n关系简单说就是根据条件选择内容nF的形式：由连接而成n关系表达式：X YnX，Y是属性名、常量、或简单函数n是比较算符， , , , , , 选择运算(列数目不变)ABC367257723443RA5(R) ABC367257443A5 C=7(R) ABC367257选择运算示例n找年龄不小于20的男学生SnoSnoSnameSnameSsexSsexSageSageSdeptSdept95001李勇男20 CSSnoSnoSnameSnameSsexSsexSageSageSdeptSdept95001李勇男20 CS95002刘晨女19 IS95003王敏女18 MA95004张立男
40、19 IS查找结果 AGE20 SEX=男 （Student）选择运算示例n查找信息系（IS系）的全体学生SdeptIS（Student）SnoSnoSnameSnameSsexSsexSageSageSdeptSdept95001李勇男20 CS95002刘晨女19 IS95003王敏女18 MA95004张立男19 IS查找结果 SnoSnoSnameSnameSsexSsexSageSageSdeptSdept95002刘晨女19 IS95004张立男19 IS投影n从关系R中取若干列组成新的关系（从列的角度）n从关系R中选出若干属性列组成新的关系n投影的结果中要去掉相同的行cbcfed
41、cbaCBABCbcef R R B , C(R)投影示例n给出所有学生的姓名和年龄SN, AGE(S)SnoSnoSnameSnameSsexSsexSageSageSdeptSdept95001李勇男20 CS95002刘晨女19 IS95003王敏女18 MA95004张立男19 ISsnamesnamesagesage李勇20刘晨19王敏18张立19投影示例n找95001号学生所选修的课程号C#( S#=001 （SC）SnoSnoCnoCnoGradeGrade950011 92950012 85950013 88950022 90950023 80cnocno1 2 3 连接n连接
42、操作是从两个关系的广义笛卡尔积中选择属性间满足一定条件的元组。通常写为：nA,B为R和S上度数相等且可比的属性列，为关系运算符 连接(笛卡尔积的部分)987654321CBADE3162ABCDE123311236245662 R S R S B D R R S S等值连接(条件相等)987654321CBADE3162ABCDE1233145662 R S R S C D R R S S自然连接n若R和S具有相同的属性组（来自相同的域，表示相同的含义），且连接的运算符为“=”，并且在连接的结果中去掉重复的属性组，这种连接称为自然连接。n记为：n当R与S无相同属性时，R S RS自然连接ABa
43、1a1a2a2b1b2b3b4C56812rBb1b2b3b3b5E371022sa1a1a2a2b1b2b3b35688b1b2b3b337102A B C B E等值连接等值连接a1a1a2a2b1b2b3b3568837102A B C E自然连接自然连接等值连接当为“”的连接运算为等值连接自然连接要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉。当两个关系中没有相同的属性组时等同于笛卡尔积关系范式关系范式所谓范式（Normal Form,NF）是指规范化的关系模式。由规范化程度不同，就产生了不同的范式。根据满足条件的不同，经常称某一关系模式为“第几范式”。
44、 从1971年起，EFodd相继提出了第一范式、第二范式、第三范式，Codd与Boyce合作提出了Boyce-Codd范式。在1976-1978年间，Fagin、Delobe以及Zaniolo又定义了第四范式。到目前为止，已经提出了第五范式。每种范式都规定了一些限制约束条件。 在任何一个关系数据库中，第一范式在任何一个关系数据库中，第一范式（1NF1NF）是对关系模式的基本要求，不满足第）是对关系模式的基本要求，不满足第一范式（一范式（1NF1NF）的数据库就不是关系数据库）的数据库就不是关系数据库定义定义: :在关系模型中的每一个具体关系在关系模型中的每一个具体关系R R中，中，如果每个属性
45、如果每个属性 都是不可再分的，则称都是不可再分的，则称R R属于属于第一范式（第一范式（1NF1NF），记作），记作R1NFR1NF。第一范式（第一范式（1NF1NF）：）：数据库表中的字段数据库表中的字段都是单一属性的，不可再分。都是单一属性的，不可再分。第一范式第一范式(1NF)第一范式第一范式(1NF)n例如，如下的数据库表是符合第一范式的：字段字段1 字段字段2 字段字段3字段字段4 第一范式第一范式(1NF) 而这样的数据库表是不符合第一范式的：而这样的数据库表是不符合第一范式的：字段字段1 字段字段2 字段字段3 字段字段4 字段字段3.1字段字段3.2 第一范式第一范式(1NF)
46、n例：如职工号，姓名，电话号码组成一个表（一个人可能有一个办公室电话 和一个家里电话号码） 规范成为1NF n总结：不能有重复的列总结：不能有重复的列, ,列不可再分列不可再分. .n不满足第一范式条件的关系为非范式关系不满足第一范式条件的关系为非范式关系, ,在关系数据库中在关系数据库中, ,凡非范式关系必须要化成凡非范式关系必须要化成范式关系范式关系. .第二范式第二范式(2NF)n第二范式（第二范式（2NF2NF）是在第一范式（）是在第一范式（1NF1NF）的基础上建立起）的基础上建立起来的，即来的，即满足第二范式（满足第二范式（2NF2NF）必须先满足第一范式）必须先满足第一范式（1N
47、F1NF） 。第二范式（第二范式（2NF2NF）说明：）说明： 要求实体的属性完全依赖要求实体的属性完全依赖于主关键字。所谓于主关键字。所谓完全依赖完全依赖是指不能存在仅依赖主是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系体，新实体与原实体之间是一对多的关系定义：如果关系模式定义：如果关系模式R1NFR1NF，且每一个非主属性都完全依赖，且每一个非主属性都完全依赖于主码，则称关系于主码，则称关系R R 是属于第
48、二范式的，记作是属于第二范式的，记作R2NFR2NF第二范式举例第二范式举例n假定选课关系表为SelectCourse(学号, 姓名, 年龄, 课程名称, 成绩, 学分)，关键字为组合关键字(学号, 课程名称)，因为存在如下决定关系：(学号, 课程名称) (姓名, 年龄, 成绩, 学分)这个数据库表不满足第二范式，因为存在如下决定关系：(课程名称) (学分)(学号) (姓名, 年龄)即存在组合关键字中的字段决定非关键字的情况。 第二范式举例第二范式举例n由于不符合2NF，这个选课关系表会存在如下问题：(1) 数据冗余：同一门课程由n个学生选修，学分就重复n-1次；同一个学生选修了m门课程，姓名
49、和年龄就重复了m-1次。(2) 更新异常：若调整了某门课程的学分，数据表中所有行的学分值都要更新，否则会出现同一门课程学分不同的情况。第二范式举例第二范式举例n(3) 插入异常： 假设要开设一门新的课程，暂时还没有人选修。这样，由于还没有学号关键字，课程名称和学分也无法记录入数据库。(4) 删除异常：假设一批学生已经完成课程的选修，这些选修记录就应该从数据库表中删除。但是，与此同时，课程名称和学分信息也被删除了。很显然，这也会导致插入异常。 第二范式举例第二范式举例n把选课关系表把选课关系表SelectCourse改为如下三个表：改为如下三个表：学生：学生：Student(学号学号, 姓名姓名
50、, 年龄年龄)；课程：课程：Course(课程名称课程名称, 学分学分)；选课关系：选课关系：SelectCourse(学号学号, 课程名称课程名称, 成绩成绩)。这样的数据库表是符合第二范式的，消除了数据冗这样的数据库表是符合第二范式的，消除了数据冗余、更新异常、插入异常和删除异常。余、更新异常、插入异常和删除异常。另外，所有单关键字的数据库表都符合第二范式，另外，所有单关键字的数据库表都符合第二范式，因为不可能存在组合关键字。因为不可能存在组合关键字。 第三范式（第三范式（3NF）：如果关系模式）：如果关系模式R为为2NF，并且中的每个非主属性并且中的每个非主属性不传递依赖不传递依赖于的主
