第4章 数据组织及数据处理

1、第4章 数据组织及数据处理n本章要点n在计算机中以何种组织形式合理存储数据n怎样快速实现数据存取、管理等操作n研究和管理数据的三个有效工具是数据结构、数据库和数据仓库。 n基本概念n内存储器中数据元素之间的关系称为数据结数据结构构。n数据库数据库是存于外存储器中通用化的相关数据集合，它不仅包括数据本身，而且包括相关数据之间的联系。n数据仓库数据仓库是面向主题的、集成的、稳定的、随时间变化的数据集合，用以支持经营管理中的决策制定过程。 n小故事 1n还记得在新千年到来之前的“千年虫”问题吗？当2000年新年钟声即将敲响，亿万人们在企盼新的千年会给他们带来好运的时刻，有些人却高兴不起来。因为“千年

2、虫”可能给他的事业带来难以预料的损失。 n小故事 2n“啤酒”和“尿布”的故事n年轻的爸爸在购买尿布之余，总是忘不了给自己捎带上几罐啤酒。百货公司将原本放在两处的啤酒和尿布集中到了一起摆放，还提供包括啤酒和尿布在内的日用杂货周末送货上门服务，结果销售额大增。启示n类似以上的故事情况早有发生，启发我们：n数据在内存中占有一定的空间；n许多数据之间是孤立、离散的，但也有许多数据之间具有明显的一定关系，需要管理；n还有许多数据具有隐藏在深处的关系，需要挖掘。 n研究数据的三个工具：n程序设计人员要熟悉数据结构，n软件应用人员利用数据库可以动态管理数据，n高层管理人员利用数据仓库可以获得决策支持。4.

3、1 基本数据结构n计算机处理的数据都是二进制的代码，大致上可分成是有大小之分的数值和仅代表某种意义的符号。这些数据在被处理之前要先放到内存储器的数据区中。用什么样的方法放置这些数据呢？这是数据结构学科主要研究的问题。对于计算机专业的学生而言，掌握数据结构的理论和方法是必须具备的基本功。 4.1.1 基本概念n1 数据类型数据类型n在一种程序设计语言中，变量所具有的数据种类称为数据类型。n例如，在 c 语言中n基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型n构造类型：数组、结构、联合、指针、枚举型、自定构造类型：数组、结构、联合、指针、枚举型、自定义义2 数据对象数据对象n某种数据

4、类型元素的集合。n例如，整数的数据对象是-3 ，-2 ，-1 ， 0 ， 1 ， 2 ， 3 ，n英文字符类型的数据对象是， b ， c ， d ， e ， f ，3 数据结构n数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 n数据之间的相互关系称为逻辑结构通常分为四类基本结构：。n一、集合结构集合结构 数据元素除了同属于一种类型外，别无其它关系。n二、线性结构线性结构 数据元素之间存在一对一的关系。n三、树型结构树型结构 结构中的数据元素之间存在一对多的关系。n四、图状结构或网状结构结构图状

5、结构或网状结构结构 数据元素之间存在多对多的关系。 数据结构的形式定义为：数据结构是一个二元组： 数据数据-结构结构=(d ， s)其中： d 是数据元素的有限集， s 是 d 上关系的有限集。例 履历表的数据结构定义如下： s=(c ， r)其中： c 是含若干个项目，例如年龄、职业、填表日期等的集合 c1 ， c2，cn ，r=p ， p 是定义在集合上的一种关系，例如，年龄与出生年月日有关。数据结构不同于数据类型，也不同于数据对象，数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。数

6、据对象各元素之间的相互关系。4 数据结构表示方法数据结构表示方法n顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。n链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。5 数据结构数据结构算法算法n算法：是对特定问题求解步骤的一种描述。算法：是对特定问题求解步骤的一种描述。n例如，查找中使用的二分法。n算法是指令的有限序列，其中每一条指令表示一个或多个操作。n例如，两个变量交换数据：nswap a ， b4.1.2 线性表n1 线性表的逻辑结构线性表的逻辑结构n线性表 (线的目录) ：由 n(n 0) 个数据元素 (结点) a

