资源描述
数据组织技术数据组织技术 数据库技术数据库技术 计算机网络技术和云计算技术计算机网络技术和云计算技术第三章第三章第三章第三章 管理信息系统的技术基础管理信息系统的技术基础管理信息系统的技术基础管理信息系统的技术基础信息技术是管理信息系统的基础，只有把信息技术与管信息技术是管理信息系统的基础，只有把信息技术与管理结合起来，才能真正发挥管理信息系统的作用。理结合起来，才能真正发挥管理信息系统的作用。数据数据组织组织技技术术第三章第三章 管理信息系管理信息系统统的技的技术术基基础础信息技信息技术术是管理是管理什么是数据处理？什么是数据处理？数据处理数据处理数据处理数据处理指把来自科学研究、生产实践和社会经指把来自科学研究、生产实践和社会经指把来自科学研究、生产实践和社会经指把来自科学研究、生产实践和社会经济活动等领域中的原始数据济活动等领域中的原始数据济活动等领域中的原始数据济活动等领域中的原始数据,用一定的设备和手段用一定的设备和手段用一定的设备和手段用一定的设备和手段,按一定的使用要求按一定的使用要求按一定的使用要求按一定的使用要求,加工成另一种形式的数据。加工成另一种形式的数据。加工成另一种形式的数据。加工成另一种形式的数据。把数据转换成便于观察分析、传送或进一步处理的形式。把数据转换成便于观察分析、传送或进一步处理的形式。从大量的原始数据中抽取，推导出对人们有价值的信息以从大量的原始数据中抽取，推导出对人们有价值的信息以作为行动和决策的依据。作为行动和决策的依据。用计算机科学地保存和管理已经过处理的大量数据用计算机科学地保存和管理已经过处理的大量数据,以便以便人们能方便而充分地利用这些宝贵的信息资源。人们能方便而充分地利用这些宝贵的信息资源。课本课本目的：目的：什么是数据什么是数据处处理？理？数据数据处处理指把来自科学研究、生理指把来自科学研究、生产实产实践和践和数据处理的基本内容数据采集数据转换数据的筛选、分组和排序数据的组织数据的运算数据存储数据检索数据输出 数据数据处处理的基本内容数据采集理的基本内容数据采集数据处理的基本内容数据处理的基本内容 数据处理是管理活动最基本的内容，也是数据处理是管理活动最基本的内容，也是管理信息系统的基本功能。管理信息系统的基本功能。数据处理一般不涉及复杂的数学计算数据处理一般不涉及复杂的数学计算,但要但要求处理的数据量很大。因此进行数据处理求处理的数据量很大。因此进行数据处理时需要考虑以下几个方面的问题：时需要考虑以下几个方面的问题：（1 1）数据以何种方式存储在计算机中？）数据以何种方式存储在计算机中？（2 2）采用何种数据结构有利于数据的存储和）采用何种数据结构有利于数据的存储和 取用？取用？（3 3）采用何种方法从已组织好的数据中检索）采用何种方法从已组织好的数据中检索数据？数据？数据数据处处理的基本内容理的基本内容 数据数据处处理是管理活理是管理活动动最基本的内容，也是管最基本的内容，也是管数据的组织数据组织是按照一定的方式和规则对数据进行数据组织是按照一定的方式和规则对数据进行数据组织是按照一定的方式和规则对数据进行数据组织是按照一定的方式和规则对数据进行归并、存储、处理的过程。归并、存储、处理的过程。归并、存储、处理的过程。归并、存储、处理的过程。管理中要处理的数据量很大，在应用计算机时，管理中要处理的数据量很大，在应用计算机时，管理中要处理的数据量很大，在应用计算机时，管理中要处理的数据量很大，在应用计算机时，首先遇到的问题就是如何组织这些数据，使他们首先遇到的问题就是如何组织这些数据，使他们首先遇到的问题就是如何组织这些数据，使他们首先遇到的问题就是如何组织这些数据，使他们便于存储、分类、检索、归并和调用。便于存储、分类、检索、归并和调用。便于存储、分类、检索、归并和调用。便于存储、分类、检索、归并和调用。数据的组织具有不同的形式数据的组织具有不同的形式数据的组织具有不同的形式数据的组织具有不同的形式 ,通常可以用通常可以用通常可以用通常可以用数组数组数组数组、文件文件文件文件及及及及数据库数据库数据库数据库来组织数据。来组织数据。来组织数据。来组织数据。在管理信息系统中，大量数据以一定的形式存在管理信息系统中，大量数据以一定的形式存在管理信息系统中，大量数据以一定的形式存在管理信息系统中，大量数据以一定的形式存放在各种存贮介质中，数据的放在各种存贮介质中，数据的放在各种存贮介质中，数据的放在各种存贮介质中，数据的存储结构存储结构存储结构存储结构及及及及内在联内在联内在联内在联系系系系的表示方式决定着数据处理的效率的表示方式决定着数据处理的效率的表示方式决定着数据处理的效率的表示方式决定着数据处理的效率 。数据的数据的组织组织数据数据组织组织是按照一定的方式和是按照一定的方式和规则对规则对数据数据进进行行归归并、存并、存储储数据结构数据结构数据结构是计算机信息处理中的一个重要概念，包括数据数据结构是计算机信息处理中的一个重要概念，包括数据数据结构是计算机信息处理中的一个重要概念，包括数据数据结构是计算机信息处理中的一个重要概念，包括数据的的的的存储结构存储结构存储结构存储结构及结构上的及结构上的及结构上的及结构上的运算或操作运算或操作运算或操作运算或操作。数据结构又分为数据的数据结构又分为数据的数据结构又分为数据的数据结构又分为数据的逻辑结构逻辑结构逻辑结构逻辑结构和和和和物理结构物理结构物理结构物理结构。数据的逻辑结构是指数据间的逻辑关系，逻辑结构包括两数据的逻辑结构是指数据间的逻辑关系，逻辑结构包括两数据的逻辑结构是指数据间的逻辑关系，逻辑结构包括两数据的逻辑结构是指数据间的逻辑关系，逻辑结构包括两大类：大类：大类：大类：线性结构线性结构线性结构线性结构-线性表、栈、队列及串线性表、栈、队列及串线性表、栈、队列及串线性表、栈、队列及串 非线性结构非线性结构非线性结构非线性结构-树和图树和图树和图树和图物理结构又称存贮结构，指数据元素在计算机存贮器中的物理结构又称存贮结构，指数据元素在计算机存贮器中的物理结构又称存贮结构，指数据元素在计算机存贮器中的物理结构又称存贮结构，指数据元素在计算机存贮器中的存储方式，存储方式一般有四种：存储方式，存储方式一般有四种：存储方式，存储方式一般有四种：存储方式，存储方式一般有四种：顺序存储顺序存储顺序存储顺序存储 链接存储链接存储链接存储链接存储 索引存储索引存储索引存储索引存储 散列存储散列存储散列存储散列存储对于给定的逻辑结构需要寻找一种对应的存储结构，以便对于给定的逻辑结构需要寻找一种对应的存储结构，以便对于给定的逻辑结构需要寻找一种对应的存储结构，以便对于给定的逻辑结构需要寻找一种对应的存储结构，以便在计算机中存储。通常把这种对应关系称为在计算机中存储。通常把这种对应关系称为在计算机中存储。通常把这种对应关系称为在计算机中存储。通常把这种对应关系称为映象映象映象映象。数据数据结结构数据构数据结结构是构是计计算机信息算机信息处处理中的一个重要概念，包括数据的理中的一个重要概念，包括数据的结点、指针与链NO.NO.NAMENAMEAGEAGENEXTNEXT 在数据结构中，表征某一数据结构特点及其连接在数据结构中，表征某一数据结构特点及其连接方式的基本单位称为结构的方式的基本单位称为结构的结点结点(Node)(Node)。一个结点。一个结点通常有几个域，用来存放与结点有关的信息。存放通常有几个域，用来存放与结点有关的信息。存放结点本身信息的域称为结点本身信息的域称为数据域数据域，存放结点与其他结，存放结点与其他结点关系信息的域，称为指针域或链域，其中存放有点关系信息的域，称为指针域或链域，其中存放有与结点有关的结点的地址称为与结点有关的结点的地址称为指针指针。若干带指针的。若干带指针的结点组成的集合，称为结点组成的集合，称为链链。一个结一个结一个结一个结点点点点课本课本结结点、指点、指针针与与链链NO.NAMEAGENEXT 在数据在数据结结构构线性表及顺序存储方式 线性表线性表是指数据的结构形式本质上是一维的线性是指数据的结构形式本质上是一维的线性关系，其中的每个结点都是同一类型的数据结构。关系，其中的每个结点都是同一类型的数据结构。线性表的线性表的结点按逻辑次序依次存放结点按逻辑次序依次存放在一组在一组连续的连续的存贮单元里，用这种方法存储的线性表称为存贮单元里，用这种方法存储的线性表称为顺序表顺序表。对于顺序表，若开始结点的存放位置为对于顺序表，若开始结点的存放位置为LOC(kLOC(k1 1)，每个结点占用空间大小为每个结点占用空间大小为L L，则第，则第i i个结点个结点k ki i的存放位的存放位置可由下式直接计算得到置可由下式直接计算得到LOC(kLOC(ki i)=LOC(k)=LOC(k1 1)+L*(i-1)+L*(i-1)顺序表的存储优点是对于任何一个结点的检索都顺序表的存储优点是对于任何一个结点的检索都很方便。通常由很方便。通常由堆栈堆栈或或队列队列实现。实现。线线性表及性表及顺顺序存序存储储方式方式 线线性表是指数据的性表是指数据的结结构形式本构形式本质质顺序表的插入与删除操作序号序号序号序号 结点内容结点内容结点内容结点内容序号序号序号序号结点内容结点内容结点内容结点内容 1 1 9 9 1 1 9 9 2 2 1515 2 2 1515 3 3 1717 3 3 1717 4 4 2525 4 4 2323 5 5 3939 5 5 2525 6 6 6 6 3939 插入前插入前插入前插入前 插入后插入后插入后插入后序号序号序号序号 结点内容结点内容结点内容结点内容序号序号序号序号结点内容结点内容结点内容结点内容 1 1 9 9 1 1 9 9 2 2 1515 2 2 1515 3 3 1717 3 3 1717 4 4 2323 4 4 2525 5 5 2525 5 5 3939 6 6 3939 6 6 删除前删除前删除前删除前 删除后删除后删除后删除后 要在顺序表中插入一个元素，由于插入后的顺序表仍要在顺序表中插入一个元素，由于插入后的顺序表仍要求有序，必须将插入位置以后的元素依次向后移动一要求有序，必须将插入位置以后的元素依次向后移动一个单元。同样，若要删除元素，则需把后面的元素依次个单元。同样，若要删除元素，则需把后面的元素依次向前移动一个单元。平均数据移动量为向前移动一个单元。平均数据移动量为n/2n/2。顺顺序表的插入与序表的插入与删删除操作序号除操作序号 结结点内容序号点内容序号结结点内容点内容 1 线性表的链式存储方式 以链接方式存储的线性表称为链表。链表结以链接方式存储的线性表称为链表。链表结构在每个结点设有构在每个结点设有链指针链指针，用来指示下一个结点，用来指示下一个结点的位置，的位置，结点结点本身则本身则可以存放在任意一组存贮单可以存放在任意一组存贮单元中元中，这些存贮单元可以是连续的，也可以是分，这些存贮单元可以是连续的，也可以是分散的。结点之间的逻辑关系由指针表示。散的。结点之间的逻辑关系由指针表示。在链表的插入和删除操作中，在链表的插入和删除操作中，只需改变前后结只需改变前后结点的指针点的指针，而不需要进行大量的数据移动。，而不需要进行大量的数据移动。线线性表的性表的链链式存式存储储方式方式 以以链链接方式存接方式存储储的的线线性表称性表称为链为链表。表。单链表headerheader元素元素1 1指针指针元素元素2 2指针指针元素元素3 3指针指针元素元素4 4指针指针 在每个节点上有一个指针项，指向该节点的后继在每个节点上有一个指针项，指向该节点的后继节点，节点，如果节点无后继，则指针项的值为空如果节点无后继，则指针项的值为空。每个。每个链表存在一个链表首指针链表存在一个链表首指针，指向链表的第一个元素。，指向链表的第一个元素。对单链表而言主要的操作有插入、删除和查找元对单链表而言主要的操作有插入、删除和查找元素。素。单链单链表表header元素元素1指指针针元素元素2指指针针元素元素3指指针针元素元素4指指针针 headerheader元素元素1 1指针指针元素元素2 2指针指针元素元素3 3指针指针元素元素4 4 NullNullP Pheaderheader元素元素1 1指针指针元素元素2 2指针指针元素元素3 3指针指针元素元素4 4 NullNullP P元素元素X XQ Q单链表的插入操作算法Step1.Step1.Step1.Step1.找到插入点找到插入点找到插入点找到插入点（假设在插入点后增加一个节点）（假设在插入点后增加一个节点）（假设在插入点后增加一个节点）（假设在插入点后增加一个节点）Step2.Step2.Step2.Step2.得到新节点，并赋值得到新节点，并赋值得到新节点，并赋值得到新节点，并赋值header元素元素1指指针针元素元素2指指针针元素元素3指指针针元素元素4NullPhheaderheader元素元素1 1指针指针元素元素2 2指针指针元素元素3 3指针指针元素元素4 4 NullNullP P元素元素X X指针指针Q Qheaderheader元素元素1 1指针指针元素元素2 2指针指针元素元素3 3指针指针元素元素4 4 NullNullP P元素元素X X指针指针Q QStep3.Step3.Step3.Step3.修改指针项修改指针项修改指针项修改指针项Q-Q-Q-Q-指针指针指针指针 :=P-:=P-:=P-:=P-指针指针指针指针P-P-P-P-指针指针指针指针:=Q:=Q:=Q:=Qheader元素元素1指指针针元素元素2指指针针元素元素3指指针针元素元素4NullP元元headerheader元素元素1 1指针指针元素元素2 2指针指针元素元素3 3指针指针元素元素4 4 NullNullP Pheaderheader元素元素1 1指针指针元素元素2 2指针指针元素元素3 3指针指针元素元素4 4 NullNullP P单链表的删除操作算法Step1.Step1.Step1.Step1.找到删除点找到删除点找到删除点找到删除点（假设在删除点删除一个节点）（假设在删除点删除一个节点）（假设在删除点删除一个节点）（假设在删除点删除一个节点）Step2.Step2.Step2.Step2.修改指针项修改指针项修改指针项修改指针项P-P-P-P-指针指针指针指针:=P-:=P-:=P-:=P-指针指针指针指针-指针指针指针指针header元素元素1指指针针元素元素2指指针针元素元素3指指针针元素元素4NullPh双向链表元素元素1 1 rlinkrlinkllinkllinkheaderheader元素元素2 2 rlinkrlinkllinkllink元素元素3 3 rlinkrlinkllinkllink元素元素4 4 rlinkrlinkllinkllink元素元素5 5 rlinkrlinkllinkllink 在每个节点上在每个节点上有两个指针项有两个指针项，一个指向该节点的，一个指向该节点的后继节点后继节点，另一个指向该节点的，另一个指向该节点的前驱节点前驱节点 。每个链。每个链表存在一个链表首指针，指向链表的第一个元素。对表存在一个链表首指针，指向链表的第一个元素。对双向链表而言主要的操作有插入、删除和查找元素。双向链表而言主要的操作有插入、删除和查找元素。双向双向链链表元素表元素1rlinkllinkheader元素元素2rlin双向链表的插入操作算法Step1.Step1.Step1.Step1.找到插入点找到插入点找到插入点找到插入点（假设在插入点后增加一个节点）（假设在插入点后增加一个节点）（假设在插入点后增加一个节点）（假设在插入点后增加一个节点）Step2.Step2.Step2.Step2.得到新节点，并赋值得到新节点，并赋值得到新节点，并赋值得到新节点，并赋值元素元素X X rlinkrlinkllinkllink元素元素1 1 rlinkrlinkllinkllinkheaderheader元素元素2 2 rlinkrlinkllinkllink元素元素3 3 rlinkrlinkllinkllink元素元素4 4 rlinkrlinkllinkllink元素元素5 5 rlinkrlinkllinkllinkP PQ Q双向双向链链表的插入操作算法表的插入操作算法Step1.找到插入点（假找到插入点（假设设在插入点后在插入点后元素元素X X rlinkrlinkllinkllink元素元素1 1 rlinkrlinkllinkllinkheaderheader元素元素2 2 rlinkrlinkllinkllink元素元素3 3 rlinkrlinkllinkllink元素元素4 4 rlinkrlinkllinkllink元素元素5 5 rlinkrlinkllinkllinkP PQ QStep2.Step2.Step2.Step2.修改指针项修改指针项修改指针项修改指针项Q-rlink Q-rlink Q-rlink Q-rlink:=P-rlink=P-rlink=P-rlink=P-rlink；Q-llink Q-llink Q-llink Q-llink:=P=P=P=P；P-rlink-llink P-rlink-llink P-rlink-llink P-rlink-llink:=Q=Q=Q=Q；P-rlinkP-rlinkP-rlinkP-rlink:=Q=Q=Q=Q；元素元素Xrlinkllink元素元素1rlinkllinkhead树 树是结点之间有分支的、层次关系的结构，类似于自树是结点之间有分支的、层次关系的结构，类似于自然界中的树。是最重要的一类非线性结构。反映不同规然界中的树。是最重要的一类非线性结构。反映不同规格的钢材的库存情况的树结构如下图：格的钢材的库存情况的树结构如下图：一棵二叉树示例一棵二叉树示例一棵二叉树示例一棵二叉树示例树树 树树是是结结点之点之间间有分支的、有分支的、层层次关系的次关系的结结构，构，类类似于自然似于自然树的抽象定义树的抽象定义Tree Tree 数据对象：数据对象：数据对象：数据对象：D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系：数据关系：数据关系：数据关系：若若 D D 为空集，则称为空树；为空集，则称为空树；若若 D D 中仅含一个数据元素，则关系中仅含一个数据元素，则关系R R为空集；否则为空集；否则 R=HR=H。(1)(1)在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素rootroot，它在关系它在关系H H下无前驱；下无前驱；(2)(2)当当n1n1时，其余数据元素可分为时，其余数据元素可分为m(m0)m(m0)个互不相交个互不相交的的(非空非空)有限集有限集 T1,T2,T1,T2,Tm,Tm,其中每一个子集本身又是一其中每一个子集本身又是一棵符合本定义的棵符合本定义的树树树树，称为根，称为根rootroot的子树，每一棵子树的根的子树，每一棵子树的根xixi都都是根是根rootroot的后继，的后继，即即 root,xi H,H,（i=1,2,mi=1,2,m）。）。树树的抽象定的抽象定义义Tree 结点结点(node)node)表示树中的元素，包括数据项及若干指向其子树表示树中的元素，包括数据项及若干指向其子树的分支的分支结点的度结点的度(degree)degree)结点拥有的子树数结点拥有的子树数叶子叶子(leaf)leaf)度为度为0 0的结点的结点孩子孩子(child)child)结点子树的根称为该结点的孩子结点子树的根称为该结点的孩子双亲双亲(parents)parents)孩子结点的上层结点叫该结点的双亲孩子结点的上层结点叫该结点的双亲兄弟兄弟(sibling)sibling)同一双亲的孩子同一双亲的孩子树的度树的度 一棵树中最大的结点度数一棵树中最大的结点度数深度深度(depth)depth)树中结点的最大层次数树中结点的最大层次数森林森林(forest)forest)m(m m(m 0)0)棵互不相交的树的集合棵互不相交的树的集合 当树的每个结点最多只允许存在两棵子树时，该树称为当树的每个结点最多只允许存在两棵子树时，该树称为当树的每个结点最多只允许存在两棵子树时，该树称为当树的每个结点最多只允许存在两棵子树时，该树称为二二二二叉树叉树叉树叉树，二叉树的子树有左右之分，不能颠倒。，二叉树的子树有左右之分，不能颠倒。，二叉树的子树有左右之分，不能颠倒。，二叉树的子树有左右之分，不能颠倒。树的基本术语和定义结结点点(node)表示表示树树中的元素，包括数据中的元素，包括数据项项及若干指向其子及若干指向其子二叉树的基本操作二叉树的基本操作 对于树结构中最常见的二叉树，其中的基本操作有对于树结构中最常见的二叉树，其中的基本操作有存储二叉树，删除存储二叉树，删除/增加树结点，遍历增加树结点，遍历/线索二叉树等。线索二叉树等。二叉树的存储表达方式主要有二叉树的存储表达方式主要有顺序存储顺序存储和和链式存储链式存储两种。对两种。对于完全二叉树，于完全二叉树，为了能在存储结构中反映出结点之间的逻辑关为了能在存储结构中反映出结点之间的逻辑关系，可用顺序存储方式将二叉树中结点依照一定规律安排在连系，可用顺序存储方式将二叉树中结点依照一定规律安排在连续存储单元中。而常用的是采用二叉链表来存储二叉树。续存储单元中。而常用的是采用二叉链表来存储二叉树。LchildLchilddatadataRchildRchild 遍历是对树结构中的每个数据元素都遍历是对树结构中的每个数据元素都访问一次且仅仅访问访问一次且仅仅访问一次一次。进行遍历应该确定一条搜索路径，使得结构中的每个数。进行遍历应该确定一条搜索路径，使得结构中的每个数据元素都出现在这条搜索路径上，才能确保每个数据元素都被据元素都出现在这条搜索路径上，才能确保每个数据元素都被访问到。非线性结构中每个数据元素可以有多个后继，为保证访问到。非线性结构中每个数据元素可以有多个后继，为保证遍历成功就需要确定合适的搜索路径。遍历成功就需要确定合适的搜索路径。对于二叉树，存在先序遍历、中序遍历及后序遍历三种路对于二叉树，存在先序遍历、中序遍历及后序遍历三种路径。径。二叉二叉树树的基本操作的基本操作 对对于于树结树结构中最常构中最常见见的二叉的二叉树树，其中的，其中的图 图是一种比较复杂的非线性数据结构。对于图结构，图图是一种比较复杂的非线性数据结构。对于图结构，图中顶点之间的关系可以是多对多，即一顶点和其它顶点间中顶点之间的关系可以是多对多，即一顶点和其它顶点间的关系是任意的，可以有关也可以无关。的关系是任意的，可以有关也可以无关。若图中的边是有方向的，则称为为若图中的边是有方向的，则称为为有向图有向图。否则，为。否则，为无无向图向图。2 21 13 34 42 21 14 45 53 3 图的基本操作有：创建图的基本操作有：创建/销毁图，增加销毁图，增加/删除删除/查找顶点，查找顶点，增加增加/删除边，遍历图等。删除边，遍历图等。图的存储结构方法有：邻接矩阵表示法；邻接表；邻接多图的存储结构方法有：邻接矩阵表示法；邻接表；邻接多重表及十字链表等。重表及十字链表等。图图 图图是一种比是一种比较较复复杂杂的非的非线线性数据性数据结结构。构。对对于于图结图结构，构，图图中中数据文件 把数据按某种数据结构组织起来存放在外部把数据按某种数据结构组织起来存放在外部设备上，就构成设备上，就构成数据文件数据文件。数据文件系统是数。数据文件系统是数据库系统的基础。据库系统的基础。数据文件是为某一目的而形成的同类记录的数据文件是为某一目的而形成的同类记录的集合，集合，记录记录是文件中数据组织的基本单位，由是文件中数据组织的基本单位，由若干个数据项组成，若干个数据项组成，数据项数据项是数据处理的最小是数据处理的最小单位。单位。常用的文件组织方式有两种：常用的文件组织方式有两种：顺序文件顺序文件和和索索引文件引文件。数据文件数据文件 把数据按某种数据把数据按某种数据结结构构组织组织起来存放在外部起来存放在外部设设 记录在文件中的位置与记录进入文件的时序直接相记录在文件中的位置与记录进入文件的时序直接相记录在文件中的位置与记录进入文件的时序直接相记录在文件中的位置与记录进入文件的时序直接相关。记录连续存放，文件结构紧凑，空间节省。关。记录连续存放，文件结构紧凑，空间节省。关。记录连续存放，文件结构紧凑，空间节省。关。记录连续存放，文件结构紧凑，空间节省。记录的查询必须顺序进行，查找时间慢，在文件中记录的查询必须顺序进行，查找时间慢，在文件中记录的查询必须顺序进行，查找时间慢，在文件中记录的查询必须顺序进行，查找时间慢，在文件中插入或删除一个记录时，该记录的后续记录的存放位置插入或删除一个记录时，该记录的后续记录的存放位置插入或删除一个记录时，该记录的后续记录的存放位置插入或删除一个记录时，该记录的后续记录的存放位置被更改，当文件过于庞大时，需要耗费大量的系统时间。被更改，当文件过于庞大时，需要耗费大量的系统时间。被更改，当文件过于庞大时，需要耗费大量的系统时间。被更改，当文件过于庞大时，需要耗费大量的系统时间。处理效率不高。处理效率不高。处理效率不高。处理效率不高。职工编号职工编号职工编号职工编号姓名姓名姓名姓名所属部门所属部门所属部门所属部门电话电话电话电话1004210042张健张健张健张健企管部企管部企管部企管部84265667842656671023310233李兵李兵李兵李兵生产部生产部生产部生产部84337654843376541000510005周茵周茵周茵周茵企管部企管部企管部企管部87850999878509991300213002王文理王文理王文理王文理供应部供应部供应部供应部84858687848586871001010010刘大鹏刘大鹏刘大鹏刘大鹏财务部财务部财务部财务部8754234587542345顺序数据文件结构 记录记录在文件中的位置与在文件中的位置与记录进记录进入文件的入文件的时时序直接相关。序直接相关。记录记录 在顺序文件的基础上增添一个索引表，索引表按关键在顺序文件的基础上增添一个索引表，索引表按关键字排序，并标注记录在文件中的位置，以提高记录的检字排序，并标注记录在文件中的位置，以提高记录的检索速度。索速度。8785099987850999企管部企管部企管部企管部周茵周茵周茵周茵10005100058754234587542345财务部财务部财务部财务部刘大鹏刘大鹏刘大鹏刘大鹏10010100108485868784858687供应部供应部供应部供应部王文理王文理王文理王文理13002130028433765484337654生产部生产部生产部生产部李兵李兵李兵李兵10233102338426566784265667企管部企管部企管部企管部张健张健张健张健1004210042电话电话电话电话所属部门所属部门所属部门所属部门姓名姓名姓名姓名职工编号职工编号职工编号职工编号13002130021023310233100421004210010100101000510005索引索引索引索引职工编号职工编号职工编号职工编号索引表索引表 顺序文件顺序文件索引数据文件结构 课本课本P38 在在顺顺序文件的基序文件的基础础上增添一个索引表，索引表按关上增添一个索引表，索引表按关键键字排序，并字排序，并数据库系统 类似于一个数据文件是相关记录的集合，一个数据库类似于一个数据文件是相关记录的集合，一个数据库类似于一个数据文件是相关记录的集合，一个数据库类似于一个数据文件是相关记录的集合，一个数据库则是相关数据文件的集合。数据库系统的出现是为了解决则是相关数据文件的集合。数据库系统的出现是为了解决则是相关数据文件的集合。数据库系统的出现是为了解决则是相关数据文件的集合。数据库系统的出现是为了解决数据文件系统的弊端。数据文件系统的弊端。数据文件系统的弊端。数据文件系统的弊端。文件系统的最大弊端是数据文件的共享性差。在文件文件系统的最大弊端是数据文件的共享性差。在文件文件系统的最大弊端是数据文件的共享性差。在文件文件系统的最大弊端是数据文件的共享性差。在文件系统环境中，每个应用程序通常都是为某个特定的操作而系统环境中，每个应用程序通常都是为某个特定的操作而系统环境中，每个应用程序通常都是为某个特定的操作而系统环境中，每个应用程序通常都是为某个特定的操作而写的，甚至可能是由不同的程序员用不同的语言编写的。写的，甚至可能是由不同的程序员用不同的语言编写的。写的，甚至可能是由不同的程序员用不同的语言编写的。写的，甚至可能是由不同的程序员用不同的语言编写的。因此，每个文件的记录往往被设计成只适合某个应用程序，因此，每个文件的记录往往被设计成只适合某个应用程序，因此，每个文件的记录往往被设计成只适合某个应用程序，因此，每个文件的记录往往被设计成只适合某个应用程序，如果其他应用程序不年此种记录格式进行设计的话，它就如果其他应用程序不年此种记录格式进行设计的话，它就如果其他应用程序不年此种记录格式进行设计的话，它就如果其他应用程序不年此种记录格式进行设计的话，它就不可能读取这些记录。因此一个企业的若干应用系统中存不可能读取这些记录。因此一个企业的若干应用系统中存不可能读取这些记录。因此一个企业的若干应用系统中存不可能读取这些记录。因此一个企业的若干应用系统中存在大量的数据文件，这些文件中包含有大量的重复数据，在大量的数据文件，这些文件中包含有大量的重复数据，在大量的数据文件，这些文件中包含有大量的重复数据，在大量的数据文件，这些文件中包含有大量的重复数据，这种情况称为数据冗余。这种情况称为数据冗余。这种情况称为数据冗余。这种情况称为数据冗余。应用程序应用程序A A文件文件A A应用程序应用程序B B文件文件B B应用程序应用程序C C文件文件C C应用程序对为其专门设计的文件的依赖应用程序对为其专门设计的文件的依赖应用程序对为其专门设计的文件的依赖应用程序对为其专门设计的文件的依赖数据数据库库系系统统 类类似于一个数据文件是相关似于一个数据文件是相关记录记录的集合，一个数的集合，一个数数据库系统的构成数据库系统的构成 计算机系统计算机系统 数据库数据库 数据库管理系统数据库管理系统(DBMS)(DBMS)人员人员 数据库管理员数据库管理员 系统程序员系统程序员 用户用户计算机系统计算机系统计算机系统计算机系统数据库数据库数据库数据库人员人员人员人员数据库管理系统数据库管理系统数据库管理系统数据库管理系统课本课本数据数据库库系系统统的构成数据的构成数据库库系系统统的构成的构成 计计算机系算机系统统 计计算机系算机系统统数据数据数据库管理系统 一个数据库管理系统（一个数据库管理系统（一个数据库管理系统（一个数据库管理系统（DBMSDBMSDBMSDBMS）是一系列软件程序）是一系列软件程序）是一系列软件程序）是一系列软件程序的集合。它一般具有以下功能：的集合。它一般具有以下功能：的集合。它一般具有以下功能：的集合。它一般具有以下功能：在数据库管理系统中，应用程序不能直接从存储介质在数据库管理系统中，应用程序不能直接从存储介质在数据库管理系统中，应用程序不能直接从存储介质在数据库管理系统中，应用程序不能直接从存储介质获得所需的数据。它必须先将请求提交给获得所需的数据。它必须先将请求提交给获得所需的数据。它必须先将请求提交给获得所需的数据。它必须先将请求提交给DBMSDBMSDBMSDBMS，由，由，由，由DBMSDBMSDBMSDBMS负负负负责从存储介质检索数据并提供给应用程序使用。因此，一责从存储介质检索数据并提供给应用程序使用。因此，一责从存储介质检索数据并提供给应用程序使用。因此，一责从存储介质检索数据并提供给应用程序使用。因此，一个数据库管理系统是应用程序与数据间的接口。个数据库管理系统是应用程序与数据间的接口。个数据库管理系统是应用程序与数据间的接口。个数据库管理系统是应用程序与数据间的接口。1 1 1 1.以规范、一致的方式存储数据；以规范、一致的方式存储数据；以规范、一致的方式存储数据；以规范、一致的方式存储数据；2.2.2.2.以规范、一致的方式将数据组织成记录；以规范、一致的方式将数据组织成记录；以规范、一致的方式将数据组织成记录；以规范、一致的方式将数据组织成记录；3.3.3.3.允许用规范、一致的方式存取记录。允许用规范、一致的方式存取记录。允许用规范、一致的方式存取记录。允许用规范、一致的方式存取记录。应用程序应用程序数据库数据库管理系统管理系统数据库数据库应用程序应用程序应用程序应用程序应用程序、数据库、数据库管理系统三者的关系应用程序、数据库、数据库管理系统三者的关系数据数据库库管理系管理系统统 一个数据一个数据库库管理系管理系统统（DBMS）是一系列）是一系列软软数据库的基本类型-层次型数据库 以树状结构描述数据以树状结构描述数据以树状结构描述数据以树状结构描述数据。最常用的层次型数据库是。最常用的层次型数据库是。最常用的层次型数据库是。最常用的层次型数据库是IBMIBMIBMIBM的的的的IMSIMS(Information Management SystemInformation Management System)。它把每个记录。它把每个记录。它把每个记录。它把每个记录中的数据元素组成一个个记录块叫做节点。对于用户来说，中的数据元素组成一个个记录块叫做节点。对于用户来说，中的数据元素组成一个个记录块叫做节点。对于用户来说，中的数据元素组成一个个记录块叫做节点。对于用户来说，每个记录就象一个组织图，最上层的节点叫根节点，上下每个记录就象一个组织图，最上层的节点叫根节点，上下每个记录就象一个组织图，最上层的节点叫根节点，上下每个记录就象一个组织图，最上层的节点叫根节点，上下层的节点以父层的节点以父层的节点以父层的节点以父-子逻辑关系关联。父节点可以有多个子节点，子逻辑关系关联。父节点可以有多个子节点，子逻辑关系关联。父节点可以有多个子节点，子逻辑关系关联。父节点可以有多个子节点，而子节点只能有一个父节点。而子节点只能有一个父节点。而子节点只能有一个父节点。而子节点只能有一个父节点。员工员工员工员工工作分配工作分配工作分配工作分配福利福利福利福利收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入收入数据数据库库的基本的基本类类型型-层层次型数据次型数据库库 以以树树状状结结构描述数据构描述数据 这是层次型数据库的变种。实际上，数据库为这是层次型数据库的变种。实际上，数据库为这是层次型数据库的变种。实际上，数据库为这是层次型数据库的变种。实际上，数据库为了优化数据处理，既可以从层次变为网状，也可以了优化数据处理，既可以从层次变为网状，也可以了优化数据处理，既可以从层次变为网状，也可以了优化数据处理，既可以从层次变为网状，也可以从网状变为层次。层次结构描述的是一对多的关系，从网状变为层次。层次结构描述的是一对多的关系，从网状变为层次。层次结构描述的是一对多的关系，从网状变为层次。层次结构描述的是一对多的关系，而网络结构描述的是而网络结构描述的是而网络结构描述的是而网络结构描述的是多对多的关系多对多的关系多对多的关系多对多的关系。课程课程课程课程1 1课程课程课程课程1 1课程课程课程课程1 1学生学生学生学生1 1学生学生学生学生5 5学生学生学生学生2 2学生学生学生学生4 4学生学生学生学生3 3数据库的基本类型 网络型数据库 这这是是层层次型数据次型数据库库的的变变种。种。实际实际上，数据上，数据库为库为了了优优化数据化数据处处 该模型将数据库中所有数据以二维关系表的形式来该模型将数据库中所有数据以二维关系表的形式来该模型将数据库中所有数据以二维关系表的形式来该模型将数据库中所有数据以二维关系表的形式来表示。表表示。表表示。表表示。表(Table)(Table)看起来类似于一个文件，多个文件中的看起来类似于一个文件，多个文件中的看起来类似于一个文件，多个文件中的看起来类似于一个文件，多个文件中的信息很容易地提取和合并。即可以将任何一个表与另一信息很容易地提取和合并。即可以将任何一个表与另一信息很容易地提取和合并。即可以将任何一个表与另一信息很容易地提取和合并。即可以将任何一个表与另一个表关联起来，前提是两个表要有共同的数据项。个表关联起来，前提是两个表要有共同的数据项。个表关联起来，前提是两个表要有共同的数据项。个表关联起来，前提是两个表要有共同的数据项。数据库的基本类型 关系型数据库24.3024.301 114514503/01/0103/01/0101/13/0101/13/011636163679.7079.703 313713702/29/0102/29/0101/12/0101/12/0116351635144.50144.502 215215202/22/0102/22/0102/02/0102/02/0116341634金额金额金额金额数量数量数量数量零件号零件号零件号零件号发货日期发货日期发货日期发货日期订货日期订货日期订货日期订货日期订单编号订单编号订单编号订单编号145145137137152152零件号零件号零件号零件号1125112570.0070.00压缩机压缩机压缩机压缩机2038203822.5022.50门把手门把手门把手门把手4058405826.2526.25门门门门 锁锁锁锁供应商编号供应商编号供应商编号供应商编号单价单价单价单价零件名称零件名称零件名称零件名称112511252038203840584058供应商编号供应商编号供应商编号供应商编号智远公司智远公司智远公司智远公司先锋公司先锋公司先锋公司先锋公司光明公司光明公司光明公司光明公司供应商名称供应商名称供应商名称供应商名称112324112324海滨路海滨路海滨路海滨路5151号号号号114321114321五四路五四路五四路五四路3232号号号号116044116044人民路人民路人民路人民路4444号号号号邮编邮编邮编邮编供应商地址供应商地址供应商地址供应商地址订货表订货表供应商表供应商表零件表零件表 该该模型将数据模型将数据库库中所有数据以二中所有数据以二维维关系表的形式来表示。表关系表的形式来表示。表数据库中的数据模型 按用户的观点对数据和信息建模，常常首按用户的观点对数据和信息建模，常常首先将现实世界的先将现实世界的客观对象客观对象抽象为某一种不依赖抽象为某一种不依赖于计算机系统和某一个于计算机系统和某一个DBMSDBMS的信息结构，即的信息结构，即概概念模型念模型；然后再把概念模型转换为计算机上某；然后再把概念模型转换为计算机上某种种DBMS支持的支持的数据模型数据模型。数据数据库库中的数据模型中的数据模型 按用按用户户的的观观点点对对数据和信息建模，常常数据和信息建模，常常概念模型 概念模型是按用户观点对数据和信息的建模。建概念模型是按用户观点对数据和信息的建模。建概念模型是按用户观点对数据和信息的建模。建概念模型是按用户观点对数据和信息的建模。建立概念模型需要确定的三大要素是：立概念模型需要确定的三大要素是：立概念模型需要确定的三大要素是：立概念模型需要确定的三大要素是：实体实体实体实体、属性属性属性属性和和和和联系联系联系联系。概念模型最常用的表示方法是概念模型最常用的表示方法是概念模型最常用的表示方法是概念模型最常用的表示方法是1976197619761976年年年年ChenChenChenChen提出的提出的提出的提出的E-RE-RE-RE-R模型模型模型模型 (Entity-Relation Model)(Entity-Relation Model)。规定：矩形表。规定：矩形表。规定：矩形表。规定：矩形表示实体，菱形表达实体间联系，椭圆表示实体的属示实体，菱形表达实体间联系，椭圆表示实体的属示实体，菱形表达实体间联系，椭圆表示实体的属示实体，菱形表达实体间联系，椭圆表示实体的属性，实体间的对应数量关系在无向边上予以标识。性，实体间的对应数量关系在无向边上予以标识。性，实体间的对应数量关系在无向边上予以标识。性，实体间的对应数量关系在无向边上予以标识。实体的关键属性在对应的属性名下方予以短横线划实体的关键属性在对应的属性名下方予以短横线划实体的关键属性在对应的属性名下方予以短横线划实体的关键属性在对应的属性名下方予以短横线划记。记。记。记。一对一联系一对一联系一对一联系一对一联系 一对多联系一对多联系一对多联系一对多联系多对多联系多对多联系多对多联系多对多联系概念模型概念模型 概念模型是按用概念模型是按用户观户观点点对对数据和信息的建模。建立概念数据和信息的建模。建立概念销售企业进销存系统销售企业进销存系统E-RE-R图图E-R图实际应用销销售企售企业进销业进销存系存系统统E-R图图E-R图实际应图实际应用用数据模型 数据模型是对客观事物及其联系的数据化描数据模型是对客观事物及其联系的数据化描数据模型是对客观事物及其联系的数据化描数据模型是对客观事物及其联系的数据化描述。在数据库系统中述。在数据库系统中述。在数据库系统中述。在数据库系统中,对现实世界中数据的抽象、对现实世界中数据的抽象、对现实世界中数据的抽象、对现实世界中数据的抽象、描述以及处理等都是通过数据模型来实现的。数描述以及处理等都是通过数据模型来实现的。数描述以及处理等都是通过数据模型来实现的。数描述以及处理等都是通过数据模型来实现的。数据模型在数据库系统设计中是用来提供信息表示据模型在数据库系统设计中是用来提供信息表示据模型在数据库系统设计中是用来提供信息表示据模型在数据库系统设计中是用来提供信息表示和操作手段的形式构架和操作手段的形式构架和操作手段的形式构架和操作手段的形式构架,是数据库系统实现的基础。是数据库系统实现的基础。是数据库系统实现的基础。是数据库系统实现的基础。目前，最主要的数据模型是目前，最主要的数据模型是目前，最主要的数据模型是目前，最主要的数据模型是关系数据模型关系数据模型关系数据模型关系数据模型(Relational Model)(Relational Model)。数据模型数据模型 数据模型是数据模型是对对客客观观事物及其事物及其联联系的数据化描述。在数系的数据化描述。在数关系数据模型 每一个关系为一张二维表，相当于一个文件。实体每一个关系为一张二维表，相当于一个文件。实体间的联系均通过关系进行描述。下表用间的联系均通过关系进行描述。下表用mm行行n n列的二维表列的二维表表示了具有表示了具有n n元组元组(n-Tuple)(n-Tuple)的的“同学同学”关系。每一行即一个关系。每一行即一个n n元组元组,相当于一条记录相当于一条记录,用来描述一个实体。用来描述一个实体。关系数据模型关系数据模型 每一个关系每一个关系为为一一张张二二维维表，相当于一个文件表，相当于一个文件 ER模型与关系模型的转换运动员运动员编号编号姓名姓名性别性别名次名次顺序顺序顺序顺序1 11 1运动员运动员运动员运动员（编号编号编号编号，姓名，性别，名次，姓名，性别，名次，姓名，性别，名次，姓名，性别，名次，上一名次编号上一名次编号上一名次编号上一名次编号，下一名次编号下一名次编号下一名次编号下一名次编号）职工职工工号工号姓名姓名年龄年龄性别性别领导领导1 1N N职工职工职工职工（工号工号工号工号，姓名，年龄，性别，姓名，年龄，性别，姓名，年龄，性别，姓名，年龄，性别，经理工号经理工号经理工号经理工号）ER模型与关系模型的模型与关系模型的转换转换运运动员编动员编号姓名性号姓名性别别名次名次顺顺序序11运运零件零件零件号零件号零件名零件名规规格格数量数量组成组成MMN N仓库仓库商品商品商店商店仓库号仓库号仓库名仓库名地址地址数量数量商店号商店号商品名商品名商品号商品号商店名商店名日期日期进货进货MMN NP P零件（零件（零件号零件号，零件名，规格），零件名，规格）组成（组成（零件号零件号，子零件号子零件号，数量），数量）仓库（仓库（仓库号仓库号，仓库名，地址），仓库名，地址）商店（商店（商店号商店号，商店名），商店名）商品（商品（商品号商品号，商品名），商品名）进货（进货（商店号商店号，商品名商品名，仓库号仓库号，日期，数量），日期，数量）零件零件号零件名零件零件号零件名规规格数量格数量组组成成MN仓库仓库商品商店商品商店仓库仓库号号仓库仓库名地址名地址关系的范式化1NF 关系数据模型必须是规范化的关系，满足一定的关系数据模型必须是规范化的关系，满足一定的关系数据模型必须是规范化的关系，满足一定的关系数据模型必须是规范化的关系，满足一定的约束条件。称为约束条件。称为约束条件。称为约束条件。称为范式范式范式范式(Normal Form)(Normal Form)(Normal Form)(Normal Form)。元组中的每一个分量都必须是不可分割的数据项。元组中的每一个分量都必须是不可分割的数据项。元组中的每一个分量都必须是不可分割的数据项。元组中的每一个分量都必须是不可分割的数据项。第一范式第一范式第一范式第一范式(1NF)(1NF)(1NF)(1NF)AM2AM2AM2AM2M2M2M2M2D2D2D2D2DN2DN2DN2DN2AM1AM1AM1AM1M1M1M1M1D1D1D1D1DN1DN1DN1DN1副经理副经理副经理副经理正经理正经理正经理正经理经理经理经理经理部门号部门号部门号部门号部门名部门名部门名部门名非非1NF1NF关系关系副经理副经理副经理副经理正经理正经理正经理正经理部门号部门号部门号部门号部门名部门名部门名部门名AM2AM2AM2AM2M2M2M2M2D2D2D2D2DN2DN2DN2DN2AM1AM1AM1AM1M1M1M1M1D1D1D1D1DN1DN1DN1DN11NF1NF关系关系关系的范式化关系的范式化1NF 关系数据模型必关系数据模型必须须是是规规范化的关系范化的关系第二范式要求数据表里的所有数据都要和该数据表的主第二范式要求数据表里的所有数据都要和该数据表的主第二范式要求数据表里的所有数据都要和该数据表的主第二范式要求数据表里的所有数据都要和该数据表的主键有完全依赖关系；如果有哪些数据只和主键的一部份键有完全依赖关系；如果有哪些数据只和主键的一部份键有完全依赖关系；如果有哪些数据只和主键的一部份键有完全依赖关系；如果有哪些数据只和主键的一部份有关的话，它就不符合第二范式。同时可以得出：如果有关的话，它就不符合第二范式。同时可以得出：如果有关的话，它就不符合第二范式。同时可以得出：如果有关的话，它就不符合第二范式。同时可以得出：如果一个数据表的主键只有单一一个字段的话，它就一定符一个数据表的主键只有单一一个字段的话，它就一定符一个数据表的主键只有单一一个字段的话，它就一定符一个数据表的主键只有单一一个字段的话，它就一定符合第二范式合第二范式合第二范式合第二范式(前提是该数据表符合第一范式前提是该数据表符合第一范式前提是该数据表符合第一范式前提是该数据表符合第一范式)。第二范式第二范式第二范式第二范式(2NF)(2NF)(2NF)(2NF)学分学分学分学分课程号课程号课程号课程号2 2 2 2KC2KC2KC2KC23 3 3 3KC1KC1KC1KC1B B B BKC2KC2S004S004B B B BKC1KC1S004S004A A A AKC2KC2S003S003C C C CKC2KC2S002S002B B B BKC1KC1S002S002A A A AKC2KC2S001S001A A A AKC1KC1S001S001成绩成绩成绩成绩课程号课程号课程号课程号学号学号学号学号2 2B BKC2KC2S004S0043
展开阅读全文