算法基础

谨以此文，感谢我在这个学校最喜欢的两个老师之一——肖my老师。本文基本为老师上课说讲授内容加上一部分自己的感悟拼凑而来，写作文本的目的是为自己的算法课程留下一点点东西，站在老师肩膀上形成粗糙的框架，方便以后的复习以及深入。文笔有限，其中包含的错误还请多多包容，不吝赐教。

to do list：

时间复杂度中递归树法；动规，分治新的感悟；

点覆盖：一组点的集合，使得图中所有边都至少与该集合中一个点相连。

支配集：一组点的集合，使得图中所有的点要么属于该集合，要么与该集合相连。

最大团：在一个无向图中找出点数最多的完全图。

独立集：一组点的集合，集合中的顶点两两不相邻。（团转过来）

SAT问题：也称布尔可满足性问题。给一组变

其中Ci被称为句子。

点覆盖<->独立集<->最大团

最小割：割是一组边集。如s-t割就是如果去掉这些边，将把原图划分为两个点集，其中一个点集包含s，一个点集包含t。（两个是指不相连，而不是代表不存在边相连，如反向边）

decision problem: 是否存在。

search problem:找到一个解。

（这个还能扩展，比如decision problem在多项式时间内解决，所以他是P问题吗）

渐进符号：

注意以上三种都是紧的，对应的两个小写的符号是不紧的，即如下图所示：

概念：算法的时间复杂度是一个函数，用于定性描述算法的运行时间。注意，这个一个代表算法输入字符串长度的函数。

[注]输入字符串长度是一个比较关键的理解，比如在背包问题中，其时间复杂度为O(nW)，因为W不定，所以只能是一个伪多项式时间。

比较：c < log2N < n < n Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n

大致：常数<对数<幂函数<指数函数<阶乘

对于指数是n相关的进行比较，优先比较指数，再比较底数。

记住一个特例：n (logn)<n!<n n

计算：

一般来说，计算采用主方法和递归树法，其中递归树技巧性比较强，主方法其实也是递归树推导归纳而来，且主方法能得到一个比较紧的结果。

主方法：

f(n) = af(n-b)+g(n) =>O( a^(n/b) g(n) )

P：decision problems有一个多项式算法。

NP（nondeterministic polynomial-time）：decision problems能够在多项式时间内验证。

NPC：NP完全问题，首先这个问题是NP的，其次，其他所有问题都可以多项式时间内归约到它。

NPH：如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。

因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。

一些NP问题能在多项式时间内解决，因为 P∈NP

NP难类型问题的证明：

先选好一个已知NP难的问题，然后将已知NP难问题多项式归约到要证明的问题上。先给出这个归约，然后再证明这个归约的正确性。

NPC类型问题的证明：

证明一个问题Y是NPC问题，先说明Y是NP的，然后找到一个NPC问题X，将这个问题X归约到问题Y上，即证明完成。

常见的NPC问题（重要，规约的时候有用！）：

packing problems: set-packing，独立集

覆盖问题：集合覆盖问题，顶点覆盖问题

严格满足问题(constraint satisfaction problems)：SAT，3SAT

序列问题：哈密尔顿回路，旅行商问题

划分问题：3D-matching, 3着色问题

数字问题：子集合问题（子集元素之和为t），背包问题

其他：分团问题（是否存在一个规模为k的团）

规约的概念与理解

规约：意味着对问题进行转换，例如将一个未知的问题转换成我们能够解决的问题，转换的过程可能涉及到对问题的输入输出的转换。

自归约：search problem <=p decision problem

归约：A归约到B，也就是说，我们对A套一个函数f，在f函数的作用下形成一个新的问题，对这个问题运用B的黑盒解法，能够解决问题A。

(B <=p A)一般说来，B问题如果可以归约到A问题，也就是说，一个解决A问题的算法可以被用做子函数（子程序）来解决B问题，也就是说，求解B问题不会比求解A问题更困难。因此，如果B问题是困难的，那么A问题也就是困难的，因为不存在求解A问题的高效算法。(最后一句不懂)

我简单说一下我理解的规约，以X规约到Y为准，大概分成两个方面：

注：在 三 的一些实例中细品。

概念：在对问题求解时，总是做出在当前看来是最好的选择。