7、1 ， a2 ，组成的有限序列其中数据元素的个数 n 定义为表的长度。当 n=0 时称为空表，常常将非空的线性表 (n0) 记作：。n (a1 ， a2 ，an)n这里的数据元素 ai(1 i n) 只是一个抽象的符号，其具体含义在不同的情况下可以不同， a i 中可能存有字符或数字。举例n例 1 26 个英文字母组成的字母表n （a， b ， c ，,z ）n例 2 某校从 1981 年到 1986 年各种型号的计算机拥有量的变化情况。n （ 1 ， 17 ， 28 ， 50 ， 92 ， 188 ）例 3 学生健康情况登记表,每一行或列都是线性表姓名学 号性别年龄 健康情况王小林79063

8、1 男 18 健康陈红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 . . 2 线性表的逻辑特征在非空的线性表，有且仅有一个开始结点 a1 ，它没有直接前趋（向左），而仅有一个直接后继（向右） a2 ；有且仅有一个终端结点，该结点没有直接后继，而仅有一个直接前趋 a n-1 ；其余的内部结点 ai(2 i n-1) 都有且仅有一个直接前趋 a i-1 和一个直接后继 a i+1 。 线性表是一种典型的线性结构。线性表是一种典型的线性结构。3 线性表算法n例，已知线性表 la 和线性表中的数据元素按值非递减有序排列，现要求将 la 和归并为

9、一个新的线性表 lc ，且 lc 中的元素仍按值非递减有序排列。n下面用高级计算机语言（类似 c 语言）表示算法。n例如： la=1,3,5 lb=2,4,6n要求 lc=1,2,3,4,5,6n（详见p73-74）4.1.3 线性链表n 链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的因此，链表中结链表中结点的逻辑次序和物理次序不一定相同。点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针 (point

10、) 或链 (link) 。结点值结点值( (数据数据) )和指针组成了链表中的结点结构。和指针组成了链表中的结点结构。其中：data是数据域，用来存放结点的值，point是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表。 显然，单链表中每个结点的存储地址是存放在其前趋结点下个域中，而开始结点无前趋，故应设头指针head 指向开始结点,同时，由于终端结点无后继，故终端结点的指针域为空，即null。 datapoint4.1.4 4.1.4 循环链表循环链表循环链表是一种头尾相接的链表其特点是无须增加存储量，仅对表的链接方式

11、稍作改变，即可使得表处理更加方便灵活。最简单的是单循环链表。单循环链表。 在单链表中，将终端结点的指针域改为指在单链表中，将终端结点的指针域改为指向表头结点的或开始结点，就得到了单链向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如链表仅有一个自成循环的头结点表示。如下图所示：下图所示： 在用头指针表示的单链表中，找开始结点 a1 的时间是 time(1)

12、 ，然而要找到终端结点，则需从头指针开始遍历整个链表，其时间是 time(n)4.1.5 栈 栈 (stack) 是限制在表的一端进行插入和删除运算的线性表，通常称插入,删除的这一端为栈顶 (顶端) ，另一端为栈底 (底部) 当表中没有元素时称为空栈。 假设栈 s=(a1 ， a2 ， a3 ，)，则 a1 称为栈底元素，为栈顶元素栈中元素按 a1 ， a2 ， a3 ，的次序进栈，退栈的第一个元素应为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（ lifo ）。例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下： a n a n-1 a2 a1栈顶 栈底1 顺序栈 由于

13、栈是一种运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表,因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top表示顶。2 链栈 栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。4.1.6 队列 队列 (queue) 也是一种运算受限的线性表它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称

14、为队头 (front) ，允许插入的一端称为队尾 (rear) 。例如：排队购物时的队列操作系统中的作业排队。由于先进入队列的成员总是先离开队列，因此队列亦称作先进先出 (first in first out) 的线性表，简称 fifo 表。1 顺序队列顺序队列当队列中没有元素时称为空队列，在空队列中依次加入元素 a1 ， a2,之后， a1 是队头元素，a2是队尾元素。显然退出队列的次序也只能是 a1 ， a2,，也就是说队列的修改是依“先进先出”的原则进行的。n由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置。 2 循环队列n将向量空间想象为一个首

