再看数据库系统概念

Posted on   |   In

E-R

  • 实体集：同类同性质实体
  • 联系集：同类联系集合
  • 属性／实体：强关联属性，弱关联单独出实体
  • 超码：一个或多个属性集，唯一标识一个实体
  • 候选码：任何真子集不为超码，即最小超码

###　实体联系图

  • 矩形：实体
  • 椭圆：属性
  • 菱形：联系
  • 双椭圆：多值属性

  • 虚椭圆：派生属性

  • 弱实体集：属性不足以形成主码，依赖于强实体集

  • 特殊化：实体集内部分组
  • 概括：高层实体集包含底层实体集
  • 概括／特殊化
    • 高层属性和联系适用于底层
    • 底层特有属性只限自身

      E-R转表

  • 实体集直接转表
  • 弱实体集表加入依赖强实体集主码
  • 联系集：联系实体主键　＋　联系属性
  • 多值属相创建新表

关系模型

  • 选择：元组
  • 投影：属性
  • 并／差
    • 关系同元：属性数目相同
    • 对应属性域相同
  • 交
  • 自然链接：笛卡尔积，童淑星相等性选择，去重
  • 广义投影：投影之后算数扩展
  • 外链接：链接之后扩展缺失信息

视图定义时之存储定义本身，每次查询都会重新计算

SQL

  • SELECT　投影
  • FROM 笛卡尔积
  • WHERE 谓词运算
    1
    2
    3
    4
    5
    6
    SELECT [distinct] A1,A2,A3....
    FROM r1,r2 ,r3.....
    WHERE P
    ORDER by  [asc/desc]
    GROUP by 
    HAVING
  • LIKE
    • %:任意字串
    • _ :任意字符
  • 集合操作: UNION [ALL]/ INTERSECT/ EXCEPT
  • 聚集函数：　avg/sum/max/min/count
  • 测试子元组集是否为空：exist/not exist

  • 测试子查询是否含重：unique/not unique

  • 视图：create v as

  • 删除

    1
    2
    3
    DELETE FROM account
    WHERE balance < (SELECT AVG(balance)
                        FROM account)

  • 插入

    1
    2
    INSERT INTO account(name1, name2, name3)
                VALUES("v1", "v2", "v3")

  • 更新

    1
    2
    3
    4
    UPDATE acount
    SET balance  = balance * 1.5
    WHERE balance > SELECT ARG(balance)
                            FROM account

完整性约束

  • 参照完整性
    • 联系集参照完整性：依赖于各实体集主码
    • 弱实体集参照完整性：依赖于强实体集主码
  • 外键参照级联

    正则覆盖：关系模式上函数依赖集Ｆ，在该关系上做任何更新时，必须保证Ｆ中所有函数依赖在新数据库下满足，否则回滚该更新操作
    Ｆ的正则依赖集Fc:

  • 包含Ｆ中全部依赖关系
  • 函数依赖的左半部唯一

模式分解

  • 子关系连接合并后投影可得原关系则为无损分解（分解不引起记录增加）
  • 保持依赖：分解后依赖集蕴含全部原依赖集依赖关系

  • BDNF：具有函数依赖集Ｆ＋的关系模式

    Ｆ+中任意a->b 的函数依赖，其中a属于Ｒ且b属于Ｒ，以下至少一个成立

    • a->b 为平凡函数依赖（b 为a 的子集）
    • a是模式超码

    BCNF不一定保持依赖

  • 3NF：具有函数依赖集Ｆ＋的关系模式

    Ｆ+中任意a->b 的函数依赖，其中a属于Ｒ且b属于Ｒ，以下至少一个成立

    • a->b 为平凡函数依赖（b 为a 的子集）
    • a是模式超码
    • b-a 中每个属性Ａ都包含在Ｒ的候选码中
      3NF无损且保持依赖
      不存在非主属性对主码的传递依赖
  • 多值依赖？
  • 连接依赖？

储存结构文件结构（数据库系统实现）

