附录一 GIS的计算机基础
导读：本章讲述了掌握GIS功能所需要的计算机基础知识，包括：
1）计算机组成原理：简单概述了计算机的发展历史，介绍了计算机的硬件组成，重点是各种输入/输出设备，这是GIS数据录入和制图输出所必需的，此外，虚拟现实设备——包括数字手套、头盔显示器的介绍将有助于理解数字地球部分的虚拟现实技术。
2）数据库知识：介绍了数据库，数据库管理系统的基本概念以及层次、网状、关系三种数据模型，并针对关系数据库讲述了其基本操作和SQL。
3）数据结构和算法：介绍了数据结构的基本概念，以及对于GIS软件实现非常重要的两种数据结构——树和图，最后给出了算法的定义以及算法效率的衡量指标，可以作为GIS算法设计的指导。
1．计算机组成原理
1．1计算机发展历史和展望
电子计算机的发展应该追溯到第二次世界大战期间，由于当时急需高速、精确的工具来解决弹道计算问题，1943年4月，宾夕法尼亚大学摩尔电工学院开始试制一台被称为ENIAC（Electronic Numerical Integrator and Computer）的电子数字计算机，并于1946年2月15日制造出了这台机器。1946年6月诺伊曼（Neumann）等发表了一份《关于电子计算装置逻辑结构初探》的报告，这份报告，提出了以二进制和程序存储控制为核心的通用电子数字计算机体系结构原理，奠定了电子数字计算机体系结构的基础，从此翻开了计算机发展的新篇章。
在电子计算机问世后，它所采用的基本电子元器件已经经历了电子管——晶体管——集成电路——大规模集成电路四个发展阶段，通常称为计算机的四代（图A1-1）。
1）电子管计算机时代，从1946年到1958年左右。这代计算机因采用电子管而体积大，耗电多，运算速度低，存贮容量小，可靠性差。虽然这个时期的计算机原始而笨重，但却确立了计算机发展的技术基础，例如，二进制、自动计算及程序设计等。
2）晶体管计算机时代，约为1958～1964年。这代计算机比第一代计算机的性能提高了数十倍。软件配置开始出现，一些高级程序设计语言相继问世，外围设备配置也由几种增加到十几种。除科学计算外，开始了数据处理和工业控制等方面的应用。
3）集成电路（IC,Integrated Circuit）计算机时代，约从1964年到1970年。这代计算机主要由中、小规模集成电路组成。这种电路器件是在一块几平方毫米的芯片上集成了几十个到几百个电子元件，使计算机的体积和耗电有了显著减小；而计算速度和存贮容量有较大提高，可靠性也大大提高，计算机软件配置进一步完善；有了操作系统，系统结构方面有了很大的改进。计算机机种多样化、系列化，并和通讯技术结合起来，使计算机应用进入许多科学技术领域。
4）大规模集成（LSI,Large Scale Integration）电路计算机时代，从70年代开始到现在。大规模集成电路是在一块几平方毫米的半导体芯片上集成上千个到十万个电子元件，使得计算机体积更小，耗电更少，运算速度提高到每秒几百万次。计算机可靠性也进一步提高。
七十年代初，出现了微处理器。它是把计算机的运算器、控制器制作在一片大规模集成电路芯片上，从而可以把处理器和半导体存贮器芯片以及外围接口电路芯片等组装在一起构成微型计算机。微型机体积小，价格便宜，灵活性大，使得计算机应用迅速发展，开始了个人用计算机的时代。
目前，计算机技术正在继续向巨型、微型、网络和人工智能等几个方向发展：
1）为满足尖端科学研究的需要，还必须发展高速、大存贮容量和强功能的巨型机；
2）计算机另一个发展方向是要研制价格低廉、使用灵活方便的微型机，以适应各种应用领域。
3）计算机网络是计算机的又一发展方向，计算机网络提高了计算机系统资源，特别是信息资源的综合利用，把分布在许多地区的计算机系统，特别是分布在各地的信息资源联结在一起，组成一个规模更大、功能更强、可靠性更高的信息综合处理系统。
4）美国、日本等国正在研制第五代“智能”计算机，它不是注重数学运算，而是注重于逻辑推理或模拟人的“智能”。
图A1-1：计算工具的发展概况
1．2计算机的基本组成
按照诺伊曼理论建立起来的当代计算机，应当具有输入/输出功能、存储记忆功能、计算功能、判断功能和自我管理功能。从功能模拟的角度，Neumann计算机通常由与上述功能对应的功能部件组成，这些部件主要包括输入/输出设备、存储器和中央处理单元（CPU,Central Processing Unit）。它们之间的关系如图A1-2所示。
图A1-2：计算机组成框图
1）输入/输出（I/O）设备
输入输出设备是接收外部信息（如输入原始数据和程序）或用来向外部输出信息（如计算结果）的功能部件，包括打印机、显示器、键盘、磁带机、扫描仪、鼠标器、光笔、触摸屏、条形码阅读器等。
2）中央处理单元（CPU,Central Processing Unit）
CPU是计算机的核心，它主要由运算部件、控制器、寄存器组所组成：
（2．l）控制器
控制器的主要功能是按时钟提供的统一节拍，把程序中每一条指令所含的各基本操作进行时序分配，并发出相应的控制信号，驱动各部件按照节拍有秩序地完成程序规定的操作内容。
（2．2）运算部件（ALU）
运算部件是直接进行数据变换与运算的部件。运算部件主要由逻辑电路构成的加法器组成。加法与逻辑运算是运算器最基本的操作，由它们可以进一步实现四则运算（加、减、乘、除）和逻辑操作（逻辑运算、条件运算等）。
（2．3）寄存器组
运算部件进行计算需要输入两个操作数，并产生两个输出：结果和运算特征。运算特征也称运算状态，如操作结果是否为零、是正还是负、有无进位、操作是加还是减等等，取得这些操作特征的目的是为了决定下一步的操作。
3）存储器
存储器是计算机的记忆装置，用以保存程序、原始数据以及中间结果。目前，计算机基本上采用线性地址存取方式。每一个地址对应一个存储单元，存储单元可以按位（bit）或按字节（8bit）、字（16bit）、半字（8bit）、双字（32bit）等编址。在按字节编址的情况下，每个存储单元存储一个字节（1Byte）信息。
存储器中存储单元的数量称为该存储器的容量，它是评价计算机功能的重要指标之一。存储器容量愈大，所能存储的信息就越多，可处理的问题的复杂度就越高。容量、价格、存取速度是评价计算机存储器的三大指标。但三者之间又互相制约：容量大，存取速度就要低；采用存取速度高的元件，成本就高；成本高，就不允许做得容量太大。为此，通常采用分级存储方式来解决这三者之间的矛盾。最基本的分级存储结构是两级存储，即把存储器分为主（内）存储器与辅助（外）存储器两级。主存储器采用半导体存储器，辅助存储器采用磁介质存储器。磁盘就是广泛使用的一种辅助存储器。为了进一步提高计算机的性能，在主存和CPU之间又增加一级比主存速度更高的高速缓冲存储器Cache，形成三级存储体系。
1．3存储系统
早期的诺伊曼计算机是以运算器为中心的，系统内各部件间的信息传送都要经过运算器。随着计算机应用的深入和外部设备的发展，内存与外存等外部设备之间的信息交换日益频繁，为适应这一情况，形成以存储器为中心的系统结构，主存同外部设备之间的信息交换不再通过运算器。共享主存的多处理机的出现，更加强了存储器作为计算机系统的中心地位。这时，存储器除了要向一台或多台高速运行的CPU提供所需的指令和数据外，还要同并行工作的外存及其它外设和终端等设备交换信息。存储系统的特性，已经成为影响整个系统最大吞吐量的决定性因素。
广义地讲，在一定条件下，物质性质的改变，就是对过程条件的记忆，如果这些物理性质可检测并且与其相应过程条件之间有确定的一一对应关系，则可用做记忆元件。基于二进制逻辑的电子计算机所要求的记忆元件应当有两个明确定义的物理状态，以分别表示两个逻辑值，并且这两个状态可以被检测并转换成电信号。信息的存取速度取决于测量与改变元件的记忆状态所需的时间，能满足这一要求的物质有机械的、磁的、电子的、光学的、化学的和生物的等等。
1．3．1主存储器组成
目前，主存储器中所使用的记忆元件是电子的，即半导体的，包括：
1）半导体RAM（Random Access Memory）记忆元件
随机存取存储器RAM要求能随机地对存储器中的任何单元进行存取，且与存取的时间和该单元的物理位置无关。具体地说，它要求元件有如下记忆特性。
有两种稳定状态；
在外部信号的激励下，两种稳定状态能进行无限次相互转换；
在外部信号激励下，能读出两种稳定状态；
可靠地存储。
2）半导体ROM（Read Only Memory）记忆元件
ROM是一种在机器运行过程中只能读出、不能写入信息的无源存储器，是一种非易失性器件。它所存储的信息是用特殊方式写入的，主要用于存储器经常要用的一些固定信息。
3）闪速存储器（Flash memory）
1．3．2辅助存储器
辅助存储器是主存储器的后援存储设备，用以存放当前暂时不用的程序或数据。对辅助存储器的基本要求是：容量大、成本低、可以脱机保存信息。目前主要有磁读写、光读写两类，如磁盘、磁带、光盘、光磁盘等。
1）软盘存储器
软盘存储器由软磁盘、软盘驱动器、软盘适配器三部分组成。它们是目前个人计算机中应用最为广泛的一种辅助存储器。
2）硬磁盘存储器
硬磁盘的盘片以铝合金为基体，因而“硬”，但存储原理与软磁盘相同，相对软盘，硬盘存储器存储容量更大，访问速度更快。
3）磁带存储器
磁带存储器是最早应用的磁表面存储器，其特点是存储容量大、价格便宜。
4）光盘存储器
由于多媒体的发展，这促使了光盘技术的迅速发展。光盘存储器是把激光束聚焦成lum左右的微小光点，使之能量高度集中，在记录介质上产生物理或化学变化而存储信息的。读出时，激光束在介质上扫描，根据反射光的变化判断记录的数据。
光盘存储技术记录密度高，存储容量大；可长期（60年～100年）保存信息；成本低廉，易于大量复制；存储密度高，体积小，能自由更换盘片；是很好的大容量存储技术。但是光盘的数据存取速率比磁盘低，目前一般为50～150MB/S，因此还不能完全取代磁盘。
5）磁盘阵列RAID
RAID（Redundant Arrays of Inexpensive Disk）是并行处理技术在磁盘系统中的应用。它把多台小型的磁盘存储器（或光盘存储器）按一定的条件组织成同步化的阵列，利用类似于存储器中的多体交叉技术，将数据展开存储在多台磁盘上，提高了数据传输的带宽，并用冗余技术提高了系统的可靠性。
1．4输入/输出系统
输入/输出系统是计算机主机与外界交换信息时需要的硬、软件设备的总称，简称外设系统。一般说来，外设系统的硬件由以下几个方面组成，这里主要介绍外部设备。
1）外部设备：围绕主机而设置的各种信息媒体转换和传递的设备。
2）设备控制器与接口：控制主机与外部设备之间的信息格式、交换过程、外部设备运行状态的硬、软件，也称设备适配器，它与外部设备的特性有关。
3）I/O总线；主机与外部设备之间的信息传送通路。
1．4．1外部设备及其分类
“外部设备”也称为外围设备。它们是指计算机系统中，除主机以外，直接或间接与计算机交换信息、改变信息媒体或载体形式的装置。从使用的角度，外部设备大致可以分为如下三类。
1）人——机交互设备
人一机交互设备，就是用户和计算机间交流信息的设备，其功能是把用户可以识别的信息媒体，转换成计算机可以识别的信息，如键盘、图形扫描仪、摄像机、语言识别器等；或者把计算机处理的结果信息，转换为用户可以识别的信息媒体，如打印机、显示器、绘图仪、语音合成器等。
2）机——机通信设备
机——机通信设备就是一台计算机与其他计算机或别的系统之间通信的设备，如两台相同型号或不同型号之间的计算机利用电话线路进行通信时，所需的调制解调器（MODEM）以及用计算机进行实时控制时的数/模（D/A，Analog/Digital）——模/数（A/D）转换设备等。
3）计算机信息的驻在设备
计算机信息的驻在设备，即计算机的外存储设备，如磁盘、光盘、磁带等。这些已在前面介绍过了。本节主要偏重于介绍人——机交互设备。
1．4．2字符输入/输出设备
1）键盘
字符输入设备的实质是将要输入的字符转换成相应的0、1码。目前，键盘是最重要的字符输入设备，键盘的基本组成元件是按键开关，它的种类很多，一般可分为触点式和无触点式两大类。
2）打印设备
打印设备是一种硬拷贝设备，它的作用是将输出信息打印在纸上，产生永久性记录。打印设备种类繁多，有多种分类方法。按印字原理分类，可以分为：
击打式：打印过程打印头要撞击纸。击打式打印机又分为活字式打印和点阵式打印；
非击打式：采用电、磁、光、喷墨等物理、化学方法印刷字符，打印过程纸不被撞击。如激光印字机（其技术来自复印机）、喷墨印字机等。
按工作方式可以分为：
串行打印机：逐字打印；
行式打印机：一次输出一行。
1．4．3图形/图像设备
1）绘图仪
绘图仪与图形显示器相似而又不同，不同处在于它是输出永久性图形的设备，而图形显示器是输出过程图形的设备，并且它们的结构元件不同；相似之处在于，它们形成图形的原理相似，即按形成图形的元素，绘图仪也可以分为向量绘图仪和点阵绘图仪两类。
（1）向量绘图仪
向量绘图仪，又称笔绘图仪，构成向量图形的基本元素是直线段。
（2）点阵绘图仪
点阵绘图仪又称无笔绘图仪，组成点阵图形的基本元素是点，或称象素。属于点阵绘图机的有静电绘图仪、喷墨绘图仪、热敏绘图仪和激光绘图仪等。
2）摄象机和扫描仪
（l）摄象机
摄象机是最直接的图像输入设备，它能把所摄图像经数字量化后变成数字图像存人磁带、磁盘或光盘，以备放映。
（2）扫描仪
扫描仪是能够全面而快速输入数据、文字和图形以及图像的输入设备。扫描仪从结构原理上可分为两大类，一类是CCD作为光敏元件，另一类是以光导纤维作为光的传导元件。在地理信息系统数据录入中，通过扫描仪得到图像数据，然后进行跟踪矢量化，是快速获取数据的重要手段。
1．4．4定位及拾取设备
定位/拾取设备通过指点来读取（位于屏幕或图表、图形上的）坐标，以画出或修改图形。按所拾取的坐标分为两类：拾取绝对坐标，如光笔和数字化仪；拾取相对坐标，如鼠标器、跟踪球、操纵杆等。
1）光笔
光笔是一种输入设备，用来检测信号，因为外形像支笔，所以叫光笔。其前端装有光敏器件，后端用导线接到计算机上。当光敏端的笔尖接触屏幕时，产生的光电信号向计算机发出中断脉冲信号，此瞬间显示存储器的地址就是光笔所指位置，计算机按操作人员的命令作出响应或画图、编辑和修改。
2）触摸屏
触模屏是一种能对物体的接触或靠近产生反应的定位设备。根据采用技术之不同，触摸屏分为五类：电阻式、电容式、表面超声波式、扫描红外线式和压感式。
3）数字化仪
在大量GIS应用中，一个至关重要的任务就是要把若干图形输入计算机中去。计算机不能直接识别这些图形，必须数字化即将其坐标输入到计算机。专门实现这一功能的计算机外部设备叫数字化仪。即所谓数字化仪是指专门用来读取图形信息的计算机输入装置。
数字化仪设备比较简单，一般由两部分组成，第一部分是感应板部分（又叫画图板Drawing Board，但叫感应板比较确切），第二部分是点设备（Pointing devices）又叫传送器或者游标。对于立式的数字化仪还有一个底座，是为了架感应板用的。
数字化仪是计算机图形系统的输入设备。当画笔接触到其图形板上的某一位置时，会将画笔位置的坐标转换为二进制的数字量，输入计算机，随着画笔的运动，可以把一个图形输入到计算机中。
数字化仪的种类较多，按测量坐标的原理，大体上可分为机电式、超声波式、磁致伸缩式和电磁感应式四种，其中电磁感应式是目前最常见的数字化仪。
4）鼠标器、跟踪球和操纵杆
鼠标器、跟踪球（也称轨迹球）和操纵杆，是与屏幕相配合拾取光标的相位坐标的输入设备。
1．4．5虚拟现实设备
一个虚拟现实系统，可以分解为三个独立的、但又相互联系的感觉引导子系统，即视觉子系统、听觉子系统和触觉动觉子系统。这三个子系统由虚拟环境产生器进行控制、协调，如图A1-3所示。
图A1-3：VR系统一般组成
1）虚拟环境产生器
虚拟环境产生器实质上是一个包括虚拟世界数据库的高性能计算机系统。该数据库包含了虚拟环境中对象的描述以及对象的运动、行为及碰撞作用等性质的描述。虚拟环境产生器的另一作用是生产图像。这些图像的生成必须在最短的时间延迟内考虑参与者头部的位置和方向。虚拟环境产生器内的任何通信延迟都必将表现为视觉的滞后。如果这种滞后可以感知，在某种条件下就会使参与者产生晕眩的感觉。
2）触觉/动觉子系统
为了增强虚拟环境中身临其境的感觉，必须给参与者提供一些诸如触觉等方面的生理反馈，触觉反馈是指VR系统必须提供所能接触到的物体的触觉刺激，如物体表面纹理或甚至包括触摸的感觉等。参与者感觉到物体的表面纹理等时，同时也感觉到运动阻力。当然，毫无疑问VR系统中的触觉/动觉反馈是很难实现的。一旦实现，将极大地增强虚拟存在的感受。目前触觉/动觉系统中一个重要的部分是手跟踪和手势跟踪。它的一个已经实用化的设备是数据手套（Data Glove），如图A1-4所示。
图A1-4：数据手套
数据手套的机理主要依靠纤细的光导纤维和光线的直线传播特性。它选用非常适合于屈伸的材料制成。对每一个指头都有一根光纤从手腕出发，经指尖绕回再到手腕处的光纤；一端装有光信号源（LED），另一端装有测量光通量的光传感器件。在指关节处光纤表面切
有微小的豁口，当手指弯曲时豁口裂开有光通量漏掉。当人带上手套后手指伸直时，由于光线的直线传播几乎能获得100％的输出光量，一旦手指弯曲则光量随弯曲程度而衰减。这种光量的变化，在控制器里由模/数变换器（A/D）转换成数字量，向主计算机传送，并进行计算、解释。
目前，数据手套暂时只能输入手势语言信息，当人情不自禁地去“触摸”或抓放一个物体时，数据手套便可以把这些手势信息转入（反馈）到虚拟环境产生器中。当然，为了反映手在“抓摸”时的用力情况，还应有压力反馈，这个问题目前正在解决。
3）视觉子系统
视觉是人类用以接收信息的主要器官。目前，VR技术中最重要的一项技术是大视场双眼体视显示技术。
人类的视觉，是一个具有双眼坐标定位功能自然序列：人的两只眼睛同时看到周围世界的同一个窗口，但由于两眼位置上的差别，在视网膜上各自生成略有差别的图像，这两
个图像通过大脑，被综合成一个含有景物深度的立体图像。VR体视显示技术用以下两种方案解决这一问题：一种是用两套主机分别计算并驱动对应左右眼的两个显示器；另一种是用一套主机分时地为左右两眼产生相应的图像。
图A1-5：一种头盔式显示器及其分解图
目前，VR显示装置的主流是头盔式显示器。图A1-5为头盔式显示器原理的分解图。当然，最重要的还是要能在显示屏上产生清晰、逼真的图像。
4）听觉子系统
通常听觉系统也安装在头盔显示器上。听觉子系统主要由声音合成、3D声音定域和语音识别组成，以给虚拟环境中的用户一个真实的声音环境。
（l）声音合成
尽管听觉系统以比视觉系统低得多的频带宽度工作，但人的听觉系统很善于在众多的声音中挑取特定的声音，作为对视觉摄取信息的补充。因此，在VR系统中加入声音合成装置是十分必要的。当视觉系统处理某一事件时，听觉系统同时在后台工作。
（2）3D声音定域
为造成逼真的声音环境，就要使参与者能通过两耳因位置不同，所接受的声波的时差等，分辨出声源与自己的相对位置；即使参与者在头部运动时，也能感觉这种声音保持在原处不变。为了达到这种效果，声音定域系统必须考虑参与者两个“耳廓”的高频滤波特性。参与者头部的方向对于正确地空间化声音信号是很重要的。因此，虚拟环境产生器要为声音定域装置提供头部的位置和方向信号。
（3）语音识别
语音识别在输入数据大量时，是非常有效的。
1．4．6调制解调器
目前使用的计算机一般都是数字计算机，即在计算机中处理的是数字信号，而普通电话线上传输的是音频信号。用普通电话线传输数字信号的效率是很低的。为了能用普通电话线进行计算机通信，应当把要发送的数字信号先调制（Modulate）成音频信号，送到目的地后再解调（Demodulate）成数字信号。完成这一功能的设备称为调制解调器MODEM。由于一台计算机既要接收信号，又要发送信号，所以调制解调器既有调制功能，又有解调功能。调制解调器是拨号接入方式下的关键设备。
一些新的输入输出设备：
随着计算机技术的发展，出现了一些新的、更加方便的输入输出设备，下面是其中的简单介绍：
源数据自动化设备：包括条形码阅读机，磁性墨水字符阅读机（用于支票上的数字）。
语音录入：也称为“语音识别”，允许用户通过讲话向系统发出指令。
数码相机：可以直接得到数字图像，并由软件进行进一步的处理。
1．5计算机系统性能
全面衡量一台计算机的性能要考虑多种指标，并且对不同的用途所侧重的方面不同。下面从普遍应用的角度，介绍主要的几种性能指标。
1）CPU字长
CPU字长是指CPU一次所能处理的位数。CPU字长越长，表明CPU所能处理的数据的精度越高，并且影响处理的速度。因为短字长的 CPU对较大的数据要通过两次甚至多次运算实现。目前微型计算机的字长从8位、16位、32位，到64位等。当然CPU字长越长，价格就越高。为了适应不同的需要，并协调精度与成本，人们还设计了可变字长计算，如半字长、全字长、双字长等。
2）主频率
CPU工作的节拍是由主时钟控制的。主时钟不断地产生固定频率的时钟脉冲，时钟脉冲的频率就是CPU的主频率。主频率越高，CPU的工作节拍越快。这是影响机器运算速度的重要参数。
3）主存容量
主存用以直接与CPU交换信息。主存容量大，处理问题的能力就强。同时由于它与外存之间的信息交换次数少，解题时间效率高。计算机的最大主存容量由CPU的地址总线的根数决定。地址总线为16条时，CPU的最大寻址范围为64K；地址总线为20条时，CPU的最大寻址范围为1M。目前，微机地址总线为32条，最大寻址空间为4G。
4）软、硬件配置及性能价格比
软、硬件配置包括外部设备的配备情况，指令系统以及操作系统功能的强弱、界面是否友好，有无其它支持软件和应用软件等。性能价格比是人们对经济效益的选择，这个值越大越好。
5）RASIS特性
可靠性（Reliability）、可用性（Availability）、可维护性（Servicebility）、完整性（Integrality）和安全性（Security）统称RASIS。它们是衡量一个现代化的计算机系统性能的五大功能特性。
6）兼容性
所谓兼容性（Compatibility），是指系统间所含的某些“东西”具有并存性，即意味着两个系统之间存在着一定程度的通用性，它使机器能承前启后、便于推广。
2．数据库系统基础
目前，数据库管理系统（DBMS,Data Base Management System）正日益进入最终用户的日常应用，人们每天都在日常生活中用到数据库，如使用信用卡购物、订票、书目查询等等，在使用过程中，用户不需要了解数据的具体存取和管理方式，正是数据管理系统提供了这些功能。
2．1数据库的基本概念
定义数据库管理系统之前，必须首先定义这种系统的基本成分——数据库，一个数据库有四个主要成分：数据、联系（Relationship）、约束（Constraint）和模式（Schema）（图A1-6）。数据是所存储的逻辑实体在计算机中的二进制表示；联系表示数据项之间的某种对应；约束是定义正确数据状态的断言；一种模式描述数据库中数据的组织和联系。
图A1-6：数据库组成
模式为数据库管理系统各个组成部分的使用和应用的安全定义数据库的各种视图。模式将数据存储的物理外表与逻辑表示分开（见图A1-7）。内部模式定义数据在物理数据存储区中如何组织以及放在何处。概念模式模型按照适当的数据库数据模型（如关系模型或对象模型）定义所存储数据的结构。外部模式为特定用户们定义数据库的一个或多个视图。
图A1-7：数据库模式的概念
数据库管理系统为访问数据库提供服务，同时维护存储数据所要求的正确性和一致性。
在数据库管理系统中，运行的工作单元是事务（Transaction）单元，在此之上定义了一致性和正确性。事务应该支持ACID属性。ACID属性包括：事务运行的原子性（Atomic）、一致性（Consistent）、独立性（Isolation）和事务执行的持久性（Durability）。
1）原子性确保事务被当成一个不可分割（All－or－Nothing，要么全做，要么根本不做）的操作单元处理。
2）事务操作的一致性确保数据库从原来的一致性状态正确转移到一个新的一致性状态，此处的一致性由数据库中数据项上的谓词定义。
3）事务的独立属性定义了允许它们可见什么。一个被孤立的事务只“看到”数据库的一个视图，就好像事务是单独在数据库上执行一样。
4）持久性属性确保一旦提交了一个事务，其结果就持久存在且不能从数据库中消除。
2.2数据库的数据模型
按照描述数据与数据间关系的方法不同，数据库常用的数据模型有层次模型、网状模型和关系模型。
2．2．1层次模型
层次模型是一种基本层次联系的集合，它实际上是一种有根定向的有序树，如图A1-8所示。层次模型的基本结构是树结构——根、枝、叶结构，数据存放的基本单位是片断（即层），片断是内在有逻辑联系的一组数据，总的来说，层次模型按照树形结构以片断为单位存放数据。层次模型比较容易实现，但是查找比较麻烦，数据的冗余度也比较大。
图A1-8：数据库层次模型
2．2．2网状模型
所谓网状模型是指一个连通的基本层次联系的集合，如图A1-9所示。复杂的网总可以分解成若干个基本结构，即分解成系。系有系主（只有一个）和系属（可以有多个），系主和系属之间有关系，而且关系是双向的。
图A1-9：网状模型示例
网状模型存放的基本单位是记录，也就是按记录存放，查询时，从系（系主和系属）查起。网状模型查找时间较省，数据和冗余度比层次模型小，但比关系模型要大。
2．2．3关系模型
关系模型是目前最为流行的数据模型，它是由许多二维关系表组成的集合。例如表1就是一张关系表，R是关系名，Ai是属性名，关系和属性（R,A1,A2…An）组成了数据表的模式(Schema)；Vij叫做分量，表中的一列是一个属性，相当于一个数据项（或数据元素），一行叫做—个元组（Tuple），相当于一条记录。
关系模型中所有数据都按表格存放，有关系的数据放在一张表上，表与表之间有连接。
表A1-1：关系表R
A1
A2
… … …
Aj
… … …
An
V11
V12
… … …
Vlj
… … …
Vln
∶∶∶
Vil
∶∶∶
∶∶∶
Vi2
∶∶∶
∶∶∶
∶∶∶
∶∶∶
Vij
∶∶∶
∶∶∶
∶∶∶
∶∶∶
Vin
∶∶∶
Vm1
Vm2
… … …
Vmj
… … …
Vmn
关系模型的特点是每一个分量必须是不可分割的数（数据元素），也就是不允许表中还有表。另外表和表之间的联系要用关系表示，而不是用其它表示。
关系模型查找很方便，数据冗余度小，但关系联结时效率较低。
关系表的操作可以分为以下四种：
通用的集合操作，如并、交、差运算等；
2）去除关系表的某些部分的操作，包括选择(Selection)和投影(Projection)，前者去除某些元组，后者则用于除去某些属性；
3）两个关系表的合并，包括“笛卡尔积”以及各种方式的连接运算；
4）更名操作，即对关系表属性名称的修改，它不改变元组，但是改变了关系表的模式。
下面以常见的学生管理例子说明这些操作：
学生关系表R1
姓名
年龄
性别
Carola
20
女
Maxwell
21
男
Churchill
18
男
学生关系表R2
姓名
年龄
性别
Johnson
17
男
Maxwell
21
男
Barbara
24
女
Williams
20
女
学生成绩表R3
姓名
语文
数学
Johnson
A
A
Maxwell
B
A
Barbara
A
A
Williams
A
C
Carola
C
C
Churchill
C
B
对R1和R2进行求交集运算的结果（R4）
姓名
年龄
性别
Maxwell
21
男
对R1和R2进行求并集运算的结果（R5）
姓名
年龄
性别
Johnson
17
男
Maxwell
21
男
Barbara
24
女
Williams
20
女
Carola
20
女
Churchill
18
男
对R5和R3根据“姓名”进行连接操作结果（R6）
姓名
年龄
性别
语文
数学
Johnson
17
男
A
A
Maxwell
21
男
B
A
Barbara
24
女
A
A
Williams
20
女
A
C
Carola
20
女
C
C
Churchill
18
男
C
B
对R6选择“性别=“男””，并且对姓名、语文、数学成绩进行投影的结果（R7）
姓名
语文
数学
Johnson
A
A
Maxwell
B
A
Churchill
C
B
关系数据库的查询和修改操作是通过SQL(结构化查询语言，Structured Query Language)，SQL的基础是关系代数，同时也包括了其它的一些操作，如求和、汇总、数据更新等等，下面是一个SQL查询的例子：
对于关系：
省份（省会，人口，产值，面积）
SQL语句：
Select *
From 省份
Where 人口>60,000,000 and 面积<160,000
用于查询得到人口大于6千万并且面积小于16万平方公里的省份。
2．2．4面向对象数据库模型
网络和层次以及关系模型都适合那些结构简单以及访问有规律的数据。这些模型的最佳应用领域有个人记录管理，清单控制，终端用户销售，商业记录等，所有这些应用领域都只有相当简单的数据结构、联系以及数据使用模式。但是，当试图把这三种模型应用于更高级的领域时，数据不能用类似于记录这样的简单结构来表示了，访问和操作方法也不再简单。这些应用领域需要更复杂的抽象数据类型，如图形，声音，图标，包，清单，队列，以及地图，这些数据类型都各自定义了独特的操作方法——例如，一个地图对象可以定义为经度、纬度、地点的时间维；以等高线来定义地形；用图标表示主要的嵌入对象，而他们本身也可能是对象。除了这些定义之外，在地图的各区域可能还含有隐藏的数据。我们可以表示人口密度、动物密度、植物、水源、建筑物及其类别（例如，单个住宅楼，高楼，工业建筑，居民楼）、污染情况以及其他信息，所有这些都是从应用领域典型使用中派生出来的抽象数据类型（图A1-10）。
图A1-10：地图抽象数据类型
面向对象数据库的引入就是为了满足一再出现的复杂信息的共享。在复杂数据进入数据库以后，数据库提供了存贮信息的统一视图，与具体存贮结构无关。把物理数据结构与逻辑数据结构分开，同时控制数据的共享及保持数据的正确性、完整性和一致性，大大方便了应用程序的开发和维护，减少生命周期内的各种费用。通过一组优化的程序来管理数据，使得整体效果更优，性能更稳定。
2.3数据库管理系统
数据库管理系统（DBMS）是为数据库访问提供服务的软件，同时维护所有数据必需的特性。数据库管理系统为支持应用程序访问和操作数据库数据提供下列服务：
1）事务处理
事务将使数据库从一个一致状态转移到另一个一致状态。数据库操作被分成两大类：数据访问操作和事务操作。有三种特定的事务操作：启动（Start）指示将开始一个新事务，提交（Commit）指示事务已正常终止且其作用结果将持久存在，以及放弃（Abort）指示事务被异常终止，其所有结果将被放弃。事务通常需要具有前面提到过的ACID属性。
2）并发控制
并发控制是一种数据库管理活动，它协调数据库操作进程的并发操作和对共享数据的访问，并且解决它们之间可能发生的潜在冲突。并发控制机制的目标是允许并发维护共享数据的一致性，数据库系统中的并发单元是事务。
3）恢复
数据库中恢复的目标是确保异常终止或出错的事务不会对数据库或其他事务产生不利影响。异常终止的事务有两种影响；对数据的影响和对其他事务的影响。恢复可使得数据库在事务异常终止后返回某个一致状态。
4）安全
安全是保护数据免受非授权的泄露、更改或破坏。每个用户和应用程序都有特定的数据访问特权。这些特权可以由外部模式定义，即根据各个用户被允许访问和/或修改的数据，给予它们不同的数据视图。安全系统提供一些方法，来决定每个用户或应用程序可访问什么视图。通过授权和身份鉴别过程，安全还具有限制初始访问数据库的功能。这些过程中最常用的是注册名和口令保护服务。
5）语言接口
DBMS提供对用于定义和操作数据的语言的支持。概念模式是用数据定义语言（Data Definition Language，DDL）说明的。这种数据库语言部件是用来描述数据、数据间联系和对数据和联系的约束的表示法。DDL首先用在数据库设计时，以后修改模式时还会用到DDL。
数据操纵语言（Data Manipulation Language，DML）用于表达数据库上的操作。DML有时也称为查询语言。DBMS提供DML，以便用户和应用程序编写者访问数据库中数据，而不必知道数据库如何存储数据或把数据存在何处。
6)容错性
不管发生什么故障仍能继续提供可靠DBMS服务的能力称为容错性。一个出错的数据库部件将使与其交互的其他部件产生故障。典型的数据库故障包括违反约束和事务超时错误。如上所述，恢复与容错性密切相关，因为恢复是一种机制，它能容许发生使事务异常终上的差错。
7)数据目录
数据目录（有时称为数据字典）是一个系统数据库，它含有主数据库中数据的描述（有时被称为元数据，Metadata）。它包含有关数据、联系、约束的信息，以及将这些特征组织到一个统一数据库中的所有模式的信息。通过查询目录可获得有关主要数据库结构的信息，因而目录被看成一个数据库。
8）存储管理
DBMS提供数据持久存储的管理机制。内部模式定义数据应该如何用存储管理机制存储。为了访问物理存储，存储管理系统与操作系统间有接口。
3．数据结构和算法
3.1数据结构的概念
3．1．1数据结构——一个例子
从提出一个实际问题到计算机解出答案需要经过下列步骤：首先从实际问题抽象出一个数学模型，然后设计一个解此数学模型的算法，最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象以及这些操作对象之间含有的关系，然后用数学语言加以描述。例如，在分析了一个物理现象或化学现象变化的规律之后可以得到一组代数方程或微分方程。然而，更多的问题无法用数学方程加以描述。下面用一个例子来说明数据结构。
多叉路口交通灯的管理问题。通常，在十字交叉的路口只要设红绿两色的交通灯便可保持正常的交通秩序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞而又达到最大的流通呢？假设有如图A1-11（a）所示的五叉路，其中C和E为单行道，在路口有13条可行的通路，其中有的可以同时通行，如A→B、和E→C，而有的不可同时通行，如E→B和A→D，那末，在路口应如何设置交通灯进行管理？这个问题可以转换成一个图的染色问题。假设在图上以一个圆圈表示一条通路，在不能同时通行的两个圆圈之间画一连线，对图中的圆圈上色，要求同一连线上的两个圆圈不同色且颜色种类最少。图A1-11（b）是与图A1-11（a）相应的图，图中13个圆圈表示13条通路，圆中的号码分别表示四种颜色的交通灯。
图11:五叉路口交通管理意图
（a）三叉路口（b）表示通路的图
由以上例子可见，描述这样一类问题的数学模型不再是数值方程，而是诸如表、树和图等的非数值性的数据结构。因此，简单说来，数据结构就是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科。
3．1．2基本术语
下面是数据结构中常用到的名词和术语的含义：
1）数据（Data）
数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。它是计算机程序加工的“原料”。例如，一个利用数值分析的方法解代数方程的程序处理的对象只是整数和实数，而一个编译程序或文字处理程序的对象是字符串。因此，对计算机而言，数据的含义极为广泛，如图形、声音等都属于数据的范畴。
2）数据元素（Data Element）
是数据的基本单位，即数据这个集合中的一个个体（客体）。有时一个数据元素可由若干个数据项（data item）组成，数据项是数据的最小单位。
3）数据对象（Data Object）
是具有相同特性的数据元素的集合，是数据的一个子集。例如，整数的数据对象是集合N＝｛…，-2，-1，0，1，2，…｝，字母字符的数据对象是集合C＝｛A，B，…，Z｝。
4）数据结构（Data Structure）
简单说来，数据结构是带有结构的数据元素的集合。从上述面的例子可以看到，被计算机加工的数据元素都不是孤立的，在它们之间存在着某种联系，这种相互的关系，通常称做结构。我们可以从集合论的观点加以形式化描述。
数据结构是一个二元组
Data-Structure＝（D,R）
其中：D是数据元素的集合，R是D上关系的集合。例如，复数可被定义为一种数据结构:
Complex＝（D，R）
其中D＝｛x|x是实数｝
R＝｛R1｝
R={<x，y＞|x，y∈D，x称为实部，y称为虚部}
由此，由任何一对实数均可得到一个复数。
在上面对数据结构的定义中，R集合中的关系指的是数据元素之间的逻辑关系，因此，又称数据的逻辑结构。与此对应，则有数据的物理结构，又称存贮结构，是数据结构在计算机中的映象（或表示）。
5）数据类型（Data Type）
是程序设计语言中所允许的变量的种类，换句话说，是变量可能取的值和能作的运算的集合。在每一种程序设计语言中都有一组它所允许的基本数据类型。各种语言所能提供变量类型的多少决定了该语言功能的强弱。我们可以把数据类型看作是程序设计语言中已经实现的数据结构，如复数、数组等。因此，数据类型实际上是数据结构（包括逻辑结构和存贮结构）及其运算的总称。
3.2两种重要的数据——树和图
3．2．1树和二叉树
树（Tree）是一种重要的非线性结构，在计算机软件设计中被广泛使用，如哈夫曼树可以应用于数据压缩编码，而B+树则在文件系统管理中被使用。图A1-12表示了树的示例。
图A1-12：树的示例
在图A1-12中，结点A为树的根，根的每个分支称为子树（Subtree），子树也是一棵树；结点子树的根为结点的孩子（Child），如B、C、D为结点A的孩子，而A为B、C、D的双亲（Parent）；同一个双亲的孩子之间为兄弟（Sibling）关系；没有孩子的结点为树的叶子（Leaf），H、F、G、D为树的叶子。
树的基本操作包括：
1）初始化一棵树；
2）得到树的根；
3）得到一个结点的双亲；
4）得到一个结点的兄弟；
5）得到一个结点的孩子；
6）插入子树；
7）删除子树；
8）遍历（Travers）树；
9）清空树。
在不同的软件系统中，由于具体实现的不同树的操作也不同。
二叉树（Binary Tree）是另一种树型结构，其特点是每个结点最多有两棵子树。树和二叉树之间可以相互转换。
各种特定的树型结构被广泛应用于查找算法的实现中，它们可以加快查找的速度；在地理信息系统中，可以用于空间索引的建立，以提高空间要素的检索效率。
3．2．1图
图（Graph）是较树更为复杂的数据结构，在图中，结点之间的关系是任意的，图中任意两个数据元素都可能相关。图A1-13给出了图的示例。
（a）有向图 （b）无向图
图A1-13：图的示例
图的形式化定义为：
Graph = (V,R)
其中：
V={x|x∈dataobject}
R={VR}
VR={<x,y>|P(x,y)∧(x,y∈V)}
图中数据元素称为顶点（Vertex），V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合，其定义中P(x,y)表示x到y的一条单向通路；若<x,y>∈VR，则<x,y>表示从x到y的一条弧，此时图称为有向图（Digraph）；若<x,y>∈VR必有<x,y>∈VR，则此时图称为无向图。
在图中，如果<x,y>∈VR，则x，y互为邻接点。路径（Path）是一个顶点序列（V1,V2,…Vn），其中Vi和Vi+1为邻接点。
图可以有多种存储结构，其中最普通的是采用邻接矩阵，如果两个结点<Vi,Vj>∈VR，则矩阵对应元素A[i,j]=1，反之，A[i,j]=0。
无向图的邻接矩阵是对称的，而有向图的邻接矩阵则不一定对称，图A1-13中两个图的邻接矩阵如下（其中没有考虑相同点邻接性）：
在地理信息系统中，可以应用图数据结构进行网络分析，判断两个空间要素之间的连通性及其最短路径。
3.3算法
3．2．1算法的概念和特性
数据结构和算法构成了计算机程序，所谓算法（Algorithm），是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每个指令表示一个或者多个操作。一个算法还具有以下五个重要特征：
1）有穷性
一个算法必须总在执行有穷步之后结束，而且每一步都可以在有穷时间内完成；
2）确定性
算法中的每一步必须有明确的含义，不会引起二义性；并且，算法只有唯一的执行路径，即相同的输入只会得到相同的输出。
3）可行性
一个算法必须是可行的，即算法中的操作都是可以通过已有的基本运算完成。
4）输入
一个算法可以有零个或者多个的输入。
5）输出
一个算法有一个或者多个的输出，这些输出同输入有特定的关系。
3．2．2算法设计的要求
设计一个“好”的算法应该考虑达到以下目标：
1）正确性
算法应该满足具体问题的要求，对于输入数据能够得到符合规格说明的结果。
2）可读性
算法的可读性有助于人对算法的理解，便于修改和调试。
3）健壮性
当输入数据非法时，算法也能够正确处理，而不会出错。
4）效率与低存储量需求
效率指的是算法执行时间，一个算法执行时间越少，效率越高；存储量需求是指算法执行过程中所需要的最大存储空间。一个好算法要有高的执行效率和低的存储量需求，但是在实际实现中，二者并不可以兼得，通常可以用大的空间开销来提高算法执行效率，或者以降低执行速度作为减少空间开销的代价。
决定一个算法的效率和存储需求的因素包括书写程序的语言、生成的机器代码的质量、机器执行指令的速度等等，但最重要的是算法解决问题的规模。一个算法是由控制结构（顺序、分支和循环三种）和原操作构成，通常是在算法中选取一个基本原操作，并以该操作重复执行的次数作为算法的时间度量。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记做：
T(n)=O(f(n))
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称为算法的渐近时间复杂度，简称时间复杂度(Time Complexity)。常见的算法时间复杂度有O(1)、O(n)、平方阶O(n2)、对数阶O(logn)、指数阶O(2n)等等，在算法设计时，可以根据时间复杂度对算法优劣进行评判，通常指数阶的时间复杂度是不可以考虑的。
算法执行所需要的存储空间通过空间复杂度来度量，记做：
S(n)=O(f(n))
其意义类同于时间复杂度。