15、尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（circular queue)在循环队列中进行出队,入队操作时，头尾指针仍要加 1 ，朝前移动。只不过当头尾指针指向向量上界（ queuesize-1 ）时，其加 1 操作的结果是指向向量的下界 0 。4.1.7 4.1.7 串串串串 ( (string) ) 是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。一般记作s=a1a2a3an，其中s是串名，双引号括起来的字符序列是串值；ai(1 i n) 可以是字母,数码或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称长度为零的串称为空串为空串 (em

16、pty string) ，它不包含任何字符。 由一个或多个空格组成的串称为空白串由一个或多个空格组成的串称为空白串 (blank string)。例如“ ”和“”分别表示长度为 1 的空白串和长度为 0 的空串。程序中串只能被引用但不能不能改变其值，即只能读不能修改。程序中串只能被引用但不能不能改变其值，即只能读不能修改。串的基本操作包括：n1 串复制 (copy) 将串 s1 复制到串 s2 中。n2 联接 (concatenation) 将串 s1 复制到串 s2 的末尾。n3 串比较(compare) 比较串 s1 和串 s2 的大小。n4 字符定位 (index) 找某字符 c 在字符

17、串中第一次出现的位置。4.1.8 数组多维数组是向量的推广。多维数组是向量的推广。例如，二维数组：。 a11 a12 a1n a21 a22 a2n am1 am2 amn可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。 1 1 行优先顺序行优先顺序将数组元素按行排列，第 i+1 个行向量紧接在第 i 个行向量后面以二维数组为例，一个 m*n 个元素数组,按行优先顺序存储的线性序列为： a11 ， a12 ， a1n ， a21 ， a22 ， a2n ， am1 ， am2 ，, amn。 在 pascal,c 语言中，数组就是按行优先顺序存储的。2 2 列优先顺序列优先

18、顺序将数组元素按列向量排列，第 j+1 个列向量紧接在第 j 个列向量之后，一个 m*n 个元素数组,按列优先顺序存储的线性序列为：a11 ， a21 ， am1 ， a12 ， a22 ， am2 ， an1 ， an2 ，,anm在fortran语言中，数组就是按列优先顺序存储的。4.1.9 树和二叉树 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。 树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织

19、信息；在分析算法的行为时，可用树来描述其执行过程等等。1 树 树 (tree) 是 n(n=0) 个结点的有限集合，记为 t ， t 为空时称为空树，否则t应满足如下两个条件：（ 1 ）有且仅有一个特定的称为根 (root) 的结点；（ 2 ）其余的结点可分为 m(m=0) 个互不相交的子集 t1，t2，t3 tm ，其中每个子集又是一棵树，并称其为子树 (sub tree) 。2 二叉树n 二叉树是由 n(n=0) 个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分

20、，说明它是左子树，还是右子树,这是二叉树与树的最主要的差别。 下图列出二叉树的 5 种基本形态，图 (c) 和图（ d ）是不同的两棵二叉树。 (a)空二叉树aababacb (b)根和空的左右子树 (c)根和左子树(d)根和右子树 (e)根和左右子树 二叉树的 5 种形式4.1.10 文件n文件是存于磁盘上的数据的集合，它不是传统意义上内存中的数据存储格式。 n记录：以若干字节组成的一组数据。n1 顺序文件是按存储的先后顺序，连续存于磁盘上的记录的集合。逻辑上顺序文件的记录是连续存储的。n2 随机文件是以标号标记每个记录，以随序号顺序存于磁盘上的记录的集合。逻辑上随机文件的记录是不连续存储的

21、。4.2 数据库n 数据库技术产生于 60 年代末， 70 年代初期，其主要目的是为了在计算机应用中，有效地管理和存取大量的数据资源。目前数据处理和以数据处理为基础的信息系统在计算机应用领域中所占的比重最大。 n 本节中，数据是指存储在某一媒体上可加以数据是指存储在某一媒体上可加以鉴别的符号资料鉴别的符号资料。n 数据的概念包括两个方面，其一，数据内容是事物特性的反映或描述；其二，数据是存储在某一媒体上符号的集合。这里的符号，不仅指数字、字母、文字和其它特殊字符，而且还包括图形、图像、动画、影像、声音等多媒体数据。存储不仅是在纸上，包括记录在磁介质、光介质上、半导体存储器等介质上。 n 数据处