贪心的证明：先假设贪心算法得到的解不是最优解，假设S1是贪心算法得到的解，而S2是所有最优解中和S1具有最多相同元素的解，然后比较S1和S2，观察S1和S2中第一个（最前面一个）不一样的元素，然后在贪心解S2中将不一样的元素换成S1中的那个元素得到另一个最优解S3，这样S3和S1比S2和S1有更多相同元素，和假设S2是与S1有最多相同元素的最优解矛盾，这样来推导S1是最优解。

我的理解：假设这个不是最优的，但是一定存在一个最优的解在某一个位置之前和我当前解结构是一样的，那么在这个位置，选最优解也可以选当前解，不影响最终答案。

[注]概念很简单，但是实际 *** 作的时候，贪心的角度很重要，同样的贪心，方向对了，算法就是对的。

例子：

给你一系列活动，每个活动有一个起始时间和一个结束时间，要求在活动不冲突的情况下找到一种有最多活动的安排。

对于这个问题，我们有一下几种贪心的角度：

①将任务按照 开始时间 升序排列。

②将任务按照 结束时间 升序排列。

③将任务按照 任务时长 升序排列。

④对于每一个任务，都记录与其他任务冲突的数量，按照 冲突数量 的升序排列。

其中1，3，4都是不可以的。

任务结束时间的贪心证明（反证法）：

假设贪心不是最最优的，那我们在最优解中找一个与当前解有最相似的解。

由图可以知道，贪心贪的就是最早结束，所以如果不是最优，那么最优的结束时间一定晚于贪心的结束时间。

由上图就可以证明。

最大流通常与最小割相联系。

f 为任意一个流，cap为容量，对于任意的s-t割出来的点集（A，B），v( f ) <= cap(A, B)。

当流增加到与割的容量相等时候，就不可能再有增长空间了，称为最大流。

对于割的容量来说，不同的割法会有不同流量，有些割法永远不会有流达到，比如部分A = {s}, B = {V - s}，这种把源点割出来的割法。

综上，通过这种感性的认识，如果能找到一个最小的割，那么这个割就一定是最大能跑到的流（如果流能更高的话在这个割上就会超过容量，反证。）

上图为一条增广路，一条增广路即为一条s-t的路径，在路径上仍有流可以跑，其曾广的流就是该条路径上最小的剩余容量。（相当于每找一条增广路，就至少有一条边达到满流。）

直到在图中找不到增广路，此时已经达到了最大流。

找ST集合：把满流的边去掉，从S出发走到能到的点，遍历的点就是S集合；剩下的点就属于T集合。注意，如果找到了在找S集合的时候找到了T点，说明还可以继续找增广路。

[补]有一个很有趣的延伸，如多源点多终点问题。问：如果我有两个源点s1，s2，两个终点t1，t2，我想求一组流，使得s1-t1，s2-t2的流达到最大，是否可以加一个源点S，S与s1，s2相连，边流无限大；加一个终点T，T与t1，t2相连，边流无限大，然后这组ST的最大流即可。——答案是No，无法保证是s1-t1，s2-t2，有可能交错。

例子讲的感觉不是特别好，对理解感觉起不到很大作用，希望以后有新的想法后进行补充。

规约是一个重要的概念和思想。

一个图的 最大独立集 与 最小点覆盖 是不相交的两个点集，它们的并就是整个点集。

个人理解：独立集和点覆盖都是从点的角度进行划分的，如果我们从边的角度来看，①一个最小的点覆盖即为我集合中的每一个点都尽可能与更多的边相连，②同时，一条边的两个端点中，只能有一个端点在最小点覆盖中[下注]

[注]我们假设有一条边两个端点（u，v）都在点覆盖之中，首先显然u，v都不是端点，因为假设u是端点的话只需要选择v即可；

给一个集合S和一堆S的子集S1，S2，，Sm，问是否存在存在k个子集，使它们的并集为S。

构造：

集合为点，集合中的元素为边，有相同元素的边相连。（注意如果某一元素只在一个子集中出现，应该怎么处理呢！）

规约：在构造的图中找最小的点覆盖，选中的点能覆盖所有的边即为对应集合的并集能包含所有的元素。所以就完成了集合覆盖到点覆盖的规约。

构造：每个句子构造一个三角形，把对应变量但是相反取值的点相连。

