第 5章 信息数据的结构、组织和管理
计算机并非天生具备这些功能，它们都是程序员赋予的，那么程序员又是如何具备这一超凡的能力？这就是本章所要学习的。 本章首先学习现实生活中的各种信息数据之间存在怎样的内在联系，如何在计算机中体现这一联系，从而使计算机能够进行信息处理。
其次，学习在面对大量信息数据时，如何提高人们的工作效率，即数据库技术。
5.1 为什么要进行数据组织？
数据组织的两层目的,一是能够解决问题,二是方便地解决问题 。
5.2 数据结构
5.2.1 数据结构要解决什么问题数据结构应该包含两层含义，即数据的逻辑结构和物理结构。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，
即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率
5.2 数据结构
5.2.2 线性表线性表是最简单,最常用的一种数据结构,它的逻辑结构是几个数据元素的有限序列 （ a1,a2,…,a n） 。 线性表的组成实际上包括两个要素,一是数据本身
―― 数据元素,它由若干个数据项组成；
二是数据元素间的联系 —— 元素间的前驱与后继关系 。 因此,解决线性表的存储问题就是要解决数据元素的存储以及元素间联系的存储 。
5.2 数据结构
5.2.3 树形结构（层次结构）
树是 n (n≥0) 个结点的有限集合，当其非空（ n>0） 时，有且只有一个特定的结点称为根，当 n>1时，其余结点可分为 m(m>0)
个互不相交的有限集合 T1… Tm,每一个集合又是一棵树，称为这个根的子树。特殊地，
若限定树的子树最多只能有两棵，且区分为左、右子树，它就成了另一种树型结构 ――
二叉树 。树与二叉树之间有个自然的一一对应关系，每一棵树都能惟一地转换到它所对应的二叉树。
5.2 数据结构
5.2.4 图
逻辑结构图是一种比线性表和树形结构更为复杂的数据结构 。 在线性表中,每个结点只有一个直接前驱和后继；在树形结构中,有明显的层次关系,每一层中的元素只和上一层中的一个元素 （ 即双亲 ）
相关 。 而在图中,任意两个元素中均有可能相关 。
5.2 数据结构
存储结构图的结构复杂，存储表示方法也多种多样，但一般的存储表示法都由明显的两部分组成，一是存储顶点信息（ G）,一般用顶点数组表示（人为给顶点加上编号）；
二是存储边的信息（ E）,当然要与相应的结点联系在一起。常用的存储表示方法有数组、邻接表、十字链表等 。数组表示法用两个数组分别存储数据元素（顶点）的信息相邻矩阵 —— 顶点数组和数据元素之间关系（边或弧）的信息。
5.2 数据结构
图的基本操作 —— 遍历和树的遍历类似,图的遍历也是从图中某一顶点出发,系统地访问图中所有顶点,且使每一个顶点恰被访问一次 。 通常有两种遍历方法：深度优先遍历和广度优先遍历 。
应该注意的是,图的遍历得到的次序不仅取决于所采用的方法,还取决于从哪个顶点以及它具体的存储结构 。
5.3 关系数据库
5.3.1 数据处理技术的发展随着计算机技术的发展，在 20世纪 50年代后期至 60年代中期，计算机的外存已有磁盘、
磁鼓等直接存取的存储设备；软件方面也有了专门管理数据的软件 —— 文件系统，它是操作系统的一部分。数据管理技术的这一发展阶段被称为文件系统阶段。在这一阶段，随着数据管理规模的扩大，数据量急剧增加，文件系统也显露出了 3个缺陷：数据冗余,数据不一致,数据联系弱 。
5.3 关系数据库
5.3.2 要会使用数据库，我们应掌握些什么首先，一个特定的数据库管理系统是以一种特定的方式来组织、描述和储存数据的，这种对数据的组织、描述和存储方式，就称为数据模型。
第二,DBMS是一个专门的数据管理软件，它负责数据的物理存储过程和各种操作的具体实现。第三，面对一个复杂的应用环境，我们还应该知道如何去设计好一个数据库 —— 数据库设计理论 。
最后，作为一个专门管理数据的软件，它不应该太脆弱，应具有一定的强壮性 。
5.3 关系数据库
5.3.3 数据模型模型是对现实世界的抽象。 数据模型 就是一组严格定义的概念工具，和地图中的图例符号一样，我们用这组概念工具，把现实世界中我们所关心的那部分内容 —— 数据及其联系描述出来。
数据模型的种类很多 。 目前广泛使用的可分为两种类型：
一种是独立于任何计算机系统的模型，不涉及信息在计算机系统中的表示，只是用于描述某个特定组织所关心的信息结构，这类模型称为,概念数据模型,。另一种是直接面向数据库管理系统的逻辑数据结构，例如：
层次、网状、关系模型等，这一类模型也称为,基本数据模型,或,结构数据模型,。
数据和联系的描述在数据处理中,将涉及不同的描述领域 。
从事物的客观存在,到计算机里的具体表示,
实际上经历了 3个数据领域 —— 现实世界,
信息世界和机器世界 。
实体联系模型 （ E-R模型 ）
实体联系模型是 P,P,S,Chen于 1976年提出的,它是一组对信息世界建模的概念工具 。
这个模型是直接从现实世界中抽象出实体类型及实体间联系,然后用 E-R图表示数据模型 。
E-R图提供了表示实体型,属性和联系的方法 。
关系模型在关系数据模型中,用二维表格结构来表示实体和实体间的联系 。
5.3.4 关系数据库标准语言 —— SQL
5,4 数据库设计数据库设计是指对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能有效地存储数据，满足各种用户的应用要求。大型数据库的设计和开发是一项庞大的工程，其开发周期长、耗资多，失败的风险也大。实践表明，数据库设计是一项软件工程，开发过程必须遵循软件工程的一般原理和方法。
5,4 数据库设计
5.4.1 数据库设计的全过程需求分析阶段 （本阶段的工作成果是,需求说明书,,它由两部分组成，一是分层的数据流图，二是数据字典。）
概念结构设计 （将需求分析阶段得到的用户需求抽象为概念模型（ E-R图）的过程就是概念结构设计。它是整个数据库设计的关键。）
逻辑结构设计 （逻辑结构设计的任务是把概念结构转换成 DBMS所支持的数据模型，即网状、
层次或关系模型。它包括把基本 E-R图转化成概念模式，把分 E-R图转换成外模式。 ）
5,4 数据库设计物理结构设计 （ 数据库在物理设备上的存储结构与存取方法称为数据库的物理结构。为一个给定的逻辑数据模型选取一个最适合应用要求的物理结构的过程，就是数据库的物理设计。）
5.4.2 关系数据库的模式设计理论我们在设计数据库逻辑结构时知道：把 E-R
图转化为数据库模式时，可能存在多种组合，
必须从中选择一个合适的、性能好的作为数据库模式。
5,4 数据库设计
不良关系模式的存储异常问题
插入异常
数据冗余
修改复杂
删除异常
属性间的函数依赖关系
5.5 数据库的保护
数据库保护是指在系统运行过程中，防止数据意外丢失、产生不一致数据或者遭到恶意破坏等情况。主要有三个方面：
一是与事务有关的数据库恢复和并发控制。二是防止不合法使用造成数据泄露、
更改或破坏等数据库安全性控制。三是防止产生不符合语义数据的完整性控制。
数据库恢复
– 事务内部故障
– 系统故障
– 介质故障
并发控制
– 排它锁 （ X）
– 共享锁（ S锁）
数据库的安全性
– 用户标识与鉴别
– 存取控制
– 数据加密
– 审计
数据库完整性
5.6 数据库技术的新发展从数据库系统的核心和基础 —— 数据模型角度看，数据库技术已从第一代的网状、层次数据库系统，第二代的关系数据库系统，发展到第三代以面向对象模型为主要特征的数据库系统。 本节将从应用领域角度，简要介绍一下数据仓库、空间数据库和工程数据库技术。
5.6 数据库技术的新发展
5.6.1 数据仓库数据仓库是信息领域中近年来迅速发展起来的新技术 。 数据仓库的建立能充分利用已有的数据资源,把数据转换为信息,
从中挖掘出知识,提炼成智慧,最终创造出效益 。 越来越多的企业开始认识到数据仓库应用所带来的好处 。
5.6 数据库技术的新发展
5.6.2 空间数据库（ Spatial Data Base)
空间数据是用于表示空间物体的位置、形状、
大小和分布特征等信息的数据，它的特点是不仅包括物体本身的空间位置及状态信息，还包括表示物体的空间关系信息。空间数据库系统是描述、
存储和处理空间数据及其属性数据的系统。它是随地理信息系统（ GIS） 的开发和应用而发展起来的。
5.6 数据库技术的新发展
5.6.3 工程数据库工程数据库是一种能存储和管理各种工程设计图形和文档，并为工程设计提供服务的数据库。传统的数据库能有效地存储规范数据，并进行事务处理，而在 CAD∕CAM,
CIM,CASE等计算机辅助工程应用领域，对结构复杂的工程以及工程领域中各种,非经典,应用，传统数据库则无能为力。
小结本章介绍了信息数据的结构、组织和管理。数据的结构是基础、是核心，它来源于现实世界，是客观存在的，基本的数据结构有集合、线性结构、树型结构和图。
数据管理是目的，而数据组织是手段，它要以数据的逻辑结构为基础。本章的两大部分内容是：数据结构和数据库。
计算机并非天生具备这些功能，它们都是程序员赋予的，那么程序员又是如何具备这一超凡的能力？这就是本章所要学习的。 本章首先学习现实生活中的各种信息数据之间存在怎样的内在联系，如何在计算机中体现这一联系，从而使计算机能够进行信息处理。
其次，学习在面对大量信息数据时，如何提高人们的工作效率，即数据库技术。
5.1 为什么要进行数据组织？
数据组织的两层目的,一是能够解决问题,二是方便地解决问题 。
5.2 数据结构
5.2.1 数据结构要解决什么问题数据结构应该包含两层含义，即数据的逻辑结构和物理结构。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，
即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率
5.2 数据结构
5.2.2 线性表线性表是最简单,最常用的一种数据结构,它的逻辑结构是几个数据元素的有限序列 （ a1,a2,…,a n） 。 线性表的组成实际上包括两个要素,一是数据本身
―― 数据元素,它由若干个数据项组成；
二是数据元素间的联系 —— 元素间的前驱与后继关系 。 因此,解决线性表的存储问题就是要解决数据元素的存储以及元素间联系的存储 。
5.2 数据结构
5.2.3 树形结构（层次结构）
树是 n (n≥0) 个结点的有限集合，当其非空（ n>0） 时，有且只有一个特定的结点称为根，当 n>1时，其余结点可分为 m(m>0)
个互不相交的有限集合 T1… Tm,每一个集合又是一棵树，称为这个根的子树。特殊地，
若限定树的子树最多只能有两棵，且区分为左、右子树，它就成了另一种树型结构 ――
二叉树 。树与二叉树之间有个自然的一一对应关系，每一棵树都能惟一地转换到它所对应的二叉树。
5.2 数据结构
5.2.4 图
逻辑结构图是一种比线性表和树形结构更为复杂的数据结构 。 在线性表中,每个结点只有一个直接前驱和后继；在树形结构中,有明显的层次关系,每一层中的元素只和上一层中的一个元素 （ 即双亲 ）
相关 。 而在图中,任意两个元素中均有可能相关 。
5.2 数据结构
存储结构图的结构复杂，存储表示方法也多种多样，但一般的存储表示法都由明显的两部分组成，一是存储顶点信息（ G）,一般用顶点数组表示（人为给顶点加上编号）；
二是存储边的信息（ E）,当然要与相应的结点联系在一起。常用的存储表示方法有数组、邻接表、十字链表等 。数组表示法用两个数组分别存储数据元素（顶点）的信息相邻矩阵 —— 顶点数组和数据元素之间关系（边或弧）的信息。
5.2 数据结构
图的基本操作 —— 遍历和树的遍历类似,图的遍历也是从图中某一顶点出发,系统地访问图中所有顶点,且使每一个顶点恰被访问一次 。 通常有两种遍历方法：深度优先遍历和广度优先遍历 。
应该注意的是,图的遍历得到的次序不仅取决于所采用的方法,还取决于从哪个顶点以及它具体的存储结构 。
5.3 关系数据库
5.3.1 数据处理技术的发展随着计算机技术的发展，在 20世纪 50年代后期至 60年代中期，计算机的外存已有磁盘、
磁鼓等直接存取的存储设备；软件方面也有了专门管理数据的软件 —— 文件系统，它是操作系统的一部分。数据管理技术的这一发展阶段被称为文件系统阶段。在这一阶段，随着数据管理规模的扩大，数据量急剧增加，文件系统也显露出了 3个缺陷：数据冗余,数据不一致,数据联系弱 。
5.3 关系数据库
5.3.2 要会使用数据库，我们应掌握些什么首先，一个特定的数据库管理系统是以一种特定的方式来组织、描述和储存数据的，这种对数据的组织、描述和存储方式，就称为数据模型。
第二,DBMS是一个专门的数据管理软件，它负责数据的物理存储过程和各种操作的具体实现。第三，面对一个复杂的应用环境，我们还应该知道如何去设计好一个数据库 —— 数据库设计理论 。
最后，作为一个专门管理数据的软件，它不应该太脆弱，应具有一定的强壮性 。
5.3 关系数据库
5.3.3 数据模型模型是对现实世界的抽象。 数据模型 就是一组严格定义的概念工具，和地图中的图例符号一样，我们用这组概念工具，把现实世界中我们所关心的那部分内容 —— 数据及其联系描述出来。
数据模型的种类很多 。 目前广泛使用的可分为两种类型：
一种是独立于任何计算机系统的模型，不涉及信息在计算机系统中的表示，只是用于描述某个特定组织所关心的信息结构，这类模型称为,概念数据模型,。另一种是直接面向数据库管理系统的逻辑数据结构，例如：
层次、网状、关系模型等，这一类模型也称为,基本数据模型,或,结构数据模型,。
数据和联系的描述在数据处理中,将涉及不同的描述领域 。
从事物的客观存在,到计算机里的具体表示,
实际上经历了 3个数据领域 —— 现实世界,
信息世界和机器世界 。
实体联系模型 （ E-R模型 ）
实体联系模型是 P,P,S,Chen于 1976年提出的,它是一组对信息世界建模的概念工具 。
这个模型是直接从现实世界中抽象出实体类型及实体间联系,然后用 E-R图表示数据模型 。
E-R图提供了表示实体型,属性和联系的方法 。
关系模型在关系数据模型中,用二维表格结构来表示实体和实体间的联系 。
5.3.4 关系数据库标准语言 —— SQL
5,4 数据库设计数据库设计是指对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能有效地存储数据，满足各种用户的应用要求。大型数据库的设计和开发是一项庞大的工程，其开发周期长、耗资多，失败的风险也大。实践表明，数据库设计是一项软件工程，开发过程必须遵循软件工程的一般原理和方法。
5,4 数据库设计
5.4.1 数据库设计的全过程需求分析阶段 （本阶段的工作成果是,需求说明书,,它由两部分组成，一是分层的数据流图，二是数据字典。）
概念结构设计 （将需求分析阶段得到的用户需求抽象为概念模型（ E-R图）的过程就是概念结构设计。它是整个数据库设计的关键。）
逻辑结构设计 （逻辑结构设计的任务是把概念结构转换成 DBMS所支持的数据模型，即网状、
层次或关系模型。它包括把基本 E-R图转化成概念模式，把分 E-R图转换成外模式。 ）
5,4 数据库设计物理结构设计 （ 数据库在物理设备上的存储结构与存取方法称为数据库的物理结构。为一个给定的逻辑数据模型选取一个最适合应用要求的物理结构的过程，就是数据库的物理设计。）
5.4.2 关系数据库的模式设计理论我们在设计数据库逻辑结构时知道：把 E-R
图转化为数据库模式时，可能存在多种组合，
必须从中选择一个合适的、性能好的作为数据库模式。
5,4 数据库设计
不良关系模式的存储异常问题
插入异常
数据冗余
修改复杂
删除异常
属性间的函数依赖关系
5.5 数据库的保护
数据库保护是指在系统运行过程中，防止数据意外丢失、产生不一致数据或者遭到恶意破坏等情况。主要有三个方面：
一是与事务有关的数据库恢复和并发控制。二是防止不合法使用造成数据泄露、
更改或破坏等数据库安全性控制。三是防止产生不符合语义数据的完整性控制。
数据库恢复
– 事务内部故障
– 系统故障
– 介质故障
并发控制
– 排它锁 （ X）
– 共享锁（ S锁）
数据库的安全性
– 用户标识与鉴别
– 存取控制
– 数据加密
– 审计
数据库完整性
5.6 数据库技术的新发展从数据库系统的核心和基础 —— 数据模型角度看，数据库技术已从第一代的网状、层次数据库系统，第二代的关系数据库系统，发展到第三代以面向对象模型为主要特征的数据库系统。 本节将从应用领域角度，简要介绍一下数据仓库、空间数据库和工程数据库技术。
5.6 数据库技术的新发展
5.6.1 数据仓库数据仓库是信息领域中近年来迅速发展起来的新技术 。 数据仓库的建立能充分利用已有的数据资源,把数据转换为信息,
从中挖掘出知识,提炼成智慧,最终创造出效益 。 越来越多的企业开始认识到数据仓库应用所带来的好处 。
5.6 数据库技术的新发展
5.6.2 空间数据库（ Spatial Data Base)
空间数据是用于表示空间物体的位置、形状、
大小和分布特征等信息的数据，它的特点是不仅包括物体本身的空间位置及状态信息，还包括表示物体的空间关系信息。空间数据库系统是描述、
存储和处理空间数据及其属性数据的系统。它是随地理信息系统（ GIS） 的开发和应用而发展起来的。
5.6 数据库技术的新发展
5.6.3 工程数据库工程数据库是一种能存储和管理各种工程设计图形和文档，并为工程设计提供服务的数据库。传统的数据库能有效地存储规范数据，并进行事务处理，而在 CAD∕CAM,
CIM,CASE等计算机辅助工程应用领域，对结构复杂的工程以及工程领域中各种,非经典,应用，传统数据库则无能为力。
小结本章介绍了信息数据的结构、组织和管理。数据的结构是基础、是核心，它来源于现实世界，是客观存在的，基本的数据结构有集合、线性结构、树型结构和图。
数据管理是目的，而数据组织是手段，它要以数据的逻辑结构为基础。本章的两大部分内容是：数据结构和数据库。
