三级数据库基础知识.txt

第一章 计算机基础知识1、计算机的发展阶段：经历了以下5个阶段(它们是并行关系)：大型机阶段(经历四小阶段它们是取代关系)、小型机阶段、微型机阶段、客户机/服务器阶段（对等网络与非对等网络的概念）和互联网阶段（Arpanet是在1983年第一个使用TCP/IP协议的。 在1991年6月我国第一条与国际互联网连接的专线建成它从中国科学院高能物理研究所接到美国斯坦福大学的直线加速器中心。在1994年实现4大主干网互连(中国公用计算机互联网 Chinanet、中国科学技术网 Cstnet、中国教育和科研计算机网 Cernet、中国金桥信息网 ChinaGBN)）2、计算机种类：按照传统的分类方法：计算机可以分为6大类：大型主机、小型计算机、个人计算机、工作站、巨型计算机、小巨型机。 按照现实的分类方法：计算机可以分为5大类：服务器、工作站、台式机、笔记本、手持设备。3、计算机的公共配置：CPU、内存（RAM）、高速缓存（Cache）、硬盘、光驱、显示器(CRT、LCD)、操作系统(OS)4、计算机的指标：位数指CPU寄存器中能够保存数据的位数、速度(MIPS、MFLOPS)指CPU每秒钟处理的指令数通常用主频来表示CPU的处理速度、容量（B、KB、MB、GB、TB）、数据传输率（Bps）、版本和可靠性（MTBF、MTTR）。5、计算机的应用领域：科学计算、事务处理、过程控制、辅助工程、人工智能、网络应用。（补充实例）6、计算机系统的组成:硬件系统具有原子特性(芯片、板卡、设备、网络)与软件系统具有比特特性。且它们具有同步性。7、奔腾芯片的技术特点: 奔腾32位芯片，主要用于台式机和笔记本，奔腾采用了RISC和CISC技术(技术特点10个请看书P8)8、安腾芯片的技术特点：安腾是64位芯片，主要用于服务器和工作站。安腾采用简明并行指令计算（EPIC）技术9、主机板与插卡的组成：(1) 主机板简称主板(mainboard)或母板(motherboard)。由5部分组成（CPU、存储器、总线、插槽和电源）与主板的分类(2)网络卡又称为适配器卡代号NIC，其功能为：（见书P11）10、软件的基本概念：软件由程序(功能实现部分)与文档(功能说明部分)组成。软件是用户与计算机硬件系统之间的桥梁。11、应用软件包括：桌面应用软件、演示出版软件、浏览工具软件、管理效率软件、通信协作软件和系统维护软件。12、程序与文档：程序是由指令序列组成的，告诉计算计如何完成一个具体的任务。文档是软件开发、使用和维护中的必备资料。13、软件开发：软件的生命周期中，通常分为三大阶段，每个阶段又分若干子阶段： 计划阶段：分为问题定义、可行性研究（是决定软件项目是否开发的关键）。 开发阶段：在开发前期分为需求分析、总体设计、详细设计三个子阶段，在开发后期分为编码、测试两个子阶段。前期必须形成的文档有：软件需求说明书，软件设计规格说明书。 运行阶段：主要任务是软件维护。为了排除软件系统中仍然可能隐含的错误，扩充软件功能。14、编程语言：（机器语言与汇编语言都依赖于具体的机器，汇编语言与高级语言都需要编译） 机器语言：能被计算机直接理解和执行，速度快，但该种语言难记、难学、难懂。 汇编语言：用英文助记符和十进制数代替二进制码，使机器语言变成了汇编语言。汇编语言属于低级语言。汇编语言要通过汇编程序把汇编语言翻译成机器语言程序计算机才能执行。 高级语言：高级语言是一种面向问题或过程的语言。它是近似于日常会话的语言。它不但直观、易学，而且通用性强。高级语言要通过编译（或解释）翻译成机器语言才能执行。15、媒体的概念与分类:(1) 媒体的概念:信息的载体(2)媒体的分类：传输媒体、表现媒体、表示媒体、感觉媒体16、多媒体的基本概念：指有声有色的信息处理与利用技术。多媒体技术可划分为偏硬件技术和偏软件技术两部分。17、MPC的组成：具有CD-ROM、具有A/D和D/A转换功能、具有高清晰的彩色显示器、具有数据压缩与解压缩的硬件支持18、多媒体的关键技术：数据压缩与解压缩技术、芯片与插卡技术、多媒体操作系统技术、多媒体数据管理技术。19、超文本与超媒体的概念：(1)超文本是非线性非顺序的而传统文本是线性的顺序的。(2)超文本概念：超文本是收集、存储和浏览离散信息以及建立和表现信息之间关系的技术。(3)超媒体的组成：当信息载体不限于文本时，称之为超媒体。超媒体技术是一种典型的数据管理技术，它是由称之为结点(node)和表示结点之间联系的链(link)组成的有向图（网络），用户可以对其进行浏览、查询和修改等操作。(4)超媒体系统的组成：编辑器、导航工具、超媒体语言第二章 网络的基本概念1、信息技术涉及内容：信息的收集、储存、处理、传输与利用。2、计算机网络形成与发展大致分为如下4个阶段：（1）第一个阶段20世纪50年代（2） 第二个阶段以20世纪60年代美国的APPANET与分组交换技术为重要标志。（3） 第三个阶段从20世纪70年代中期开始。（4） 第四个阶段是20世纪90年代开始。3、计算机网络的基本特征：资源共享。4、计算机网络的定义：把分布在不同地理位置上的自治计算机通过通信设备和通信协议进行互联实现共享资源信息传输。5、早期计算机网络结构实质上是广域网的结构。 广域网的功能：数据处理与数据通信。逻辑功能上可分为：资源子网与通信子网。资源子网负责全网的数据处理，向网络用户提供各种网络资源与网络服务。主要包括主机和终端。主机通过高速通信线路与通信子网的通信控制处理机相连接。终端是用户访问网络的界面。通信子网由通信控制处理机、通信线路与其他通信设备组成，完成网络数据传输、转发等通信处理任务。通信控制处理机在网络拓扑结构中被称为网络节点。通信线路为通信处理机之间以及通信处理机与主机之间提供通信信道。6、现代网络机构的特点：微机通过局域网连入广域网，局域网与广域网、广域网与广域网的互联是通过路由器实现的。7、按传输技术分为： 广播式网络（通过一条公共信道实现）点-点式网络（通过存储转发实现）。采用分组存储转发与路由选择是点-点式网络与广播网络的重要区别之一。8、按规模分类：局域网（LAN）、城域网（MAN）、广域网（WAN）（1）广域网的通信子网采用分组交换技术，利用公用分组交换网、卫星通信网和无线分组交换网互联。（2）广域网（远程网）以下特点：1 适应大容量与突发性通信的要求。2 适应综合业务服务的要求。3 开放的设备接口与规范化的协议。4 完善的通信服务与网络管理。（3）几种常见的广域网的特点：X25、FR、SMDS、B-ISDN、N-ISDN、ATM（4）广域网扩大了资源共享的范围，局域网增强了资源共享的深度。（5）期的城域网产品主要是光纤分布式数据接口(FDDI)（6）各种城域网建设方案有几个相同点：传输介质采用光纤，交换接点采用基于IP交换的高速路由交换机或ATM交换机，在体系结构上采用核心交换层，业务汇聚层与接入层三层模式。城域网MAN介于广域网与局域网之间的一种高速网络。9、计算机网络拓扑是通过网中结点与通信线路之间的几何关系表示网络结构，反映出网络中各实体间的结构关系。主要是指通信子网的拓扑构型。10、网络拓扑可以根据通信子网中通信信道类型分为：（1） 点-点线路通信子网的拓扑：星型，环型，树型，网状型。（2）广播式通信子网的拓扑：总线型，树型，环型，无线通信与卫星通信型。11、描述数据通信的基本技术参数有两个：数据传输率与误码率。（1）数据传输速率:在数值上等于每秒钟传输构成数据代码的二进制比特数,单位为比特/秒(bit/second),记作bps.对于二进制数据,数据传输速率为:S1/T(bps),其中,T为发送每一比特所需要的时间.（2）奈奎斯特准则：信号在无噪声的信道中传输时,对于二进制信号的最大数据传输率Rmax与通信信道带宽B（B=f，单位是Hz）的关系可以写为： Rmax=2*f(bps)（3）香农定理：香农定理则描述了有限带宽;有随机热噪声信道的最大传输速率与信道带宽;信号噪声功率比之间的关系.在有随机热噪声的信道上传输数据信号时，数据传输率Rmax与信道带宽B，信噪比S/N关系为： Rmax=B*LOG（1+S/N）其中：B为信道带宽，S为信号功率，n为噪声功率。（4）误码率是二进制码元在数据传输系统中被传错的概率，它在数值上近似等于：Pe=Ne/N（传错的除以总的）a、误码率应该是衡量数据传输系统正常工作状态下传输可靠性的参数.b、对于一个实际的数据传输系统,不能笼统地说误码率越低越好,要根据实际传输要求提出误码率要求;在数据传输速率确定后,误码率越低,传输系统设备越复杂,造价越高.c、对于实际数据传输系统,如果传输的不是二进制码元,要折合成二进制码元来计算.d、差错的出现具有随机性,在实际测量一个数据传输系统时,只有被测量的传输二进制码元数越大,才会越接近于真正的误码率值.12、网络协议（1）概念：为网络数据传递交换而指定的规则，约定与标准被称为网络协议。（2）协议分为三部分：(1)语法,即用户数据与控制信息的结构和格式;(2)语义,即需要发出何种控制信息,以及完成的动作与做出的响应;(3)时序,即对事件实现顺序的详细说明.13、计算机网络体系结构（1）概念：将计算机网络层次模型和各层协议的集合定义为计算机网络体系结构。（体现出的两个内涵请补充）（2）计算机网络中采用层次结构，可以有以下好处：各层之间相互独立、灵活性好、各层都可以采用最合适的技术来实现各层实现技术的改变不影响其他各层、易于实现和维护、有利于促进标准化。14、ISO/OSI（国际标准化组织 / 开放系统互连参考模型）（1）功能：构建网络和设计网络时提供统一的标准（2）概述：采用分层的体系结构将整个庞大而复杂的问题划分为若干个容易处理的小问题，采用了三级抽象，既体系结构，服务定义，协议规格说明。实现了开放系统环境中的互连性，互操作性与应用的可移植性。（3）ISO将整个通信功能划分为七个层次,划分层次的原则是:网中各结点都有相同的层次、不同结点的同等层具有相同的功能、同一结点内相邻层之间通过接口通信、每一层使用下层提供的服务,并向其上层提供服务、不同结点的同等层按照协议实现对等层之间的通信（补充服务、接口、协议的概念）.（4）OSI七层：1 物理层：主要是利用物理传输介质为数据链路层提供物理连接，以便透明的传递比特流。（NIC、HUB）2 数据链路层：分为MAC和LLC，传送以帧为单位的数据，采用差错控制，流量控制方法。（NIC、SWITCH）3 网络层：实现路由选择、拥塞控制和网络互连功能，使用TCP和UDP协议（ROUTER）4 传输层：是向用户提供可靠的端到端服务，透明的传送报文，使用TCP协议。5 会话层：组织两个会话进程之间的通信，并管理数据的交换使用NETBIOS和WINSOCK协议。6 表示层：处理在两个通信系统中交换信息的表示方式。7 应用层：应用层是OSI参考模型中的最高层。确定进程之间通信的性质，以满足用户的需要。15、TCP/IP参考模型（1）TCP/IP协议的特点：a、开放的协议标准，可以免费使用，并且独立于特定的计算机硬件与操作系统。b、独立于特定的网络硬件，可以运行在局域网、广域网，更适用于互联网。c、统一的网络地址分配方案，使得整个TCP/IP设备在网中都具有唯一的地址。d、标准化的高层协议，可以提供多种可靠的用户服务。（2）TCP/IP参考模型可以分为：应用层，传输层，互连层，主机-网络层。（各层功能见教材P33）（3）应用层协议分为:a、依赖于面向连接的TCP协议：主要有: 文件传送协议FTP、电子邮件协议SMTP以及超文本传输协议HTTP等b、依赖于面向连接的UDP协议：主要有简单网络管理协议SNMP;简单文件传输协议TFTP.c、既依赖于TCP协议，也可以依赖于UDP协议：域名服务DNS等.16、ISO/OSI参考模型与TCP/IP参考模型的比较17、NSFNET采用的是一种层次结构，可以分为主干网，地区网与校园网。18、Internet2的初始运行速率可达10Gbps.Internet2在网络层运行的是IPv4，同时也支持IPv6业务.19、移动计算网络 P3920、多媒体网络是指能够传输多媒体数据的通信网络。多媒体网络需要支持多媒体传输所需要的交互性和实时性要求。网络视频会议系统是一种典型的网络多媒体系统。多媒体网络应用对数据通信的要求：1高传输带宽要求；2不同类型的数据对传输的要求不同；3网络中的多媒体流传输的连续性与实时性要求；4网络中多媒体数据传送的低时延要求；5网络中的多媒体传输同步要求；6网络中的多媒体的多方参与通信的特点。改进传统网络的方法是：增大带宽与改进协议。增大带宽可从传输介质和路由器性能两方面入手。改进协议主要表现在支持IP多播、资源预留协议、区分服务与多协议标识交换等方面。21、机群系统的分类与计算与存储区域网络 P42-43第三章 局域网基础1、 局域网主要技术特点是：P452、共享介质访问控制方式主要为：（1） 带有冲突检测的载波侦听多路访问CSMA/CD方法。（2）令牌总线方法（TOKEN BUS）。（3）令牌环方法（TOKEN RING）。3、局域网参考模型（IEEE802）（1）IEEE802参考模型：IEEE802参考模型是美国电气电子工程师协会在1980年2月制订的，称为IEEE802标准，这个标准对应于OSI参考模型的物理层和数据链路层，数据链路层又划分为逻辑链路控制子层（LLC）和介质访问控制子层（MAC）。（2）IEEE803标准(P49)（3）IEEE802.2标准定义的共享局域网有三类：a、采用CSMA/CD介质访问控制方法的总线型局域网。(ETHERNET)b、采用TOKEN BUS介质访问控制方法的总线型局域网。c、采用TOKEN RING介质访问控制方法的环型局域网。（4）CSMA/CD的发送流程可以简单的概括为：先听先发、边听边发、冲突停止、延迟重发。冲突检测是发送结点在发送的同时，将其发送信号波形与接受到的波形相比较。（5）TOKEN BUS（令牌总线方法）是一种在总线拓扑中利用“令牌”作为控制结点访问公共传输介质的确定型介质访问控制方法。所谓正常稳态操作是网络已经完成初始化，各结点进入正常传递令牌与数据，并且没有结点要加入与撤除，没有发生令牌丢失或网络故障的正常工作状态。令牌传递规定由高地址向低地址，最后由低地址向高地址传递。令牌总线网在物理上是总线网，而在逻辑上是环网。交出令牌的条件：1 该结点没有数据帧等待发送。2 该结点已经发完。3 令牌持有最大时间到。环维护工作：1环初始化2新接点加入环3接点从环中撤出4环恢复5优先级（6）TOKEN RING（令牌环方法）4、CSMA/CD与TOKEN BUS、TOKEN RING的比较5、ETHERNET物理地址的基本概念（1） 地址与寻址的概念（2） ETHERNET物理地址的长度（48位）、构成、表示方法6、共享介质局域网可分为Ethernet，Token Bus，Token Ring与FDDI以及在此基础上发展起来的100Mbps Fast Ethernet、1Gbps与10Gbps Gigabit Ethernet。7、交换式局域网可分为Switch Ethernet与ATM LAN，以及在此基础上发展起来的虚拟局域网。8、光纤分布式数据接口FDDI是一种以光纤作为传输介质的高速主干网。FDDI主要技术特点:(1)使用基于IEEE802.5的单令牌的环网介质访问控制MAC协议;(2)使用IEEE802.2协议,与符合IEEE802标准的局域网兼容;(3)数据传输速率为100Mbps,连网的结点数小于等于1000,环路长度为100km;(4)可以使用双环结构,具有容错能力;(5)可以使用多模或单模光纤;(6)具有动态分配带宽的能力,能支持同步和异步数据传输.9、快速以太网（100Mbps Fast Ethernet） IEEE802.3U10、千兆位以太网（1Gbps Gigabit Ethernet） IEEE802.3Z Gigabit Ethernet的传输速率比Fast Ethernet（100Mbps）快10倍，达到1000Mbps，将传统的Ethernet每个比特的发送时间由100ns降低到1ns。11、10Gbps Gigabit Ethernet12、交换机的的帧转发方式：（各自特点）（1） 直接交换方式。（2） 存储转发交换方式。 （3） 改进直接交换方式。13、局域网交换机的特性：低交换传输延迟、高传输带宽、允许10Mbps/100Mbps、局域网交换机可以支持虚拟局域网服务。14、虚拟网络（VLAN）（1）是建立在交换技术基础上（局域网交换机或ATM交换机）的，以软件的形式来实现逻辑组的划分与管理，逻辑工作组的结点组成不受物理位置的限制。（2）对虚拟网络成员的定义方法上，有以下4种：用交换机端口号定义虚拟局域网、用MAC地址定义虚拟局域网、用网络层地址定义虚拟局域网（用IP地址来定义）、IP广播组虚拟局域网这种虚拟局域网的建立是动态的，它代表一组IP地址。15、无线局域网（1）无线局域网的应用领域 （P64）（2）红外无线局域网的主要特点及数据传输的三种技术 （P65）（3）扩频无线局域网：FHSS、DSSS （P66）（4）无线局域网标准：IEEE802.1116、IEEE 802.3物理层标准类型 （请补充完整P67）17、网卡是网络接口卡简称NIC是构成网络的基本部件。（1）网卡分类：按网卡支持的计算机种类：标准以太网卡。PCMCIA网卡（用于便携式计算机）。按网卡支持的传输速率分类：普通的10Mbps。高速的100Mbps网卡。10/100Mbps自适应网卡。1000Mbps网卡。按网卡支持的传输介质类型分类：双绞线网卡。粗缆网卡。细缆网卡。光纤网卡。(它们所使用的接口)18、局域集线器(HUB)普通的集线器两类端口：一类是用于连接接点的RJ-45端口，这类端口数可以是8，12，16，24等。另一类端口可以是用于连接粗缆的AUI端口，用于连接细缆的BNC端口，也可以是光纤连接端口，这类端口称为向上连接端口。按传输速率分类：1。10Mbps集线器。2。100Mbps集线器。3。10Mbps/100Mbps自适应集线器。按集线器是或能够堆叠分类：1。普通集线器。2。可堆叠式集线器。按集线器是或支持网管功能：1。简单集线器。2。带网管功能的集线器。19、局域网交换机（SWITCH）专用端口，共享端口。局域网交换机可以分为：1 简单的10Mbps交换机。2 10Mbps/100Mbps自适应的局域网交换机。3大型局域网交换机。20、各种组网方法21、结构化布线的地位及与传统布线的区别结构化布线系统与传统的布线系统最大的区别在于：结构化布线系统的结构与当前所连接的设备位置无关。结构化布线系统先预先按建筑物的结构，将建筑物中所有可能放置计算机及其外部设备的位置都布好了线，然后再根据实际所连接的设备情况，通过调整内部跳线装置，将所有计算机设备以及外部设备连接起来。22、智能大楼的组成:结构化布线系统、办公自动化系统（OA）、通信自动化系统（CA）、楼宇自动化系统（BA）、计算机网络（CN）23、结构化布线系统的应用环境：建筑物综合布线系统、智能大楼布线系统、工业布线系统（各自特点）24、网络互连（1）同种局域网使用网桥就可以将分散在不同地理位置的多个局域网互连起来。（2）异型局域网可以用网桥、路由器或网关互连起来。（3）ATM局域网与传统共享介质局域网互连必须解决局域网仿真问题。（4）路由器或网关是实现局域网与广域网、广域网与广域网互连的主要设备。（5）数据链路层互连的设备是网桥。网桥在网络互连中起到数据接收，地址过渡与数据转发的作用，它是实现多个网络系统之间的数据交换。（6）网络层互连的设备是路由器。如果网络层协议不同，采用多协议路由器。（7）传输层以上各层协议不同的网络之间的互连属于高层互连。实现高层互连的设备是网关。高层互连的网关很多是应用层网关，通常简称为应用网关。（8）网络互连指将分布在不同地理位置的网络，设备相连接，以构成更大规模的互联网络系统，实现互联系统网络资源的共享。（9）网络互连的要求（P80）（10）网络互连的问题（P80）（11）网络互连的功能有以下两类：1 基本功能。2 扩展功能。（12）网桥是在数据链路层上实现不同网络互连的设备。（网桥的基本特征（P81）。 网桥在局域网中经常被用来将一个大型局域网分成既独立又能互相通信的多个子网的互连结构，从而可以改善各个子网的性能与安全性。 基于这两种标准的网桥分别是：透明网桥（IEEE802.1适用于ETHERNET）、源路选网桥（IEEE802.5适用于TOKEN RING）（13）路由器是在网络层上实现多个网络互连的设备。（14）网关可以完成不同网络协议之间的转换。实现协议转换的方法主要是：直接将网络信息包格式转化成输出网络信息包格式 N(N-1)； 将输入网络信息包的格式转化成一种统一的标准网间信息包的格式 2N。一个网关可以由两个半网关构成。第四章 网络操作系统1、网络操作系统的三大阵营：UNIX、NOVELL公司Netware、Microsoft公司Windows NT2、单机操作系统的功能：（1）进程管理：对CPU的管理，在DOS中启动进程机制函数为EXEC在WINDOWS或OS/2中是Createprocess（2）内存管理：对RAM用户区的管理，DOS中的内存管理运行在实模式下而WINDOWS或OS/2中的运行在保护模式下（3）文件I/O管理：对硬盘的管理主要涉及文件的保护、保密、共享等。（文件名柄、FAT、VFAT、HPFS）3、网络操作系统（NOS）：（1）概述：是网络用户与计算机之间的接口一般具有硬件独立性的特征即独立于具体的硬件平台支持多平台。（2）概念：能使网络上各个计算机方便而有效的共享网络资源，为用户提供所需要的各种服务的操作系统软件。（3）功能：使连网的计算机能够方便而有效的共享网络资源，为网络用户提供所需要的各种服务的软件与协议的集合。（4）任务：屏蔽本地资源与网络资源的差异性、为用户提供各种基本网络服务功能、完成网络共享系统资源的管理、提供网络系统的安全性服务。4、网络操作系统分为两类：面向任务型NOS与通用型NOS。通用型又可以分为：变形系统与基础级系统。5、网络操作系统的发展经历了从对等结构与非对等结构演变的过程。（1）对等结构网络操作系统的特点、优点、缺点、提供服务（2）非对等结构网络操作系统，将连网结点分为以下两类：1 网络服务器。2 网络工作站。虚拟盘体可以分为以下三类：专用盘体（分配给不同用户，用户通过网络命令将专用盘体链接到工作站）、共用盘体（具有只读属性，允许多用户同时操作）与共享盘体（具有可读可写属性，允许多用户同时操作）（3）基于文件服务的网络操作系统，分为两部分：文件服务器（具有分时系统文件管理的全部功能，能为用户提供数据、文件、目录服务）、工作站软件。6、局域网软硬件的典型构成典型的局域网可以看成由以下三个部分组成：网络服务器，工作站与通信设备。7、网络操作系统的基本功能：文件服务、打印服务、数据库服务、通信服务、信息服务、分布式服务、网络管理服务、Internet/Internet服务（分别用一句话总结其特点）8、Windows NT（1）Windows NT Server是服务器端软件，Windows NT Workstation是客户机端软件（2）Windows NT的版本不断变化过程中有两个概念始终没有变那就是工作组模型与域模型（3）域的概念与分类： P94（4）特点（5个）： P94（5）Windows NT的优缺点 P95第二章 数据结构算法 2.1基本概率 考点1数据结构的基本概念 1.数据 在计算机系统中，数据不仅包含了通常的数值概念，还有更广泛的含义我们把采用计算机对客观事物进行识别、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的信息 数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位，又称为关键码，其值能够唯一确定一个数据元素的数据项。 2.数据结构 数据结构包括3个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式，以及在这些数据上定义的运算的集合。 (l)数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树型结构。 (2)数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。 (3)数据的运算。数据的各种逻辑结构都有相对应的运算，每一种逻辑结构都有一个运算的集合。数据运算主要包括查找(检索)、排序、插人、更新及删除等。考点2主要的数据存储方式 实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储结构是两种最主要的存储方式。 1.顺序存储结构 顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据。顺序存储结构的主要特点如下。 (1)由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自身的信息域，存储密度大，空间利用率高。 (2)数据结构中第i个节点的存储地址乙可由下述公式计算求得： L?iL?0(i1)×K L?0为第一个节点存储地址，左为每个节点所占的存储单元数。 (3)插人、删除运算会引起相应节点的大量移动各节点的物理地址是相邻的，每一次插人、删除运算会引起相应节点物理地址的重新排列。 2.链式存储结构 链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中链式存储结构的每个节点中至少有一个节点域，来体现数据之间逻辑上的联系。 链式存储结构的主要特点包括以下几个方面。 (1)节点中除自身信自、外，还有表示链接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低。 (2)：罗辑上相邻的节点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构的存储表示。 (3)插人、删除等操作灵活方便，不需要大量移动节点，只需将节点的指针值修改即可。考点3算法设计与分析 在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算，它是解决特定问题的方法。一个算法所占用的计算机资源包括时间代价和空间代价两个方面 时间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法运行时所耗费的时间也以某种单位由f( 1)增至f(n)，则称该算法的时间代价为f(n)。 空间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现时所占用的空间也以某种单位由到g(1)增至g(n)，则称该算法的空间代价为g(n)。2.2线性表 线性表的逻辑结构是由n个数据元素组成的一个有限序列。线性表中所包含元素的个数叫线性表的长度它是可变的可同线性表中增加或删除元素。线性表包括顺序表、链表、散列表和串等。 线性表的基本运算有：置表空、求表长、读表元素、插人、删除及检索等操作。考点4顺序表和一维数组 线性表的顺序存储是线性表的一种最简单的存储结构。其存储方法是：在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于或等于线性表的长度，让线性表的第一个元素存储在这个存储空间的第一个单元中，第二个元素存储在第二个单元中，其他元素依次类推。一般情况下，若长度为n的顺序表，在任何位置土插入或删除的概率相等，元素移动的平均次数均为n/2。考点5链表 链表分为线性链表和非线性链表二线性链表是线性表的链式存储表示，非线性链表是非线性数据结构树和图的链式存储表示。 1.线性链表 线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算时只需改变节点中指针域的值。 (1) 在指针一P后插人指针9的关键运算步骤： q . link：Plink： p . link：q； (2)删除指针P后继节点q的关键运算步骤： q：p . link； p. link：qlink； (3)在第一个节点(或称头节点)前插人一个指针P的关键运算步骤： p. link：head； head：二P； (4)删除表中头节点的关键运算步骤： head：head . link： 2.双链表 在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点。rlink指向节点的后继，llink指向节点的前驱，这样的结构方便向后和向前查找。 (l)若要在双链表中删除指针P所指的节点时，只需修改其前驱的rlink字段和后继的Mink字段，步骤如下： p . llink. rlink：p. rlink； PTrlink. llink：Pllink； (2)如果要在指针P后面插人指针q所指的新节点，只需修改P指针所指节点的rlink字段和原来后继均Ilink字段，并重新设置q所指节点的Mink和rlink值，步骤如下： q . Mink：P： qrlink：Prlink; Prlink r. Rink：q； prlink：q; 3.可利用空间表 可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。 考点6栈 栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运算，可进行运算的一端为栈顶( top)，另一端为栈底( bottom)。表中无任何元素的栈称为空栈。由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后进先出”(LIFO)表。 栈的基本操作有： (1) push(S,X)。往栈S中插人(或称推人)一个新的栈顶元素x，即进栈。 (2)pop(S)。从栈S中删除(或称弹出)栈顶元素，即出栈。 (3)lop(S，X)：把栈S的栈顶元素读到变量x中，栈保持不变。 (4)empty(S)。判断栈S是否为空栈，是则返回值为真。 (5)makempty。(S)将栈S设置为空。 栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。 考点7队列 队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入，而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的尾. 队列的基本操作有： (1) enq(Q, X)。往队列口中插人一个新的队尾元素x，即人队。 (2)deq(口)从队列Q中删除队头元素，即出队。 (3 ) front口,x)将队列口的队头元素值读到变量x中，队列保持不变。 (4)empty ( Q )判断队歹，l口是否为空，是则返回值为真。 (5)makempty(口)将队列口置为空队列。 和线性表一样、队列的存储方式也有顺序存储和链式存储两种。顺序队列在进行人队操作时，会产生假溢出现象解决的办法是让队列首尾相连，构成一个循环队列。 考点8串 串(或字符串)是由零个或多个字符组成的有限序列。零个字符的串是空串。串中字符的个数就是串的长度串中的字符可以是字母、数字或其他字符。 串的存储同样也有顺序存储和链式存储两种。顺序存储时，既可以采用非紧缩方式，也可以采用紧缩方式。 串的基本运算有连接、赋值、求长度、全等比较、求子串、找子串位置及替换等，其中找子串位置(或称模式匹配)比较重要。 2.3多维数组、稀疏矩阵和广义表 考点9多维数组的顺序存储 多维数组是一维数组的推广。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组就需要按一定次序把所有的元素排在一个线性序列里。常用的排列次序有行优先顺序和列优先顺序两种。考点10稀疏矩阵的存储 稀疏矩阵是指矩阵中含有大量的0元素。对稀疏矩阵可进行压缩存储，即只存储其中的非0元素。若非0元素分布是有规律的，可用顺序方法存储非0元素。对于一般的稀疏矩阵，常见的存储方法还有不元组法和十字链表法，这里就不再介绍了。考点11广义表的定义和存储 广义表(又称列表)是线性表的另一种推广，是由零个或多个单元素或子表所组成的有限序列。它与线性表的区别在于：线性表中的元素都是结构上不可分的单元素，而广义表中的元素既可以是单元素，又可以是有结构的表广义表与线性表相比，具有如下3个方面的特征。 (1)广义表的元素可以是子表，而子表的元素还可以是子表。 (2)广义表可被其他广义表引用二 (3)广义表可以是递归的表，即广义表也可以是自身的一个子表。2.4树型结构 树型结构是节点之间有分支的、层次关系的结构，它类似于自然界中的树，是一类重要的非线性结构常用的树型结构有树和二叉树。 考点12树的定义 树是树型结构的一个重要类型。一棵树或者是没有任何节点的空树，或者是由一个或多个节点组成的有限集合T，其中： (1)有且仅有一个称为该树根的节点。 (2)除根节点外的其余节点可分为。M(m0)个互不相交的有限集71,，兀，T ，其中每一个集合本身又是一棵树，并且称为根的子树。 这是一个递归的定义，即在树的定义中又用到了树的概念。这恰好显示了树的固有特性。 考点13二叉树定义 1.二叉树的定义 二叉树是一种最简单而巨重要的树型结构它或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。有两种特殊形态的二叉树，它们是满二叉树一和完全二叉树。 2.二叉树与树的区别 尽管树和二叉树的概念之间有许多关系，但它们是两个概念二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和了。子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 考点14树与二叉树之间的转换 1.树转换成二叉树 将一棵树转换成相应的二叉树应包括以下几个步骤： (1)在兄弟竹点之间加条连线 (2)对每一个节点，只保留它与第一个子节点的连线，与其他子节点连线全部抹掉 (3)以树根为轴心，顺时针旋转45。 2.森林转换成二叉树 如果F=是森林，则可按如下规则将其转换乘一棵二叉树B=(root,LB,RB,)： (1)若F为空，即m0，则B为树。 (2)若F非空，即m0, 则B的跟root即为森林中的第一棵树的跟ROOT(?T)；B的左子树LB是从T、中根节点的子树森林F1T11，T?，T?m转换而成的二叉树；其右子树RB是从森林F转换而成的二叉树。 3.二叉树转换成森林 如果B二(root，LB，RB)是、棵二叉树，则可按如下规则转换成森林F： (1)若B为空，则F为空。 (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root; T1中根节点的子树森林Fl是由B的左子树LB转换而成的；F中除T1之外其余树组成的森林F 是由B的右子树RB转换而成的。 考点15二叉树和树的周游 周游(或称遍历)是树型结构的一种重要运算，是其他运算的基础。周游一棵树就是按一定的次序访问树中听有节点，并且每个节点仅被访问一次的过程。 1.周游二叉树 二又树的周游主要有以下3种方式。 (1)前序法(NLR)。访问根，按前序周游左子树，按前序周游右子树。 (2)后序法(LRN)。按后序周游左子树，按后序周游右子树，访问根。 (3)对称序法(LNR)。按对称序周游左子树，访问根，按对称序周游右子树。 2.周游树和树林 对树和树林的周游分为按深度优先和按广度优先两种方式进行。 按深度优先方式又可分为按先根次序和按后根次序周游两种方式。 (1)先根次序周游访问第一棵树的根，按先根次序周游第一棵树的根子树，按先根次序周游其他的树。 (2)后根次序周游按后根次序周游第一棵树的子树，访问第一棵树的根，按后根次序周游其他的树。 比较一下树与一又树之间的对应关系，可以看出，按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同。 按广度优先方式可以做层次次序周游，首先依次访问层数为0的节点，然后依次访问下一层的节点，直至访问完最后一层的节点。 考点16二叉树的存储和线索 l二叉树的llink一rlink法存储表示 二叉树的存储通常采用链接方式，即每个节点除存储节点自身的信息外再设置两个指针域llink和 rlink，分别指向节点的左子女和右子女。当节点的某个子女为空时，则相应的指针值为空。再加上一个指向 树根的指针t，就构成了二叉树的存储表示。这种存储表示法被称为llink - rlink表示法。 2.线索二叉树 在有n个节点的二叉树的且ink - rlink法存储表示中，必定有n+1个空指针域，将这些指针位置利用起来，存储节点在指定周游次序F的前驱、后继节点指针，则得到线索二叉树。 考点17哈夫曼树 哈夫曼树是树型结构的一种应用二哈夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，这种树在信息检索中经常用到。所谓路径长度就是从一个节点到另一个节点所经过的分支总数。树的路径长度是从树的根到每个节点的路径长度之和。完全二叉树就是这种路径长度最短的二叉树。节点的带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之和，WPL最小的不是完全二叉树，而是权大的叶子离根最近的二叉树。2.5“查找 查找是数据结构中一种很常用的基本运算。 查找就是在数据结构中找出满足某种条件的节点。所给的条件可以是关键码字段的值，也可以是非关键码字段的值，本节只考虑基于关键码值的查找 考点18顺序查找 顺序查找是线性表的最简单、最基本的查找方法顺序查找的优点是对线性表节点的逻辑次序无要求，对线性表存储结构也无要求 顺序查找的缺点是速度较慢，平均检索长度与表中节点个数和n成正比，查找成功最多需比较n次，平均查找长度为(n +1 )/2次，约为表长的，半，查找失败需比较n+l次顺序查找算法的时间复杂度为O(n)。 考点19二分法查找 二分法查找是一种效率比较高的查找方法，在进行二分法查找时，线性表节点必须按关键码值排序，且 线性表是以顺序存储方式存储的。 二分法查找的优点是比较次数少，查找速度快，平均检索长度小，经过loge n次比较就可以完成查找过程。缺点是在查找之前要为建立有序表付出代价，同时对有序表的插人和删除都需要平均比较和移动表中 的一半元素。一般情况下，二分查找适应于数据相对固定的情况，且二分法查找只适用于线性表的顺序存储。 考点20分块查找 分块查找又称索引顺序查找，是介于线性查找和二分法查找之间的一种查找方法。它要求把线性表分 成若干块，每一块中的节点不必有序，但块与块之间必须排序，不妨设每一块中各节点的关键码都大于前一块的最大关键码值。另外，还要求将各块中的最大关键码值组成一个有序的索引表。满足上述条件的线性 表称做分块有序表。它的分块检索的过程分以下两步进行。 (I)先查索引表(可以用线性检索或二分法检索)，确定要找的记录在哪一块。 (2)在相应的块中线性检索待查记录。考点21散列表的存储和查找 散列存储中使用的函数称为散列(Hash)函数散列表(又称哈希表)是线性表的一种重要的存储方式 和检索方法。实现散列技术检索必须解决两个问题：一个是构造一个好的散列函数，尽可能避免冲突现象的发生；另一个是设计有效的解决冲突的方法。 1.散列函数 常用的散列函数有以下几种。 (l)除余法。选择一个适当的正整数川通常选p为不大于散列表存储区域大刁、的最大素数)，用p去除 关键码值，取其余数作为地址，即h(key)二key mod p。 (2)数字分析法。当关键码的位数比存储区域地址码位数多时，可以对关键码的各位进行分析，去掉分 布不均匀的位，留下分布均匀的位作为地址。 (3)折叠法。将关键码值从某些地方断开，分为几段，折叠相加，作为地址。 (4)中平方法。对关键码值求平方，取中间的几位数作为地址。 2.处理冲突的方法 发生冲突是指由关键字求得的散列地址为i(O-i-m一l)的位置上已存有记录，处理冲突就是为该关健字找到另一个“空”的散列地址。常用的处理冲突的方法有开地址法、拉链法等。 3.负载因子(装填因子)和平均检索长度 装填因子表示散列表的装满程度，定义为散列表中节点的数目除以基本区域能容纳的节点数所得的商，用a表示a越小，冲突的可能性越小，a越大，冲突的可能性越大，检索时需要比较的次数就越多。平均检索长度依赖于散列表的装填因子。 2.6排序 排序是数据处理领域经常要使用的一种运算，就是将一组元素按照关键码的递增或递减的顺序来排列为过程 按照排序过程中的存储器不同，可将排序方法分为内部排序和外部排序两类。一厂面将介绍插人排序、选择排序、交换排序和归并排序等几种常用的内部排序方法。 考点22插入排序 插人排序的基本思想：每一步将一个待排序的记录按其关键字值的大小插人到一个有序的文件中，插人后该文件仍然是有序文件。 l.直接插入排序 直接插人排序是一种最简单的排序方法它的基木思想是将一个记录插人到已排好序的有序表中，从而得到一个新的、记录数增I的有序表整个排序过程为：先将第一个记录看成是一个有序的子序列，然后从第2个记录起依次逐个地插人到这个有序的子序列中去。 直接插人排序的时间复杂度为0(n )。 直接插人排序方法不仅适用于顺序表，而且适用于单链表 2.二分法插入排序 在直接插人排序，若采用二分法查找而不是顺序查找待插入元素的插人位置，则称为二分法插入排序这种插人排序可减少比较次数，使排序速度有所提高，但提高不会太多，因为移动记录的总次数不受改变，其时间复杂度仍为0(n2)。 直接插人和二分法插入排序方法都是稳定的，因为它们不会改变原序列中具有相同关键字记录的相对次序。 3.希尔排序 希尔排序又称缩小增量排序，它是对直接插人排序的一种改进方法希尔排序的基本思路：对相隔较大距离的记录进行比较，就能使记录在比较后移动较大的距离这样能使较小的记录尽快往前移，较大的记录尽快往后移，从而提高排序的速度 希尔排序是一种不稳定的排序过程 考点23选择排序 选择排序的基木思想是每次从待排序的记录中选出关键码值最小或最大的记录放在已排好序的记录序列后面，直至排序完毕。 1.直接选择排序 直接选择排序也是一种简单的排序方法。选择排序的基本方法是：每次从待排序的区间中选择出具有最小排序码的元素。把该元素与该区间的第一个元素交换位置。第一次待排序区间为A1 An，经过选择和交换后，A1为最小排序码的元素。第二次待排序区间为A2An，经过选择和交换后，A2为仅次于A1的具有最小排序码的元素，依次类推，经过n-1次选择和交换后，排序完毕。 直接选择排序方法的时间复杂度为O(n2)，此方法是不稳定的。 2.堆排序 堆的定义如下：n个元素序列，当且仅当满足下列关系时，称之为堆。 人毛人KiK2i, KiK2i1，i1，2，n/2 堆排序的基本思想：对一组待排序的关键码，首先把它们按堆的定义排列成一个序列，找到其中最小的关键码接着将最小的关键码取出，然后将剩下的关键码再建堆排序，依次进行，直到将全部关键码排好为止。建堆的基本方法是将大的元素下沉，小的元素上浮，即所谓的筛选法。 在最坏的情况下，堆排序时间复杂度为O(nlog2 n )。堆排序仅需一个记录大小的辅助存储空间。堆排序是不稳定的。 考点24交换排序 交换排序的基本思想：两两比较待排序记录的关键字值，并交换不满足顺序要求的那些记录，直到全部记录满足关键字值排序要求为止。 1.起泡排序 起泡排序又称为冒泡排序，其基本思想是通过相邻记录之间关键字的比较和交换，使关键字值较小的记录逐渐从底部移向顶部，即从下标较大的单元移向下标较小的单元，关键字较大的记录从顶部移向底部。从起泡排序算法可以看出，若初始序列为“正序”序列，则只需进行一趟排序；反之，若初始序列为“逆序”序列，则需进行。一I趟排序。因此，总的时间复杂度为。(矿)。 起泡排序是一种稳定的排序过程。 2.快速排序 快速排序是口前内部排序中速度最快的一种排序算法，其实质是对起泡排序的改进在快速排序中，记录的比较和交换是从两端向中间进行的，排序码较大的记录一次就能够从前面交换到后面单元，排序码较小的记录一次就能够从后面交换到前面单元，记录每次移动的距离较远，总比较和移动次数较少。 快速排序是不稳定的排序。排序速度最快时，其时间复杂度为0 ( nlog, n )；排序速度最慢时，其时间复杂度为。(n)快速排序的平均时间复杂度为0 (nlog2 n )。快速排序除了需要一个记录的辅助空间来存放每次选取的基准记录外，还需要一个栈空间来实现递归。 考点25归并排序 归并是将两个或者多个有序表合并成一个有序表归井排序要求待排序文件已经部分排序。归并排序的基本思想是将这些已排过序的文件进行合并，得到完全排序的文件。 假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或I的有序子序列，再两两归并，如此重复，直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序。 归并排序平均时间复杂度为0(n1092 n )，辅助空间为0(n)。第3章操作系统 3.1操作系统 考点1操作系统概念 1.操作系统基本概念 操作系统是计算机系统中的一个系统软件，是控制和管理计算机硬件和软件资源，合理组织计算机工作流程及方便用户的程序集合。操作系统有两个重要的作用：一是管理系统中的各种资源；二是给用户提供一个友好的界面，方便用户操作计算机。 2.操作系统的基本特征 操作系统包括以下3个基本特征： (1)并发性。所谓并发性是指在计算机系统中同时存在多个程序，从宏观上看，这些程序是同时向前推生的。 (2)共享性。所谓资源共享性是指操作系统程序与多个用户程序共享系统中的各种资源。这种共享是在操作系统控制下实现的。 (3)随机性。操作系统运行在一个随机环境中。一个设备可能在任何时候向处理机发出中断请求，系统无法知道运行着的程序会在什么时候做什么事情。 考点2操作系统的功能 操作系统的主要功能包括以下几个方面。 (1)进程管理。主要是对处理机进行管理。 (2)存储管理。主要是对内存的分配、保护和扩充。 (3)设备管理。对所有输人、输出设备的管理。 (4)文件管理。主要涉及文件的逻辑组织和物理组织，目录的结构和管理。 (5)作业管理。为用户提供一个友好的环境，方便用户组织自己的工作流程。 考点3操作系统的类型 随着计算机硬件技术的不断发展，出现了多种类型的操作系统：手工操作系统、批处理操作系统、分时系统、实时系统及通用操作系统。随着网络技术的发展，相应地出现了网络操作系统和分布式操作系统。下面将对主要的操作系统进行简单介绍。 1.批处理操作系统 批处理操作系统最大的特征就是用户不直接操作计算机，而是将作业交给系统操作员，由操作人员将作业成批地输人计算机，然后按某种调度策略，顺序地执行作业流中的每一个作业，以节省人工操作时间和 提高机器的使用效率。批处理操作系统又可分为单道批处理系统和多道批处理系统。 2.分时系统 分时系统中的分时指多个用户通过终端可同时使用一台计算机。操作系统在接收用户发出的请求后，按照时间片轮转算法轮流分配给每个用户一段CPU时间，进行各自的处理。但对于每个单独的用户都仿佛自己独占了整个计算机系统分时系统主要有以下几个方面的特点： (1)多路性若干个用户同时使用一台计算机，从微观上看是各用户轮流使用计算机；从宏观上看是各用户在并行工作。 (2)交互性二用户可根据系统对清求的响应结果，进一步向系统提出新的请求。 (3)独立性用户之间可以相互独立、互不十涉；系统保证各用户程序运行的完整性，不会发生相互混淆或破坏等现象。 (4)及时性系统对用户的输人及时做出啊应。分时系统性能的主要性能指标之一是响应时间，即从终端发出的命令到系统予以应答听需的时间。 3.实时系统 实时系统是指可对外部事件做出及时洞应并在一定时间内完成对事件的处理的操作系统，其特点是及时响应和高可靠性实时系统可分为实时控制系统和实时信息处理系统两大类。 4.个人计算机操作系统 个人计算机操作系统是指用于个人计算机上的操作系统，提供联机交互功能：这要求系统有友好的用 户接口和操作界面 5.网络操作系统 网络操作系统可通过通信设备将分散的具有独立功能的多个计算机系统互联起来，用于实现信息交换、资源共享、互操作和协作处理的系统各用户间都要遵守一定的网络协议来共享资源。 6.分布式操作系统 分布式操作系统可统?管理和调度整个系统上的资源以实现各计算机之间的资源共享和信息传输，对任务实行动态、合理的分配及并行的处理分布式系统各个计算机之间无主次之分，为用户提供一个标准的接口和统一的界面，使用户方便实现听需要的操作。 考点4研究操作系统的方法 研究操作系统可以从以下几种不同的角度进行 1.资源管理观点 从资源管理的观点来看，操作系统的管理对象是计算机系统的资源，操作系统则是管理系统资源的程序集合通常，把操作系统分为处理机管理、存储管理、设备管理、作业管理和文件管理等5个主要部分，由这几部分程序的协调、配合来完成用户的作业要求。 2.进程观点 这种观点把操作系统看作由若干个可以同时独立进行的程序和一个对这些程序进行协调的核心所组成，这些同时运行的程序称为进程，每个进程都可完成某一特定的任务。 3.虚机器观点 从服务用户和机器功能扩充的观点来看，操作系统为用户使用计算机提供了许多服务功能和良好的工作环境。 考点5操作系统的硬件环境 硬件是构造操作系统的基础，硬件对操作系统的构造提供必要的支持。通常，操作系统所涉及的硬件环境主要包括以下几个方面。 1.特权指今与处理机状态 (1)特权指令。只允许操作系统使用，而不允许一般用户使用的指令。 (2)非特权指令。特权指令之外的指令称做非特权指令，非特权指令的执行不影响其他用户及系统。 (3)CPU状态。CPU交替执行操作系统程序和用户程序。在执行不同程序时，根据运行程序为机器指是，的使用权限而将CPU置为不同的状态CPU的状态属于程序状态字PSW中的一位。 2.中断机制 中断机制是现代计算机系统中的基本设施之一，它在系统中起着通信联络的作用，以协调系统对各种外部事件的响应和处理。 3.定时装置 为了实现系统管理和维护，硬件必须提供时钟，即定时装置硬件时钟通常分为两类：即绝对时钟和相讨时钟。 3.2进程管理 考点6多道程序设计 1.程序的顺序执行 程序的顺序执行具有以下几个特点： (1)顺序性。程序所规定的动作在机器上严格地按顺序执行，每个动作的执行都以前一个动作的结束为前提条件。 (2)封闭性。程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响，即只有程序本身的动作才能改变程序的运行环境。 (3)可再现性。顺序执行的最终结果与程序运行的速度无关。 2.多道程序系统中程序执行环境的变化 程序执行环境具有以下3个特点： (1)独立性。在多道环境下执行的每道程序都是逻辑上独立的，且执行速度与其他程序无关，执行的起止时间也是独立的。 (2)随机性。在多道程序环境下，程序和数据的输入与执行的开始时间都是随机的。 (3)资源共享性。一般来说，多道环境下执行程序的道数总是多于计算机系统中CPU的个数，单CPU也是如此。 3.程序的并发执行 程序的并发执行是指为了充分利用系统资源，提高计算机的处理能力，在计算机系统中有两个或两个以上的程序同时执行的状态。参与并发执行的程序称为并发程序，并发程序执行时的特点如下： (1)各并发程序在执行期间相互制约。 (2)程序与计算不是一一对应的关系。 (3)不可再现性。 4.多道程序系统 一般情况下，计算机要同时处理多个具有独立功能的程序来增强系统的处理能力和提高机器的处理效率。常采用并行操作技术来使系统的各种硬件资源做到并行工作，即在计算机中，所运行程序的道数(吞吐量)多。程序在运行时有如下3个特点：独立性、随机性和资源共享性。 考点7进程 1.进程的概念 进程是操作系统中最基本、最重要的概念。通常是指内存区域中的一组指令序列的执行过程，是程序中具有一定独立功能的关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立单位。 2.进程的特性 (1)并发性可以同其他进程一道向前推进，即一个进程的第一个动作可以在另一个进程的最后一个动作结束之前开始 (2)动态性是指进程对应用程序的执行过程，体现在两方面：其一，进程动态产生，动态消亡；其二，在进程的生命周期内，其状态动态变化。 (3)独立性。一个进程是一个相对完整的调度单位，它可以获得处理机并参与并发执行。 (4)交往性。一个进程在运行过程中可能与其他进程发生直接的或间接的相互作用。 (5)异步性。每个进程按照各自独立的、不可预知的速度向前推进。 3.进程与程序的区别与联系 (1)进程是程序的执行，是动态的；而程序是指令的集合，是静态的。 (2)进程的存在是有限的，从运行到结束，是暂时的；而程序则是永久存在的。 (3)进程包括程序、数据和进程控制块(PCB)。 (4)一个程序可以有多个进程，一个进程也可以包含多个程序。 4.进程的状态 进程在其存在过程中，它们的状态在不断发生变化。系统中的不同事件均可以引起进程状态的变化。 一般情况下，一个进程可分为以下3种状态： (1)就绪状态。是指一个进程已经具备运行条件，但由于没有获得CPU而不能运行所处的状态。一旦 把CPU分配给它，该进程就可运行二处于就绪状态的进程可以是多个。 (2)运行状态。是指进程已获得CP1,并且在CPU上执行的状态。 (3)等待状态。也称阻塞状态或封锁状态，是指进程因为等待某种事件发生而暂时不能运行的状态。 在一定的条件下，进程的状态是可以相互转换的。 5.进程控制块 进程控制块(Process Contro1 B1ock，简称PCB)是用来记录进程状态及其他相关信息的数据结构,PCB是进程存在的唯一标志，PCB存在则进程存在。系统创建进程时会产生一个PCB，撤销进程时，PCB也自动消失。 考点8进程控制 进程控制也称进程管理，对进程实施有效的管理，包括进程的建立、撤销、进程阻塞及进程的唤醒等。 进程控制是通过原语来实现的，用于进程控制的原语一般有：创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒进程及改变进程优先级等。 1.创建原语 创建原语用于建立一个新的进程，其主要操作过程是先向系统申请一个空闲的PCB，然后根据父进程提供的参数，将相关信息填入，最后返回一个进程的内部名。 2.撤稍原语 撤销原语是用于撤销一个已完成任务的进程，以释放它所占用的所有的内部和外部资源。实质上是撤销PCB，有两种撤销策略，一种是只撤销1个具有特定标识符的进程，另一种是撤销该进程及其所有子孙进程。 3.阻塞原语 阻塞原语的作用是将进程由运行状态变回阻塞状态。具体过程是先中断CPU，将CPU的当前状态保存在PCB现场信息中，将进程的当前状态置为等待，插人到等待队列中去。 4.唤酸原语 唤醒原语的作用是将进程由阻塞状态变为就绪状态，其操作过程是在等待队列中找出某进程，将它的当前状态置为就绪，然后将其从等待队列中撤出并插人到就绪队列中去。考点9进程的同步与互斥 1.临界资源和临界区 临界资源是指一次只允许一个进程使用的资源：一个进程中访问临界资源的那段程序代码称为临界区。它们不允许两个及以上的进程同时访问或修改。 2.进程的同步 进程的同步运行是指进程之间的一种直接的协同工作关系，这些进程通过相互合作来完成一项任务。 3.进程的互斤 进程间一种间接的相互作用构成进程互斥。进程互斥的目的就是使某一进程可以在某一时间内独占一些资源? 考点10进程通信 1.信号量和P, V操作 解决进程的同步与互斥，既可用硬件实现，也可用软件实现。 (1)在系统中信号量(S)是一个整数。当S- 0时，表示可供并发进程使用的资源实体数；当S0时，代表等待使用临界区的进程数。 (2)只能通过P、V操作原语来改变P,V操作信号量的数值。P操作表示在当前进程申请的各种资源，V操作代表当前进程释放所占用的资源。P操作和V操作都是低级进程通信原语。 (3)利用P、V操作可以解决并发进程间的互斥问题。 (4)利用P、V操作也可以解决并发进程间的同步问题。 2.高级通信机构 对进程间大量信息的交换常采用消息通信的方法，高级通信原语不仅可保证相互制约的进程的正确关系，同时还实现了进程之间的信息交换。该方法不仅能实现进程间的通信，而且能实现进程间数据的传送。下面分别介绍3种高级进程通信。 (1)消息缓冲通信。消息缓冲通信的基本思想：系统管理一组消息缓冲区，在每一个缓冲区可以存放一个信息。发送进程在发送消息前，在内存中设置一个发送区，装人欲发送的消息，在申请到一个消息缓冲区以后，将发送区里的消息发送到缓冲区中。 (2)管道通信。管道通信实质上是利用外存来进行数据通信，传输数据量大，但速度较慢。发送进程从管道的一端写人数据，接收进程在需要的时候从管道的另一端读出数据。 (3)信箱通信。信箱通信指进程并不把消息直接发送给对方，而是将通信的消息以信件的方式放在信箱内。 考点11进程调度 进程调度即处理机调度在多道程序系统中，进程数目往往大于处理机数目，这会使进程相互争夺处理机，必须按照一定的策略将C 1't分配给这些进程中的某一进程 1.进程调度的功能 记录系统中所有进程的状态、优先数及资源使用情况，CPU空闲时按一定算法确定将CPU分配给哪个进程和分配多长时价。 2.进程调度方式 进程调度方式是指有优先数更高的进程进人就绪队列时，如何分配CPU，一般包括剥夺方式和非剥夺方式两种调度方式 3.进程调度算法 (1)先来先服务算法FCFS。该算法按照进程进入就绪队列的先后顺序来选择二即每当进行进程调度时总是把就绪队列的队首进程投人运行二 (2)时间片轮转算法。这主要是分时系统中使用的一种调度算法。其基本思想是：将CPU的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行一个时间片。当时间片结束时，就强迫运行进程让出CPU，该进程进人就绪队列，等待下一次调度。同时，进程调度又去选择就绪队列中的另一个进程，分配给它一个时间片，以投人运行。 影响时间片大小设置的主要因素有：系统响应时间、就绪进程数目(终端数目)和一计一算机处理能力。 (3)最高优先级算法进程调度每次将处理机分配给具有最高优先级的就绪进程，进程的优先级由进程优先数决定 进程优先数的设置可以是静态的，也可以是动态的。 最高优先数算法又可与不同的C1'U方式结合起来，形成可剥夺式最高优先数算法和不可剥夺式最高优先数算法。 考点12死锁 1.死锁的概念 死锁是指在多道程序系统中，两个或两个以上的进程无限期地等待永远不会发生的事件，得不到所需资源因而不能运行的状态处于死锁状态的进程称为死锁进程。 死锁产生的原因：一是系统资源不足；二是多道程序运行时，进程的推进顺序不合理。 2.产生死锁的必要条件 (1)互斥条件。进程互斥使用资源，任一时刻一个资源只为一个进程独占，其他进程若请求一个已被占用的资源，只能等占用者释放后才能使用 (2)不可剥夺条件(不可抢rt1-)。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放 (3)部分分配(占有等待)。进程每次申请它所需要的一部分资源，在申请新的资源的同时，继续占用已分配到的资源。 (4)循环等待：存在一个进程环路，环路中每一个进程已获得的资源同时被下一个进程所请求。 3.资源分配图 死锁问题可用一个有向图来表示。资源分配图就是描述进程、资源及它们之间关系的有向图。当进程请求资源时，系统检查并发进程组是否构成资源的请求环路。存在环路，可能存在死锁；不存在环路，一定没有死锁。 4.死锁预防 只要破坏死锁产生的4个必要条件之一，就可有效避免死锁的产生，主要有以下几种方法： (1)破坏互斥条件 (2)破坏不可剥夺条件。 (3)破坏部分分配条件二 (4)破坏循环等待条件 5.死锁解除 当发现死锁后，可采用以下两种方法来解除死锁： (1)资源剥夺法。从一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态 (2)撤销进程法。按照某种策略逐个地撤销死锁进程，直到获得为解除死锁所需要的足够使用的资源为按照什么原则撤销进程，实用而又简便的方法就是撤销那些代价最小的进程，或者撤销进程的数量最少。 考点13线程 1.线程的概念 线程是进程中的一个实体，是CPU调度和分派的基本单位 2.线程的属性 (1)每个线程有一个唯一的标识符和一张线程描述表。 (2)不同的线程可以执行相同的程序。 (3)同一级的进程中的各个线程共享该进程的地址空间。 (4)线程是处理器的独立调度单位，多个线程是可以并发执行的。 (5)一个线程被创建以后便开始了它的生命周期，直到终止。 3.线程与进程的比较 线程与进程的主要区别表现在以下几个方面： (1)调度。在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位只有进程，而在引线程的操作系统中，则把线程作为调度和分派的基本单位，把进程作为资源拥有的基本单位，使传统进程两个属性分开，从而使线程能轻装运行，这样可以显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程切换，在由一个进程中的线程切换到另一进程中的线程时，将会引起进程切换。 (2)并发性在引人线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之也可以并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统的吞吐。在引入了线程的操作系统中，可以在一个文件服务进程中设置多个服务线程。当第一个线程等待时，件服务进程中的第二个线程可以继续运行；当第二个线程封锁时，第3个线程可以继续执行，从而显著地高了文件服务的质量及系统的吞吐量C (3)拥有资源不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位。一般地说，线程自己不拥有系统资源(也有一点儿必不可少的资源)，但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及系统资源(如已打开的文件、1/0设备等)，可供同一个进程的其他所有线共享 (4)系统开销。由于在创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、1/0设备等。因此操作系统所付出的开销将显著地大于在创建或撤销线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程CPU环境的保存及新近被调度运行的进程的CPU环境的设置。而线程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。 3.3作业管理 考点14操作系统与用户之间的接口 操作系统向用户提供了两类接口：一类是程序级接口，另一类是作业级接口。 1.程序级接口 程序级接口是由一组系统调用命令组成的。系统调用命令可以看成是机器指令的扩充，用户通过在程序中使用这些系统调用命令来请求操作系统提供服务。 2.作业级接口 作业级接日是为用户在作业一级请求操作系统为其服务而设置的，用户可通过这类接口组织控制作业的工作流程。作业级接1-1可分为联机接口和脱机接口两类。 考点15作业管理 作业就是用户在一次事务处理过程中，要求计算机系统所做工作的总称。一个作业分为几个步骤，每个步骤称为作业步。在批处理系统中将作业安排在输人设备上，然后依次读人系统进行处理，从而形成了 作业流作业管理分为作业调度和作业控制两部分。 1.作业调度 作业调度的主要任务是：按照各种调度算法，从后备作业队列中挑选一批合理搭配的作业。进人运行状态，同时，为选中的作业分配内存和外部设备等资源，为其建立有关的进程，当作业执行结束进人完成状态时，做好释放资源等善后处理工作。 (1)作业的状态：一个作业进入系统到运行结束，要经过4种状态的变迁，即提交状态、后备状态、执行状态和完成状态 (2)作业调度算法：常用的作业调度算法有以下几种 先来光服务算法 短作业优先算法 最高响应比作业优先算法 优光数算法 2.作业控制 作业控制是指用户或系统操作员对作业运行的全过程控制。作业控制可以分为联机作业控制和脱机作业控制两种方式。 3.4存储管理 考点16基本概念 1.存储器 存储器是计算机系统中的重要资源，必须重点管理的资源。存储器可分为3类：主存储器、外存储器和高速缓存 2.存储管理的主要目的和功能 (1)内存空间的分配和回收。操作系统为每个进程分配一定的内存空间，进程结束时要收回内存空间。 (2)内存空间的共享。内存共享是指两个或多个进程共用内存中相同的区域，其目的是节省内存空间，实现进程间通信，提高内存空间的利用效率。存储共享的内容可以是程序的代码，也可以是数据。 (3)存储保护。在多道程序并发运行的环境下，内存中系统程序和数据段可供不同的用户进程共享。为了保护存储区内各类程序和信息不被破坏和干扰，保证系统正常运行，需要对内存中的程序和数据段采取保护措施。内存保护一般有防止地址越界和防止操作越权两种方式。 (4)地址映射。地址映射又称为地址的重定位。地址有物理地址和逻辑地址(又称相对地址)两个概念。 程序被调入主存时，首先要将程序的逻辑地址变换为物理地址，包括相应地调整程序中有关地址的指令，这个过程称为地址重定位。重定位的方法有两种：静态地址重定位和动态地址重定位 (5)内存扩充。系统中内存容量是有限的，操作系统为了满足用户的作业对内存空间的需要，以某种方式将内、外存联合起来，向用户提供一个虚拟存储器，其容量比实际内存要大得多。 3.碎片管理 碎片是指内存中出现的一些零散的小空闲区域解决碎片的方法是紧凑(拼接)技术. 考点17分区存储管理 分区式存储管理是满足多道程序运行的一种存储管理技术，其基本思想是将内存划分为若十连续区域，称为分区，每个分区装入一个运行作业。按分区的方式，又可分为同定分区和可变分区。 1.固定介区 固定分区是指在处理作业前将内存划分为若十个固定大小的存储区，每个分区装人一个作业，到该作业完成后收回该区。固定分区会浪费一些存储空间。 2.可变介区 可变分区是指在作业装人内存时进行分区，分区的大小正好与作业要求的存储空间相等，分区的个数与大小都是不确定的。这种分区方式的缺点就是会引起碎片的产生。 系统利用空闲区表来管理内存中的空闲分区，常用的分配策略有：最先适应算法、最佳适应算法和最坏适应算法。系统为正在运行的进程提供一对硬件寄存器，可采用两种方式： (1)基址寄存器和限长寄存器。 (2)上界寄存器和下界寄存器。 考点18页式存储管理 1.基本概念 (1)内存分配。页式存储管理把内存空间分为相同大小的存储区称为“块”，用户的作业地址空间也分成与“块”同样大小的若干个片段，称之为“页”。页和块从零开始按顺序编号，分别称为“页号”和“块号”。 分配内存时，每一个页对应一个块，这些块在物理上可以是连续的，也可以是不连续的； (2)页表。在内存中的固定区域，系统为每个作业建立了一个页面映像表，简称“页表”。页表的作用是实现从页号到物理块号的地址映射，页表中有页号、块号和状态。页表状态是表示该页是否已经调人内存，1为已经调入，0为尚未调入。 (3)快表。快表是存放在一个具有并行查询能力的特殊高速缓存中的活动页。 (4)页面大小。页面大小直接影响到地址转换和页式存储管理的性能，一般取2的整数次幂。页面太大则与分区存储相差不大，页面太小则会增加系统的开销。 2.含实现方法 系统为用户程序建立一张页表，用于记录用户程序逻辑负面与内存物理页面之间的对应关系。并且设立一张内存空闲页面表，来记录内存物理页面情况，用于内存分配和回收。为了实现页式存储，要有一对硬件寄存器，即页表始址寄存器和页表长度寄存器。 考点19段式存储管理 1.基本原理 (1)内存划分在段式管理中，作业的地址空间分成若干段，每段都是一个连续的地址空间，每个段中有一个起始地址即段首址段中所有单元从零开始依次编址，得到段内地址。 (2)逻辑地址用户程序按逻辑上有完整意义的段来划分的存储空间称为逻辑段。用户程序的逻辑地址由段号和段内地址两部分组成。 (3)内存分配系统为每个逻辑段分配一个连续的内存区域，但逻辑上连续的段在内存中不一定连续存放 2.实现方法 系统为每个用户程序建立一张段表，用于记录用户程序的逻辑段与内存物理段之间的对应关系。一个段表包括逻辑段号、物理段首址和物理段长度。同时系统还产生一张内存空闲区表，记录内存中空闲区域情况，便于分配和回收内存实现段式存储的硬件是需要段表始址寄存器和段表长度寄存器。 3.段的保护 为保证段的共享并使程序顺利运行，一般对段采取的保护措施有：利用段表及段长来保护段，防止程序运行时地址越界；存取权限保护；存储保护键保护。 考点20段页式存储管理 1.基本思想 用页式存储管理方法来分配和管理内存，用段式方法对用户程序按照其内存的逻辑关系分成若干段，每一段划分成若干个大小相等的页面 2.实现方法 (1)系统为用户建立一张段表来记录页表始址和页表长度。 (2)建立一张页表来记录该段中的逻辑页号与物理页号之间的对应关系。 (3)建立张内存空闲页面表来记录内存空闲页面。 (4)硬件支持 (5)地址映射过程 考点21虚拟存储管理 虚拟存储得以实现是由程序的局部性原理来决定的。程序的局部性原理包括时间局部性和空间局部性。虚拟存储管理技术是指在一个进程运行时，进程的程序不是一次全部装入内存，而是可多次分别装入，暂时不用的部分可退出内存，将需要用到的部分装人。 系统分配给每个程序的页面数是有限的，若缺页而内存中又无空白区时，就要对内存中的页面及时更换，称为“页面淘汰”。若页面淘汰处理不当，则会出现被淘汰的页面又需要访问而再次调人的现象，出现反反复复的频繁调度，降低系统的效率。常用的页面淘汰算法有：先进先出法(F1FO)、最近最久未使用淘汰算法(1RU)、最佳淘汰算法(OPT)及最近最少使用淘汰算法(1FU)。 3.5文件管理 考点22文件与文件系统 1.文件的概念 文件是具有符号名(文件名)的、在逻辑上具有完整意义的一组相关元素的有序集合文件是操作系统进行信息管理的基本单位。文件可由若干个记录组成，记录是一些相关的信息项的集合，是用户存取文件的基本单位。 2.文件的分类 从不同的角度对文件进行分类，主要有以下几种： (1)按文件的性质和用途可分为系统文件、库文件及用户文件。 (2)按文件的物理结构可分为连续文件、索引文件、链接文件、索引顺序文件和Hash文件。 (3)按文件的逻辑结构可分为记录文件和流式文件。 (4)按文件的存取方式可分为顺序存取文件和随机存取文件 (5)按文件的保护级别可分为只读文件、读写文件、可执行文件和无保护文件。 (6)UN1X系统中的文件可分为普通文件、目录文件和特殊文件： 3.文件系统 所谓文件系统，就是操作系统中实现文件统一管理的一组软件、被管理的文件及为实施文件管理所需要的一些数据结构的总称 文件系统的优点包括以下几个方面： (1)按名存取文件以对用户透明的方式实现对名字空间的管理和信息浮动，使用方便灵活。 (2)采取保护、保密措施，安全可靠。 (3)实现文件共享，节省空间和时间开销。 考点23文件结构和存取方式 一个文件的结构有逻辑结构和物理结构之分逻辑结构是从用户角度所看到的文件组织形式；物理结 构又称为文件的存储结构，是文件在外存上的存储组织形式。 1.文件的逻辑结构 有记录式的结构文件和流式的结构文件。在记录式的文件中，有着相同的数据项，文件的长度用记录数口表示。流式文件的长度是以字节为单位的，对它的访问是利用读写指针来完成的。 2.文件的杨理结构 文件的物理结构是指文件的内部组织形式，即文件在物理存储设备上的存放方法它一般分为连续结钩、链接结构、索引结构及Hash结构等。 3.文件的存取方式 文件的存取方式是由文件的性质和用户使用文件的情况而定的，一般可以采用顺序存取和随机存取两种形式。顺序存取是按照文件的逻辑地址顺序存取；随机存取可以允许以任意次序直接存取文件中的某一个记录。 考点24文件目录 文件系统的最大特点就是“按名”存取。 1.一文件控制块FCB 系统为所有存人的文件建立一个从文件名到文件存储地址的映射，即设置一个文件控制块FCB(系统为管理文件而设置的一个数据结构)，对文件进行管理，并存放映射信息和其他管理信息。 2.文件目录与目录文件 文件目录是文件控制块的有序集合，提供了用户与文件系统之间的接口。口录文件是将文件目录以文件的形式保存在外存空间。日录文件是长度固定的记录式文件。 3.文件目录结构 文件口录的结构形式按系统的大小分为一级目录、二级目录和多级目录。口前大多数操作系统如11nux ,DOS等都采用多级目录结构，又称树型目录结构。 4.当前目录 当前目录是系统为用户提供一个目前正在使用的工作目录。引入这概念，可以提高检索速度。 5.文件目录的改进 把目录项(文件控制块)分为名号目录项和基本目录项，这种文件叫做目录项分解法，它可以提高文件检索速度。 考点25文件存储空间的管理 1.位示图法 系统为文件存储空间建立一张位示图，用一串二进制数值来反映磁盘空间的分配和使用情况。 2.空闲块表法 空闲块表法是将所有的空闲块按照一定的方式链接在一起，当申请者需要空闲块时，分配程序从链表上选取合适的空闲块分配给它。 3.空闲块镬表法 系统将所有空闲物理块组成一个链，外存空间的申请和释放以块为单位，申请时从链首取一块，释放时将其链人链尾。 考点26文件的存取控制及安全性 1.文件的存取控制 文件的存取控制体现为文件的共享、保护和保密3个方面。 2.文件的操作和使用 在通常情况下，文件系统应该提供一些有关文件操作的系统调用，以便用户方便、灵活、有效地使用文件。最基本的命令有：建立文件、打开文件、读文件、写文件、关闭文件和撤销文件。 3.文件的系统安全 文件系统的安全性是指抵抗和预防各种物理性破坏及人为性破坏的能力。常用的措施是备份，通过转储操作来完成，包括海量转储和增量转储。 3.6设备管理 考点27设备管理概述 没备管理是指操作系统对除CPU和主存储器以外的其他一切硬件部分的管理 1.设备的分类 (1)按设备的卜作特性可以分为存储设备和输人输出设备两种。 (2)按设备的从属关系可以分为系统设备和用户设备两种。 (3)按照设备分配方式可以分为独享设备、共享设备和虚拟设备3种。 2.设备管理的目的和功能 管理的口的就是要提供一个方便的巨独、达于设备的接口，它将用户和硬件特性分开，提高CPU与输人输设备之间、设备与设备之问的并行1一作程度，从而提高外部设备资源的使用效率，并可以解决CPU与设备之的瓶颈问题设备管理程序提供的功能有设备分配和回收、管理输人输出缓冲区、设备驱动、外部设备中断理、虚拟设备及其实现和1/0操作 CPU对设备的控制主要有4种方式：循环测试1/0方式、中断处理方式、直接内存存取(DMA)方式和通道控制方式。 考点28缓冲技术 缓冲技术是系统在内存中开辟一个区域作为缓冲区，用于暂时存放内存和外没之间的传输数据，改善外没备与CPU速度不匹配的问题，减少中断次数和CPU中断的处理时间、缓冲区分为硬件缓冲区和软件缓冲区。根据系统设置缓冲器个数的多少，叮以分为单缓冲、双缓冲和多缓冲。 考点29设备分配 设备分配就是按照一定的策略给需要设备的进程分配合适的设备，设备类型不同，分配策略不同。从分配的角度来看，可将系统的设备分为独占、共享和虚拟3种 1.独占设备的介配 独占分配方式又分为静态分配方式和动态分配方式独：；方式的设备分配算法通常有两个：一是先来先服务，二是优先级高者先服务。 2.共享设备的分配 付共享设备的使用，用户常通过文件系统进行。用户以文件的形式将自己的信息存放在共享设备上，需要使用时再进行存取 3.虚拟设备的分配 虚拟设备最常用的是SPOO11ng( S1mu1taneous Per1phera1 Operat1on On-11ne)技术，又称假脱机技术。SPOO11ng系统由输入SPOO11ng和输出SPOO11ng两部分组成SPOO11ng系统将一个作业从进入系统到完成退出系统的过程划分成输人、处理和输出3个并发执行的过程。 考点30设备管理程序 1.设备介配程序 在进行设备分配时，通常借助一些表格，如设备控制表、系统设备表、控制器表和通道表等，在这些表格中录了相关设备或控制器的状态及对设备或控制器进行控制所需的信息。 2.设备处理程序 设备驱动程序和设备中断处理程序统称为设备处理程序。设备驱动是控制设备实现1/0操作，完成相应的硬件任务；中断处理是恢复CPU对设备的控制。 考点31通道技术 1.通道分类 按照信息交换的方式和连接的设备种类，通道可以分为以下3种类型：字节多路通道、选择通道和成组多路通道。 2.工作原理 通道具有自己的指令系统，包括读、写、控制、转移、结束及空操作等，就像一个功能简单的处理器。通道的运算控制部件包括：通道地址字(CAW)、通道命令字(CCW)、通道状态字(CSW)。通道与CPU共享一个内存，其访问内存的形式是“周期窃用”方式。第4章数据库系统基本原理 4.1数据库基本概念 考点1数据库的基本概念 1.信息 信息(Information)是现实世界事物的存在方式或运动状态的反映。 2.数据 数据(Data)是用于描述现实世界事物的符号记录，包括数字、文字、图形和声音等。数据有多种表现形式，是信自、表达方式的一种。 3.信息与数据的关联 数据是信息的符号表示，或称载体；信息是数据的内涵，是数据的语义解释。信息与数据是密切相关联的，因此，在某些不需要严格区分的场合，也可以把两者不加区别地使用，例如信息处理也可以说成数据处理。 4.数据库 数据库(DataBase，简称DB)是长期存储在计算机内的有组织的、可共享的数据集合。其数据是按一定的数据模型组织、描述和存储的，具有较小的冗余度、较高的数据独立性和易扩展性，并可为一定范围内的各种用户共享 5.数据库管理系统 数据库管理系统(DataBase Management System，简称DBMS)是指负责数据库存取、维护和管理的系统软件。它的基本功能有：数据定义功能、数据操作功能、数据库的运行管理和数据库的建立、维护功能。 6.数据库系统 数据库系统(DataBase System,简称DBS )是指在计算机系统中引人数据库后的系统构成。一般由数据库、操作系统、数据库管理系统(及其工具)、应用系统、数据库管理人员和用户构成。 考点2数据管理技术发展的3个阶段 数据管理技术的发展同计算机硬件、软件和计算机应用的范围有着密切关系。它是对数据的分类、组织、编码、存储、检索和维护的技术，其发展经过如下3个阶段： 1.人工管理阶段 该阶段具有如下几个特点： (1)数据不保存。 (2)由应用程序管理数据。 (3)数据不共享。 (4)数据不具有独立性。 2.文件系统阶段 该阶段具有如下几个特点： (1)数据可以长期保存。 (2)由文件系统管理数据。 (3)数据共享性差，冗余度大。 (4)数据独立性差。 3.多数据库系统阶段 与前边两个相比，数据库系统阶段具有如下几个方面的特点： (1)数据结构化。 (2)数据的共享性高，冗余度低，易扩充。 (3)数据独立性高。 (4)数据由DBMS统一管理和控制。 考点3数据库技术的研究领域 数据库技术的研究领域是十分广泛的，概括地讲可包括以下3个领域： (1)数据库管理系统软件的研制。 (2)数据库设计。数据库设计的主要任务是在DBMS的支持下，按照应用的要求，为某一部门或组织设计一个结构合理、使用方便、效率较高的数据库及其应用系统。 (3)数据库理。论数据库理论的研究主要集中于关系规范化理论和关系数据理论等。 4.2数据模型 考点4数据模型的概念 模型是指现实世界的模拟和抽象数据模型是数据库系统的数学形式框架，是数据库系统的核心和基础。根据模型应用的不同，可以将模型分为两类：第一类模型是概念模型，也称信息模型。另一类模型是结构模型，主要包括网状模型、层次模型和关系模型等。 考点5数据模型的要素 数据模型通常由数据结构、数据操作和完整性约束3部分组成。 1.数据结构 数据结构是所研究的对象类型的集合，用于描述系统的静态特征。数据的静态特征是指对数据结构和数据间联系的描述。数据结构是刻画一个数据模型性质最重要的方面。 2.数据操作 数据操作是指对数据库中各种对象的实例允许执行的操作的集合，包括操作及相关的操作规则。 3.数据完整性约束 数据完整性约束是一组完整性规则的集合完整性规则是给定的数据模型中数据及其联系所具有的制约和储存规则，用以限定符合数据模型的数据库状态及状态的变化，以保证数据的正确、有效和相容。 考点6概念模型E-R模型 为了将现实世界中的具体事物抽象组织为某一DBMS支持的数据模型，一般先将现实世界抽象为信息世界，然后将信息世界转换成机器世界。概念模型实际上是现实世界到机器世界的一个中间层次。 1.信息世界中的羞本概念 (1)实体(Entity)：客观存在并可相互区别的事物称为实体，它可以是具体的人、事、物，也可以是抽象的概念或联系。 (2)属性(Attribute)：实体所具有的某一特性称为属性。 (3)主码(Primary Key)：唯一标识实体的属性集称为主码。 (4)域(Domain)：属性的取值范围称为该属性的域。 (5)实体型(Entity Type)：具有相同属性的实体必然具有共同的特征和性质。用实体名及其属性名集合来抽象和刻画同类实体，称为实体型。 (6)实体集(Entity Set)：同型实体的集合称为实体集。 (7)联系(Relationship)：在现实世界中，事物内部及事物之间是有联系的，这些联系在信息世界中反映为实体(型)内部的联系和实体(型)之间的联系。实体内部的联系通常是指组成实体的各属性之间的联系。两个实体之间的联系可以分为3类：一对一联系(1：1)、一对多联系(1：n)，以及多对多联系(m: n)。 2.概念模型的表示方法 概念模型的表示方法很多，其中最为著名的是1976年P. P. S. Chen提出的实体一联系方法(Entity - Re-tionship Approach) o该方法用E-R图来描述现实世界的概念模型，称为实体一联系模型，简称E-R模型。 E-R图提供了表示实体型、属性和联系的方法。 (1)实体型：用矩形表示，矩形框内写明实体名。 (2)属性：用椭圆形表示，并用无向边将其与相应的实体连接起来。 (3)联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体连接起来，同时在无向边旁标上联系的类型。 考点7常用的数据结构模型 目前，数据库领域中最常用的数据模型有4种，它们是：层次模型、网状模型、关系模型及面向对象模型。其中层次模型和网状模型统称为非关系模型。 1.层次模型(Hierarchical Model) 层次模型是数据库系统中最早出现的数据模型，用树型结构来表示各类实体及实体间的联系。层次模型的查询效率很高，曾得到广泛应用，但它只能表不I：N联系，对数据进行查询和更新操作时则很复杂，所以编写应用程序也很复杂。 2.网状模型(Network Model) 用有向图结构表示实体类型及实体间联系的数据模型称为网状模型。网状数据模型的特点是记录之间的联系通过指针来实现，M: N联系容易实现，查询效率较高，但是编写应用程序较复杂，程序员必须熟悉数据库的逻辑结构，而月其DDI,和DMI,语言复杂，用户不容易使用。 3.关系模型(Relational Model ) 关系模型是目前最重要的一种数据模型。关系数据库系统采用关系模型作为数据库的组织方式。它是由美国IBM公司San Jose研究室的研究员E. F. Codd首次提出的用表格形式结构表示实体类型及实体间联系的模型称为关系模型关系模型中数据的逻辑结构是一张二维表，它由行和列组成。关系模型的数据结构简单，容易被初学者接受它是一个成熟的、有前途的模型，已得到广泛应用。 4.面向对象模型(Object一Oriented Model) 现实世界中存在着许多含有更复杂数据结构的实际应用领域，如CAD数据、图形数据等，加上人工智能研究的需要，就导致了面向对象的数据模型。在面向对象的数据模型中，最基本的概念为对象和类。面向对象的数据模型可完整地描述现实世界的数据结构，比层次、网状、关系数据模型具有更加丰富的表达能力，能表达嵌套、递归的数据结构。 4.3.数据库系统的模式结构 考点8数据库系统模式的概念 在数据模型中有“型”和“值”的概念型是指对某一类数据的结构和属性的说明，值是型的一个具体赋值。 模式是数据库中全体数据的逻辑结构和特征的描述，它仅仅涉及到型的描述，不涉及到具体的值。模式的一个具体值称为模式的一个实例一模式是相对稳定的，反映的是数据的结构和联系，而实例是相对变动的，反映的是数据库某一时刻的状态。 考点9数据库系统的三级模式结构 数据库系统的三级模式结构是指数据库系统是由外模式、模式和内模式三级构成的。 1.模式(Schema) 模式也称概念模式或逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。模式实际是数据库数据在逻辑级上的视图。定义模式时不仅要定义数据的逻辑结构，而且要定义数据之间的联系，定义与数据有关的安全性、完整性要求。一个数据库只有一个模式。 2.外模式(External Schema) 外模式也称子模式或用户模式，它是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。外模式通常是模式的子集。一个数据库可以有多个外模式。外模式是保证数据库安全性的一个有力措施。 3.内模式(Internal Schema) 内模式也称存储模式或物理模式，一个数据库只有一个内模式。它是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式。 考点10数据库的二层映像与数据独立性 数据库管理系统为了能够在内部实现数据库三个抽象层次的联系和转换，数据库管理系统在这三级模式之间提供了两层映像：外模式模式映像和模式内模式映像。 这两层映像保证r数据库系统中的数据能够具有较高的逻辑独立性和物理独立性 1.外模式模式映像 外模式描述的是数据的局部逻辑结构，模式描述的是数据库数据的全局逻辑结构。对应于同一个模式可以有任意多个外模式对于每一个外模式，数据库系统都有一个外模式模式映像，它定义了该外模式与模式之间的对应关系。外模式模式映像保证了数据与程序的逻辑独立性。 2.模式内模式映像 数据库中只有一个模式，也只有一个内模式，所以模式内模式映像是唯一的，它定义了数据库全局逻辑结构与存储结构之间的对应关系模式内模式映像保证了数据与程序的物理独立性。 4.4关系数据库系统概述 考点11关系数据库系统 关系数据库系统是支持关系数据模型的数据库系统。关系数据库应用数学方法来处理数据库中的数据最早提出将这类方法用于数据处理的是1962年CODASYL发表的“信息代数”一文，但系统而严格地提出关系模型的是美国IBM公司的E. F. Codd。 考点12关系数据模型 关系模型由关系数据结构、关系操作集合和关系完整性约束3部分组成。 1.关系数据结构 关系模型中的数据结构非常单一。实体及实体间的联系都用关系表示，一个关系就是一张二维表，是关系模型中数据的逻辑结构。 2.关系操作集合 关系模型中的关系操作的理论依据为关系代数和关系演算。 关系模型中常用的关系操作包括：选择(select)、投影(project)、连接(join)、除(divide)、并(union)交(intersection)和差(difference)等，以及查询(query)操作和增(insert)、删(delete)、改(update)操作两大部分。查询的表达能力是其中最主要的部分。 关系数据语言可以分为如下3类：关系代数语言、关系演算语言(包括元组关系演算语言和域关系演算语言)及具有关系代数和关系演算双重特点的语言。 3.关系的完整性约束 数据库的数据完整性是指数据库中数据的正确性和相容性，那是一种语义概念，包括两个方面：与现实世界中应用需求的数据的相容性和正确性数据库内数据之间的相容性和正确性。 关系模型中有3类完整性约束：实体完整性、参照完整性和用户自定义的完整性。 4.5关系模型的数据结构 考点13关系模型的数据结构和基本术语 (1)关系( Relation) ;关系是个元素个数为K(K,1 )的元组集合。一个关系对应一个二维表，二维表名就是关系名。 (2)属性(Attribute)和值域(Domain)：二维表中的列(字段)，称为属性，属性的个数称为关系的元数，列的值称为属性值属性值的取值范围称为值域 (3)关系模式(Relation Schema)：关系的描述称为关系模式。 (4)元组(Tuple)：二维表中的行(记录的值)称为一个元组。关系模式和元组的集合通称为关系。 (5)候选码(Candidate Key)或候选键：如果在一个关系中，存在多个属性(或属性集合)都能用来唯一标识该关系的元组，这些属性(或属性集合)都称为该关系的候选码或候选键。而包含在任何一个候选码中的属性称为主属性或码属性，相反，不包含的为非主属性或非码属性。关系模式的所有数据组是这个关系模式的候选码，称为全码。 (6)主码(Primary Key)或主键：在一个关系的若十个候选码中指定一个用来唯一标识该关系的元组，这个唯一的码称为该关系的主码或主键。 (7)外码(Foreign Key)或外键：当关系中的某个属性(或属性组)不是该关系的主码或只是主码的一部分，但却是另一个关系的主码时，称该属性(或属性组)为这个关系的外码。 (8)参照关系(Referencing Relation)与被参照关系( Referenced Relation)：它们是指与外码相关联的两个关系。以外码作为主码的关系称为参照关系；外码所在的关系称为被参照关系或目标关系。 (9)分量(Component)：元组中的一个属性值。 (10)主属性(Primary Attribute)和非主属性(Nonprimary Attribute)：关系中包含在任何一个候选码中的属性称为主属性或码属性，不包含在任何一个候选码中的属性称为非主属性或非码属性。 考点14关系的形式定义和关系数据库对关系的限定 1.关系的形式定义 关系从数学的观点来定义有以下两种解释。 (1)集合论观点：即前面所述，关系是一个元素个数为K(K,1)的元组集合。 (2)值域的观点：关系是属性值域笛卡儿积的一个子集。 2.关系数据犀对关系的限定 当关系作为关系数据模型的数据结构时，关系数据库对关系有如下的限制。 (1)列是同质的即每一列中的分量是同一类型的数据，来自同一个域。 (2)不同的列可以出自同一个域，称其中的每一列为一个属性，不同的属性要给予不同的属性名。 (3)列的顺序无关紧要，即列的次序可以任意交换。 (4)任意两个元组不能完全相同。 (5)行的顺序无关紧要，即行的次序可以任意交换。 (6)每一个属性是不可分解的这是关系数据库对关系的最基本的一条限定。分量必须取原子值，即每一个分量都必须是不可拆分的数据项。 4.6关系模型的完整性约束 考点15数据完整性规则的分类 关系模型的完整性规则是对关系的某种约束条件。关系模型中可以有3类完整性约束：实体完整性、参照完整性和用户自定义的完整性。其中实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称为两个不变性、应该由关系系统自动支持。 1.实体完整性规则 实体完整性规则：若属性“是基本关系“的主属性，则属性A不能取空。实体完整性关系的所有主属性都不能取空值，而不仅是主码整体不能取空值。说明实体完整性规则应包括如下几个方面： (1)实体完整性规则是针对基本关系而言的。一个关系(基本表)通常对应现实世界的一个实体集。 (2)现实世界中的实体是可区分的，即它们具有某种唯一性标识。 (3)相应地，关系模型中以主码作为唯一标识。 (4)主码中的属性即主属性不能取空值。所谓空值就是“不知道”或“不确定”的值。 2参照完整性规则 若属性(或属性组)F是基本关系R的外码，它与基本关系S的主码K.s相对应(基本关系R和S不一定是不同的关系)，则对于R中每个元组在F上的值必须为：取空值(F的每个属性值均为空值)或者等于S中某个元组的主码值。 3用户有定义的完整性 用户定义的完整性通常是定义对关系中除外码与主码属性之外的其他属性取值的约束，即对其他属性值域的约束，也称为域完整性规则，包括数据类型、精度、取值范围、是否允许空值等。 4.7关系代数 考点16传统集合运算 传统的集合运算包括并、交、差和广义笛卡儿积4种运算。 1.并(union) 设关系R和关系S具有相同的目n(即都有n个属性)，且相应的属性取自同一个域，则关系R与S的并是由属于R或属于S的元组组成的，结果仍为n目关系，记做： RUSttRtS，t是元组变量。 2.差(difference) 设关系R和关系S具有相同的目n，且相应的属性取自同一个域，则关系R与关系S的差是由属于R而不属于S的所有元组组成的，结果仍为n目关系，记做： RS=,t是元组变量。 3.交(intersection) 设关系R和关系S具有相同的目n，且相应的属性取自同一个域，则关系R与关系S的交是由既属于R而不属于S的所有元组组成的，结果仍为n目关系，记做： RS=t|tRtSt ER八：ES,t是元组变量。 显然R自sR一(R一s)。 4.广义笛卡儿积(Extended Cartesian Product) 设关系R和s的元数分别是厂和，定义R和s的笛卡儿积是一个(r+s)元元组的集合，每一个元组的前r个分量来自R的一个元组，后s个分量来自S的一个元组。若R有m个元组，S有n个元组，则关系R 和S的广义笛卡儿积有m ×n个元组，记做： R×St|t=t?r ,tst?r tsS 考点17专门的关系运算 专门的关系运算包括：对单个关系进行垂直分解(投影操作)或水平分解(选择操作)和对多个关系进行结合(连接操作)等。 1.选择(selection) 选择又称为限制，是在关系R中选择满足给定条件的各元组，记做： (R)=，其中F表示选择条件，是一个逻辑表达式。 选择运算实际上是从关系R中选取使逻辑表达式F为真的元组。这是从行的角度进行的运算。 2.投影(projection) 关系R上的投影是从R中选择出若干属性列组成新的关系，记做： 二1(R、tAI t ER,A为R的属性列。 投影操作实际上是从关系中选取某些列，即从列的角度进行的运算。 3.连接(join ) 连接是从两个关联的笛卡儿积中选取属性间满足一定条件的元组。 连接运算中有两种最为重要也是常用的连接，一种是等值连接( equi - join)，一种是自然连接(naturaljoin)自然连接是构造新关系的有效方法。一般，自然连接使用在两个关系有公共属性的情况中。 4.除(di%-ision) 给定关系R(X，州和别Y, Z)，其中X，Y, Z为属性组。R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集R与S的除运算得到一个新的关系尸(X)，P是R中满足下列条件的元组在X属性列上的投影：元组在X分量值的对象Yx包含S在Y上投影的集合。记做： R÷St,Xt,ER八二，(S) C-玖 除操作是同时从行和列的角度进行运算。 4.8 SQL概述： 考点18结构化查询语言SQL SQL (Structured Query Language)称为结构化查询语言，是于1974年由Boyce和Chamberlin提出的，1975年IBM公司研制的关系数据库管理系统的原型系统System R实现了SQL语言。SQL是一个通用的、功能极强的关系数据库语言。我国制定了SQL的国家标准为GB12911, SQL已经成为关系数据库领域中的一种主流语言。 考点19 SQL的特点一 SQL语言集数据查询、数据操纵、数据定义和数据控制功能于一体，主要特点包括以下几个方面： (1)综合统一。 (2)高度非过程化。 (3)面向集合的操作方式。 (4)以同一种语法结构提供两种使用方式。 (5)语言简洁，易学易用。 考点20 SQL数据库体系结构 SQL语言支持关系数据库三级模式结构：其中外模式对应于视图和部分基本表，模式对应于基本表，内模式对应于存储文件： 基本表是本身独立存在的表，在SQL中一个关系就是一个基本表。一个基本表对应一个存储文件，一个表可以带若干索引，索引也存放在存储文件中存储文件的逻辑结构组成了关系数据库的内模式。存储文件的物理结构是任意的，对用户是透明的。 视图是从一个或几个基本表导出的表二视图是一个虚表视图在概念上与基本表等同，用户可以在视上再定义视图。 4.9 SQL的数据定义 考点21基本表 1.定义基本表 SQL语言使用CREATE TABLE语句定义基本表，其格式如下： CREATE TABLE表名(列名数据类型列级完整性约束 ，列名数据类型列级完整性约束 ，表级完整性约束)； 如果完整性约束条件涉及到该表的多个属性列，则必须定义在表级上，否则既可以定义在列级，也可以定义在表级。 2.修改基本表 SQL语言用ALTER TABLE语句修改基本表，其格式为： ALTER TABLE表名 ADD新列名数据类型完整性约束 DROP完整性约束名 MODIFY列名数据类型； ADD子句用于增加新列和新的完整性约束条件。DROP子句用于删除指定的完整性约束条件。MOD-IFY子句用于修改原有的列定义，包括修改列名和数据类型。 3.删除基本表 当某个基本表不再需要时，可以用DROP TABLE语句进行删除，其格式为： DROP TABLE表名 基本表一旦被删除，表中的数据、此表上建立的索引和视图都将自动被删除。因此执行删除基本表的操作时一定要格外小心。 考点22索引 建立索引是加快查询速度的有效手段。可以根据需要在基本表上建立一个或多个索引，从而提高系统的查询效率。 1.建立索引 在SQL语言中，建立索引使用CREATE INDEX语句，其格式为： CREATEUNIQUE乙CLUSTERINDEX索引名 ON表名(列名次序，列名次序)； 索引可以建立在该表的一列或多列上，各列名之间用逗号分隔。每个列名后面还可以用次序指定索引值的排列次序，可选ASC(升序)或DESC(降序)，默认值为ASC。 UNIQuE表明此索引的每一个索引值只对应唯一的数据记录。 CLUSTER表示要建立的索引是聚簇索引。所谓聚簇索引是指索引项的顺序与表中记录的物理顺序一致的索引组织。 2.删除索引 删除索引使用DROP INDEx语句删除索引时，系统会同时从数据字典中删去有关该索引的描述，其一般格式为： DROP INDEX索弓l名； 4.10 SQL的数据操纵 SQL语言的数据操纵包括INSERT(插人)、DELETE(删除)、UPDATE(更新)和SELETE(检索，又称查询)4个语句. 考点23 SQL的查询语句 数据库查询是数据库的核心操作SQL语言提供了SELECT语句进行数据库的查询，该语句具有灵活的使用方式和丰富的功能二其一般格式为： SELECTALLI DISTINCT目标列表达式，目标列表达式 FROM基本表或视图，基本表或视图 WHERE条件表达式 GROUP BY列名lHAVING条件表达式 ORDER BY列名2ASC 1 DESC； 1.简单查询 简单查询涉及数据库中的一个表，包括以下几种： (1)查询表中的若干列。 (2)查询经过计算的值。 (3)消除取值重复的行。 (4)查询满足条件的元组。 (5)利用LIKE的查询。 (6)涉及空值NULL的查询。 (7)对查询结果排序。 (8)使用集函数。 (9)对查询结果分组。 2.连接查询 若一个查询同时涉及两个以上的表，则称之为连接查询。连接查询是关系数据库中最主要的查询，也是查询中最难的一部分，包括等值连接、自然连接、非等值连接查询、自身连接查询、外连接查询和复合条件连接查询。 3.嵌套查询 在SQL语言中，一个SELECT一FROM一WHERE语句称为一个查询块。将一个查询块嵌套在另一个查询块的WHERE子句或HAVING短语的条件中的查询称为嵌套查询或子查询。嵌套查询是由里向外处理的，这样外层查询可以利用内层查询的结果。 (I)由谓词IN引导的子查询：IN是最常用的谓词。 (2)谓词是比较运算符的子查询。 (3)由NOTEXISITS谓词引导的子查询。 (4)集合查询。 考点24 SQL的修改语句 SQL的修改语句包括更新、删除和插人3类语句 1.更新(UPDATE) 更新操作语句的格式如下： UPDATE表名 SET列名二表达式，列名二表达式 WHERE条件； 更新的功能是修改指定表中满足WHERE子句条件的元组。其中SET子句用于指定修改方法，即用表达式的值取代相应的属性列值。如果省略WHERE子句，则表示要修改表中的所有元组。 2.删除(DELETE) 删除语句一般有两种，格式如下： DELETE FROM表名 WHERE条件； DELETE语句的功能是从指定表中删除满足WHERE子句条件的所有元组。如果省略WHERE子句，表示删除表中全部元组，但表的定义仍在字典中。 3.插入(INSERT) 插人语句的一般格式有两种。 (1)插人一个元组格式如下： INSERT INTO表名(字段名)，字段名) VALUES(常量，常量)； (2)插人子查询结果格式如下： INSERT INTO表名(字段名)，字段名) 子查询； 第一种格式是把一个新记录插人指定的表中；第二种格式是把子查询的结果插人指定的表中。 4.11视图 视图是关系数据库系统提供给用户以多种角度观察数据库中数据的重要机制。视图是一个定制的虚拟表可以是本地的、远程的或带参数的；其数据可以来源于一个或多个表，或者其他视图；它是可更新的，可以引用远程表，它可以更新数据源。 考点25定义视图 1.创建视图 SQL语言用CREATE VIEW命令建立视图，其一般格式为： CREATE VIEW视图名(列名，列名 AS子查询 LWITH CHECK OPTION： 其中子查询可以是任意复杂的SELECT语句，但通常不允许含有ORDER BY子句和DISTINCT短语。WITH CHECK OPTION表示对视图进行UPDATE、INSERT和DELETE操作时要保证更新、插人或删除的行满足视图定义中的谓司条件(即子查询中的条件表达式)。 2.刚除视图 视图创建好以后，如果导出的此视图的基本表被删除了，则该视图也将失效，但一般不会被自动删除。删除视图通常需要显式地使用DROP VIEW语句进行。该语句格式为： DROP VIEW视图名： 考点26查询视图 DBMS执行对视图的查询时，首先进行有效性检查。检查查询涉及的表、视图等是否在数据库中存在，如果存在，则从数据字典中取出查询涉及的视图的定义，把定义中的子查询和用户对视图的查询结合起来，转换成对基本表的查询，然后冉执行这个经过修正的查询。将对视图的查询转换为对基本表的查询的过程称为视图的消解(View Resolution)。 考点27修改视图 修改视图包括插入(INSERT)、删除(DELETE)和更新(UPDATE) 3类操作。 为防止用户通过视图对数据进行增、删、改操作时，无意或有意操作不属于视图范围内的基本表数据可在定义视图时加仁WITH CHECK OPTION子句，这样在视图上增、删、改数据时，DBMS会进一步检查视图定义中的条件，若不满足条件，则拒绝执行该操作。 应该指出的是，不可更新的视图与不允许更新的视图是两个不同的概念。 考点28视图的作用 合理使用视图能够给用户带来许多好处，其优点包括以下儿个方面： (1)能够简化用户的操作。 (2)使用户能以多种角度看待同一数据。 (3)对重构数据库提供了一定程度的逻辑独立性。 (4)能够对机密数据提供安全保护。 4.12数据控制语句禾口嵌入式SQL 考点29授予权限 SQL,语言用GRANT语句向用户授予操作权限，GRANT语句的一般格式为： GRANT权限仁，权限 ON对象类型对象名 TO用户仁，用户 WITH GRANT OPTION； 其语义为：将对指定操作对象的指定操作权限授予指定的用户。接受权限的用户可以是一个或多个具体用户，也可以是PUBLIC，即全体用户。 如果指定了WITH GRANT OPTION子句，则获得某种权限的用户还可以把这种权限再授予别的用户。如果没有指定WITH GRANT OPTION子句，则获得某种权限的用户只能使用该权限，但不能传播该权限。 考点30收回权限 授予的权限可以由DBA或其他授权者用REVOKE语句收回，REVOKE语句的一般格式如下： REVOKE权限，权限 ON对象类型对象名 FROM用户，用户； 考点31嵌入式SQL SQL语言提供了两种不同的使用方式一种是在终端交互方式下将SQL语言嵌入到某种高级语言中使用。利用高级语言的过程性结构来弥补SQL语言在实现复杂应用方面的不足，这种方式下使用的SQL语言称为嵌入式SQL(Embedded SQL)，而嵌人SQL的高级语言称为主语言或宿主语言。 对宿主型数据库语言SQL, DBMS可采用两种方法处理，一种是预编译，另一种是修改和扩充主语言，使之能处理SQL语句。目前采用较多的是预编译的方法。 4.13函数依赖 考点32“不好”的关系模式 “不好”的关系模式有以下4个“毛病”： (1)插人异常如果某供应者没有供应任何货物，则我们无法记录他的名称和地址。 (2)删除异常。如果一个供应者供应的所有货物都被删除，则我们会丢失该供应者的名称和地址。 (3)冗余太大。一个供应者每供应一种货物，他的地址就要重复一次。 (4)更新异常(不一致性的危险)。由于数据冗余，有可能使我们在一个元组中更改了某供应者的地址，而没有更改另一个元组片同一供应者的地址，于是同一供应者有了两个不同地址，与实际情况不符。 考点33函数依赖 1.函数依赖的定义 设R(必是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称_X函数确定Y或Y函数依赖于X，记作X- Y, 函数依赖包括非平凡的函数依赖、平凡的函数依赖、完全函数依赖、部分函数依赖及传递函数依赖。 2.函数依赖的逻辑蕴含 设RU, F是一个关系模式，X，Y是U中的属性组，若在RU, F中的任何一个满足F函数依赖的关系：r上，都有函数依赖XY成立，则称F逻辑蕴含XY。 在关系模式RU, F中，F所逻辑蕴含的函数依赖的全体称做F闭包，记做F。 3.码 设K为R ji.，科中的属性或属性组合，若K- U在F十中，而找不到K的任何一个真子集K，能使KU在F中，则K为R的候选码。当候选码多于一个时，则选定其中的一个为主码。包含在任何一个候选码中的属性，叫做主属性，不包含在任何码中的属性称为非主属性或非码属性。最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码。 4.函数依赖的办理系统 1974年Armstrong首先提出了Armstrong公理系统，包括3条推理规则： 设F是属性组U上的一组函数依赖，于是有如下推理规则。 (1)自反律(Reflexivity )，若YCXC U,lnl X-" Y为F所逻辑蕴含。 (2)增广律(Augmentation)，若X-Y为F所逻辑蕴含，且ZCU，则XZ-YZ为F所逻辑蕴含。 (3)传递律(Tran sitiv讲)，若X- Y及Y-"Z为F所逻辑蕴含，则X-Z为F所逻辑蕴含。 考点34 1NF,2XF、3NF、BCNF 1.第一范式(1NF)及进一步规范化 关系模式需要满足一定的条件，不同程度的条件称做不同的范式，最低要求的条件是元组的每个分量必须是不可分的数据项，这叫第一范式，简称1NF，是最基本的范式。对于各种范式之间的联系有5NF C4NF仁BCNFC3NF仁2NFCINF成立。 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这个过程就叫规范化。 2.第二范式(2NF) 若R EINF，且每一个非主属性完全函数依赖于码，则R2NFo 2NF就是不允许关系模式的属性之间有这样的函数依赖X-. Y。其中X是码的真子集，Y是非主属性,也就是说，不允许有非主属性对码的部分函数依赖。 3.第三范式(3NF) 关系模式R，U，F中若不存在这样的码X，属性组Y及非主属性Z(Z不包含于均使得XY，(Y函数依赖于X)YZ成立，则称RU, F3NF 4.Boyce一Codd范式(BCNF) 若关系模式REINF，且对于每个非平凡的函数依赖X- Y都有X包含码，则R EBCNF。在函数依赖的范围内，BCNF达到了最高的规范化程度。 考点35多值依赖和4NF 1.多值依赖 设R(U)是属性集U上的一个关系模式X、Y,Z是U的子集，并且ZU一X一Y关系模式R (U)中多值依赖XY成立，当且仅当对R(U)功的任一关系r，给定的一对(x,z)值有一组Y的值，这组值仅仅决定于x值而与z值无关。 4.第四范式(4NF ) 关系模式RU，F司NF，如果对于R的每个非平凡多值依赖XY(Y不包含于X)，X都含有码，则称RU，F4NF。 如果一个关系模式是4NF，则必为BCNF。 4.14关系模式的分解 考点36模式分解的等价标准 常用的等价标准要求分解是具有无损连接性的，并且是保持函数依赖的。 考点37关于模式分解的几个事实 (1)分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。 (2)若要求分解具有无损连接性，那么模式分解一定可以达到BCNF)。 (3)若要求分解保持函数依赖，刀厂么模式分解可以达到3NF，但不一定能达到BCNF。 (4)若要求分解既具有无损连接性，又保持PA数依赖，则模式分解可以达到3NF，但不一定能达到BCNF。 4.15数据库设计的内容、方法和步骤 考点38关于数据库设计的概述 数据库设计是指对于一个给定的应用环境，包括硬件环境、操作系统和数据库管理系统(DBMS)等软件环境，如何使用这个环境来表达用户的要求，构造最优的数据库模式，建立数据库及围绕数据库展开的应用系统，使之能够有效地收集、存储、操作和管理数据，满足企业组织中各类用户的应用需求。 数据库设计方法中比较著名的有新奥尔良(New Orleans)方法。它将数据库设计过程分为4个阶段：需求分析、概念结构设计一、逻辑结构设计和物理设计。 4.16需求分析 考点39需求分析的任务 需求分析的任务是通过详细调查现实世界要处理的对象(组织、部门、企业等)，充分了解原系统(手工系统或计算机系统)的下作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。新系统必须充分考虑今后可能的扩充和改变，不能仅仅按当前应用需求来设计数据库。 需求分析的重点是调查、收集与分析用户在数据管理中的信息要求、处理要求、安全性与完整性要求。需求分析的阶段成果是产生系统需求说明书。 考点40需求分析的基本步骤 需求分析的步骤有以下几个方面： (1)需求的收集：数据，发生时间、频率，发生的规则、约束条件、相关联系、计划控制及决策过程。 (2)需求的分析整理二包括数据流程分析、数据分析结果描述、数据分析统计及分析围绕数据的各种业务处理功能，并以带说明的系统功能结构图形式给出。 4.17概念结构设计 考点41概念结构设计的目标和策略 概念结构是对现实世界的一种抽象，即对实际的人、物、事和概念进行人为处理，抽取人们关心的共同特性，忽略非本质的细节，并把这些特性用各种概念精确地加以描述。 设计概念结构通常有4类方法：自顶向下、自底向上、由里向外和混合策略。无论采用哪种设计方法，一般都以E-R模型为工具来描述概念结构。最常用的设计策略是自底向上设计策略。 考点42采用E-R方法的数据概念模型设计 1数据抽象与局部视图设计 以自底向上设计概念结构的方法为例，它通常分为两步： (1)根据需求分析的结果(数据流图、数据字典等)对现实世界的数据进行抽象，设计各个局部视图即E-R图。 (2)集成局部视图。 设计E-R图的步骤如下： (1)选择局部应用 (2)逐一没计E-R图二 2视图的集成 集成局部E-R图时需要两步。 (1)合并E-R图，生成初步E7R图。 各E-R图之间的冲突主要有3类：属性冲突、命名冲突和结构冲突： (2)修改与重构，生成基本E-R图。 修改、重构初步E-R图以消除冗余，主要采用分析方法。除分析方法外，还可以用规范化理论来消除冗余。 4.18逻辑结构设计 考点43 E-R模型向关系数据模型的转换 将E-R图转换为关系模型实际上就是要将实体、实体的属性和实体之间的联系转化为关系模式，这种转换的规则包括以下几点： (1)一个实体型转换为一个关系模式。 (2)一个m: n联系转换为一个关系模式。 (3)一个1：n联系可以转换为一个独立的关系模式，也可以与n端对应的关系模式合并。 (4)一个1：1联系可以转换为一个独立的关系模式，也可以与任意一端对应的关系模式合并。 (5)3个或3个以上实体间的一个多元联系转换为一个关系模式。 (6)同一实体集的实体间的联系，即自联系，也可按上述1: 1,1: n和m: n三种情况分别处理。 (7)具有相同码的关系模式可以合并。 考点44关系数据库的逻辑结构设计过程 关系数据库的逻辑结构设计过程如下： (1)从E-R图导出初始关系模式。 (2)规范化处理。 (3)模式评价。 (4)优化模式。 (5)形成逻辑结构设计说明书。 4.19物理结构设计 考点45物理设计的内容 (1)存储记录的格式设计。对数据项类型特征进行分析，并对存储记录进行格式化 决定如何进行数据压缩或代码优化。 (2)存储方法的设计。物理设计中最重要的一个考虑是把存储记录在全范围内进行物理安排，包括顺序存放、散列存放和聚列存放。物理设计的结果是物理设计说明书。 (3)存取方法设计。存取方法设计为存储在物理上的数据提供数据访问的路径。 DBMS产品一般都提供了一些存储分配参数，供数据人员和DBA对数据库进行物理优化。 考点46物理设计的评价 数据库物理设计过程中需要对时间效率、空间效率、维护代价和各种用户要求进行权衡，其结果可以产生多种方案，数据库设计人员必须对这些方案进行细致的评价，从中选择一个较优的方案作为数据库的物理结构。 在数据库应用系统生存期中，总的开销包括：规划开销、设计开销、实施和测试开销、操作开销、运行维护开销。评价物理数据库的方法完全依赖于所选用的DBMS。 4.20实现和维护 考点47数据库的实现 数据库实现的主要工作有以下几个方面： (1)定义数据库结构。 (2)编制与调试应用程序。 (3)数据装载。 (4)数据库试运行。 考点48其他设计 其他设计工作包括加强数据库的安全性、完整性控制，以及保证一致性、可恢复性等，总是以牺牲效率为代价的。设计人员的任务就是要在实现代价和尽可能多的功能之间进行合理平衡。其他设计包括数据库的再组织设计、故障恢复方案设计、安全性考虑和事务控制等。 考点49数据库的运行和维护 在数据库运行阶段，对数据库经常性的维护工作主要是由DBA完成的，它包括以下几个方面： (1)数据库的转储和恢复。 (2)数据库的安全性、完整性控制。 (3)数据库性能的监督、分析和改进。 (4)数据库的重组织和重构造。 4.21数据库管理系统概述 考点50 DBMS的系统目标 数据库管理系统(DBMS)是操作和管理数据库的软件系统，它由一组计算机程序构成，管理并控制数据资源的使用。数据库管理系统是数据库系统的核心DBMS的目标是用户界面友好、结构清晰和开放性。 考点51 DBMS的基本功能 DBMS主要是实现对共享数据有效的组织、管理和存取。因此，DBMS具有如下几个方面的基本功能。 (1)数据库定义功能。 (2)数据存取功能。 (3)数据组织、存储和管理。 (4)数据库运行管理。 (5)数据库的建立和维护。 (6)通信功能和数据转换功能等。 考点52 DBMS程序模块的组成 大致来说，DBMS的程序模块可按功能划分为以下5个模块： (1)数据定义方面的程序模块。 (2)数据操纵方面的程序模块 (3)数据库运行管理方面的程序模块 (4)数据库组织、存储和管理方面的程序模块。 (5)数据库建立、维护和其他方面的程序模块。 考点53 DBMS的层次结构 可以将DBMS划分成若干层次，这样可以帮助我们更清晰地认识DBMS，更重要的是有助于DBMS的设计和维护。 (1)最上层是应用层位于DBMS核心之外。 (2)第二层是语言翻译处理层它处理的对象是数据库语言A SQL, (3)第三层是数据存取层：该层处理的对象是单个元组。 (4)第四层是数据存储层。该层处理的对象是数据页和系统缓冲区。 (5)操作系统是DBMS的基础。它处理的对象是数据文件的物理块。 4.22新的应用需求对DBMS的挑战 考点54新的应用需求对DBMS的挑战 由于现在以关系型数据库管理系统(RDBMS )为主流。这些新应用需求要求数据库管理系统应该具有支持分布式操作、联机事务处理能力、决策支持能力、支持多媒体、大容量、复杂数据应用、兼容性和集成能力、异种数据库之间的互访能力、系统可靠性、安全性、大型系统等方面的管理能力。 在我国，当前流行的数据库管理系统绝大多数是关系型数据库管理系统，一般可分为如下3类： (1)以PC机、微型机系统为运行环境的数据库管理系统。 (2)以Oracle为代表的数据库管理系统，这类系统还有IBM DB2,Sybase等，也被称为主流数据库管理系统。 (3)以Microsoft SQI. Server为代表的介于以上两类之间的数据库管理系统。 4.23 Oracle数据库系统 考点55Oracle数据库系统简介 Oracle关系型数据库管理系统是美国Oracle公司的优秀软件产品，它采用SQL语言作为数据库语言。该公司于1979年推出了世界上第一个商业化的关系型数据库系统。 Oracle数据库的特点包括兼容性、可移植性、可连接性及高的生产率。 考点56 Oracle的主要产品及其功能 1Oracle数据库服务霖功能及其特色 Oracle数据库服务器包括标准服务器和许多可选的服务器选件，选件用于扩展标准服务器的功能，以适应特殊的应用需求。 (1)标准服务器主要具有下列特色：多进程多线索的体系结构、高性能核心技术、高可用性和SQL的实现。 (2)并行服务器选件(paralle server option)和并行查询选件(paralle query option)。 (3)分布式选件(distributed)。 (4)过程化选件(procedural option)。 2Oracle的工具产品及其功能 为方便用户开发数据库应用程序，Oracle提供了众多工具供用户选择使用，主要包括以下几个方面： (1)Developer/2000。它是Oracle的一个较新的应用开发工具集，包括Oracle Forms， Oracle Reports，Oracle Graphics和Oracle Books等多种工具，用来实现高生产率、大型事务处理及客户服务器结构的应用系统。 (2)Designer/2000 。它是Oracle提供的CASE工具，能够帮助用户对复杂系统进行建模、分析和设计，由BPR、Modellers、Generators等组成。 (3 ) Discoverer/2000。它是一个OLAP工具，主要用于支持数据仓库应用。 (4)Oracle Office。它是用于办公自动化的，能完成企业范围内的消息接收与发送。 (5)SQL DBA 。SQL DBN 是一个易于使用的。菜单驱动的DNA实用工具，可供用户进行动态性能监视、远程DB管理等。 4.24 IBM DB2数据库系统 考点58 IBM DB2数据库系统简介 IBM DB2数据库系统是美国IBM公司的产品1973年位于美国加州圣荷西市的IBM研究中心开始了一个大的关系型数据库系统研究项目jvstem R，探讨并验证在多用户与大量数据下关系型数据库的实际可行性。 考点59 DB2通用数据库的功能和特色 DB2家族除r包含在各种平台土运行的数据库管理系统内核之外，产品包中还包括了数据复制、数据库系统管理、Internet网关支持、在线分析处理、多媒体支持和各种并行处理能力，并为所有平台上的异构数据库访问提供中间件”解决方案。 DB2通用数据库(LDB)V7. 1的特色包括支持Internet应用、支持面向对象和多媒体应用、支持联机分析处理和了干行处理能力。 考点60 IBM的商务智能解决方案 商务智能解决方案的基本结构往往包含以下3个部分： (1)数据仓库，用于抽取、整和、分布、存储有用的信息。 (2)多维分析模型，全方位了解现状。 (3)前台分析工具，提供简单易用的图形化界面给管理人员。 考点61 IBM内容管理解决方案 (1) IBM Content Manager On Demand.它可以完成电子存储、回取、分发、打印和传真，在极短的时间内就可以在显示器上获得与原来提供给客户的一模一样的报表账单及其他计算机的输出信息。 (2)Digital Library IBM数字图书馆技术使人们快速而廉价地管理、访问、保护及传递大量多种多样的资料成为可能。这种数字化工作流程包含了一系列最新信息技术。 4.25 Sybase数据库系统 考点62 Svbase数据库简介 Sybase是美国Sybase公司的产品。1986年正式推出Sybase数据库系统。 Sybase在新兴的EP发展策略中充分利用了已有的核心产品和战略优势，提供了满足电子商务需求的解决方案。 考点63Sybase数据库系统的功能及其特色 目前,Sybase数据库系统定位在4个方向，分别在企业解决方案,Internet应用、商务智能和移动与嵌人计算领域为客户提供先进的技术： 企业解决方案包括企业级数据库、数据复制和数据访问。主要产品有：Sybase EP,Adaptive Server Enter-prise、Adaptive Server Replication、Adaptive Server Connect及异构数据库互联选件。 4.26 IBS-SQL Server数据库系统 考点64 MS-SQL Server数据库系统 MS-SQL Server数据库系统是美国Microsoft公司的产品。MS-SQL Server数据库系统是在Svbase SQL erver 4的版本基础上发展起来的。目前Microsoft SQL Server 7. 0和Microsoft SQL Server 2000广泛使用于我国的各行各业，包括许多政府部门。 考点65 Microsoft SQL Server系统主要功能及其特性 1数据库服备器MS-SQI, Server MS-SQL决rver数据库系统的核心是Microsoft SQL Server，简称MS-SQL Server或SQL Server，它有7.0、2000和2005三个主要版本。 2MS-SQL Server 2000的主要功能及其特色 MS-SQL Server 2000的主要功能有充分的Web支持、高度可伸缩性和可靠性、最快投放市场、充分的数据仓库功能和广泛的支持电子商务功能。 考点66 SQL Server 2000多版本支持 SQL Server 2000提供了各种不同的版本，包括SQL Server 2000企业版、SQL Server 2000标准版、SQLServer 2000个人版、SQL Server 2000开发人员版,SQL Server 2000企业评估版,SQL Server 2000桌面引擎和SQL Server 2000 Windows CE版。第5章事务管理和新一代数据库 5.1事务管理与数据库安全性 考点1事务概念和事务特性 1.事务的概念数据库的一些操作的集合通常是一个独立单元，这种具有独立性的逻辑单元即是事务 2.事务的特性 (1)原子性(Atomicity )。事务的所有操作在数据库中是不可分割的，或全部反映出来或全部不反映。 (2)一致性( Consistency)。事务执行的结果必须是使数据库从一个一致性状态转变到另一个一致性状态。即数据库中只包含成功事务提交的结果。 (3)隔离性(Isolation)。事务的执行不能被其他事务所干扰，一个事务内部的操作及使用的数据对其他并发事务是隔离的，互不影响。 (4)持久性(Durability)。事务一旦提交并执行后，它对数据库中数据的改变是永久的。 考点2事务的并发控制 1.事各的并发执行 一个事务在等待过程中需要不同的资源，但是不可能显示占有系统的全部资源，所以在串行时总会浪身系统资源，为了更好地利用系统资源，允许多个事务并发执行。并发执行时可能会破坏数据库的一致性，主要问题包括以下方面： (1)丢失更新。 (2)对未提交更新的依赖。 (3)不一致的分析。 2.全并发事务的调度如果多个事务在某个调度下的执行结果与这些事务在某个串行调度下的执行结果相同，则称这个调度为可串行化的调度。若用等价的概念来表示就是指某个调度等价于一个串行调度。 3.封锁 在事务的并发执行过程中为保证数据库的一致性，常采用封锁的方法来限制其他事务对该事务数据项的访问。对数据项加锁的方式主要有两种。 (1)共享锁。如果事务T获得了数据项Q上的共享型锁(记为S)，则Ti可读Q但不能写e。 (2)排他锁。如果事务Ti获得了数据项Q上的排他型锁(记为X)，则T既可读Q又可写Q。 两阶段封锁协议是可串行性的一个协议，它要求每个事务分两个阶段提出加锁和解锁申请。 (1)增长阶段。事务可以获得锁，但不能释放锁。 (2)缩减阶段。事务可以释放锁，但不能获得新锁。 考点3故障恢复 1.故障的类型 (1)事务故障可分为逻辑错误和系统错误，它们都可能造成事务执行失败。 (2)系统故障二硬件故障或者是数据库软件或操作系统的错误，致使系统停止运行。主存储器内容丢失，而外存储器完好无损。 (3)磁盘故障。数据传送操作过程中由于磁头损坏或故障而造成的数据内容丢失。 2.基于目志的恢复 日志是记录数据库中更新活动的结构，它记录了数据库中的所有更新活动。日志记录用于记录数据库的写操作和事务处理过程中的重要事件，包括事务开始日志记录、更新日志记录、事务提交日志记录和事务终止日志记录。 发生事务故障后，事务故障恢复的步骤如下： (1)反向扫描日志，查找该事务的更新记录C (2)对事务的更新操作执行逆操作，将日志记录中的“改前值”写人数据库。 (3)反复进行直到恢复到该事务的开始日志，则事务故障恢复结束。 对于系统的故障恢复步骤如下： (1)正向扫描日志文件，将在故障发生前提交的事务的标识记人REDO队列；将故障发生时尚未完成的事务的标识记人UNDO队列。 (2)对UNDO队列中的事务进行反向扫描，执行逆操作。 (3)对REDO队列中的事务进行正向扫描，重新执行日志记录登记操作。 考点4数据库安全性 1.安全措施的层次 恶意访问的形式包括未经授权读取数据、未经授权修改数据和未经授权删除数据。为了保证数据库的安全性，必须在以下几个层次上采取措施 (1)物理层。计算机系统所位于的节点(一个或多个)必须在物理上受到保护，以防止人侵者强行闯人或暗中潜入。 (2)人员层：对用户的授权必须格外小心，以减少授权用户接受贿赂或其他好处而给人侵者提供访问机会的可能性。 (3)操作系统层不管数据库系统多安全，操作系统安全性方面的弱点总是可能成为对数据库进行未授权访问的一种手段。 (4)网络层。由于几乎所有的数据库系统都允许通过终端或网络进行远程访问，网络软件的软件安全性和物理安全性一样重要，不管在Internet上还是在企业私有的网络内。 (5)数据库系统层。数据库系统层的某些用户获得的授权可能只允许他访问数据库中有限的部分。而另外一些用户获得的授权可能允许他提出查询，但不允许他修改数据。保证这样的权限不被违犯是数据库系统的责任。 2.权限和授权 访问数据库的权限介绍如下： (1)read权限。允许读取但不可修改数据： ( 2 ) insert权限二允许插人新数据但不可修改数据。 (3)update权限。允许修改数据但不可删除数据。 (4)delete权限。允许删除数据。 修改数据库模式的权限介绍如下： (1)index权限允许创建和删除索引。 (2)resource权限。允许创建关系。 (3) alteration权限。允许添加和删除关系中的属性。(4) dr叩权限。允许删除关系 在SQL语言中，通过grant和revoke语句分别进行权限的授予和回收。 3.在SQL中进行安全性说明 SQL数据定义语言中包含了权限授予和回收的命令,SQL -92标准定义了数据库模式的基本授权机制：只有模式属主才能对模式进行修改。 4.加密 对敏感的数据可以加密，加密数据只有解码后才能被读出。 5.2新一代数据库应用开发工具 考点5概述 1.新一代客户服务器数据库系统的前端开发工具的特征 (1)支持与多种数据库连接，对不同的数据库可进行透明访问。 (2)支持独立的DBMS开发，提供统一的访问DBMS的用户界面和应用程序接口。 (3)支持可视化图形用户界面。 (4)支持面向对象的程序设计。 (5)拥有完善的数据对象。 (6)支持开放性。 (7)功能完备和集成化。 (8)支持汉化。 2.开发工其的发展趋势 (1)采用3层客户服务器结构。 (2)支持Web应用。 (3)开放的、构件式的分布式计算环境。 考点6开发工具的选择 1.当前对开发工具的要求 (1)提高开发和运行效率。 (2)降低开发和维护费用。 (3)先进的应用系统。 (4)代码兼容性。 2.当前开发工具存在的问题 (1)开发过程过于复杂，涉及过多低层技术实现。 (2)难于满足要求稳定的大规模的企业级业务处理。 (3)难于快速适应低层技术的更新和业务逻辑变化。 3. CASE工其 具有代表性的CASE开发工具，主要包括以下几种： (1) Sy base公司的PowerDesignero (2)Oracle公司的Designer/20000 (3)Rational公司的Rose (4)CA公司的Erwin 4.前端应用开发工具 (1)Uniface公司的Uniface (2)Lotus公司的Lotus (3)Borland公司的Delphi (4) Sybase公司的PowerBuilder, (5)Oracle公司的Developer/2000和Discoverer/20000 考点7 CASE工具PowerDesigner PowerDesigner的6个模块介绍如下： (I)PowerDesigner ProcessAnalyst。 (2)PowerDesigner DataArchitect。 (3)PowerDesigner AppModeler。 (4)PowerDesigner MetaWorks。 (5)PowerDesigner WarehouseArchitect。 (6)PowerDesigner Viewer。 考点8可视化开发工具Delphi Delphi的主要特点介绍如下： (I)良好的面向对象设计能力。 (2)良好的数据处理能力。 (3)具有良好的对标准技术的支持。 (4)良好的Internet/ Intranet开发支持。 (5)良好的对第三方构件产品和工具支持。 考点9应用系统开发工具PowerBuilder PowerBuilder是由美国著名的数据库应用开发工具厂商Power Soft公司(现已并人Syabse公司)于1991年6月推出的完全按照客户服务器体系结构设计的快速应用开发系统，是一个客户机前端开发工具。它提供了组件生成器，可以生成C,Java Proxy, COM等组件，提供多种方式支持Web应用。 Pow erBuilder的主要特点介绍如下： (1)专业的客户机服务器应用开发工具。 (2)全面支持面向对象开发。 (3)使用专门接口或ODBC,可同时支持与多种数据库的连接。非常适合于多层客户服务器结构的集成化应用系统开发。 (4)提供丰富的数据表现风络，可定制的称为“数据窗口(Data Window)”对象(该项技术已获专利)，可容易地对数据库进行操作并能灵活地制作报告和商业图形。 (5)支持动态数据交换(DDE)、动态链接库(DLL)、对象链接与嵌人(OLE)。 (6)提供灵活、快捷的数据和结构移动(复制)方式。 (7)提供强大的调试器和多种调试方式 (8)支持Internet多层体结构下的快速Web应用开发。 5.3数据库技术的发展 考点10数据库技术的发展阶段 1.第一代教据库系统 第一代数据库系统是指层次模型数据库系统和网状模型数据库系统二它确立了数据库的基本概念和方法，标志着数据管理由文件系统阶段进人了应用系统，但其数据模型复杂，必将会被第二代数据库所取代 2.第二代数据库系统 第二代数据库系统指支持关系模型的关系数据库系统。 第二代数据库系统奠定了关系模型的理论基础，给出了关系模型的规范说明；研究了关系数据语言、关系代数、关系演算,SQL查询语言等描述性语言；攻克了系统实现中的查询优化、并发控制、故障恢复等一系列问题 3.第三代数据库系统 在一些新领域中，关系数据模型已经不能满足应用的需求，不能建立起适合的关系模型。为了满足这些需求，面向对象的技术与数据库技术相结合便产生了第三代数据库系统。 考点11数据库系统体系结构 1.集中式数据库系统 数据库在一台计算机上运行，不与其他计算机交互，包括在个人计算机上的小型数据库系统，也包括运行在大型机器上的高性能数据库系统。 2.客户服务霖数据库系统 数据库根据功能可分为两个部分，即前端和后端。后端负责存取结构、查询计算和优化、并发控制及故障恢复，前端则是由表格生成工具、报表书写工具、图形用户界面工具等组成的。 前端和后端都在同一个系统中运行。客户与服务器之间相连要满足一系列的标准。通过应用程序接日来实现，客户使用接口来对服务器进行数据操作。 3.并行数据库系统 并行操作时，许多操作是同时执行的，通过并行地使用多个CPU来提高处理速度。大规模并行机具有数千个处理器。并行机器的体系结构模式主要有以下几种： (1)共享内存。所有的处理器共享一个公共的主存储器。 (2)其享磁盘。所右的朴理器其享冷冬其的磁盘。 (3)无共享。各处理器既不共享公共的主存储器，又不共享公共的磁盘。 (4)层次模式。它是前几种体系结构的混合。 并行数据库物理存储结构常用的划分技术有轮转法、散列分布和范围分布。 4.分布式数据库系统 一个分布式数据库系统是一个节点的集合，其中每一个节点是一个独立的数据库系统节点，这些节点协调工作，使得任何一个节点上的用户都可以对网络上的数据访问，就像这些数据都存储在用户自己所在的节点上一样。 考点12面向对象的数据库系统 1.关系数据库的局限性 关系数据库无法实现的新的应用领域包括以下方面： (1)计算机辅助设计(CAD)。 (2)计算机辅助软件工程(CASE)。 (3)多媒体数据库。 (4)办公信息系统(OIS)。 (5)超文本数据库。 2.面向对象的概念 面向对象的概念有：对象、属性、方法、消息、封装、类、继承和多继承等。 (1)对象：由一组属性和对这组属性进行操作的一组方法构成。 (2)属性：用来描述对象静态特征的数据项。 (3)方法：用来描述对象动态特征的操作序列。 (4)消息：请求对象执行某一操作或回答某些信息要求。? (5)封装：一种信息隐蔽技术，将属性和对这组属性进行的操作组成一个独立的单位。 (6)类：具有相同属性和方法的一组对象的集合。 (7)继承：相似类之间的一种联系。 3.对象一关系数据库系统 对象一关系数据库系统的基本特征如下： (1)SQL环境中支持基本数据类型的扩充。 (2)支持复杂对象。 (3)支持继承性。 (4)支持规则系统。 考点13数据仓库与数据挖掘 1数据仓库 数据仓库的基本特征包括以下几个方面： (1)数据仓库面向主题。 (2)数据集成。 (3)数据相对稳定。 (4)数据反映历史变化。 2数据挖掘 数据挖掘常用的方法包括以下几个方面： (1)关联规则挖掘。 (2)特征描述。 (3)分类分析。 (4)聚类分析。