注该总结只包含概念、定义和知识点.docx

注：该总结只包含概念、定义和知识点。关系代数、元组关系演算、域关系演算、SQL、XQuery、事务协议一大坨、范式模式分解Armstrong公理那一大坨，这里面都只有个大概，卤煮是考完了明确地讲，只看这个是【有可能】及格的。TAT 一、概论数据库系统的特点：1. 面向整体的复杂数据结构2. 数据冗余小，易扩充3. 数据和程序的独立性：物理数据独立性、逻辑数据独立性4. 统一的数据控制功能：安全性保护、完整性控制、并发控制5. 最小存取单位：数据项数据抽象层次：物理层-逻辑层-视图层数据库规划：模式物理模式-逻辑模式-子模式嵌入式数据库语言：预编译方式、函数调用方式数据模型三要素：数据结构、数据操作、数据的约束条件ER模型、层次模型、网状模型、关系模型数据库用户：最终用户、应用程序员、系统分析员、DBA数据库应用的开发步骤： 定义需求 定义包含应用所需要的数据和数据之间的关系 定义数据之上的完整性约束 定义关系数据库的模式描述 创建和生成数据库 编写应用程序，实现用户界面二、关系模型域：相同数据类型的值的集合关系的性质：1. 列的同质性2. 行的无序性3. 元组的唯一性属性属性域：允许的取值集合原子属性、多值属性、复合属性码超码：唯一性候选码：唯一性、最小性主属性（包含在任一候选码中）主码：指定的候选码外码：外部引用为主码关系模式关系的型：关系名、关系中的属性名、属性向域的映象、属性间的数据依赖关系等关系操作集合操作：关系代数、关系演算（等价的）关系模型的完整性实体完整性：主码属性值不能为null参照完整性：外码的外部主码引用必须存在（外码属性值可以为null）用户定义的完整性：自定义的查询语言分类：过程性、非过程性（描述性）纯语言：关系代数、元组关系演算、域关系演算实际语言：SQL（介于关系代数和关系演算之间）关系代数：过程性6个基本操作：一元（选择、投影、更名）、二元（并、差、笛卡尔积）运算封闭性：两个或以上关系一个关系外连接：一方加空行，另一方不失配视图不属于概念模型，但是为用户所见的虚拟关系优点：个性化服务、安全性、逻辑独立性（内外模式）数据库中仅保存视图定义，用时计算更新视图可能遇到问题：主码信息缺失、连接属性信息缺失直接依赖、依赖、依赖路径、递归的视图定义物化视图元组关系演算形式化定义： t | P（t），P是公式，定义同数逻安全的表达式：结果全部来自P的域dom(P) which def as 显式出现在P中的值+P中关系的元组的值域关系演算非过程性语言形式化定义： x1, x2, , xn | P(x1, x2, , xn)SQL特点：1. 一体化（QL、DDL、DML、DCL）2. 面向集合操作：一次一集合3. 非过程化4. 两种使用方式：自含式、嵌入式5. 简洁易学功能：DML数据操纵：select、insert、update、deleteDDL数据定义：create、alter、dropDCL数据控制：grant、revoke数据查询：嵌套查询、复杂查询、递归查询事务Commit、rollback数据定义语言DDL 关系的模式 关联每个属性的值域 完整性约束 关系中的索引 关系的安全性和权限信息 关系在磁盘上的物理存储结构索引显式创建：显式：create unique cluster index 索引名 on 表名 (列名 asc/desc , 列名asc/desc)隐式：通过定义 PRIMARY KEY 或 UNIQUE 约束由系统自动创建索引删除：drop index 索引名作用：1. 提高查询速度2. 实现数据约束3. 降低更新、增加、删除效率特点：1. 动态的：随时建立删除2. 连接频率高的表应该索引3. 一个表可以多个索引存储过程存储在数据库中的编译好的程序。语言：SQL或C等特点：1. 安全性2. 性能3. 可维护性4. 扩展数据库系统功能5. 开发复杂性嵌入式SQL宿主语言 预编译宿主变量执行方式差别：一次一集合、一次一记录游标分类：滚动、非滚动、更新游标使用流程：声明游标declare-打开游标open-检索游标fetch-关闭游标close-释放游标free缺点：1. 预编译后的程序调试代价高2. 预编译器随数据库变化而变化另一种方法：过程库，向数据库发送SQL，彻底分离SQL和编程语言动态SQL：支持参数ODBC：只能查询JDBC：跨平台；update、增删Prepared语句：查询编译一次，用不同参数执行多次优点：易使用，不需要预编译缺点：需要动态绑定，执行效率低其他语言：Datalog、QBE完整性1. 域约束：create domain blabla datatype constraint xxx check(expr)2. 引用完整性：ER中引用完整性：联系集的外码。插入删除：拒绝或级联外码类型：CASCADE级联（refer xxx on delete cascade）、RESTRICT拒绝、SET NULL/DEFAULT事务的中间过程允许违反完整性3. 断言：create assertion check 数据库范围。Not exists常用4. 触发器：event condition action触发粒度：行触发器（受影响的元组）for each row 语句触发器（特定的语句执行之后）for each statement使用reference old/new table；当SQL作用于多条记录时更高效优点：实现数据一致性，完成数据库操作的审计缺点：很难优化、聚合性和可终止性判定较难安全性1. 安全性控制层次：物理、操作系统、网络、数据库方法：存取访问控制（DAC自主访问控制、MAC强制）、视图、审计、加密、鉴权DBA：grant、revoke（DAC）、设置安全标签（MAC）2. 授权授权图：删除用户U权限时，删除U的入边和所有出边权限：数据访问权限：Read、insert、update、delete都是保守的数据模式权限：index增删、resources建表后全部权限alteration增删属性drop删表grant 表级权限 on 表名 | 视图名 to 用户 with grant option，select和update可指定列revoke 表级权限 on 表名 | 视图名 from 用户 ，用户 | public结合视图实现细粒度访问控制基于角色的安全访问控制：节省grantsMAC：更安全，安全级别细到元组（TS，S，C，U）统计数据库的推导问题加密、鉴权（避免传递密码）、审计（建立操作记录但降低执行效率）数据库设计需求分析-概念数据库设计(ER model)-逻辑数据库设计-模式细化-物理数据库设计-安全设计概念数据模型按用户的观点对数据和信息建模，强调语义表达能力，如ER模型ER模型实体和联系；定义数据库的全局逻辑结构；语义模型实体、实体集（类似实体构成的集合）、属性（赋予某个实体集）、域实体：（属性，数据值）对的集合。实体型、实体值属性：简单属性、复合属性（分层）、单值属性、多值属性（多元组）、基属性/派生属性（只存定义，用时计算）、NULL：无值/值未知属性在ER图中表示：多值属性（双椭圆）、派生属性（虚椭圆）联系、联系集：实体集参与联系。参与约束：E全部参与R（双线）/E部分参与R（单线）联系集的度：参与联系的实体集数目。联系集可包含属性。多元联系-二元联系：约束转换不一定可行角色同一实体集多次参与到联系中，显示指明其角色（线上加标注）映射基数二元联系：一对一（不是一一对应）、一对多（多对一）、多对多。单箭头指向单方实体集，没箭头可能是多对多或一对多。映射基数限制(a,b)a=0/1：是否全部参与联系b=1/n(*)：最多参与几个联系联系集的码：主码结构依赖于映射基数存在依赖支配实体、从属实体弱实体集（双边框）1. 没有主码2. 存在依赖于标识实体集3. 标识性联系（双边框）：弱和标识集的(1,1)-(1,n)联系4. 分辨符（部分码），弱实体主码：所依赖的强实体主码、自身分辨符弱实体集必然存在依赖于强实体集，但存在依赖并不总是导致一个弱实体集弱实体集必要性：避免数据冗余和不一致性、反映了依赖的逻辑结构、弱随强删除/存储实体集的多值、复合属性可以抽取出来作为弱实体集弱实体集除了标识性联系还可以参与其他联系特化/概化特化自顶向下，概化自底向上属性继承层次结构：底层实体集只能参与一个Isa联系格结构：可以多个概化约束成员资格：条件定义、用户定义成员身份：不相交的、有重叠的完备性约束：全部的、部分的聚集把联系看作抽象实体，允许联系中存在联系ER模式转换为表关系每个实体集和联系集构建一个表复合属性：细分属性作为属性多值属性：新的关系（新的表），要包含所在实体的码弱实体集：省略标识性联系表，主码=分辨符+所依赖的强实体集的码一对一联系（部分参与）：新关系一对一联系（一方全部参与）：另一方的码作为该方属性一对多联系：单方的码作为多方的属性，同一实体集也一样多对多联系：新关系，同一实体集也一样联系集的码：参与联系的实体集主码合并为超码，多对一由多方主码，一对一由任一方概化转换：1. 高底层实体集都转换为表，低层关系包括高层码2. 若概化是不相交的、全部的，则可以只转换低层，同时包括高层所有属性聚集转换：构建两个表，在某些允许为空的情况下可以只构建一个ER设计要点1. 属性还是实体2. 实体集还是联系集3. 多元联系还是多个二元联系4. 强实体集还是弱实体集5. 概化/特化，聚集属性-实体：存在描述该属性的属性、参与多个联系、多值属性转换包含多种属性的联系集为实体集三元转换为二元1. 断链法：空间开销大，语义不清晰，比原有的信息量大2. 连环法：信息丢失局部ER模式设计：确定局部结构范围-实体定义-联系定义-属性分配全局ER模式设计：确定公共实体类型-合并两个局部ER-检查消除冲突-继续合并全局ER模式优化：合并实体类型-消除冗余属性-消除冗余联系冲突：属性冲突、命名冲突、结构冲突存储与文件结构定长的存储器单位：块。块是存储器分配和传输的单位缓冲区：主存。缓冲区管理器：分配缓冲区空间的子系统。类似于虚存缓冲区管理器的替换操作。替换策略LRU。查询优化器可以提供启发式知识钉住；立即替换；MRU(最近最常使用)；强制输出文件组织字段-记录-文件-数据库定长记录文件、变长记录文件定长记录：存取简单，但记录可能跨块。删除方式：前移两种、自由链表（指向被删的记录）变长记录：1. 记录末尾控制字符EOF。难以删除、增长。2. Slotted page结构：块头包含记录个数、自由空间末端、每条记录的位置大小记录可以在页内移动，要更新块头信息3. 定长表示法：预留空间法、指针法文件中的记录组织堆、顺序（基于搜索码）、散列顺序文件组织按搜索码排序，搜索码一般主码。维护记录的物理顺序代价高，需要不时重组聚簇文件组织语义关联，减少磁盘I/O；导致变长记录存储一个关系到一个文件减少DBMS处理代价，但不支持某些DBMS优化策略存储多个关系到一个文件支持优化策略，可以在文件中设计复杂结构；增加数据库实现复杂性数据字典（系统目录）保存元数据：关系信息、账号信息、统计数据、文件组织、索引信息等索引与散列搜索码、索引文件（索引项：searchkey-pointer）、有序索引/散列索引索引评价：访问类型（point query/range query）、存取插入删除时间、空间开销有序索引主索引（聚集索引）搜索码顺序=记录顺序，搜索码通常主码。索引顺序文件稠密索引：每个搜索码值都有索引记录，可以不按照索引数据物理存放稀疏索引：只对某些搜索码值有索引记录，仅当文件按搜索码排序才可用多级索引：为主索引建立稀疏索引辅助索引（非聚集索引）搜索码顺序!=文件记录顺序用于按属性查找，索引指向指针桶。必须稠密。更新开销。顺序扫描代价高索引顺序文件（带主索引的顺序文件）缺点：溢出块导致周期性重组B+树索引优点；以较少的局部变化自动重组缺点：额外的插入删除开销、空间开销中间结点有n/2到n 个子节点，结点两端是P叶节点有(n1)/2到n1 个值根节点至少两个子节点中间结点：子节点数=搜索码数+1搜索码前面指针指的都小于，后面的大于等于查询开销：K个搜索码，查询路径不超过logn/2(K)Hash数据索引需要顺序扫描桶Hash索引通常是辅助索引桶溢出处理：溢出桶静态散列的不足：要么浪费，要么溢出动态散列动态hash表：可扩展hash函数，使用所得hash值的前i位缺点：桶地址表Hash不适合range查询，B+树适合多码访问：多属性索引、位图索引（低基数属性、离散化）数据库设计不良的设计：数据冗余、函数依赖设计问题：不可表示：插入异常、删除异常冗余：数据冗余、更新异常范式、模式分解函数依赖 设R(U)是属性集U上的关系模式，X，Y U， r是R(U) 上的任意一个关系，如果l 对t，s r，若tX = sX，则tY = sYl 或者：不存在t，s r，tX = sX，但tY sY成立，那么称“X函数决定Y”，或“Y函数依赖于X”，记作XY，称X为决定因素称 r 满足F，如果关系r 在函数依赖集合 F 下合法称 F 在R上保持，如果R的所有合法关系都满足函数依赖 F函数依赖分类平凡：Y X完全/部分：f/p传递：如果X Y，Y Z，Y X，且(XY)Z=null，则称Z对X传递函数依赖SQL中通过断言保证函数依赖：B-C group by B having count(distinct c) 1规范化：通过模式分解将一个低级范式转换为若干个高级范式1NF：关系中每一分量不可再分（与具体应用有关）2NF：若R1NF，且每个非主属性完全函数依赖于候选码，则称R2NF即将非主属性分成完全依赖和部分依赖候选码两种3NF：若不存在这样的候选码X，属性组Y及非主属性Z(Z Y)，使得下式成立：XY，YZ，YX，则称R3NF消除非主属性对候选码的传递函数依赖BCNF：对于属性组X，Y，若XY且YX时X必含有候选码，则R BCNF 非平凡依赖的左部必定为超码多值依赖：给定的一对(x，z)值有一组Y的值，这组值仅仅决定于x值而与z值无关对称性；函数依赖是平凡的多值依赖4NF：若XY（YX）是非平凡的多值依赖，且X含有候选码，则称R4NF模式分解的要求：无损连接分解；保持依赖；冗余少（BCNF/3NF）逻辑蕴涵如果从函数依赖集合F能够推出XY，则称F逻辑蕴涵XY，记作F XY被F所逻辑蕴涵的函数依赖的全体所构成的集合称作F的闭包，记作F+ = XY | F XYArmstrong公理自反律：若Y X， 则X Y增广律：若X Y ，则XZYZ传递律：若X Y，Y Z，则XZ有效性、完备性合并律、分解律、伪传递律从F计算F+：循环自反、增广；传递属性集闭包：测试函数依赖、测试超码依赖冗余 无关属性正则覆盖（Fc与F相互蕴涵、左部唯一、不含无关属性）算法：循环合并、找到含有无关属性的函数依赖并删去无关属性无损连接分解Ri(r) = r关系模式R(U)的分解r=R1，R2，则r是一个无损连接分解的充要条件是 R1R2R1-R2 或R1R2R2-R1成立保持函数依赖的模式分解Z是U的子集，函数依赖集合F在Z上的投影定义为Z(F) = XY | XYF+ XY Z检查依赖保持算法：多项式时间！检查是否满足BCNF只需检查F中a b的a+是否包含全部属性当R分解后，必须检查F+。针对F在Ri上的投影检查Ri 是否属于BCNFBCNF分解不一定保持函数依赖、指数时间3NF分解：需要给定一个候选码、保持依赖、多项式时间去规范化设计对象-关系数据库Db2、oracle是对象关系数据库。增加系统灵活性，优化机制受影响嵌套关系、复杂数据类型、面向对象支持嵌套关系：原子可以变成集合、关系，违反1NF。解决传统数据类型缺陷：属性之间关系、变长属性、嵌套表。相比于4NF分解，不必需要连接操作适合树状数据，不适合网状数据导航式检索、查询执行代价高1NF不适合树状，但查询优化理论成熟复杂数据类型大对象类型（char、bin）、对象表的类（create type XXX as object. member function,procedure）Collection(set,array,multiset)SQL中结构类型：create type XXX as，可嵌套，可直接建表，可定义methodcreate method xxx(para) for row begin set end构造函数create function type-name(para) return begin set end面向对象支持类型继承 create type xxx under yyy表继承 create table students of Student under people 子表、超表查询people时也查询student中公共属性，除非only people表的存储：ER向关系模式的转换，概化的两种方法引用类型用户设置引用标识create type Department(name varchar(20),head ref(Person) scope people)ref(对象表的别名)返回行对象的指针引用。SQL中不支持ref(),只能ref using, ref is oid user/sys generated。ref from:主码作标识，ref is oid derived复杂数据类型的查询自定义结构：引用的属性用-，表达式叫做路径表达式，避免显式连接复合属性仍然用.表示法Collection访问：unnest将集合视为关系，可以用in操作Array访问可用下标Nest操作：select title, set(keyword) as keyword-set From books group by title查询处理基本步骤1. 词法分析与翻译：验证合法性，查询-查询树-关系代数表达式2. 优化：执行计划：表达式上加标注说明执行策略。利用统计信息估计代价3. 执行查询代价度量：磁盘块传送数 忽略随机与顺序I/O不同选择操作：线性、二分、候选码主索引、非主属性主索引、辅助索引排序操作：外排序：创建有序段、归并序段连接操作：嵌套循环连接（nr * bs + br）、块嵌套循环连接（br * bs + br）索引嵌套循环连接（br + nr * c）、归并连接（br + bs +排序，只用于等值和自然）Hash连接:在joinattr上用hash划分，分布式连接去重操作：散列/排序投影操作：每个元组投影，然后去重聚集操作：排序/散列、从构造就一直聚集，保持更新集合运算：排序/散列变种表达式执行：物化执行、流水线物化执行：生成临时关系，总是可行的。读写代价高，可用双缓冲流水线：有时不可用，如排序和散列连接两种方式：需求(lazy)驱动（向下请求）、生产者(eager)驱动（操作之间维护缓冲区，空满切换）以迭代子句的形式XML没有固定的标签集，有固定的语法但没有语义，是一种自描述语言XML提供了一种定义标签和描述标签间结构的功能定义语义标签、支持嵌套数据结构标签、元素（可有属性！）、唯一顶级元素元素属性和子元素区别：属性属于标签，子元素属于文档；子元素可嵌套；属性无顺序命名空间：unique-name:element-nameXML文档的数据模式是可选择的，XML结构约束表达方式：DTD/XML schemaDTD：不限制数据类型， !ELEMENT bank (account|customer|depositor)+)|：元素之间是or +：元素重复1次以上 *：0到多次 ？：0次或1次ID和IDREF(S)提供了一定的数据完整性约束，但是无类型的XML Schema值有类型、支持自定义数据类型、支持数据类型的继承、本身用XML语法说明XPath/author./title = “WMD”/last/authorposition( ) 视图可串行，视图可串行化不一定冲突可串行化，因为盲写结果相同但非两种可串行化：可交换顺序的写（加减操作）可恢复调度：如果T2读取了T1所写的数据，则T1必须先于T2提交无级联调度（必可恢复）：如果T2读取了T1所写的数据，则T1必须在T2读取之前提交为保证数据库的一致性，调度必须是冲突或视图可串行化的，可恢复的，并且最好是无级联回滚的隔离性丢失修改、读脏数据、不能重复读、发生幻象SQL中隔离性级别：serializable、reapeatable read（幻象）、read commited（幻象+不能重复读）、read uncommitted（读脏数据+不能重复读+发生幻象）可串行化判定调度的优先图：Ti Tj，都存取同一个数据项，至少一个写，有向，时间早指向时间晚无环=冲突可串行化。Ti Tj意味着任何等价的串行调度中Ti在Tj之前拓扑排序得到等价串行顺序并发控制事务调度器、事务协议悲观控制策略（锁、等待、死锁）、乐观控制策略（回滚）锁协议排它锁lock-X、共享锁lock-S两阶段封锁协议增长阶段、收缩阶段：确保可串行化：按lock points（获得最后一个锁的点）的次序串行化为了夭折后可恢复、无级联：严格两阶段锁、强两阶段锁锁转换：upgrade、downgra