索引

  • 按搜索码顺序存储，搜索码对应索引为主索引
  • 稠密索引：每个搜索码值有一个索引记录
  • 稀疏索引：搜索码值　＋　搜索码值指向具有该搜索码值的第一个数据项

    稀疏索引空间小，易维护，开销小，稀疏索引放入主存，查找迅速

B+树索引

  • 每个节点最多包含　n-1个搜索码值和ｎ个子节点指针
  • B+树非叶节点形成叶节点的多级稀疏索引，叶节点顺序链接
  • B+树为平衡树，根到任一叶子节点路径长度相同，非叶节点只起索引作用
  • B树搜索码只出现一次，增加一个指向文件的指针，即非叶节点不仅是索引作用，也指向具体记录或者文件
  • B树中查询一次访问节点数取决于节点位置，找到即停止，B+树必须找到叶节点才能确定记录位置
  • 散列索引
    • 闭散列：增加溢出桶
    • 开散列：线性搜索（删除比较麻烦）
  • 动态索引？
  • 网格索引和分段散列适用于多属性查询
    1
    2
    CREATE [UNIQUE]INDEX <index-name> ON <realtion-name> (<attribute-list>)
    DROP INDEX <index-name>

查询处理

选择运算

  • A1：线性搜索，平均代价Br/2，最坏情况Br
  • A2: 二分搜索，属性有序，代价[logBr]

    索引选择

  • A3: (主索引，码属性等值比较)可以检索到唯一一条满足条件的记录，代价：B+树树高加上读取一条记录I/O代价
  • A4: (主索引，非码属性等值比较)主索引可以检索到多条满足条件的记录，且多条记录顺序存储，代价：B+树树高加上具有搜索码值的盘块数
  • A5: (辅助索引，等值比较)索引字段为码属性直接得到一条记录．索引字段为非码属性，得到多条记录

    比较选择

  • A6: (主索引，比较)B+树有序主索引
  • A7: (辅助索引，比较)有序辅助索引，小值从小段开始，大值从　大端开始

    比较选择

  • A8: 索引合取（取交）先现则满足一个条件的记录，加入缓冲区，在缓冲区中验证其他条件
  • A9: (组合所用合取)直接利用合适的符合索引查询
  • A10: (记录标识符的交)每个条件遍历标记一边，取所有被标记的交际
  • A11: (记录标识符的并）逐一扫描索引获取满足单个条件的元祖指针，将所有指针集做并集

连接运算

  • 嵌套循环（重名属性会出现）
  • 块嵌套循环，每次在块内循环嵌套检查元组匹配，有效减少比较次数
  • 索引嵌套循环连接：嵌套循环连接的内层如果有索引，使用索引代替循环
  • 归并链接：用于自然链接和等值连接
    • 双有序直接有序归并
    • 单有序，归并后，对索引项进行按地址排序，可实现有序
  • 消除重复: 代价高，明确声明是否去重
    • 归并/散列可直接在过程中消除重复
  • 集合
    • 并集：　Hr建立散列索引，将Hs中元组加入到上诉散列索引中，条件是该元组不在散列索引中，散列索引最终即结果
    • 交集：　Hr建立散列索引，对Hs中元组探查散列索引，出现在散列索引的记录放入结果
    • 差集：　Hr建立散列索引，对Hs中元组探查散列索引，出现在散列索引的记录从索引中删除

外连接

  • 计算连接法：
  • 左外连接：计算链接，将左集未参与链接集合扩展放入结果
  • 右外连接：计算链接，将右集未参与链接集合扩展放入结果
  • 全外连接：计算链接，将左右集未参与链接集合扩展放入结果
    • 嵌套修改法
      • 左外连接：左边外循环，右表内循环，内外匹配加入结果，内部均不匹配的外记录也加入结果
      • 右外连接：右边外循环，左表内循环，内外匹配加入结果，内部均不匹配的外记录也加入结果
    • 扩展归并连接获得自然链接和等值全外联
      • 归并完成，将不与另一关系任一记录匹配的记录加入结果

        启发优化

  • 合取选择分解为单个选择
  • 选择运算下推到最早执行位置
  • 选择与链接合并求取最小元组数关系
  • 选择加笛卡尔积替换成链接
  • 投影分解下移

事务

  • 事务性质：原子性，一致性，隔离性，持久性
  • 原子性：事务未完成则回复原值
    • db-pointer 指向影子副本，更新完成时指向影子副本
  • 持久性：
    • 事务更细在事务完成前已写入磁盘
    • 事务执行的更新和已写更新信息充分，故障时可重新构造数据库
  • 交换非冲突指令得出冲突等价，等价与串行执行时，即为冲突可串行化
  • 两个视图中读取的值来源形同，写进的值来源相同，即试图等价
  • 每个冲突可串行化都是视图可串行化的，但存在非冲突可串行化视图可以串行化调度
  • 冲突可串行化判定：构造无环优先图（拓扑排序）

    并发

  • 锁授予

    不存在冲突锁

  • 两阶段锁
    • 增长阶段：只加锁，不释放
    • 缩减阶段：可释放，不申请新锁

      两阶段封锁不能保证避免死锁

  • 严格两阶段事务锁：事务持有的排它锁必须在事务提交后才能释放
  • 强两阶段事务锁：事务提交前不释放任何锁

  • 树协议

    • 首次加锁直接执行
    • 之后加锁前提是必须先获得父项的锁
    • 解锁随时可以进行
    • 一个数据项加锁解锁后不能再加锁（只可加锁解锁一次）

      树协议保证冲突可串行化，保证避免死锁

  • 时间戳

    每个数据项Ｑ维持两个时间戳关联数据

    • 成功执行写操作最大时间Wtimestap
    • 成功执行读操作最大时间Rtimestap
  • 事务Ti发出read(Q)操作
    • TS(Ti) < Wtimestap，　Ti 需要读入的Q值已经被覆盖，read 操作被拒绝，Ti回滚
    • TS(Ti) >= Wtimestap， 执行read操作，Rtimestap更新为　max(Rtimestap,TS(Ti))
  • 事务Ti发出write(Q)操作
    • TS(Ti) < Rtimestap，　Ti 产生的Q值先前被覆盖，write操作被拒绝
    • TS(Ti) < Wtimestap， Ti 想写入Q值过时，Ti 拒绝，回滚
    • 其他执行write,　Wtimestap设为TS(Ti)

      死锁预防

  • 事务开始前封锁它的全部数据项
  • 抢占与事务回滚
    • wait-die机制非抢占：老事务等待新事务释放数据项
    • wound-die机制抢占：老事务不等待新事物
  • 锁超时：事务等待锁超时自动回滚

  • 幻象冲突：两事务就数据项是否存在产生不一致

    • 解决：在关系上加锁，插入数据项的事务需要排它锁，将和其他事务在以存在数据项上冲突
    • 问题：两个插入事务将冲突，并发程度降低

  • 有效性检查

    事务读入局部变量并修改，然后进行有效性检查，有效时写入数据库

恢复

  • undo日志：事务更新的数据行回复为旧值
  • redo日志：事务更新的数据项更新为新值
  • 事务Ti需要undo, 如果日志记录包含,但不包含
  • 事务Ti需要redo, 如果日志记录包含, 又包含
  • 从后向前扫描遇到第一个
  • 主存日志记录输出到稳定存储器上
  • 所有修改了的缓冲块输出到磁盘
  • 将日志记录输出到稳定存储器

    重启动回复

    崩溃回复时：构造undo-list和redo-list事务

    1
    2
    3
    4
    5
    - 从后向前扫描日志，直到发现第一个<checkpoint>
    - 对每一个形如<Ti commit>, 将Ti加入redo-list
    - 对每一个形如<Ti start>, 如果Ti不属于redo-list ,Ti 加入undo-list
    - 构造完成后，从后向前重新扫描日志，执行undo-list记录undo操作
    - 找出最后一个cjeckpoint,从前向后扫描执行redo-list中的redo事务

FLAG

立下FLAG,已经看到15章，后几章一定要看的涉及数据库体系结构、分布式数据库、高级查询、授权