22、理（包括管理）是指将数据转换成信息的过程。广义地讲，处理包括对数据的收集、存储、加工、分类、检索、传播等一系列活动。狭义地讲，处理是指对所输入的数据进行加工处理。可用以下式子简单表示：n 信息数据处理信息数据处理4.2.1 计算机数据管理n计算机数据管理大致经历了如下四个阶段：n1 人工管理阶段人工管理阶段。数据与程序不具有独立性；数据不长期保存；系统中没有对数据进行管理的软件。n2 文件系统阶段文件系统阶段。程序与数据有了一定的独立性，程序和数据分开存储，有了程序文件和数据文件的区别数据文件可以长期保存。但数据冗余度大；缺乏数据独立性；数据无集中管理。 n3 数据库系统阶段数据库系统阶段。避

23、免了以上两阶段的缺点，实现数据共享，减少数据冗余；采用特定的数据模型；具有较高的数据独立性；有统一的数据控制功能。n4 分布式数据库系统阶段分布式数据库系统阶段。分布式数据库是一个逻辑上统一、地域上分布的数据集合，是计算机网络环境中各个结点局部数据库的逻辑集合。由于分布式数据库管理系统具有分布、透明、局部自治与集中控制相结合的特点，它的可靠性、可用性；灵活性更好，管理效率更高。 n 80 年代，随着多媒体计算机技术的兴起，超文本也很快发展起来了超文本（hyper text）是一种非线性的网状结构。超文本机制实质上是一种典型的数据库技术，它是结点，链,网三个要素的组合，提供一种沿着链访问数据的方

24、法。windows中的帮助文件就是一个很好的超文本示例。 4.2.2 数据库系统n 数据库系统是指引进数据库技术后的计算机系统。这类系统由五部分组成：硬件系统，数据库集合，数据库管理系统（ dbms database management system）及相关软件,数据库管理员（ dba database administrator）和用户。1 dbms 功能：n(1)数据库的定义功能提供数据定义语言 ddl （数据描述语言）或操作命令以便对各级数据模式进行具体的描述。如 foxpro 中用create或 modi stru 命令进行定义和修改库结构。n(2)数据操纵功能提供数据操纵语言 dm

25、l （data manipulation language）对数据库中的数据进行追加，插入，修改，删除,检索等操作。 n(3)数据库运行控制功能包括数据的完整性控制、数据库的并发操作控制、数据的安全性控制、数据库的恢复。n(4)数据字典数据字典 dd （data dictionary）中存放着对实际数据库各级模式所作的定义，即对数据库结构的描述这些数据是数据库系统中有关数据的数据，称为元数据（ metadata ）。2. 数据关系模型数据关系模型n 在数据库中所存储的数据之间一般都有一定的关系。例如在人才库中，性别、年龄等数据都依赖于姓名，离开了具体的姓名，这些数据毫无意义。n(1) 关系的逻

26、辑结构n一个关系的逻辑结构是一张二维表，关系在磁盘上以文件形式存储，每个字段（属性）是表中的一列，每个记录是表中的一行。这种用二维表的形式来表示实体和实体之间联系的数据模型称为关系数据模型。 n每个字段（属性）是表中的一列，每个记录是表中的一行。这种用二维表的形式来表示实体和实体之间联系的数据模型称为关系数据模型。(2) 第三范式表n第三范式表是属性不可再分的二维表。 n如果一个关系中其他的属性都依赖于某个属性而存在，该属性就是主关键字。例如上表中的姓名属性，其他项都与它有惟一的依赖关系，它是主关键字。如果一个关系中的属性或属性组并非该关系的关键字，但它们是另外一个关系的关键字，则称为该关系的

27、外关键字（公共关键字）。例如，上表的地址属性是外关键字，它可能是房屋管理部门的某一张房产管理表的一个属性。 范式与非范式表n 姓名出生年性别住址张三1982男1-101李四1981男1-102姓名年龄性别住址出生年张三20男 1-101 1982李四21男 1-102 1981(3) 关系运算n关系运算包括，集合运算的“并”、“差”、“交”运算和专门的 “选择”、“投影”、“联接” 等关系运算。n注意，非第三范式的第一、第二范式表的关系运算由于目前没有严格的数学证明，运算结果的正确与否要靠实践检验。a、b的关系运算 3. 数据库设计数据库设计n建立一个完整的数据库需要完成以下几步工作。n(1)

