数据库复习大纲.doc

基本知识：45分，填空 、 简答1、 数据库的概念、发展过程及关系数据库的优点 1.数据库的概念P4：长期储存在计算机内、有组织、可共享的大量数据集合。（通常所称数据库指在数据库管理系统（DBMS）管理下的数据集合。） 2.数据管理技术的发展过程P6：人工管理阶段(1955s前) 文件系统阶段(1955s-1965s) 数据库系统阶段(1965s后) 3.关系数据库的优点P27：关系模型建立在严格的数学概念基础上；关系模型概念单一。联系均用“关系”表示，数据结构清晰，易懂易用，能快速响应查询要求。存取路径对用户透明，数据独立性、安全保密性好，简化了数据库开发建立。可用SQL语言表达查询，应用性强。易于维护。完整性约束降低数据冗余和数据不一致概率。2、 关系及关系模式的概念 1.关系(Relation)概念P25：表示实体的元数为K（K1）的元组的集合，只包含单一的数据结构。一张二维表格对应一个关系。表中的一行称为关系的一个元组；一列称为关系的一个属性。 2.关系模式(Relation Schema)概念P42：关系的描述。一个五元组：R(U,D,DOM,F) R: 关系名 U:组成该关系的属性名集合 D:属性组U中属性所来自的域 DOM:属性向域的映像集合 F:属性间数据的依赖关系集合3、 关系代数运算（包括除法）P49（数据模型三要素：结构、操作和约束） 关系代数运算能从给定的关系构建新的关系。关系代数不直接用于DBMS，但它是DBMS查询语言（如SQL）的内核，SQL就是为了表达关系代数内容的。 1.传统的集合运算：并、差、交、广义笛卡尔积P49 把关系看成是元组的集合（元组是关系的元素）；两个关系R、S，t表示元组。R、S满足： R、S必须具有相同属性集合，且对应属性数据类型必须一致。 集合操作前，R、S的属性顺序也必须一致。 （1）RS，由R或S中的元组组成的集合。 RS = t|tRtS 。 （2）RS，由既属于R又属于S的元组组成的集合。 RS = t|tRtS （3）RS， RS= RRS （4）笛卡尔积 2.专门的关系运算：选择、投影、连接、除P51 选择运算产生操作数R的元组的子集作为新的关系，新关系中的元组是R中那些满足给定的条件的元组。F是条件表达式，检查R中的每个元组，满足条件F的，加到结果关系中去，不满足的不在结果中。F(R) = t|tRF(t)= 真 投影运算是由操作数R产生一个新的关系，这个新关系仅保留R的某些列。用A(R)表示投影运算，A是属性集合。 tAi表示元组t中相应于属性Ai的一个分量。A(R) = tA|t R 投影操作去掉了操作对象的若干列，结果可能出现相同元组，将相同元组去掉。自然连接参与自然连接的两个关系R和S应有相同的属性（一个或多个）。自然连接的结果为笛卡尔积中，元组r和s在共同属性上取值相等的连串，即匹配成功的连串放入自然连接的结果集中。由于连串有共同的属性，在自然连接中，属性不再重复，只取其一。连接象集Z给定一个关系R（X，Z），X和Z为属性组。当tX=x时，x在R中的象集（Images Set）为：Zx=tZ|t R，tX=x 它表示R中属性组X上值为x的诸元组在Z上分量的集合。 除（Division）给定关系R (X，Y) 和S (Y，Z)，其中X，Y，Z为属性组。R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。R与S的除运算得到一个新的关系P(X)，P是R中满足下列条件的元组在X属性列上的投影：元组在X上分量值x的象集Yx包含S在Y上投影的集合。 Yx：x在R中的象集，x = trXRS = tr X | tr RY (S) Yx 查询的关系代数表达式4、 数据独立性的概念，逻辑/物理独立性 1.数据独立性的概念P30:数据库系统重要目标之一,使数据独立于应用程序。包括数据的物理独立性和逻辑独立性。 2.物理独立性P30:用户应用程序与数据库存储结构相互独立。当数据库存储结构改变，只需相应改变模式/内模式映像，模式、应用程序不必改变。 3.逻辑独立性P30:用户应用程序与数据库逻辑结构相互独立。当模式改变，只需相应改变外模式/模式的映像，外模式、应用程序不必改变。5、 完整性规则的概念，种类 1.完整性规则的概念P45：对关系的某种约束条件。即关系的值随时间变化时应满足一些约束条件（实际是现实世界的要求）。 2.完整性约束种类P45：实体完整性、参照完整性、用户定义的完整性。 实体完整性规则：若属性A是基本关系R的主属性，则属性A不能取空值设F是基本关系R的一个或一组属性，但不是关系R的码。如果F与基本关系S的主码Ks相对应，则称F是基本关系R的外码；基本关系R称为参照关系；基本关系S称为被参照关系或目标关系。 参照完整性规则：若属性（属性组）F是基本关系R的外码它与基本关系S的主码Ks相对应（基本关系R和S不一定是不同的关系），则对于R中每个元组在F上的值必须为：取空值（F的每个属性值均为空值）；或等于S中某个元组的主码值。 用户定义的完整性：针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求。六、码的概念，主码，外码。主属性，非主属性。P181 1.码：能唯一标识一个元组的属性集合。 码是关系中的一组属性（单个或多个属性组合），设置为码的属性取值在所有关系实例中不能相同。通常，设置一个人工属性来作为一个关系的码，如学生的学号。 2.主码：多个候选码（能唯一标识一个元组的最少的属性集合）中的一个码。 3.外码：一个关系中的一个属性是另一个关系中的主码，该属性是外码。关系模式R中属性（或属性组）X并非R的码，但X是另一个关系模式的码，则称X是R的外码。 4.主属性：包含在任何一个候选码中的属性。 5.非主属性：不包含在任何候选码中的属性。七、 数据库设计的几个阶段及每个阶段的输出。P209 1、需求分析阶段 输出数字字典、数据项、数据结构、数据流、数据存储的描述 2、概念结构设计阶段 输出概念模型（E-R图）、数据字典 3、逻辑结构设计阶段 输出数据模型 4、物理结构设计阶段 输出存储安排、存取方法选择、存储路径建立 5、数据库实施阶段 输出创建数据库模式、装入数据、数据库试运行 6、数据库运行和维护阶段 输出性能监测、转储/恢复、数据库重组和重构八、 规范化的概念，函数依赖的相关概念 1.规范化：改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。一低一级范式的关系通过模式分解转换为若干高一级范式的关系模式的集合的过程叫规范化。 2.函数依赖 平凡函数依赖与非平凡函数依赖 完全函数依赖与部分函数依赖 传递函数依赖9、 数据在磁盘中的存储及磁盘访问的时间构成P390 1.存储级别 缓存(cache):高速缓存，一般计算机配有1M或更多容量的缓存。当数据或指令要送到处理器时，先从内存移到缓存。访问时间为几纳秒。 主存(memory):内存，计算机主要存储器，指令和数据均需在此驻留。从内存向缓存或处理器移动的时间为10-100纳秒。 外存(secondary storage):典型的外存是磁盘，一般单个磁盘的存储容量达到T字节，在磁盘与内存间传递单个字节约需10毫秒，但大量字节可同时传递。 三级存储(tertiary storage):DVD，磁盘阵列等，可能用到机械手和传送带等设备。 虚拟内存(virtual memory):操作系统制造的产物，在外存中开辟一个区域当成内存用。 2.磁盘访问特点 访问一个数据块分三个步骤： 磁盘控制器将磁头移动到指定扇区所在的柱面，延迟时间称为寻道时间（seek time)，一般需要10毫秒； 磁盘控制器将第一个要访问的扇区旋转到磁头下，延迟时间称为旋转延迟时间（rotational latency)。一般需要8毫秒; 所有要访问的扇区通过磁头，磁盘控制器读或写这些扇区，时间称为传输时间（transfer time),一般需要0.5毫秒。 寻道时间+旋转时间+传输时间=磁盘访问时间十、事务的概念及特性 1.事务的概念P293：用户定义的一个数据库操作序列，这些操作只能全做或全不做，是不可分割的工作单位。 COMMIT：提交，将事务中所有对数据库的更新写回到磁盘上的物理数据库中。 ROLLBACK：回滚，系统将事务中对数据库的所有已完成的操作全部撤销，回滚到事务开始时的状态。 2.事务的ACID特性P294：原子性：事务是数据库的逻辑工作单位，操作要么全做，要么不做。 一致性：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。 隔离性：一个事务的执行不能被其他事务干扰。 持续性（永久性）：事务一旦提交，对于数据库中的数据的改变是永久性的。 保证事务ACID特性是事务处理的任务。11、 数据转储的概念及种类 1.数据转储的概念P297：数据库恢复中采用的基本技术。转储即管理员定期将整个数据库复制到磁带、磁盘或其他存储介质上保存起来的过程。 2.数据转储的种类P298：转储方式转储状态动态转储静态转储海量转储动态海量转储静态海量转储增量转储动态增量转储静态增量转储 静态转储：系统中无运行事务时转储。 实现简单。 降低了数据库的可用性。（转储必须等用户事务结束；新的事务必须等转储结束。） 动态转储：转储期间允许对数据库存取、修改。 不用等待正在运行的用户事务结束；不会影响新事务的运行。 不能保证副本中的数据正确有效。 海量转储：每次转储全部数据库。 增量转储：每次只转储上次转储后更新的数据。 从恢复角度看，使用海量转储得到的后备副本进行恢复更方便；但若数据库很大，事务处理十分频繁，则增量转储方式更实用更有效。12、 日志文件的作用和内容 1.日志文件的作用P299：用于事务故障恢复和系统故障恢复。在动态转储方式中，后备副本和日志文件结合以有效恢复数据库。在静态转储方式中，数据库毁坏后可重新装入后援副本把数据库恢复到转储结束时刻的正确状态，再利用日志文件重做处理已完成事务，撤销故障发生时尚未完成的事务。 2.日志文件的内容P299：事务标识（标明是哪个事务）、操作类型（插、删、改）、操作对象（记录内部表示）、更新前数据旧值（对插入操作，此项为空值）、更新后数据新值（对删除操作，此项为空值）。 对于以数据块为单位的日志文件，内容包括事务标识、被更新的数据块。13、 封锁及种类，死锁及死锁的预防、发生死锁的处理。 1.封锁的概念P312：实现并发控制的重要技术。事务T在对某个数据对象（表、记录）操作前，先向系统发出请求，对其加锁。加锁后事务T对该数据对象有一定的控制，在释放锁前，其他事务不能更新此数据对象。 2.封锁的种类P312：排他锁、共享锁。 排他锁：写锁X。T加锁后，只允许T修改，其他事务均不可对该数据对象再加锁。保证其他事务在T释放锁前不能再读取、修改该数据对象。 共享锁：读锁S。T加锁后，T只可读取但不能修改该数据对象。其他事务只能加S锁，不能加X锁。保证其他事务可以读取该数据对象，但在T释放锁前不能对该数据对象做修改。 3.死锁的形成P315：事务T1在等待T2，而T2又在等待T1，T1、T2两个事务永远不能结束。 4.死锁的预防P315：一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁，否则不继续执行。会降低系统并发度。顺序封锁法：预先对数据对象规定封锁顺序，所有事物按顺序实施封锁。维护顺序苦难，成本高；难以事先确认每一事务封锁对象。 5.发生死锁的处理P316： 诊断：超时法：如果事务等待时间超过规定时限，认为发生死锁。 等待图法：事务等待图动态反映事务等待情况。并发控制子系统周期性生成事务等待图，进行检测。若图中存在回路，则认为发生死锁。 解除：选择一个处理死锁代价最小的事务，撤销，释放此事务的所有锁，使其他事务得以继续运行，并恢复撤销的事务所执行的数据修改操作。 14、 并发及事务并发带来的数据不一致问题 1.并发概念：单处理机系统中，一时间段中多个事务都处于开始执行到执行完毕之间，轮流交叉运行的过程。 能够减少处理机的空闲时间，提高系统的效率。 2.并发带来的数据不一致性 丢失修改：两事务T1、T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。 不可重复读：事务T1读取数据后，事务T2 执行更新操作，使T1无法再现前一次读取结果。 读“脏”数据：事务T1修改某一数据并将其写回磁盘，事务T2读取同一数据后，T1 由于某种原因被撤销，这时被T1修改过的数据恢复原值，T2读到的数据就与数据库中数据不一致，则T2读取数据不正确。 原因:并发操作破坏了事务的隔离性。十五、三级封锁协议P313：在一级封锁协议基础上增加事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。十六、并发调度、正确的并发调度判别 1.可串行化调度：几个事务的并行执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。可串行性是并行事务正确性的唯一准则。 2.保证并发操作调度正确性的方法 封锁方法：两段锁（Two-Phase Locking，简称2PL）协议 时标方法 乐观方法十七、两段锁协议P319：事务分两阶段，第一阶段获得封锁，也称扩展阶段，事务可以申请获得任何数据项上任何类型的锁，但不能释放任何锁；第二阶段释放封锁，也称收缩阶段，事务可以释放任何数据项上任何类型的锁，但不能再申请任何锁。应用题：55分关系运算：会计算关系的选择、投影、连接和除法。（15）SQL语言的运用（20）给出关系数据库（含多个表），根据操作要求写出正确的SQL语句。含SQL语言的单表查询、多表查询，聚集函数的应用（求和、平均值、计数、最大最小值），分组查询，嵌套查询。表的插入、修改和删除操作。权限的授予和回收。 关系数据理论（20）一、掌握函数依赖的概念及推导规则，会求解属性集合的闭包 1.函数依赖规则 依据函数依赖规则，可从已知函数依赖集合推导出新的函数依赖。 Armstrong推理规则：A1.自反律（Reflexivity）：若Y X ，则X Y A2.增广律（Augmentation）：若XY, 则XZYZ A3.传递律（Transitivity）：若XY及YZ，则XZ 2.导出的规则 根据A1，A2，A3，得：合并规则：由XY，XZ，有XYZ。（A2，A3） 伪传递规则：由XY，WYZ，有XWZ。（A2，A3） 分解规则：由XY及 ZY，有XZ。（A1，A3） 3.求属性集合闭包的算法 算法 求属性集X（X U）关于U上的函数依赖集F 的闭包XF+ 输入：X，F 输出：XF+ 步骤：（1）令S（0）=X，i=0 （2）搜索F，找B C，B为S的子集，C 不在S中，令 S（ i+1）=CS（i） （3）重复第二步，直到再没有C加入到S中。S即为XF+2、 掌握求解最小函数依赖集的方法 求解F的最小函数依赖集：依据最小函数依赖集的特征分三步对F进行“最小化处理”，找出F的一个最小依赖集。 (1)利用分解规则，将函数依赖的右部属性单一化。 逐一检查F中各函数依赖FDi：XY，若Y=A1A2 Ak，k 2， 则用 XAj |j=1，2， k 来取代XY。 (2)去掉多余的函数依赖 逐一检查F中各函数依赖FDi：XA，令G=F-XA，若AXG+， 则从F中去掉此函数依赖。 (3)左部最简 逐一取出F中左部为多属性（不止一个）的函数依赖FDi：XA， 设X=B1B2Bm，逐一考查Bi （i=l，2，m）， 若A （X-Bi ）F+ ， 则以X-Bi 取代X。 注：函数依赖“最小化”过程的每一步都是等价变换三、会求码；给定关系R（U，F），可求得R的码。简便方法。 1、求F的最小函数依赖集Fmin，替换F; 2、属性分组， L类：F中仅出现左部的属性； R类：F中仅出现右部的属性； LR类：F中既出现在左部又出现在右部的属性； N类：不出现在F中的属性。 3、若A为L类属性或者N类属性，则A必是构成码的属性，即码的成员。 4、考察L类和N类属性，设X为L类属性和N类属性的并，如果XU，则X是R的码，且是唯一码。 5、如果X U，或X为，则需依照码的定义逐个考察LR类属性，将LR类逐个并到X中，确定是不是码(按照定义求解) 6、R类属性为非主属性，不是码的成员。 四、会判断范式级别：三个步骤（表的关键字属性间的依赖关系不同级别的范式要求判断结果），要求掌握1NF、2NF、3NF、BCNF（函数依赖范围内的范式） 1NF：关系模式的基本要求，关系模式的都需要符合1NF，1NF规定关系实例中每个元组分量的取值必须是原子值。 2NF：若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。 例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NF SLC(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF 第三范式（3NF） 任一关系均可实现既无损连接又保持函数依赖的3NF分解，算法如下：给定R（U，F），（1）求解F的最小函数依赖集G （2）求出R的所有码 （3）分组；按左部相同的原则，将G中的函数依赖分组，设为F1,F2,Fk, F1,F2,Fk中出现的属性各为R1,R2,Rk。 （4）吸收；在R1,R2,Rk中，若存在Ri包含Rj，则Ri吸收Rj。 （5）若R1,R2,Rk中有一个包含码，则R1,R2,Rk为R的既无损连接又保持函数依赖