规约：3SAT的有一个特点就是，每一个句子中至少有一个为真即可，每个句子都必须是真。将相同变量相反取值相连的目的就是，在最大独立集中，比如选择x为真，则剩下所有句子中x-ba一定不会被选中，同时由独立集和构造出来三角形的性质可以知道，每一个句子，有且仅有一个会被选中（为真）。如上图，x1-ba为真，x2-ba和x3任选一个为真即可满足。

search problem <=p decision version

比如：如果能在多项式时间内找到一个哈密尔顿圈，那么就能在多项式时间内找到一个哈密尔顿圈（删边）

在此再谈P和NP：

我们知道有些问题是可以从搜索问题规约到判断问题的，也就是所该问题如果能在多项式内判断，那么久能在多项式中搜索到，那么我们只需要说，这个判断问题能在多项式时间内求解，就叫做P问题，也就是上图红字的意思；那NP问题呢，必须要给出一个解的实例，判断的是这个实例是否满足求解问题，这个才是上图中的红字。比如，我如果能在多项式时间内判断哈密尔顿圈是否（Yes/No）存在，那这个就是ploy-time algorithm，如果我给出了一系列点，能过多项式时间内判断这些点能否构成哈密尔顿圈，那这个就是poly-time certifier。

构造：把一个点拆分成三个点。

构造：（下面两个图要连在一起看）

从行的角度看，一行代表一个变量；从列的角度来看，每三列代表一个句子。两边中一边是两个点，一边是一个点，所以有k个句子的话，每一行有3k+3个节点。从哈密尔顿圈的答案转到3SAT的答案看这个圈在每一行是从左到右还是从右到左。

子集和问题：给一个集合S，问是否能在集合中选取元素，使得总和为W。

构造：如下图，按照前六行和前三列进行分割，可以分成4部分，其中1,3,4部分是固定的，即在第一部分，变量v列和 变量为v（包括变量及取反）的行对应的格子为0，其余为0；第三部分全为0；第四部分按照12依次写下来。第二部分，如果Ci句子中有变量v，则记为1，因为一个句子只有三个变量，可以简单通过第二部分每一列和为3进行判定。此时集合已经构造出来，W为111444，与上面的规约相似，可以通过3SAT的简单性质进行感性的认知。

近似的想法很简单，要解决一个问题，我们希望能够做到①求解结果是最优的 ②在多项式时间内解决 ③对于任意的实例都能够通过该算法解决。现在对于部分问题，无法完全满足以上要求，所以就牺牲了①，但是我们希望结果不是盲目的，所以就引入了近似的概念。

近似算法。比如2-近似，认为W为近似解，W 为最优解，在求最小值的情况下W<=2W ；在求最大值的情况下，W>=1/2W

给m个机器和n个任务，每个任务有一个ti的执行时间，我们认为完成最后一个任务所需的时间为负载时间，希望能够让这个负载时间最短。

第一种：将任务依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

证明：

引理1最短时间安排是大于等于任务中时间最长的任务，L >= max tj

我们在考虑放入最后一个任务前，根据我们放置的规则，该机器是耗时最短，也就是说，该机器此时的用时是低于除掉最后一个任务后的平均时长，更低于所有任务的平均时长（引理2）；再根据引理1，最后一个任务应该是小于最优解的。

补充：

在这里，我还想讨论一下这个近似算法的中等于符号，先上结论：等号不一定能够找到一个实例，但是可以构造出一种结构，通过取极限求得，我们认为这样 也算是紧的。

构造实例：有m个机器，其中m(m-1)个任务的用时为1，1个任务的用时为m。肯定有一种任务集合，可以按照以下方式进行安排，此时的贪心解为19。

此时最佳的解为10，如下图：

通过推广可以知道此时的比为（2m-1）/m，当m取极限，能够达到2倍。

第二种：将任务从大到小排序，然后依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

引理3：如果有大于m个任务，那么L>=2t(m-1)。证明：t(m+1)是目前最短的任务，且目前所有机器上都有任务了，所以该任务加入时最优的情况不过是加入设备的原有任务刚好和t(m+1)相等，即等号。

（2近似）在n个点中，选取k个中心点，使得这些中心点能够以半径R的圆包含所有的点，让其中最大的半径最小，如下图所示：

基础：距离需要满足的三个定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)

r(C)为C集合中所有点的最大覆盖半径。（需要求min r(C)）

算法：在点集中任选一个作为中心点，然后重复以下步骤k-1次:选取距离已选点集中最远的点，加入点集。