28、 数据库设计数据库设计n1）需求分析需求分析 通过大量访问、调查用户和潜在用户后，形成文档资料。资料至少包括，各项业务的数据流图（data flow diagram，dfd）及有关说明和对各类数据描述的集合，即数据字典（dd）。n2）收集资料收集资料 收集资料工作是数据库设计人员和用户共同完成的任务。强调各级用户的参与。 n3）分析整理分析整理 分析的过程是对所收集到的数据进行抽象的过程。n4）画数据流图画数据流图 在系统分析中通常采用dfd来描述系统的数据流向和对数据的处理功能。 n5）建立数据字典建立数据字典（dd， data dictionary ） 除了一套dfd外，还要从原始的数据资

29、料中分析整理出下述数据信息：数据元素的名称、同义词、性质、取值范围、提供者、使用者、控制权限、保密要求、使用频率、数据量、数据之间联系的语义说明、各个部门对数据的要求及数据处理要求等。并把这些资料用非专业术语与用户交流。 n数据字典可以看作是数据库系统自身的小数据库，它是元数据。数据字典有两方面的作用：有利于数据库管理员掌握整个系统结构和系统运行情况。方便用户使用系统。ndd 经历了人工字典，计算机文件,专用数据字典系统和数据库管理系统与数据字典一体化四个发展阶段，支持数据字典功能的数据库管理系统能够自动建立和更新数据字典。例如oracle （甲骨文）的数据字典就是数据库管理系统的一部分，系统

30、自动建立并更新一组数据字典表。(2) 概念结构设计n1) 实体关系模型 (entity relationship model，e-r) e-r模型简称e-r图。它是描述概念，建立概念模型的使用工具。图中用矩形表示实体，用菱形表示实体之间的联系，用椭圆表示属性，用直线表示各部分的联系。确定实体和属性，确定关系类型，画出各局部 e-r 图。n下图所示为学校信息管理系统的学籍管理局部e-r图。 局部e-r图 n2)局部 e-r 图的合并n3)消除冲突 消除可能具有的属性冲突、命名冲突和结构冲突。n4)导出初始关系模式n5)规范化处理 4. 数据库实施数据库实施n(1) 原始数据输入n由于数据库的数据

31、量很大，一般是通过系统提供的实用程序或自编的专门录入程序输入原始数据。输入数据之前应当建立严格的数据录入和检验规范，设计完善的数据检验与校正程序，确实保证数据的质量。n(2) 数据库运行和维护4.2.3 数据查询语言 sqln sql 是结构化查询语言（structured query language）的缩写，产生于 70 年代中期，由 boyce 和 chambwelin 提出。该语言类似程序设计高级语言，不依赖于某特定的计算机数据库系统，通用性较强。它包括查询、定义、操纵和控制四个部分，是一种功能齐全的数据库语言。n 数据定义是指对关系模式一级的定义。数据操纵是指对关系中的具体数据进行增

32、、删、改和更新等操作。数据控制是指对数据访问权限的授予或撤消。n1 sql 数据库的体系结构nsql 支持关系数据库的三级模式结构，在 sql 中，有些术语与传统的关系数据库不同，关系模式称为 基本表 ，存储模式称为 存储文件 ，子模式称为 视图 ，元组称为 行 ，属性称为 列 。n(1)基本表（基本表（base table） 本身独立存在的表，即实际存储在数据库中的表，而不是从其它表导出来的表，它可有若干个索引。基本表的集合组成关系模型，即全局概念模式（数据的整体逻辑结构）。基本表也可以由某种数据库管理系统生成。 sql 可兼容许多格式的表格。 n(2)视图（视图（view）：从一个或几个基

33、本表或其它视图导出来的表。视图本身并不独立存储数据，系统只是保存视图的结构。访问视图时，系统将按照视图的定义从基本表中存取数据。由此可见，视图是个虚表。视图可以看作用户按照应用需要定义的外模式，即用户的局部数据逻辑结构。nnsql 数据定义功能是指定义数据库的结构，包括数据定义功能是指定义数据库的结构，包括定义基本表，定义视图，定义索引三个部分。定义基本表，定义视图，定义索引三个部分。2 sql 查询n基本查询模块的结构是：nselect, ，,nfrom， ，,nwhere ；n例如，找出姓李的读者全部情况。n select *；（* 是用于表示全部字段的通配符）n from 读者n whe

