数据库与数据挖掘.ppt

2020 3 26 1 数据库与数据挖掘 2020 3 26 2 计算机专业研究生的专业成长 培养目标 1 具有扎实的基础理论和专业知识课程学习 领域知识 知识面 2 开发能力 熟悉开发工具 3 科研能力 创新能力 科研成果 论文 2020 3 26 3 2 科研方法与步骤 1 确定研究方向 2 收集阅读资料了解发展过程 现状 现有方法 3 确定课题 4 提出解决方案 5 方案实现 6 实验结果分析 性能测试 7 论文写作 8 学术交流 2020 3 26 4 本课程的任务 数据库基础知识的回顾与整理数据库系统原理的深化与巩固数据仓库数据挖掘技术上机实验 某种数据挖掘算法的实现课程考核 笔试70 上机实验30 答辩 2020 3 26 5 第1章基础知识 一 数据库技术的发展历程1964年 第1个DBMS问世 IDS 网状数据库1960 末 推出IMS 层次数据库 1970 推出SystemR 关系数据库 E F Codd 关系数据库之父 1980 关系数据库典盛时期 1990 面向对象数据库 特种数据库 2020 3 26 6 特种数据库 多媒体数据库 工程数据库 时态数据库 空间数据库 知识库2000年后 Web数据库 XML数据库数据组织的种类 无结构 结构化 半结构化 2020 3 26 7 二 DBMS的功能7个功能1 提供用户接口2 查询处理与优化3 数据目录管理4 并发控制5 数据恢复6 完整性约束7 访问控制 2020 3 26 8 三 数据模型与数据模式1 数据模型的含义数据结构 操作 完整性约束关系模型 层次模型 网状模型2 数据模式描述具体数据的方式例如 关系模型中二维表外模式 模式 内模式 2020 3 26 9 四 数据模型的种类与分析1 概念数据模型面向用户 面向现实世界 与DBMS无关E R模型2 逻辑数据模型描述数据的逻辑关系关系 层次 网状 面向对象3 物理数据模型面向物理实现 2020 3 26 10 关系模型数据结构 二维表完整性约束 域完整性 实体完整性 引用完整性操作 连接例 运算 2020 3 26 11 五 数据库生命周期规划 设计 建立 运行管理和维护 扩充与重构六 数据库语言SQL组成 DDL QL DML DCLcreatetable createindex droptable dropindex createview as 2020 3 26 12 select from where groupby orderby insertinto deletefrom update set where 嵌入式SQL SQL嵌入到程序设计语言中动态SQL 支持动态查询 执行的SQL语句不是事先确定 2020 3 26 13 SQL的存储过程 将常用的访问数据库的程序 定义一个过程 经编译后 存储在数据库中 供用户调用 格式 定义过程 execsqlcreateprocedure in输入参数 out输出参数 beginatomic atomic表示执行保持原子性 end execsql调用过程 call NoSQL数据库 2020 3 26 14 七 数据库系统结构4种1 单机数据库系统2 C S B S数据库系统3 逻辑上集中 物理上分布的数据库系统4 逻辑上分布 物理上分布的数据库系统 2020 3 26 15 八 DBMS中的事务DBMS的一个执行单位ACID准则 A 原子性C 一致性I 隔离性 多个事务并发执行 应像各个事务独立执行一样D 持久性 2020 3 26 16 九 数据目录是一组关于数据的数据 也叫元数据 数据目录中的数据分为两类 1 来自基表 视图和索引的定义 相对稳定 2 来自数据库状态的统计 例如 元组个数 不同属性值的个数 2020 3 26 17 十 数据库文件的组织1 顺序文件 堆文件 2 直接文件 Hash文件 3 索引文件静态索引 表组织 不插入 删除动态索引 B 树 插入 删除主索引 次索引倒排文件 所有属性都建立索引簇集索引 关键字相同的记录放在连续物理块稠密索引 每个键有一个索引项非稠密索引 2020 3 26 18 十一 存储系统的发展1 三级存储体系Cache 内存 外存2 RAID磁盘阵列3 存储器网络通过网络共享磁盘数据 2020 3 26 19 第2章查询处理与优化 一 基本概念1 查询是数据库中最基本 最常用 最复杂的操作2 查询一般以查询语言表示3 查询优化是查询处理中的重要环节 二 查询优化的方法1 规则优化2 代价估算优化 2020 3 26 20 1 规则优化 1 代数优化 对查询语句进行等效变换 2 物理优化 选择合理的存取策略2 代价估算优化先预估代价 再从中选优 三 代数优化 1 先做选择 投影 后做连接 2 先做小关系连接 再做大关系连接 3 提取查询中的公共表达式 2020 3 26 21 举例 设有关系S 供应商 P 零件 SP 供应关系 关系模式如下 S SNUM SNAME CITY P PNUM PNAME WEIGHT SIZE SP SNUM PNUM DEPT QUAN 设有查询 SELECTSNAMEFROMS P SPWHERES SNUM SP SNUMANDSP PNUM P PNUMANDS CITY NANJING ANDP PNAME BOLT ANDSP QUAN 10000 2020 3 26 22 画查询树 处理过程 1 select子句对应投影操作 from子句对应笛卡尔乘积 where子句对应选择操作 生成原始查询树 2 应用变换规则 尽可能将选择条件移向树叶方向 3 按照小关系先做的原则 重新安排连接 笛卡尔乘积 的次序 4 如果笛卡尔乘积后还需按连接条件进行选择操作 则将两者组合成连接操作 5 对每个叶结点加必要的投影操作 以消除对查询无用的属性 2020 3 26 23 四 物理优化依赖于存取路径的规则优化顺序存取 索引存取 散列存取1 选择操作的实现与优化 1 对于小关系 不必考虑其他存取路径 直接用顺序扫描 2 如果无索引或散列可用 则用顺序扫描 3 对于主键的等值查询 最多只有一个元组满足条件 应优先采用主键上的索引或散列 4 对于非主键的等值查询 如果选中的元组数较多 则用簇集索引或顺序扫描 否则可用一般次索引 5 对于范围查询 若中选的元组数在关系中所占比例较大 且无簇集索引 则采用顺序扫描 6 对于用and连接的合取选择条件 若有相应的多属性索引 则优先使用多属性索引 7 对于用or连接的析取选择条件 按其中各个条件分别选出 然后求这些元组集的并 2020 3 26 24 2 连接操作的实现与优化有4种实现方法 1 嵌套循环法 2 利用索引或散列寻找匹配元组法内关系上建立索引或散列 3 排序归并法 4 散列连接法连接属性R A和S A具有相同的域 用A B作为散列键 用相同的散列函数 把R S散列到同一散列文件中 符合连接条件的R S的元组必然位于同一桶中 2020 3 26 25 优化规则 1 如果两个关系都已按连接属性排序 则优先用排序归并法 2 如果两个关系中有一个关系在连接属性上有索引 特别是簇集索引 或散列 则可令另一关系为外关系 顺序扫描 利用内关系上的索引或散列寻找其匹配元组 以替代多遍扫描 3 如果上述条件不具备 且两个关系都比较小 可以应用嵌套循环法 4 如果上述都不适合 则用散列连接法 2020 3 26 26 3 投影操作的实现投影操作一般与选择 连接操作同时进行 不需要附加的I O开销 主要任务是 消除重复元组 比较费时 方法 1 排序 将投影结果按属性排序 使重复元组连续存放 以便发现和消除 2 散列 将投影结果按属性散列成一个文件 当一个元组散列到一个桶中时 可以检查是否与桶中已有元组重复 2020 3 26 27 4 集合操作的实现R S R S R S关键是发现R S的共同元组 方法 1 排序 2 散列 2020 3 26 28 五 代价估算优化 适用于编译型DBMS 1 查询代价的组成I O代价 CPU代价 通信代价I O代价是主要的 I O代价 I O次数 D I O代价 I O次数2 选择操作的代价估算按照不同的存取策略估算 1 顺序扫描若最多选择一个元组 C 0 5b b为关系的物理块若选取多个元组 C b 2020 3 26 29 2 利用主键上的索引或散列等值查询索引 C L 1 L为索引级数散列 C 1 3 利用非主键的无序索引进行等值查询可能有多个元组满足条件 假设属性值均匀分布 满足条件的元组数s n N n是元组总数 N是不同取值的个数代价估算 C L s 2020 3 26 30 4 利用簇集索引进行等值查询C L s p 5 利用簇集索引进行范围查询假设有一半元组符合条件C L b 23 连接操作的代价估算4种实现方法 1 嵌套循环法 要考虑内存缓冲的大小 块数 2 利用索引或散列寻找匹配元组法 3 排序归并法 4 散列连接法 2020 3 26 31 第3章事务管理 一 基本概念事务管理恢复 保证事务在故障时满足ACID准则并发控制 保证事务在并发执行时满足ACID准则2 故障的种类事务内部故障 程序本身造成系统故障 如 CPU故障 OS故障介质故障计算机病毒 2020 3 26 32 3 恢复技术 1 数据转储 2 运行记录 后备复本 3 多复本技术运行记录 日志文件日志文件是用来记录事务对数据库更新操作的文件 内容包括 事务标识 操作类型 操作对象 更新前数据的旧值 前像 更新后数据的新值 后像 2020 3 26 33 日志文件的登记原则 按事务执行时间顺序先写日志文件 后写数据库二 恢复操作与恢复策略1 操作 撤销事务 undo 使用前像重做事务 redo 使用后像2 恢复步骤 1 事务故障恢复采用undo 2020 3 26 34 反向扫描日志文件 查找更新操作对更新操作执行逆操作重复执行 直到此事务开始标识 2 系统故障恢复根据事务状态采取恢复策略 undo redo 恢复步骤 正向扫描日志文件 查找已提交的事务和未提交的事务对于已提交的事务 redo对于未提交的事务 undo 2020 3 26 35 3 介质故障恢复数据和日志文件均被破坏 只有重装数据库 重做已完成的事务 用复本恢复 三 并发控制引论什么是并发 交叉并发 单CPU同时并发 多CPU并发执行引起的问题读写冲突 写写冲突 数据不一致举例 2020 3 26 36 3 并发控制的任务避免访问冲突引起数据不一致 并发控制的正确性原则若某个调度是可串行化的 则是正确的什么是调度 对n个事务的所有操作顺序的一个安排 例如 调度的等价性目标等价 两个调度读出的数据一样 数据库的最终状态一样 冲突等价 通过调换不冲突的操作 得到的新调度 2020 3 26 37 冲突等价目标等价目标等价冲突等价7 可串行化调度若某个调度与一个串行调度等价 则称此调度可串行化 目标可串行化冲突可串行化例 S为冲突可串行化 不一定 2020 3 26 38 目标可串行化不一定是冲突可串行化 例 目标等价于 它是目标可串行化 但不是冲突可串行化 8 可串行化调度判断算法前趋图法画前趋图 若无回路 则可串行化 举例 并发控制的基本方法加锁 基于时间标记的方法 乐观并发控制 2020 3 26 39 四 用加锁方法实现并发控制 X锁 排斥锁在数据对象进行读写之前 要加锁 获得X锁后 才能进行读或写操作 某事务获得X锁后 其他事务不能再加锁 不论是读还是写 X锁要保持到事务结束 否则出错 例 2020 3 26 40 2 两段封锁协议两段事务 加锁都在释放锁之前 合式事务 先加锁 后操作 定理 如果所有事务都是两段 合式事务 则任何调度都是可串行化的 反证法 是充分条件 不是必要条件 2020 3 26 41 3 S X 锁S锁用于读操作 对S锁相容X锁用于写操作若其他事务拥有S锁 此时某事务申请S锁可以获得 但不能获得X锁 4 S U X 锁U锁用于更新操作 多粒度封锁数据库 关系 元组 2020 3 26 42 6 死锁的检测与防止 1 死锁的检测与处理超时法等待图法选择一个事务作为牺牲者 卷回 2 死锁的防止等待 死亡策略击伤 等待策略 2020 3 26 43 五 基于时间标记的封锁协议 要求事务的执行等效于按事务的时间标记顺序串行执行 时间标记系统生成的随时间增长的整数事务的时间标记ts T 事务T启动时赋一个时间标记数据读时间标记tr 读过该数据的所有事务的时间标记最大值数据写时间标记tw 写过该数据的所有事务的时间标记最大值 2020 3 26 44 2 事务读数据的实现read D ifts T twthen 符合时间标记协议tr max ts T tr elserollbackTandrestartit 2020 3 26 45 3 事务写数据的实现ifts T trandts T twthen 符合时间标记协议 wr