画布 1
数据库系统概念
  关系数据库
    关系模型
      关系数据库由表的集合构成
        关系指代表
          关系是元组的集合
        元组指代行
        属性指代列
        关系实例表示一个关系所包含的一组特定的行
        关系模型由属性序列以及各属性对应的域组成
      码
        超码
          唯一的识别一个元组
        候选码
          最小的超码
        主码
          人为选定、区分不同元组的候选码
        外码
          对于参照关系中的每个元组来说，它在外码属性上的取值肯定等于被参照关系中某个元组在主码上的取值
      模式图
        表示一个含有主码和外码依赖的数据库模式
        实体-联系图（E-R图）
          表示更多的参照完整性约束
      关系运算
        作用于单个关系或是一对关系上
          运算结果总是单个关系
        关系代数
          选择
            给出满足给定谓词的元组
          连接表达式
            连接条件
              join...using
              on
                表示任何SQL谓词
            笛卡尔积
              内连接
            自然连接
            外连接
          投影
            一元运算
            返回作为参数的关系，将一些属性排除在外
            重复的行被去除
          并、交、差
    SQL
      SQL数据
        基本类型
          空值
            表示一个缺失的值
            可能存在但不为人知，可能根本不存在
            尽量禁止空值
          日期与时间类型📅
            date
            time
            datetime
          默认值
          创建索引
            高效查询关系中在索引属性上取给定值的元组
          大对象类型
          用户定义类型
            独特类型
              create type
                使用cast转换类型
              create domain
                在域上可以声明约束
                域不是强类型，基本类型相同即可
            结构化数据类型
        基本模式定义
          完整性约束
            primary key
              主码必须非空而且唯一
            Foreign key
              子主题 1
            not null
          增删改
      SQL查询
        select
          distinct
            强行删除重复
          允许对常数、元组的属性使用算术表达式
            +、-、*、/等
          输出集合中select子句指定的属性、表达式结果
        from
          定义该子句中所列出关系上的笛卡尔积
        where
          允许使用逻辑连词and、or、not。
            逻辑连词运算对象可以包含比较运算符
          where子句中的谓词限制笛卡尔积所建立的组合
      附加的基本运算
        更名运算
        字符串运算
          %：任意匹配
          _：单字符匹配
          /：转义字符
        select子句中属性说明
          在select子句中表示所有属性
        排列元组顺序
          order by
            desc：降序
            asc：升序
        where子句谓词
          between
          元组字典序比较
      集合运算
        union
        intersect
        expect
        集合运算自动去除重复
          使用 xxx all保留所有重复
      空值
        任何涉及空集的比较运算结果视为unknown
          除true、false外的第三逻辑值
            And
              True and unknown = unknown
              False and unknown = false
              Unknown and unknown = unknown
            Or
              True or unknown = true
              False or unknown = unknown
              Unknown.or unknown = unknown
            Not
              Not unknown =unknown
          Where子句谓词对一个元组计算出false或是unknown，则该元组不能加入结果集
        使用null测试空值
        使用is unknown测试表达式结果是否为unknown
        select distinct中
          null=null结果为true
          对于两个元组的属性值都为空认为是相同的
        谓词中
          null=null结果为unknown
      聚集函数
        以值的一个集合（集或多重集）为输入
          返回单个值的函数
        基本聚集
          平均值：avg
          总和：sum
          最小值：min
          最大值：max
          计数：count
          count（*）中不允许使用distinct
          输入必须为数字集
        分组聚集
          group by
            该子句中的所有属性取值相等的元组被分在同一分组
            select子句中没有被聚集的属性只能是出现在group by子句中的属性
        having子句
          对分组加以限定
            having子句中没有被聚集的属性只能是出现在group by子句中的属性
        对空值与布尔值的聚集
          除count（*）外，所有聚集函数忽略空值
            空集的count为0
            其他聚集函数空集下返回空值
          some、every处理布尔值集合
      嵌套子查询
        集合成员资格
          in
        集合比较
          >some等
        空关系测试
          exists
        重复元组存在性测试
          unique
        from子句中的子查询
          SQL查询结果是关系，因此S-F-W可出现在任何关系可以出现的地方
        with子句
          提供定义临时关系的方法
        标量子查询
          允许子查询（只返回单个属性的单个元组）出现在返回单个值的表达式能够出现的地方
      数据库修改
        删除
        插入
        更新
      视图
        定义一个虚关系，只在使用时通过查询被计算
        物化视图
          存储视图关系，但是保证如果定义视图的实际关系变化，视图也会跟着变化
            视图维护
        视图更新
          可更新视图
            from子句只有一个数据库关系
            select子句只包含关系属性名
              不包含任何表达式、聚集、distinct声明
            出现在select子句中的属性不可为空
            查询中不含group by或having子句
      完整性约束
        函数依赖
        单关系约束
          not null
          Unique
          Check(P)
            带来很大的开销
        参照完整性
          保障在一个关系中给定属性集上的取值也在另一个特定属性集的取值中出现
            cascade：级联操作
              外码依赖链
              如果一个级联操作导致的对约束性的违反不能通过进一步的级联操作解决，则系统中止该操作
          Set constraints constraint-list deferred
            对指定约束的检查延迟到该事务结束时执行
        断言assertion
          域约束、参照完整性
          描述性表达式，指定了我们要求总为真多谓词
      授权
        权限
          select
          insert
          delect
          all privilege（所有权限）
        角色🎭
          给角色授予权限
        视图授权
          如果用户在该视图上不能获得任何权限则不能创建该视图
        模式授权
        权限转移
        权限回收♻️
          级联回收
  基本概念
    数据视图
      物理层
      逻辑层
        物理数据独立性
      视图层
    实例
      存储在数据库的信息的集合为数据库的一个实例
    模式
      数据库的总体设计（逻辑设计）
    数据模型
      关系模型
      实体-联系模型
      基于对象模型
      本结构化数据模型
    数据库语言
      DML
        数据操纵语言
          查询访问特定数据
      DDL
        数据定义语言
          数据结构、一致性约束
  数据库设计
    实体-联系模型
      实体集
        具有相同属性的实体的集合
        实体：区别于其他对象的一个事物
        属性：实体集中每个成员拥有的描述性性质
      联系集
        相同类型联系的集合
        联系：多个实体间相互关联（参与）
        角色：实体在练习中扮演的功能
        描述性属性
      属性
        域：属性可取值的集合
        简单、复合属性
          复合属性还可以划分更小部分
        单值、多值属性
        派生属性
          派生属性的值不存在，只是在需要时计算出来
    约束
      映射基数
        表示一个实体通过一个联系集能关联的实体个数
        一对一
        一对多
          箭头指向代表一的实体集
        多对一
        多对多
        基数约束(l..h)
          l：最小映射基数
          h：最大映射基数
          该实体集上的实体通过联系集可以关联的实体个数
      参与约束
        全部参与
        部分参与
      码
        联系集R
          参与联系的实体集主码集合的并集并上联系集的描述性属性构成集合R的一个联系
            必要时重命名码
          R的超码为参与联系的实体集主码集合的并集
    E-R图
      基本结构
        分为两部分的矩阵
          实体集
            实现标明主码
        菱形
          联系集
            非二元联系集
              一个联系集最多允许一个箭头
        未分割的矩阵
          联系集属性
        线段
          实体集连接到联系集
        虚线
          联系集属性连接到联系集
        双线
          实体全部参与联系
        双菱形
          连接到弱实体集的标志性联系集
            弱实体集
              没有足够属性形成主码的实体集
                用虚线标明分辩符
              弱实体集必须与一个标识实体集关联才有意义
              弱实体集到标识实体集的联系为标示性联系
                从弱实体集到标识实体集到多对一
                弱实体集全部参与
    拓展E-R特性
      特化
        将实体集的一部分属性特化出来
      概化
        约束
          条件定义
            成员资格确定基于实体是否满足一个显式的条件
          用户定义
            用户将实体指派给实体集
          不相交
            一个实体最多属于一个低级实体
          重叠
            一个实体可以属于同一概化中的多个低层实体集
          全部
            每个高层集实体必须属于一个底层实体集
          部分
            允许一些高层实体集不属于任何低层实体集
      属性继承
        高层实体集属性被底层实体集继承
    转换为关系模式
      强实体集
        简单属性
        复合属性
          为每个子属性创建单独的属性
          不为复合属性自身创建属性
        多值属性
          创建新的关系模式
        派生属性
      弱实体集
        属性为弱实体集属性加上标识实体集的主码
        弱实体集主码由所依赖强实体集的主码与弱实体集分辩码组成
        外码约束
          说明参照了标识实体集的主码
      联系集
        属性有所有参与联系的实体集主码并集与联系集的描述性属性组成
        主码
          多对多
            参与实体集主码的并集
          一对一
            任何一个实体集的主码
          多对一、一对多
            多的实体集的主码
          n元联系集
            没有箭头
              参与实体集的主码并集
            有箭头
              不在箭头侧的实体集的主码并集
            尽量使用2元联系
        外码约束
          参与的实体集的主码
      概化
        为高层实体集创建一个模式
        为每个低层实体集创建一个模式
          对应高层实体集主码的属性
      模式冗余
        链接弱实体集与标识实体集的联系集模式是冗余
          不必给出
      模式合并
        实体集A到实体集B以及多对一段联系集AB
          将A与AB合并
            合并后的主码为融入联系集模式的实体集的主码
        一对一联系下
          联系集模式可以与联系的任意实体集模式合并
    关系数据库设计
      函数依赖A->B
        给定r（R）的一个实例，该实例满足函数依赖
          对实例中所有元组对t1，t2
          t1[A]=t2[A],则t1[B]=t2[B]
        成立hold
          r（R）中任何实例满足函数依赖
        平凡性trivial
          在所有包含属性A，B的模式上满足
          一般A包含B则是平凡的
      函数依赖理论
        函数依赖集的闭包
          Armstrong公理
            自反律
            增补律
            传递律
            推广
              合并律
              分解律
              伪传递律
        属性集的闭包
          如果a->B,称属性B被a函数确定
          属性闭包算法
            判断超码
            函数依赖是否成立
            计算函数依赖集闭包
        正则覆盖
          最小化函数依赖
        依赖保持
        无损分解
          R1并R2是R1或R2的超码
      BCNF
        条件（满足一个即可）（函数依赖集的闭包中）
          A->B是平凡函数依赖
          A是模式R的一个超码
        分解不满足BCNF的模式
          R中至少存在一个非平凡函数依赖A->B
            A U B
            R-（B - A）
            使用这两个模式取代R，直至全部为BCNF
      第三范式
        条件（满足一个即可）（函数依赖集的闭包中）
          A是模式R的一个超码
          A->B是平凡函数依赖
          B-A中的每个属性c都包含与R的一个候选码中
      分解算法
        BCNF
        第三范式
  数据存储与查询
    文件组织
      文件：逻辑上组织成记录的一个序列
      定长记录
        文件头
          记录空闲链表
      变长记录
        记录
          初始部分
            定长属性
            记录变长属性的（偏移量，长度）的值
              偏移量：该记录中该属性的数据开始位置
              长度：变长属性的长度
        块
          分槽的页结构
            块头
              块头中记录条目的个数
              块中空闲空间的末尾处
              由包含记录位置和大小的记录条目组成的数组
            实际记录从块尾部开始连续排序
      记录的组织
        堆文件组织
          记录可在文件中任何地方
        顺序文件组织
          记录根据搜索码的值顺序存储
            需要定时重组文件
        散列文件组织
          对记录上的属性计算散列值
        多表聚簇文件组织
          几个不同关系的记录存储在同一文件
            优化关系间的连接运算
    索引
      顺序索引
        基于值的顺序排序
        聚集索引
          包含记录的文件按照某个搜索码指定的顺序排序
            该搜索码对应的聚集排序
        非聚集索引
          搜索码指定的顺序与文件中记录的物理顺序不同
        稠密索引
          文件中每个搜索码都有一个索引项
            稠密聚集索引
              索引指向具有该搜索码值第一条数据记录的指针
            稠密非聚集索引
              索引指向具有相同搜索码值的记录的指针列表
        稀疏索引
          只为部分搜索码建立索引项
          只有聚集索引才能使用稀疏索引
          索引指向具有该搜索码值的第一条数据记录
        多级索引
        索引更新
          使用delect、insert、update时可能会因为修改索引项而降低速率
        辅助索引
          必须是稠密索引
      散列索引
        值所属的散列通由hash函数确定
        静态散列
          从搜索码值到桶地址的函数
          桶溢出
            溢出桶🪣
              溢出链
        动态散列
          由位数确定hash计算时的数值
    查询处理
      选择运算
      排序
      连接运算
      其他运算
    查询优化
      等价规则
      启发式优化
        step1:将合取选择分为多个单独的选择
          使单个选择操作尽可能沿查询树下移
        step2:利用选择操作的交换律和分配律
          将每个选择操作尽可能移向叶结点
        step3:利用连接操作的结合律和交换律
          重新安排查询树的叶结点
          含有最少元组的叶结点先执行
        step4:用连接操作代替选择与笛卡尔乘积操作
        step5:将投影操作尽可能下移
          减少中间结果
          select
        step6:将最终查询树分解为多个子树
          子树各操作采用流水线方式执行
          减少对外设的访问次数
        where
        from
  事务管理
    事务
      构成单一逻辑工作单位的操作集合
      ACID特性
        原子性
          全部完成或者不完成
          恢复系统
        一致性
          隔离执行事务时保持数据库的一致
          完整性约束
        隔离性
          并发执行时，每个事物感觉不到有其他事务
          并发控制系统
        持久性
          一个事物成功完成后对数据库的改变是永久的
          恢复系统
      事务状态
        active
          初始状态，事务执行
        partially committed
          最后一条语句执行后
        failed
          正常执行不能继续后
          回滚选择
            重启事务
              硬件错误
            杀死事务
              内部逻辑错误
        aborted
          事务回滚并恢复事务开始前的状态
        committed
          成功完成
      可串行化
        冲突等价
          S通过一系列非冲突指令交换转换为S‘
        冲突可串行化
          一个调度与一个串行调度冲突等价
        优先图
          描述一个调度的拓扑结构
          图中不含环说明是冲突可串行化的
      调度
        可恢复调度
          每对事务T1、T2满足，如果T1读取T2所写的数据项，则T2先于T1提交
        无级联调度
          每对事务T1、T2满足，如果T1读取T2所写的数据项，则T2在T1读操作前提交
    并发控制
      基于锁的协议
        锁🔒
          共享锁
          排它锁
          意向锁
            共享意向锁
            排他意向锁
            共享排他意向锁
          相容函数
        两阶段封锁协议
          增长阶段
            获得锁不可释放锁
          缩减阶段
            释放锁不可获得锁
          封锁点
        严格两阶段封锁协议
          排它锁在事务提交后释放
        强两阶段封锁协议
          必须在事务提交后释放锁
        锁转换
          升级
            共享锁->排它锁
            增长阶段
          降级
            排它锁->共享锁
            缩减阶段
        锁管理器
      死锁处理
        死锁预防
          事务开始前封锁所有数据项
          对数据项排序
          锁超时
        死锁检测与恢复
          等待图
      多粒度
        意向锁
          如果在一个结点加意向锁
            则要在底层进行显式加锁
        多粒度封锁协议
    恢复系统
      日志记录
        字段
          事务标识
          数据项标识
          旧值
          新值
        类型
          start
          abort
          commit
          写操作
          redo-only
      检查点
        将主存中所有日志记录输出到磁盘
        将所有修改的缓冲块输出到磁盘
        添加日志记录<checkpoint L>
          L为当下正活跃的事务列表
      恢复算法
        事务回滚
        系统崩溃后的恢复
          重做阶段
          撤销阶段