34、re 姓名 “ 李”；3 sql 数据控制n数据控制是指通过对数据库各种权限的授予或回收来管理数据库系统这些权限，包括对基本表的修改（alter），插入（insert），删除（delete），更新（update）,建立索引（index）,查询（select）和用户所拥有的权限（all）。4.2.4 实用数据库管理系统介绍n1 windows excel 表处理软件n2 windows access 数据库n参见http:/ foxpron参见http:/ 其他大型数据库n 数据库的广泛应用，推动着数据库技术的发展。各厂商都采用类似的新技术，使产品性能更优、更强，更具有竞争力。大型数据库比xba

35、se一类的小型数据库具有更大的可靠性，正是因为这些重要特点，在高级办公自动化系统中，都是采用大型数据库系统。n 大型数据库方面的主要产品有 sybase，oracle，informix，ingress等。目前在世界市场上流行的是oracle和sybase。4.3 数据仓库与数据挖掘n4.3.1数据仓库n随着市场竞争的加剧和信息社会需求的发展，从大量数据中提取(检索、查询等) 制定市场策略的信息就显得越来越重要了。这种需求既要求联机服务，又涉及大量用于决策的数据，而传统的数据库系统已无法满足这种需求。其具体体现在两个方面：n历史数据量很大，数据库难于管理； n辅助决策信息涉及许多部门的数据，而不

36、同系统的数据难以集成。 n 随着客户机/服务器机制（c/s，client/service）技术的成熟和并行数据库的发展，信息处理技术的发展趋势是从大量的事务型数据库中抽取数据，并将其清理、转换为新的存储格式，即为决策目标把数据聚合在一种特殊的格式中。随着此过程的发展和完善，这种支持决策的、特殊的数据存储即被称为数据仓库(dw ，data warehouse)。 n业界公认的数据仓库概念创始人w.h.inmon在建立数据仓库（building the data warehouse ）一书中对数据仓库的定义是：数据仓库是一个面向主题的数据仓库是一个面向主题的(subject-oriented)、稳

37、定的、稳定的(non-volatile)、与时间相、与时间相关的关的(time-variant)、集成的、集成的(integrated)、能够更好地支持企业或组织的决策分析处理的环能够更好地支持企业或组织的决策分析处理的环境。境。数据集市是基于部门级的、面向单一主题领域的数据仓库子集。n下面解释定义的含义： n面向主题：面向主题：n“主题”在数据仓库中是由一系列表（格）实现的。数据仓库依然是基于关系数据库。一个主题之下包含许多表，表的划分可能是由于对数据的综合程度不同，也可能是由于数据所属的时间段不同而进行的划分。基于一个主题的所有表都含有一个称为公共键的属性作为其主键的一部分。公共键将各个表

38、统一联系起来，从根本上体现出它们属于一个主题。比如，基于客户这一主题的所有表都包含公共键 customer id。同时，由于数据仓库中的数据都是同某一时刻联系在一起的，所以每个表除了其公共键之外，还必然包括时间成分作为其码键的一部分。因为数据仓库包含的都是历史数据，它的表必然包括对应的时间属性。公共键客户名、时间键交易时间 n数据集成：数据集成：n在数据进入数据仓库之前，必须对原始表中的数据进行加工与集成。这一步实际上是数据仓库建设中最关键、最复杂的一步。首先，要统一原始数据中的所有矛盾之处，如字段的同名异义、异名同义、单位不统一、字长不一致等等，还要将原始数据结构做一个从面向应用到面向主题的

39、迁移。 n稳定的数据仓库：稳定的数据仓库：n由于它反映的是历史数据的内容，而不是处理联机数据。因而，数据经集成进入数据仓库后是极少或根本不更新的。n数据仓库与数据库时间属性的差别数据仓库与数据库时间属性的差别：n它表现在以下几个方面：首先，数据仓库内的数据时限要远远长于操作型环境中的数据时限。前者一般在510年，而后者只有6090天。数据仓库保存数据时限较长是为了适应 dss进行趋势分析的要求。其次，操作型环境包含当前数据，即在存取一刹那是正确、有效的数据；而数据仓库中的数据都是历史数据。数据仓库数据的码键都包含时间项，从而标明了该数据的历史时期。 n数据仓库是在数据库基础上发展而来的，它通常

