数据库
一、基础知识
1．计算机系统的组成和应用领域。
计算机系统由(硬件)系统、(软件)系统两部份组成。
计算机的硬件基本上由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。
软件系统分为(系统)软件、(应用)软件两部分。 计算机的应用领域包括什么?
1、科学计算 2、数据通信与数据处理、3、自动控制4、计算机辅助设计 5、计算机人工智能 2．计算机软件的基础知识。
软件系统分为(系统)软件、(应用)软件两部分 二、数据结构与算法
1．数据结构、算法的基本概念。
数据：是信息的载体，是指能够被计算机识别、存储和加工的信息的载体。
数据元素：是数据的基本单位，一个数据元素可以由一个或若干个数据项组成，在计算机程序中通常作为一个整体考虑和处理。
数据项: 数据的不可分割的最小单位。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据元素与数据项的区别：
1、数据元素是数据的基本单位，它在计算机存储器上的映像是结点。 2、数据项是数据的最小标识单位，它在计算机存储器上的映像是数据域。
数据结构（data-structure）：是相互之间存在的一种或多种特定关系的数据元素的集合。它反映一个数据的内部构成，即一个数据由哪些成份构成，以什么方式构成，呈什么结构。 基本数据结构：线性结构、树、图、集合 数据结构的形式定义为：DS=（D，S） 如“复数”表示为：Complex=(C,R)
其中：C是含两个实数的集合{c1,c2},R是定义在集合上的一种关系{
数据的逻辑结构、数据的物理存储结构和数据的运算。 算法的设计取决与数据的逻辑结构，
算法的实现取决与数据的物理存储结构。
数据的逻辑结构：是“数据结构”定义中的关系，指数据间的逻辑关系。包括：线性结构和非线性结构，其中非线性结构又包括：树型结构和网状结构。通常所说的数据结构就是指数据的逻辑结构。 Ａ、线性结构：除了第一个和最后一个元素以外，其他元
素有且仅有一个直接前驱元素，有且仅有一个直接后继元 素。
Ｂ、树型结构：是一种层次关系，数据元素只能与上一层 中的一个数据元素相关，但可以和下一层的多个数据元素相 关。
Ｃ、网状结构：任何两个数据元素间都可以相关。
数据的存储结构：是数据的逻辑结构的计算机存储器里的实现（亦称为映象），即数据元素及其关系在计算机中的表示。
包括：顺序、链式、索引、散列等存储方式。
A：顺序存储结构：逻辑结构中相邻的数据元素在存储器 中存放的位置是相邻的。
B：链式存储结构：逻辑结构中相邻的数据元素在存储器
1
中存放的位置是不相邻的。是通过指针进行联系的。 数据运算：施加于数据的操作。
算法：是指解决特定问题的方法，是由若干条指令组成的有穷序列。 算法的基本特征：
（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<=I<=n)只是一个抽象符号,其具体含义在具体情况下是不同的。 线性表的基本操作:
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．排序的基本概念和排序算法。 排序定义
将一组记录按某排序码递增或递减排列的过程，称为排序。内部排序：指的是待排序记录存放在计算机随机存储器进行的排序过程。外部排序：在进行内部排序时还要访问外存。本节讨论内部排序 稳定与不稳定
对于具有同一排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。 稳定的排序方法
直接插入排序、冒泡排序、归并排序 不稳定的排序方法
直接选择排序、希尔排序、快速排序、堆排序
2
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）：
3
数据库系统是指在计算机系统中引入数据库后的系统构成，一般由数据库、数据库管理系统（及
其开发工具）、应用系统、数据库管理员和用户构成。 关于数据库管理员和用户的观念
数据库系统管理员（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。 ? 数据模型的组成要素：两种意义的模型都是基于三个组成要素展开讨论 一、数据结构
数据结构用于描述系统的静态特性，研究与数据类型、内容、性质有关的对象，例如关系模型中的域、属性、关系等。
二、数据操作
4
数据库主要有检索和更新（包括插入、删除、修改）等两大类操作。数据模型必须定义这些操作的确切含义、操作符号、操作规则（如优先级）以及实现操作的语言。
三、数据的约束条件
数据的约束条件是一组完整性规则的集合。完整性规则是给定的数据模型中数据及其联系所具有的制约和储存规则，用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效、相容。此外，数据模型还应该提供定义完整性约束条件的机制。
? 概念模型用于信息世界的建模
概念模型不依赖于某一个DBMS支持的数据模型。概念模型可以转换为计算机上某一DBMS支持的特定数据模型。
概念模型特点
(1) 具有较强的语义表达能力，能够方便、直接地表达应用中的各种语义知识.
(2) 应该简单、清晰、易于用户理解，是用户与数据库设计人员之间进行交流的语言。
? 不同的数据模型具有不同的数据结构形式。 ? 主要包括：
网状模型：网状数据模型是一种比层次模型更具普遍性的结构，它去掉了层次模型的两个限制，允许多个结点没有双亲结点，允许结点有多个双亲结点，此外它还允许两个结点之间有多种联系（称之为复合联系）。
优点： · 能够更为直接地描述现实世界。 · 具有良好的性能，存取效率较高。 缺点： · 其DDL语言（数据描述语言）极其复杂。 · 数据独立性较差。由于实体间的联系本质上通过存取路径指示的，因此应用程序在访问数据时要指定存取路径。
层次模型：限制：只有一个结点没有双亲结点，称之为根结点 · 根以外的其它结点有且只有一个双亲结点 这就使得层次数据库系统只能处理一对多的实体关系。
关系模型：在用户看来，一个关系模型的逻辑结构是一张二维表，它由行和列组成。 3．关系数据模型的基本概念，关系操作和关系代数。 有关概念：
关系：对应通常说的表；
元组：表中的一行即为一个元组； 属性：表中的一列即为一个属性；
主码（Key）：表中的某个属性组，它可以唯一确定一个元组； 域（Domain）：属性的取值范围； 分量：元组中的一个属性值；
关系模式：对关系的描述，一般表示为
关系名（属性1，属性2，…，属性n）
例：学生（学号，姓名，年龄，性别，家庭地址）
在关系模型中，实体以及实体间的联系都是用关系来表示。关系模型要求关系必须是规范化的，最
基本的条件就是，关系的每一个分量必须是一个不可分的数据项，即不允 许表中还有表。
关系数据模型的操纵与完整性约束
5
计算机三级数据库考点串讲资料