证明：先假设r(C )< 1/2 r(C)以选好的点画半径为1/2 r(C)的圆，显然可知[注]，这个圆里有且仅有一个r(C )中的点。那么根据在下图中，根据三角不等式可以得出：

[注]在每个点上r(c )一定会包含到c点，而r(C )<1/2 r(C)，相当于大圆套小圆，所以c一定在c的圆中。

（2近似）问题还是很好理解的，在点上加权值，要找一个点覆盖，使得权值最小。如下图左边就是一个带权的最小点覆盖。

算法： 任选一条边(i, j)加上代价，这个代价从零开始，且这个代价的最大值低于i和j节点的权值。显然，这个边权值的最大值取决于两个端点权值的最小值，我们认为当边权值与点权值相等时，对应的那个点是紧的。把所有紧的点找出来即为点覆盖。

流程：

证明：

引理：边权之和小于等于点覆盖的点权之和。这主要是由于涉及到一条边上两个点都被选（紧的）的情况，感性认知可以看上图，缩放证明如下：

w(S)是等于所选的节点的权值之和的，等于所选节点节点所对应的边权之和，可以把它放大到所有节点对应边权之和，这样因为一条边(u, v)在u上算过一次后还要在v上算一次，所以等于边权和的两倍。再由上面引理可得。

主要为了线性规划和整数规划。

（2近似）没啥好说的，只需要把方程构造出来就行了。

由于求解出来结果不一定是整数，所以我们认为某一点的值大于1/2，就选入点集。

证明：

因为xi+xj >=1,且都是正数，那必至少一个点是大于1/2的（反证，两个都小于1/2则和小于1）。

给你n个物品和一个背包，每个物品有一个价值v和一个大小w，背包的容量是W，要求让背包装下尽可能大价值。

背包的时间复杂度：O(nW)

注意其中n表示物品的个数，无论是1个还是999个，他都是多项式的，这个很好理解。但是W就不一样了，这是一个数字。我理解的是这个数字会很奇特，比如100001，比如99999，这些有可能看起来不大但是实际在处理的时候很难处理的数字，统一的来说，如果我们把这些数字放在电脑上，都会以二进制的方式存储起来，有些数字用十进制表示很小，但是放在二进制上面就会很大，由W导致不能在多项式时间内解决（找不到一个范围/上界来框它）。

算法： 为了处理这个问题，我们改动了dp的状态转移方程，要让这个转移方程和W无关[注]。

此时还不是多项式的，然后我们再对value进行约。[注]

[注]这两步中，我们把w改成v，并对v进行近似处理。OPT的含义变成了，在面对是否选择第i个物品时，要想让价值达到当前值，最少的weight。理由是更改后的误差是可以忍受的：对v进行近似，结果只会出现最大价值的上下误差，如果对w进行近似，则有可能出现该物品不能放入背包中，导致整个物品直接放弃的情况。

LRU(最近最少使用算法) / MRU(最近最常使用算法)

LRU算法(Least recently used)的基本概念是:当内存的剩余的可用空间不够时,缓冲区尽可能的先保留使用者最常使用的数据,换句话说就是优先清除”较不常使用的数据”,并释放其空间之所以”较不常使用的数据”要用引号是因为这里判断所谓的较不常使用的标准是人为的、不严格的

MRU算法(Most recently used)的意义正好和LRU算法相反

LRU与MRU两者在缓冲区工作机制中的作用和区别

看一下Oracle 9i Cache对LRU和MRU的使用，看看LRU与MRU两者在缓冲区工作机制中的作用和区别:

在Oracle 9i中有LRU List的概念: 我们可以把LRU List想象成是一连串的缓冲区集合,两端分别是LRU端和MRU端, 当数据库从磁盘上读取数据放入缓冲区时,系统必须先确定缓冲区中有free buffers,这个时候Oracle 9i会扫描LRU List,扫描的基本原则是:

1 从LRU端到MRU端;

2 当扫描到free buffer或已扫描的缓冲区数目超过临界值时,就会停止扫描动作;

如果在扫描过程顺利的在LRU List中找到了free buffer,那么Oracle 9i就把从磁盘读出的数据写到free buffer中然后把free buffer加到LRU List的MRU端

那如果扫描过程没有在LRU List中找到free buffer怎么办当然是从LRU List的LRU端开始清除缓冲区,如此一来就可以腾出新的空间了