40、有三个部分：数据仓库（数据储入仓库），联机分析处理 (olap) 及数据挖掘 (data mining) ，它们之间具有极强的互补关系。4.3.2 数据挖掘n高层决策者的问题，现有信息管理系统中的数据分析工具无法给出答案。因为无论是查询、统计还是报表，其处理方式都是对指定的数据进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取。 n 从大量数据中提取出隐藏在其中的有用信息，就是数据挖掘(data mining)技术要解决的问题。n数据挖掘，也可以称为数据库中的知识发现( kdd，knowledge discover database)，它是从大量数据中提取出可信、新颖、有效并能被人理

41、解的模式的高级处理过程。1 数据挖掘过程n1)问题定义：了解相关领域的有关情况，熟悉背景知识，弄清用户要求。n2)数据提取：根据要求从数据库中提取相关的数据。n3)数据预处理：主要对前一阶段产生的数据进行再加工，检查数据的完整性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 n4)数据挖掘：运用选定的知识发现算法，从数据中提取出用户所需要的知识，这些知识可以用一种特定的方式表示或使用一些常用的表示方式。n5)知识评估：将发现的知识以用户能了解的方式呈现，根据需要对知识发现过程中的某些处理阶段进行优化，直到满足要求。2 数据挖掘的成果n1)数据总结：其目的是对数据进行浓缩，给出

42、它的紧凑描述。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。n2)分类：其目的是学会一个分类函数或分类模型(也称作分类器)，该模型能把数据库的数据项映射到给定类别中的某一个。 n3)聚类：是把一组个体按照相似性归类，即物以类聚。它的目的是使属于同一类别的个体之间的距离尽可能地小，而不同类别的个体间的距离尽可能地大。 n4)关联：关联规则是形式如下的一种规则，在购买面包和黄油的顾客中，有90的人同时也买了牛奶(面包+黄油+牛奶)。关联规则发现的思路还可以用于序列模式发现。用户在购买物品时，除了具有上述关联规律，还有时间或序列上的规

43、律。3 数据挖掘工具n 目前较成熟的数据挖掘工具主要有两类：特定领域的数据挖掘工具和通用的数据挖掘工具。 n特定领域的数据挖掘工具针对某个特定领域的问题提供解决方案。在设计算法的时候，充分考虑到数据、需求的特殊性，并作了优化。通用的数据挖掘工具对任何领域，都可以开发。 (1) 特定工具介绍特定工具介绍n1)ibm公司的advancedscout系统针对nba的数据，帮助教练优化战术组合；n2)加州理工学院喷气推进实验室与天文科学家合作开发的skicat系统，帮助天文学家发现遥远的类星体；n3)芬兰赫尔辛基大学计算机科学系开发的tasa，帮助预测网络通信中的警报。(2) 通用工具介绍n1）que

44、st多任务数据挖掘系统nibm公司almaden研究中心开发，目的是为新一代决策支持系统的应用开发提供高效的数据开采基本构件。系统具有如下特点：na)提供了专门在大型数据库上进行各种开采的功能：关联规则发现、序列模式发现、时间序列聚类、决策树分类、递增式主动开采等。nb)各种开采算法具有近似线性（o(n)）计算复杂度，可适用于任意大小的数据库。nc)算法具有找全性，即能将所有满足指定类型的模式全部寻找出来。nd)为各种发现功能设计了相应的并行算法。 n2）mineset多任务数据挖掘系统n由sgi公司和美国standford大学联合开发。集成多种数据挖掘算法和可视化工具，帮助用户直观地、实时地发掘、理解大量数据背后的知识。特点：na)mineset以先进的可视化显示方法闻名于世。n b)支持多种关系数据库。可以直接从oracle、informix、sybase的表读取数据，也可以通过sql命令执行查询。n c)具有多种数据转换功能。在进行挖掘前，可以去除不必要的数据项，统计、集合、分组数据，转换数据类型，构造表达式由已有数据项生成新的数据项，对数据采样等。nd)操作简单、支持国际字符、可以直接发布到web。 n3）dbminer多任务数据挖掘系统n 加拿大simonfraser大学开发，它的前身是dblearn。该系统设计的目的是把关系数据库和数据