计算机三级数据库考点串讲资料
数据库
一、基础知识
1.计算机系统的组成和应用领域。
计算机系统由(硬件) 系统、(软件) 系统两部份组成。
计算机的硬件基本上由五大部分组成:运算器、控制器、存储器、输入设备、输出设备。 软件系统分为(系统) 软件、(应用) 软件两部分。
计算机的应用领域包括什么?
1、科学计算 2、数据通信与数据处理、3、自动控制4、计算机辅助设计 5、计算机人工智能
2.计算机软件的基础知识。
软件系统分为(系统) 软件、(应用) 软件两部分
二、数据结构与算法
1.数据结构、算法的基本概念。
数据:是信息的载体,是指能够被计算机识别、存储和加工的信息的载体。
数据元素:是数据的基本单位,一个数据元素可以由一个或若干个数据项组成,在计算机程序中通常作为一个整体考虑和处理。
数据项: 数据的不可分割的最小单位。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
数据元素与数据项的区别:
1、数据元素是数据的基本单位,它在计算机存储器上的映像是结点。
2、数据项是数据的最小标识单位,它在计算机存储器上的映像是数据域。
数据结构(data-structure ):是相互之间存在的一种或多种特定关系的数据元素的集合。它反映一个数据的内部构成,即一个数据由哪些成份构成,以什么方式构成,呈什么结构。
基本数据结构:线性结构、树、图、集合
数据结构的形式定义为:DS=(D ,S )
如“复数”表示为:Complex=(C,R)
其中:C 是含两个实数的集合{c1,c2},R是定义在集合上的一种关系{}。
数据结构包含的三方面:
数据的逻辑结构、数据的物理存储结构和数据的运算。
算法的设计取决与数据的逻辑结构,
算法的实现取决与数据的物理存储结构。
数据的逻辑结构:是“数据结构”定义中的关系,指数据间的逻辑关系。包括:线性结构和非线性结构,其中非线性结构又包括:树型结构和网状结构。通常所说的数据结构就是指数据的逻辑结构。 A、线性结构:除了第一个和最后一个元素以外,其他元素有且仅有一个直接前驱元素,有且仅有一个直接后继元素。
B、树型结构:是一种层次关系,数据元素只能与上一层中的一个数据元素相关,但可以和下一层的多个数据元素相关。
C、网状结构:任何两个数据元素间都可以相关。
数据的存储结构:是数据的逻辑结构的计算机存储器里的实现(亦称为映象),即数据元素及其关系在计算机中的表示。包括:顺序、链式、索引、散列等存储方式。
A :顺序存储结构:逻辑结构中相邻的数据元素在存储器中存放的位置是相邻的。
B :链式存储结构:逻辑结构中相邻的数据元素在存储器中存放的位置是不相邻的。是通过指针进行联系的。
数据运算:施加于数据的操作。
算法:是指解决特定问题的方法,是由若干条指令组成的有穷序列。
算法的基本特征:
(1)输入:0个或多个输入;
(2)输出:1个或多个输出;
(3)有穷性:算法必须在有限步内结束;每步有限时间内完成。
(4)确定性:组成算法的操作必须无二义性。
(5)可行性:组成算法的操作必须能够在计算机上实现。
算法的分析:主要是算法复杂度的分析方法及其运用。
评价算法的标准:正确性,可读性,健壮性,效率与低存储要求。
2.线性表的定义、存储和运算。
线性表的定义:
线性表(linear list)是由n(n>=0)个数据元素(结点) a1,a2,…,an 组成的有限序列。
1)、数据元素的个数n 定义为表的长度(n=0时为空表)。
2)、将非空的线性表(n>0)记作:( a1,a2,…,an) 。
3) 、数据元素ai(1
线性表的基本操作:
1、存取操作:存取线性表中第i 个数据元素;
2、查找操作:在线性表中查找满足条件元素;
3、插入操作:在线性表的第i 个元素之前插入一个新元素;
4、删除操作 :删除线性表的第i 个元素;
5、分解操作 :将一个线性表拆分为多个线性表;
6、合并操作:
7、排序
线性表的存储结构:顺序表、链式存储
3.树形结构的定义、存储和运算。
树形结构是一种重要的非线性结构,讨论的是层次和分支关系。树是n 个结点的有限集合,当n=0时,称为空树, 在任一棵非空树中:
(1)有且仅有一个称为根的结点。
(2)如果n>1,除根结点外的其余结点可分成m(m>0)个不相交的集合T1,T2, „,Tm, 其中每一个集合都是一棵树。树T1,T2, „,Tm 称为这个根结点的子树。
4.排序的基本概念和排序算法。
排序定义
将一组记录按某排序码递增或递减排列的过程,称为排序。内部排序:指的是待排序记录存放在计算
机随机存储器进行的排序过程。外部排序:在进行内部排序时还要访问外存。本节讨论内部排序
稳定与不稳定
对于具有同一排序码的多个记录来说,若采用的排序方法使排序后记录的相对次序不变,则称此排序
方法是稳定的,否则称为不稳定的。
稳定的排序方法:直接插入排序、冒泡排序、归并排序
不稳定的排序方法:直接选择排序、希尔排序、快速排序、堆排序
5.检索的基本概念和检索算法。
检索的定义:在特定的数据元素集合中寻找关键字与给定值相等的元素并输出寻找结果的过程称为
查找,也叫检索。
关键字:指的是数据元素中用以标识该数据元素的某个数据项的值,如学生成绩表中,学生可以同名,同分等,只有学号是各不相同的,一个学号就对应一个学生,所以学号是关键字。如果某数据元素只有一个数据项,那么该数据元素的值就是关键字。
检索方法包括:顺序查找;二分查找(又称折半查找);索引查找(又称分块查找);Hash 查找(哈希表,散列表)。
三、操作系统
1.操作系统的基本概念、主要功能和分类。
操作系统可分为(批处理操作系统) 、(分时操作系统) 、(实时操作系统) 三种操作系统。个人、网络、
分布式操作系统。
操作系统的特征:(并发) 、(资源共享) 、(虚拟) 、(异步) 。
操作系统的五大功能:(处理机管理) 、(设备管理) 、(存储器管理) 、(文件管理) 、(提供友好的用户
接口) 。
操作系统发展的过程:(无操作系统) 、(单道批处理系统) 、(多道批处理系统) 、(分时系统) 、(实时
系统) 、(网络操作系统) 、(分布式系统) 。
2.进程、线程、进程间通信的基本概念。
进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配的一
个独立的单位,进程是动态产生, 动态消亡的,每一个进程都有一个数据结构——进程控制块——记录其执行情况,进程有三种基本状态,随着进程的进展 ,它们在状态之间相互变化。
线程(thread )是" 进程" 中某个单一顺序的控制流。也被称为轻量进程(lightweight processes)。
计算机科学术语,指运行中的程序的调度单位。
线程与进程的区别可以归纳为以下几点: 1)地址空间和其它资源(如打开文件):进程间相互
独立,同一进程的各线程间共享。某进程内的线程在其它进程不可见。 2)通信:进程间通信IPC ,线程间可以直接读写进程数据段(如全局变量)来进行通信——需要进程同步和互斥手段的辅助,以保证数据的一致性。 3)调度和切换:线程上下文切换比进程上下文切换要快得多。 4)在多线程OS 中,进程不是一个可执行的实体。
四、数据库系统基本原理
1.数据库的基本概念,数据库系统的构成。
数据(Data ):数据实际上就是描述事物的符号记录。
数据库(Database ,简称DB ):
数据库是长期存储在计算机内有结构的大量的共享的数据集合。
它可以供各种用户共享、具有最小冗余度和较高的数据独立性。DBMS 在数据库建立、运用和维护时对数据库进行统一控制,以保证数据的完整性、安全性,并在多用户同时使用数据库时进行并发控制,在发生故障后对系统进行恢复。
数据库管理系统(Database Management System,简称DBMS ):
数据库管理系统是位于用户与操作系统之间的一层数据管理软件。
数据库在建立、运用和维护时由数据库管理系统统一管理、统一控制。数据库管理系统使用户能方便地定义数据和操纵数据,并能够保证数据的安全性、完整性、多用户对数据的并发使用及发生故障后的系统恢复。
典型的数据库管理系统:Microsoft SQL Server、Microsoft Access、Microsoft FoxPro
Oracle 等。
数据库系统(Database System,简称DBS ):
数据库系统是指在计算机系统中引入数据库后的系统构成,一般由数据库、数据库管理系统(及
其开发工具)、应用系统、数据库管理员和用户构成。
关于数据库管理员和用户的观念
数据库系统管理员(Database Administrator ,简称DBA ):负责数据库的建立、使用和维护的专门的人员。
数据库用户:终端用户、应用程序开发人员、数据库管理员。
A、终端用户是指将数据存储到数据库管理系统中,并对数据进行操作的人。
B、应用程序开发人员:开发程序包,以便终端用户通过数据库管理系统来存取数据。
C、数据库管理员(Database Administrator,简称 DBA):是专门负责设计和维护数据库的人员。
他们的主要任务是:
(1)决定数据库的内容与结构
(2)决定数据库的存储结构和存取策略。
(3)定义数据库的安全性要求和数据完整性约束条件。
(4)监督和控制数据库的使用和运行,提供数据库故障恢复策略。比如定期对数据进行备份和维护系统日志文件等。
(5)数据库的改建和重组。
数据库系统是一个整体的概念,这里讨论数据库的传统概念。
(1) 数据
(2) 数据库文件
(3) 数据库
(4) 数据库管理系统
(5) 数据库应用系统
(6) 数据库系统
综上所述,数据、数据库文件、数据库、数据库管理系统、数据库应用系统、数据库系统是不同层次的概念。 数据库系统特点
数据结构化
数据的共享性、数据冗余度、数据的一致性
物理独立性、逻辑独立性
数据的安全性(Security )
数据的完整性(Integrity )
并发控制(Concurrency )
数据库恢复(Recovery )
2.数据模型概念和主要的数据模型。
在数据库中用数据模型这个工具来抽象、表示和处理现实世界中的数据和信息。通俗地讲数据模型就
是现实世界的模拟。
• 数据模型包括两个不同的概念:
(1)概念模型,概念模型也称信息模型,它是按用户的观点来对数据和信息建模(基于行为的语义描
述模型)。用于设计数据库。
(2)数据模型,它是按计算机系统的观点对数据建模,主要包括网状模型、层次模型、关系模型等 ( 基于数据结构的数据模型)。用于实现数据库管理系统DBMS 。
• 数据模型的组成要素:两种意义的模型都是基于三个组成要素展开讨论
一、数据结构
数据结构用于描述系统的静态特性,研究与数据类型、内容、性质有关的对象,例如关系模型
中的域、属性、关系等。
二、数据操作
数据库主要有检索和更新(包括插入、删除、修改)等两大类操作。数据模型必须定义这些操
作的确切含义、操作符号、操作规则(如优先级)以及实现操作的语言。
三、数据的约束条件
数据的约束条件是一组完整性规则的集合。完整性规则是给定的数据模型中数据及其联系所具有
的制约和储存规则,用以限定符合数据模型的数据库状态以及状态的变化,以保证数据的正确、有效、相容。此外,数据模型还应该提供定义完整性约束条件的机制。
• 概念模型用于信息世界的建模
概念模型不依赖于某一个DBMS 支持的数据模型。概念模型可以转换为计算机上某一DBMS 支持的特
定数据模型。
概念模型特点
(1) 具有较强的语义表达能力,能够方便、直接地表达应用中的各种语义知识.
(2) 应该简单、清晰、易于用户理解,是用户与数据库设计人员之间进行交流的语言。
• 不同的数据模型具有不同的数据结构形式。
• 主要包括:
网状模型:网状数据模型是一种比层次模型更具普遍性的结构,它去掉了层次模型的两个限
制,允许多个结点没有双亲结点,允许结点有多个双亲结点,此外它还允许两个结点之间有多种联系(称之为复合联系)。
优点:
· 能够更为直接地描述现实世界。
· 具有良好的性能,存取效率较高。
缺点:
· 其DDL 语言(数据描述语言)极其复杂。
· 数据独立性较差。由于实体间的联系本质上通过存取路径指示的,因此应用程序在访问数据
时要指定存取路径。
层次模型:限制:只有一个结点没有双亲结点,称之为根结点 · 根以外的其它结点有且只
有一个双亲结点 这就使得层次数据库系统只能处理一对多的实体关系。
关系模型:在用户看来,一个关系模型的逻辑结构是一张二维表,它由行和列组成。
3.关系数据模型的基本概念,关系操作和关系代数。
有关概念:
关系:对应通常说的表;
元组:表中的一行即为一个元组;
属性:表中的一列即为一个属性;
主码(Key ):表中的某个属性组,它可以唯一确定一个元组;
域(Domain ):属性的取值范围;
分量:元组中的一个属性值;
关系模式:对关系的描述,一般表示为
关系名(属性1,属性2,…,属性n )
例:学生(学号,姓名,年龄,性别,家庭地址)
在关系模型中,实体以及实体间的联系都是用关系来表示。关系模型要求关系必须是规范化的,最
基本的条件就是,关系的每一个分量必须是一个不可分的数据项,即不允 许表中还有表。
关系数据模型的操纵与完整性约束
关系数据模型的操纵主要包括查询、插入、删除和更新数据。这些操作必须满足关系的完整性约束条件。关系模型中的数据操作是集合操作,操作对象和操作结果都是关系,即若干元组的集合。关系模型把存取路径向用户隐蔽起来,用户只要指出“ 干什么 ”,不必详细说明 “怎么干”,从而大大地提高了数据的独立性,提高了用户生产率。
关系数据库标准操作语言是SQL 语言。
关系模型决定了关系操作的特点。操作的对象是关系,操作的结果也是关系,这种操作是集合操作。用户不必关心存取路径,这正是层次模型和网状模型的缺点。
关系操作:关系代数和关系演算。
关系代数:是过程化的查询语言。它包括一个运算集合,这些运算以一个或两个关系为运算对象,产生
一个新的 关系。
关系演算:是非过程化的查询语言。它只是描述所需要的信息,而并不给出获得这些信息的具体操作过程。
关系代数包括:赋值和更名、传统的集合运算和专门的关系运算。
传统的集合运算(运算以关系的元组为单位):并、交、差、广义笛卡尔积。
专门的关系运算(运算同时对行和列进行操作):选择、投影、连接、除。
4.结构化查询语言SQL 。
SQL 是一种介于关系代数和关系演算之间的结构化查询语言,是一个综合的、功能极强同时又简捷易学的语言。主要特点包括:
1、综合统一
SQL集数据定义语言(DDL )、数据操纵语言(DML )和数据控制语言(DCL )于一体,语言风格统一,可以实现数据库生命周期中的全部活动。
2、高度非过程化
SQL提供导航功能,系统能自动完成存取路径的选择。
3、面向集合的操作方式
非关系数据模型采用面向记录的操作方式,一次一记录,而SQL 语言语言采用集合操作方式,不仅操作对象、查找结果可以是元组的集合,而且一次插入、删除、更新操作的对象也可以是元组的集合。
4、以同一种语法结构提供两种使用方式
SQL语言既是自含式语言,又是嵌入式语言。作为自含式语言,它能够独立地用于联机交互的使用方法,用户可以在终端键盘上直接键入SQL 命令对数据库进行操作;作为嵌入式语言,SQL 语句能够嵌入到高级语言(如C ,COBOL ,FORTRAN )程序中,供程序员设计程序时使用。
5、语言简洁、易学易用
SQL语言功能极好,语言十分简洁,完成核心功能只用了9个动词,如下图所示:
主要SQL 语句一览表
5.事务管理、并发控制、故障恢复的基本概念。
事务:是用户定义的一个数据库操作序列,是数据库更新操作的逻辑单位。通常,一个应用程序包括多个事务。这些操作要么全做要么全不做,是一个不可分割的工作单位。
ACID 特性
原子性:一个事务是一个不可分割的工作单位,事务中的诸多操作要么都做,要么都不做。 一致性:如果数据库中只包含成功事务提交的结果,则称数据库处于一致状态。
隔离性:一个事务内部的操作及使用的数据对并发的其他事务是隔离的,并发事务之间不能相互干扰。 一个事务一旦提交后,它对数据库中数据的改变是永久性的。
事务是并发控制和恢复的基本单位。
并发控制:
为了避免发生并发操作引起的数据不一致性问题,则采用数据封锁技术实现并发控制。
封锁是防止存取同一资源的用户之间相互干扰的机制,即当一个用户对数据库某个数据对象执行修改操作时,对该部分数据加锁,拒绝其他用户对该部分的并发访问要求,直至该事务执行完毕才释放数据对象。
封锁类型:排它锁和共享锁。
封锁会带来新问题:活锁和死锁。通常采用先来先服务策略来避免活锁;采用一次封锁法、顺序封锁法来预防死锁;采用定期诊断、释放某事务的方法来解除死锁。
数据库恢复:在某种故障使数据库的当前状态已经不再正确或者至少可疑时,把数据库恢复到已知正确的某一状态。
故障的种类:事务内部的故障、系统故障、介质故障、计算机病毒
数据库恢复的基本原理 : “冗余”
恢复的实现技术
建立冗余数据通常采用的方法是数据转储和日志文件。
数据转储:是数据库恢复中采用的基本技术,它是指DBA 将数据库复制到另一个磁盘上或其他介质上的过程。
日志文件:是用于记录事务对数据库的更新操作的文件。利用日志文件与后备副本文件配合可以实现故障恢复。
五、数据库设计和数据库应用
1.关系数据库的规范化理论。
规范化的关系的基本性质:
(1)、表中所有元组格式相同,长度相同。
(2)、任意两个元组不能完全相同。
(3)、同一列数据取自同一域,是同一属性值。
(4)、行和列的排列顺序不重要。
(5)、每个数据项不可再分。
每个数据项不可再分是最基本的规范条件。规范化的关系称为范式。
为了防止不规范或者错误的数据进入数据库,需要使用完整性约束来限制进入数据库的数据。关系模型中的完整性约束分为3类:实体完整性、参照完整性和用户自定义完性。
关系模型的三类完整性
实体完整性、参照完整性和用户定义的完整性。
关系的两个不变性
实体完整性和参照完整性是关系模型必须满足的完整性约束条件,应该由关系自动支持。
1、 实体完整性:若属性A 是关系R 的主属性,则属性A 不能取空值。也称为码约束。
2、 参照完整性(也称为外码约束):若某一属性或属性组F ,在基本关系R1中不是码,而是基本关系
R2的码(注:F 就是R2的主码),则称F 是R1的外码,R1为参照关系,R2为被参照关系。
3、 用户自定义完整性:用户自己定义的。如:“商品编号”只能以数字形式出现,不能包括字母以及
其他字符。
规范化的过程就是通过关系的投影分解逐步提高关系范式等级的过程。从1NF 到4NF ,其过程可以表示为 消除非主属性对键的部分依赖
消除非主属性对键的传递依赖
消除主属性对键的部分依赖和传递依赖
BCNF
消除非平凡且非函数依赖的多值依赖
4NF
2.数据库设计的目标、内容和方法。
数据库设计的目标:针对具体应用环境,建立一个合适的数据库模式。
数据库设计的内容:数据库的结构特性设计(逻辑结构设计)
数据库的行为特性设计(设计子模式)
数据库的物理模式设计(存储模式、存取方法)
数据库设计的特点:硬件、软件、干件(技术与管理的界面)的结合。
结构(数据)设计和行为(处理)设计密切结合。
数据库设计方法:手工试凑法、规范设计法、数据库设计工具与CASE 工具
数据库设计步骤(阶段):
需求分析:调查处理对象,了解现行系统概况,收集基础数据,明确用户对将要建立的数据库的信息需求和处理需求(数据需求、加工要求、完整性、一改要求、性能要求等)。
概念设计:产生反映组织需求的数据库概念模型,它独立于数据库逻辑结构,独立于具体的DBMS 。数据抽象→局部概念模式→全局概念模式→概念模式评价和改进。
结果:完成局部概念模式描述(局部E-R 图)和全局概念模式描述(全局E-R 图),提交修改后的数据清单和业务活动清单。
逻辑设计:把概念模型转换为与选用的DBMS 所支持的数据模型相符合的基本数据结构,即从概念模型导出特定DBMS 可处理的数据库逻辑结构(包括模式和子模式)。
步骤:将E-R 图转换为数据模型→数据模型优化→设计用户子模式。(2)对物理结构进行评价结果:形成逻辑结构说明书,包括应用设计指南、物理设计指南、关系模式及子模式集合及其相关说明(访问方式、查
询路径、处理要求、约束条件和数据传输量)。
物理设计:(1)确定数据库的物理结构(物理设备上的存取方法和存储结构)
(2)对物理结构进行评价。
存储结构具体包括:关系、索引、聚簇、日志、备份等的存储结构;
步骤:存储格式设计→存储方法设计→访问方法设计→完整性、安全性设计→应用设计→评价物理设计。 结果:形成物理设计说明书,说明书中包括存储格式、存储位置、访问方法、交互界面和输入/输出格式说明。
数据库实施:数据库实施阶段的两项重要工作:1)数据的载入;2)应用程序的编码和调试
任务:根据逻辑设计和物理设计,在计算机上建立数据库并完成其应用开发,装入数据,进行测试和试运行。另外,还要借助DBMS 提供的手段设计故障恢复方案。
步骤:定义数据库结构→数据装载→编制、试调应用程序→数据库试运行。
结果:初步完成实际的数据库应用系统。
运行与维护:任务:数据库的转储和恢复,数据库的安全性和完整性控制,监测并改善数据库的性能。如果需要,进行数据库的重组和重构,扩充数据库的功能,改正运行时发现的错误。数据库维护工作又分为日常维护、定期维护和故障维护几种。
结果:开发任务基本完成,交付一个软件系统和技术文档。技术文档包括系统说明书、技术说明书和使用说明书。
3.数据库应用开发工具。
4.数据库技术发展。
(1)、第一代数据库系统:层次和网状数据库系统
1969年,IBM 公司,IMS (层次)
六十年代末七十年代初,美国数据库系统语言协商会
DBTG 报告(网状)
(2)、第二代数据库系统:七十年代,关系数据库系统。
(3)、新一代数据库系统
八十年代以来,新一代数据库系统的研究与发展呈现出了百花齐放的局面。