Oracle 9i Cache对LRU和MRU的使用例子

使用者查询数据A,初始的时候LRU List中没有数据A,于是Oracle 9i到磁盘读取A,然后放到LRU List的MRU端,使用者再从LRU List中读取数据A,同理对于B,C…当LRU List满了以后,如果使用者查询N,此时N不在LRU List中而且LRU List中已经没有free buffer了,此时Oracle 9i就开始从LRU端淘汰A以腾出空间存放N

我们再来看另外一种情况:

在State 3之后,恰好使用者持续的查询A—这将会导致A一直被放置在靠近MRU端的缓冲区,结果将如图State m’所示,你会发现图2的State m’与图1的State m缓冲区存放的数据完全一样但是存放位置不一样此时LRU List满了,如果再放N的时候LRU List`淘汰的是B,因为A的查询率高于B,所以LRU List让A在缓冲区中呆上较长的时间而先淘汰掉”较不常用的”的B

Datebase Buffer Cache由3部分组成: Dirty buffers,Free buffers,Pinned Buffers

Dirty buffers 是表示 block被读到sga中后被修改过，还没有写入数据文件

Free buffers 是表示可以被覆盖的，也就是不包含未写入数据文件的数据

Pinned Buffers 表示该 buffer 目前正被进程使用，这个使用可能是正在这个buffer上读也可能是正在修改，这个buffer在被标志为pinned之前可能是 dirty的也可能是free的，一个buffer在同一时刻只能由一个进程访问（9i有改进 读/读 可以同时进行）

这是从不同的角度去描述buffer的状态的

数据依赖，数学概念，是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系，数据依赖是现实世界属性间相互联系的抽象，属于数据内在的性质。在计算机科学中，数据依赖是指一种状态，当程序结构导致数据引用之前处理过的数据时的状态。在编译学中，数据依赖是数据分析的一部分。

中文名

数据依赖

外文名

Data dependence

定义

数学概念

体现

体现出来的数据间的相互关系

位置

数据分析的一部分

数学定义计算机学定义种类数据库中的数据依赖TA说

数学定义

定义：设有一关系模式R（A1,A2,…,An),X和Y均为（A1,A2,…,An)的子集，对于R的值r来说，当其中任意两个元组u,v中对应于X的那些属性分量的值均相等时，则有u,v中对应于Y的那些属性分量的值也相等，称X函数决定Y，或Y依赖于X，记为X->Y[1]。

例：有关系，学生（学号S#，姓名SN，系名SD），子集X（学号S#），子集Y（系名SD）。

每个学生有唯一的一个学号，学生中可以有重名的姓名，每个学生只能属于一个系，每个系有唯一的系代号。有此，可以找出学生关系模式中存在下列函数依赖：

S#->SN；S#->SD

例：有关系，学校简况(学号S#，系名SD，系主任MN，课程CN，成绩G)。可写出函数依赖：

S#->SD；SD->MN；S#,CN->G

根据函数依赖的不同性质，函数依赖可分为完全函数依赖、部分函数依赖和传递函数依赖。

22 完全函数依赖

定义：在R(U)中，如果X->Y，对于X的任意一个真子集X’,都有X’不能决定Y，则称Y对X完全函数依赖，记为XY 。

例：（S#,CN）->G

23 部分函数依赖

定义：在R(U)中，如果X-> Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖。

24 传递函数依赖

定义：在R(U)中，当且仅当X-> Y，Y->Z时，称Z对X传递函数依赖。

例：描述学生（S#）、班级（SB）、辅导员（TN）的关系U(S#,SB,TN)。一个班有若干学生，一个学生只属于一个班，一个班只有一个辅导员，但一个辅导员负责几个班。根据现实世界可得到一组函数依赖：

F={S#->SB，SB->TN}

学生学号决定了所在班级，所在班级决定了辅导员，所以辅导员TN传递函数依赖于学生学号S#。

数据依赖还包括多值依赖和连接依赖两种形式。

--------------------------------------------------------------------------------------------------

计算机学定义

数据依赖是指一种状态，当程序结构导致数据引用之前处理过的数据时的状态。在编译学中，数据依赖是数据分析的一部分。

解说：假设有如下表述S1和S2，

(I (S1) ∩ O(S2)) ∪ (O(S1) ∩ I(S2)) ∪ (O(S1) ∩ O(S2)) ≠ Φ

那么S2依赖S1。I（Si）是内存位置的集合，可由Si和S2读

O（Sj）是内存地址的集合，由Sj写，

则这里S1和S2就有一个必须遵守的执行顺序。

种类

数据依赖有三种，

1 流依赖（flow dependency)，一个变量在一次表达式中赋值或修改然后用在后来的另一个表达式中。例

a=bc

d=a-e

2反依赖（anti dependency)，一个变量在一个表达式中被使用然后在后来一个表达式中被修改赋值。例

a=bc

b=d+e

3输出依赖，一个变量在一表达式中被修改赋值然后又在后来另一个表达式中被修改值，例

a=b+c

a=d-e

数据库中的数据依赖

数据依赖是数据之间的相互制约关系，是一种语义体现，主要分为函数依赖（FD）、多值依赖（MVD）和连接依赖（JD）[2]。

函数依赖

两个实例化的属性集X,Y，如果属性集X中的两个元组取值相同，必有对应的另外一个属性集Y中元组取值相同，则称Y函数依赖于X函数。

特别值得注意的是，如果属性集X中不存在两个取值相同的元组集合，则Y必定依赖于函数X，且函数X的属性集为超键。

平凡函数依赖和非平凡函数依赖。平凡函数依赖：如果Y依赖于X，同时Y是X的子集，那么称X -> Y 为平凡函数依赖；非平凡函数依赖：Y不是X的子集。对于任意关系模式而言，平凡函数依赖是必然成立的，其并不反映新的语义特征，因此我们一般不讨论平凡函数依赖。

完全函数依赖和部分函数依赖。完全函数依赖表示的就是函数X的属性集构成了候选键。其中形式化的表示就是如果对于X的任何一个子集Z，都有Y不依赖于Z，则称Y完全函数依赖于X。如果Y不完全函数依赖于X，则称Y部分函数依赖于X。完全函数依赖的左部构成主键，不包含冗余的属性。

传递函数依赖和直接函数依赖。如果Y函数依赖于X，Z函数依赖于Y，其Y不是X的子集，X不依赖于Y，则称Z传递依赖于X，否则称Z直接函数依赖于X。

函数依赖的逻辑蕴涵。

，即对于关系模式上的函数依赖集合F，只要X→Y是一个函数依赖，那么必然可以推导认为F逻辑蕴涵X→Y。

函数依赖集合的闭包。由函数依赖集合F所逻辑蕴涵的全部函数依赖所构成的集合称之为F的闭包。

。闭包的性质：1 F 属于 F+，这是因为根据闭包的定义F中的每个函数依赖必定也在中F+；2 (F+)+=F+，该性质说明闭包运算是幂等的，即F经过任意多次的闭包运算后其结果仍然等于F+；3如果F=F+，则称F是完备的。

编辑

传视频

TA说

目录

在

sql运行问题？

数据库运行过程中常见的故障有3类：事物故障、系统故障、介质故障。

恢复策略：

1、事物故障：

发生事务故障时，被迫中断的事务可能已对数据库进行丁修改，为了消除该事务对数据库的影响，要利用日志文件中所记载的信息，强行回滚该事务，将数据库恢复到修改前的初始状态。

为此，要检查日志文件中由这些事务所引起的发生变化的记录，取消这些没有完成的事务所做的一切改变，这类恢复 *** 作称为事务撤销。

2、系统故障：

系统故障的恢复要完成两方面的工作，既要撤销所有末完成的事务，还要重做所有已提交的事务，这样才能将数据库真正恢复到一致的状态。

3、介质故障：

介质故障比事务故障和系统故障发生的可能性要小，但这是最严重的一种故障，破坏性很大，磁盘上的物理数据和日志文件可能被破坏，这需要装入发生介质故障前最新的后备数据库副本，然后利用日志文件重做该副本后所运行的所有事务。

“数据故障恢复”和“完整性约束”、“并e799bee5baa6e4b893e5b19e31333431353364发控制”一样，都是数据库数据保护机制中的一种完整性控制。所有的系统都免不了会发生故障，有可能是硬件失灵，有可能是软件系统崩溃，也有可能是其他外界的原因，比如断电等等。

数据库运行的突然中断会使数据库处在一个错误的状态，而且故障排除后没有办法让系统精确地从断点继续执行下去。这就要求DBMS要有一套故障后的数据恢复机构，保证数据库能够回复到一致的、正确地状态去。

关于数据库安全及其防范方案的分析

随着网络的不断发展，数据的共享日益加强，数据的安全保密越来越重要。为了计算机数据库整体安全性的控制，需要做好很多细节性的工作，并根据具体应用环境的安全需要来分析安全薄弱环节，并制定统一的安全管理策略加以实施，以保证其最高的安全性。

1数据库安全环境的分析

随着时代的发展，我国的计算机信息安全标准也在不断提升。在当下的数据库系统安全控制模块中，我国数据库安全分为不同的等级。但是总体来说，我国的数据库安全性是比较低的，这归结于我国数据技术体系的落后。为了更好的健全计算机数据库体系，进行数据库安全体系的研究是必要的。我国现有的一系列数据安全理论是落后于发达国家的。这体现在很多的应用领域，比如电力领域、金融领域、保险领域等。很多软件都是因为其比较缺乏安全性而得不到较大范围的应用，归根结底是数据库安全性级别比较低。

为了满足现阶段数据库安全工作的需要，进行相关标准的深化研究是必要的。这需要对数据库安全进行首要考虑，且需要考虑到方方面面，才更有利于数据库保密性的控制，从而保证这些数据存储与调用的一致性。

在当前数据库安全控制过程中，首先需要对这些数据进行可用性的分析，从而有利于避免数据库遭到破坏，更有利于进行数据库的损坏控制及其修复。其次为了保证数据库的安全性、效益性，也离不开对数据库整体安全性方案的应用。最后必须对数据库进行的一切 *** 作进行跟踪记录，以实现对修改和访问数据库的用户进行追踪，从而方便追查并防止非法用户对数据库进行 *** 作。

2数据库安全策略的更新

为了满足现阶段数据库安全性方案的应用，进行身份的鉴别是必要的。所谓的身份鉴别就是进行真实身份及其验证身份的配比，这样可以避免欺诈及其假冒行为的发生。身份鉴别模式的应用，表现在用户使用计算机系统进行资源访问时。当然在一些特定情况下，也要进行身份鉴别，比如对某些稀缺资源的访问。

身份鉴别通常情况下可以采用以下三种方法：一是通过只有被鉴别人自己才知道的信息进行鉴别，如密码、私有密钥等；二是通过只有被鉴别人才拥有的信物进行鉴别，如IC卡、护照等；三是通过被鉴别人才具有的生理或者行为特征等来进行鉴别，如指纹、笔迹等。

在当前访问控制模块中，除了进行身份鉴别模式的应用外，还需要进行信息资源的访问及其控制，这样更有利于不同身份用户的权限分配。这就需要进行访问级别的控制，针对各个系统的内部数据进行 *** 作权限的控制，进行自主性及其非自主性访问的控制，满足数据库的安全需要。实现用户对数据库访问权限进行控制，让所有的用户只能访问自己有权限使用的数据。当某一个用户具有对某些数据进行访问的权限时，他还可以把对这些数据的 *** 作权限部分或者全部的转移给其他用户，这样其他的用户也获得了对这些数据的访问权。

为了更好的进行数据库的安全管理，审计功能的应用也必不可少。这需要就数据库的数据进行统一性的 *** 作。这样管理员更加方便对数据库应用情况进行控制，审计功能也有利于对数据库的 *** 作行为进行控制，更有利于控制用户对数据库的访问。攻击检测是通过升级信息来分析系统的内部和外部所有对数据库的攻击企图，把当时的攻击现场进行复原，对相关的攻击者进行处罚。通过这种方法，可以发现数据库系统的安全隐患，从而来改进以增加数据库系统的安全性。

在数据库数据处理过程中，可以进行一些合法查询模式的应用，当需要调取保密数据时，就需要应用推理分析模块。这是数据库安全性方案控制过程中的重难点，而通过这种简单的推理分析方法调取保密数据，是得不到有效解决的。但是我们可以使用以下几种方法来对这种推理进行控制：数据加密的基本思想就是改变符号的排列方式或按照某种规律进行替换，使得只有合法的用户才能理解得到的数据，其他非法的用户即使得到了数据也无法了解其内容。

通过对加密粒度的应用，更有利于进行数据库加密性的控制。其分为几种不同的应用类型等级。在当前应用模块中，需要进行数据保护级别的分析，进行适当的加密粒度的分析。更有利于满足数据库级别加密的需要。该加密技术的应用针对的是整体数据库，从而针对数据库内部的表格、资料等加密。采用这种加密粒度，加密的密钥数量较少，一个数据库只需要一个加密密钥，对于密钥的管理比较简单。但是，由于数据库中的数据能够被许多的用户和应用程序所共享，需要进行很多的数据处理，这将极大的降低服务器的运行效率，因此这种加密粒度只有在一些特定的情况下才使用。

表级加密也是比较常用的方法，这种方法应用于数据库内部的数据加密。针对具体的存储数据页面进行加密控制。这对于系统的运行效率的提升具备一定的帮助，不会影响系统的运行效率。这种方法需要应用到一些特殊工具进行处理，比如解释器、词法分析器等，进行核心模块的控制，进行数据库管理系统源代码的控制及其优化。但是其难以确保数据库管理系统的整体逻辑性，也存在缺陷。记录级加密；这种加密技术的加密粒度是表格中的每一条记录，对数据库中的每一条记录使用专门的函数来实现对数据的加密、解密。通过这种加密方法，加密的粒度更加小巧，具有更好的选择性和灵活性。字段级加密；这种加密技术的加密粒度是表格中的某一个或者几个字段。通过字段级的加密粒度只需要对表格中的敏感列的数据进行加密，而不需要对表格中的所有的数据进行加密。

选择加密算法也是比较常见的数据加密方法。它是数据加密的核心部分。对于数据库的整体安全性的控制具有直接性的影响。通过对加密算法的分析，得知其分为公共密钥加密及其对称加密。在数据加密模块中，需要进行密文及其明文的区分，从而进行明文及其密文的转换，也就是普遍意义上的密码。密码与密钥是两个不同的概念。后者仅是收发双方知道的信息。在数据加密技术中，对密钥进行管理主要包括以下几个方面，产生密钥。产生怎样的密钥主要取决于使用什么样的算法。若产生的密钥强度不一样就称这种算法实现的是非线性的密钥空间，若产生的密钥强度一样就称这种算法实现的是线性的密钥空间。分配密钥、传递密钥：分配密钥就是产生一个密钥并且将这个密钥分配给某个用户使用的过程。

密钥的传递分为不同的应用形式，集中式与分散式。所谓的集中式就是进行密钥整体式的传递；所谓的分散式就是对密钥的多个部分进行划分，以秘密的方法给用户进行传递。通过将整体方法与分散方法应用到存储模块中，更好的满足现阶段数据库整体安全性的需要。对于密钥的备份可以使用和对密钥进行分散存储一样的方式进行，以避免太多的人知道密钥；而销毁密钥需要有管理和仲裁机制，以防止用户对自己的 *** 作进行否认。

3结束语

随着计算机，特别是网络的不断发展，数据的共享日益加强，数据的安全保密越来越重要。本文详细阐述了数据库的安全防范，分别从数据分析、用户鉴别、访问权限控制、审计、数据加密等环节逐一剖析数据库安全。为了计算机数据库整体安全性的控制，需要做好很多细节性的工作，并根据具体应用环境的安全需要来分析安全薄弱环节，并制定统一的安全管理策略加以实施，以保证其最高的安全性。

createtablenews(---建一个名为news的表

newsidnumberprimarykey,----主键为newsid

titlevarchar2(20),----剩下的其他字段

contentvarchar2(1000),

createdatevarchar2(20)

);

createsequencenews_seq----创建一个时序

minvalue1----最小值1

maxvalue9999999----最大9999999

startwith1----从1开始

incrementby1----增减值1

nocache;

CreateOrReplaceTriggernews_tri--创建一个触发器

Beforeinsert---条件是执行insert之前触发

onstudent---下边的是触发字段和事件

foreachrow

begin

selectnews_seqNEXTVALinto:newnewsidfromal;

end;

自己找本sql的书，自己转。别人动手自己永远学不会

问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。

VertexSet approxVertexCover ( Graph g )

{ cset=NULL；

e1=ge；

while (e1 !=NULL) {

从e1中任取一条边(u,v)；

cset=cset∪{u,v}；

从e1中删去与u和v相关联的所有边；

}

return c

}

Cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。即e1为空。

图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。

以上就是关于算法基础全部的内容，包括:算法基础、数据库中什么是MRU、数据依赖左部是什么意思等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！