数据库系统实现目录
译者订单
译者简介
出版前言
第1章dbms系统概述
1.1数据库系统的开发
1.1.1早期数据库管理系统
1.1.2关系数据库系统
1.1.3越来越小的系统
1.1.4越来越大的系统
1.1.5信息集成
1.2数据库管理系统概述
1.2.1数据定义语言命令
1.2.2查询处理概述
1.2.3主存储器和缓冲区管理器
1.2.4交易处理
1.2.5查询处理器
1.3图书概述
1.4数据库模型和语言复习
1.4.1关系模型回顾
1.4.2sql审查
1.5次引用
第一部分是数据库系统的实现。
第二章辅助仓储管理
2.1内存层次结构
2.1.1内存层次结构
2.1.2在存储器级之间传输数据
2.1.3易失性和非易失性存储器
2.1.4虚拟内存
2.1.5运动
2.2磁盘
2.2.1磁盘结构
磁盘控制器
2.2.3磁盘访问特征
练习
2.3加速对辅助存储器的访问
2.3.1用于计算的i/o模型
2.3.2按柱面组织数据。
使用多个磁盘
磁盘镜像
2.3.5磁盘调度和电梯算法
2.3.6预取和大规模缓冲
练习
2.4磁盘故障
2.4.1间歇性故障
校验和
稳定储存
2.4.4稳定存储的错误处理能力
2.4.5从磁盘崩溃恢复
2.4.6作为冗余技术的镜像
奇偶校验块
2.4.8一项改进:raid 5
2.4.9多个磁盘崩溃时的处理
2.4.10练习
2.5整理磁盘上的数据
2.5.1定长记录
2.5.2块中固定长度记录的放置
练习
2.6块和记录地址的表示
2.6.1客户端-服务器系统中的地址
逻辑地址和结构地址
指针混合书写
2.6.4块返回磁盘
2.6.5钉住的记录和块
练习
2.7可变长度数据和记录
2.7.1具有可变长度字段的记录
2.7.2具有重复字段的记录
可变格式记录
2.7.4不能加载块中的记录。
2.7.5blob
色谱柱存储
练习
2.8记录的修改
2.8.1插入
删除
修改
练习
2.9摘要
2.10参考文献
第三章指数结构
3.1指标结构基础
3.1.1顺序文件
3.1.2密集指数
3.1.3稀疏指数
3.1.4多级指数
3.1.5辅助指数
3.1.6辅助指标的应用
间接在3.1.7辅助指数
3.1.8文档检索和倒排索引
3.1.9运动
3.2b树
3.2.1b树结构
3 . 2 . 2 B-B树的应用
3.2.3b-树形搜索
3.2.4范围查询
3.2.5b-树插入
3.2.6b-树删除
3.2.7b-采油树效率
锻炼
3.3哈希表
3.3.1二级哈希表
3.3.2插入哈希表
3.3.3删除哈希表
3.3.4哈希表索引的效率
3.3.5可扩展哈希表
3.3.6可扩展哈希表的插入
3.3.7线性哈希表
3.3.8插入线性哈希表
锻炼
3.4多维索引
3.4.1多维索引应用
3.4.2使用传统索引执行范围查询
3.4.3使用传统索引执行最近邻查询
3.4.4多维索引结构概述
3.5多维数据的哈希结构
3.5.1网格文件
搜索网格文件
网格文件的插入
网格文件的性能
3.5.5分段哈希函数
3.5.6网格文件和段哈希的比较
锻炼
3.6多维数据的树形结构
3.6.1多键索引
3.6.2多键索引性能
3.6.3kd树
3.6.4kd树操作
3.6.5使kd- tree适合于辅助存储。
四叉树
r-树
3.6.8r-采油树的操作
锻炼
3.7位图索引
3.7.1位图索引动机
3.7.2压缩位图
3.7.3段长度编码位向量的操作
3.7.4位图索引管理
锻炼
3.8摘要
3.9参考文献
第4章查询执行
4.1物理查询计划运算符介绍
4.1.1扫描表
4.1.2扫描表格时的排序
4.1.3物理运算符计算模型
4.1.4参数来衡量成本
4.1.5扫描运算符的I/o成本
4.1.6实现物理运算符的迭代器
4.2单行程算法
4.2.1一次单元组操作的一遍算法
4.2.2整体关系一元运算的一步算法
4.2.3二进制运算的单行程算法
锻炼
4.3嵌套循环连接
4.3.1基于元组的嵌套循环连接
4.3.2基于元组的嵌套循环连接迭代器
4.3.3基于块的嵌套循环连接算法
4.3.4嵌套循环连接分析
4.3.5迄今为止的算法总结
锻炼
4.4基于排序的两遍算法
4.4.1两级多重合并排序
4.4.2使用排序来消除重复
4.4.3通过排序进行分组和聚合
4.4.4基于排序的联合算法
4.4.5基于排序的交差算法
4.4.6基于排序的简单连接算法
4.4.7简单排序连接分析
4.4.8更有效的基于排序的连接
4.4.9基于排序的算法概述
4.4.10练习
4.5基于哈希的两遍算法
4.5.1通过哈希划分关系
4.5.2基于哈希的重复消除算法
4.5.3基于哈希的分组和聚合算法
4.5.4基于哈希的并、交、差算法
散列连接算法
4.5.6节省一些磁盘I/O
4.5.7基于哈希的算法概述
锻炼
4.6基于索引的算法
4.6.1聚集索引和非聚集索引
4.6.2基于索引的选择
使用索引的连接
4.6.4使用有序索引的连接
锻炼
4.7缓冲管理
4.7.1缓冲管理结构
缓冲管理策略
4.7.3物理操作员选择和缓冲区管理之间的关系
锻炼
4.8使用两遍以上的算法
4.8.1基于排序的多遍算法
4.8.2基于排序的多遍算法的性能
4.8.3基于哈希的多遍算法
4.8.4基于哈希的多遍算法的性能
锻炼
4.9总结
4.10参考文献
第5章查询编译器
5.1语法分析和预处理
5.1.1语法分析和语法分析树
5.1.2sql的简单子集的语法
5.1.3预处理器
5.1.4预处理涉及视图的查询
5.1.5运动
5.2改进查询规划的代数法则
5.2.1交换律和结合律
5.2.2关于选择的法律
下推选择
5.2.4有关投影的法律
5.2.5关于连接和产品的法律
5.2.6关于消除重复的法律
5.2.7关于分组和聚合的法律
锻炼
5.3从解析树到逻辑查询计划
5.3.1转化为关系代数
5.3.2从条件中删除子查询
5.3.3逻辑查询计划的改进
5.3.4可组合/可赋值运算符的分组
锻炼
5.4运营成本估算
5.4.1中间关系大小估计
5.4.2预计作业规模
5.4.3作业规模估算的选择
5.4.4连接操作规模的估算
5.4.5多连接属性的自然连接
5.4.6多重关系的连接
5.4.7其他作业规模的估算
锻炼
5.5引入基于成本的计划选择
5.5.1获取尺寸参数的估计值
5.5.2统计的计算
5.5.3启发式估计以减少逻辑查询规划的成本
5.5.4列举物理平面图的方法
锻炼
5.6连接顺序的选择
5.6.1左右参数连接的含义
5.6.2连接树
5.6.3左深连接树
5.6.4通过动态规划选择连接顺序和分组。
5.6.5具有更具体成本函数的动态规划
5.6.6选择连接顺序的贪婪算法
锻炼
5.7完成实物查询方案选择
5.7.1选择选择方法。
选择连接方法
5.7.3管道化和具体化
5.7.4一元流水线操作
5.7.5二进制操作的流水线操作
5.7.6物理查询计划的符号
物理操作的分类
锻炼
5.8摘要
5.9参考文献
第六章系统故障对策
6.1可恢复运行的问题和模型
6.1.1故障模式
6.1.2交易的进一步讨论
6.1.3交易的正确执行
6.1.4交易的原始操作
6.1.5运动
6.2撤消日志
6.2.1日志记录
6 . 2 . 2撤消日志规则
6.2.3使用撤消日志恢复
检查点
非静态检查点
练习
6.3重做日志
6 . 3 . 1重做日志规则
6.3.2使用重做日志进行恢复
6 . 3 . 3重做日志的重做检查点
6.3.4使用带检查点的重做日志进行恢复
练习
6.4撤消/重做日志
撤消/重做规则
6.4.2使用撤消/重做日志进行恢复
6.4.3撤消/重做日志的检查点
锻炼
6.5介质故障保护
6.5.1备份
非静态转储
6.5.3使用备份和日志进行恢复
练习
6.6总结
6.7参考文献
第7章并发控制
7.1串行调度和可串行化调度
7.1.1调度
7.1.2串行调度
7.1.3可串行化调度
7.1.4事务语义的影响
7.1.5一个用于事务和调度的符号
7.1.6运动
7.2冲突可串行化
6.5438+0冲突
7.2.2优先级图和冲突可串行化判断
7.2.3优先图测试发挥作用的原因
锻炼
7.3使用锁的可序列化实现
7.3.1锁
7.3.2阻塞调度程序
7.3.3两阶段封锁
7.3.4两阶段封锁奏效的原因
练习
7.4具有多种锁定模式的锁定系统
7.4.1***享受锁和专属锁
兼容性矩阵
锁升级
更新锁
增量锁
练习
7.5阻塞调度程序的体系结构
7.5.1调度员进行插入锁定动作
锁表
锻炼
7.6数据库元素的层次结构
7.6.1多粒度锁
警告锁
7.6.3错觉和插入的正确处理
练习
7.7树形协议
7.7.1树形封锁的动机
7.7.2访问树形结构数据的规则
7.7.3树协议工作的原因。
练习
7.8使用时间戳的并发控制
7.8.1时间戳
7.8.2事实上不能实现的行为。
7.8.3脏数据问题
7.8.4基于时间戳的调度规则
多版本时间戳
时间戳和阻止
练习
7.9使用有效性确认的并发控制
基于有效性确认的调度程序的结构
有效性确认规则
7.9.3三种并发控制机制的比较
练习
7.10汇总
7.11引用
第八章再论事务管理
8.1连续性和可恢复性
8.1.1脏数据问题
8.1.2级联回滚
8.1.3可恢复调度
8.1.4避免级联回滚的调度
8.1.5基于锁的回滚管理
8.1.6团体投稿
8.1.7逻辑日志
8.1.8从逻辑日志中恢复
8.1.9运动
8.2僵局
8.2.1超时死锁检测
8.2.2等待图表
8.2.3通过元素排序防止死锁
8.2.4通过时间戳检测死锁
8.2.5死锁管理方法比较
练习
8.3长期业务
8.3.1长交易问题
8.3.2saga(连续记录)
8.3.3赔偿事务
8.3.4薪酬问题发挥作用的原因
练习
8.4总结
8.5参考文献
第9章并行和分布式数据库
9.1关系的并行算法
9.1.1并行模式
9.1.2并行操作,一次一个元组
9.1.3全关系运算的并行算法
9.1.4并行算法的性能
9.1.5运动
9.2地图?减少并行架构
9.2.1存储模式
映射功能
9.2.3还原功能
锻炼
9.3分布式数据库
数据分布
分布式交易
9.3.3数据复制
锻炼
9.4分布式查询处理
9.4.1分布式连接操作问题
半连接简化
9.4.3多重关系的连接
9.4.4非循环超图
9.4.5非循环超图的完全简化
9.4.6为什么完全简化算法有效?
练习
9.5分布式提交
9.5.1支持分布式原子性。
9.5.2两阶段提交
9.5.3分布式事务的恢复
锻炼
9.6分布式封锁
9.6.1集中闭塞系统
9.6.2分布式阻塞算法的成本模型
9.6.3具有多个副本的阻塞元素
9.6.4阻止主副本
9.6.5由局部锁组成的全局锁
练习
9.7点对点分布式搜索
9.7.1对等网络
9.7.2分布式哈希问题
9.7.3分布式哈希的集中式解决方案
9.7.4带绳子的圆圈
9.7.5弦圆上的链环
9.7.6用手指表查找。
9.7.7添加新节点
9.7.8当终端离开网络时,
9.7.9当一端崩溃时,
9.7.10练习
9.8摘要
9.9参考文献
第二部分是现代数据库系统的主题。
第10章信息整合
10.1信息集成简介
10.1.1为什么要整合信息?
10.1.2异质性问题
10.2信息集成模式
10.2.1联邦数据库系统
10.2.2数据仓库
10 . 2 . 3中介
10.2.4练习
10.3基于中介的系统中的包装器
10.3.1查询模式模板
10.3.2包装生成器
10.3.3过滤器
10.3.4包装上的其他操作
10.3.5练习
10.4基于容量的优化
10.4.1有限的数据源能力
10.4.2描述数据源功能的符号
10.4.3基于能力的查询计划选择
10.4.4添加基于成本的优化。
10.4.5练习
10.5优化中介查询
10.5.1简化修饰符号
10.5.2得到子目标的答案。
10 . 5 . 3链算法
10.5.4组合并查看中介
10.5.5练习
10.6将本地作为视图的中介
10.6.1lav介体的动机
10 . 6 . 2法律调解人术语
10.6.3扩展解决方案
10.6.4包含联合查询
10.6.5为什么包含映射测试有效?
10.6.6发现介体查询的解决方案。
10.6.7为什么lmss定理成立?
10.6.8练习
10.7实体分析
10.7.1决定记录是否代表* * *实体。
10.7.2合并相似记录
10.7.3合并函数的相似性和有用性质
icar录制的10.7.4icar?Swoosh算法
10.7.5为什么是R?Swoosh算法将是有效的
10.7.6实体解析的其他方法
10.7.7练习
10.8汇总
10.9参考文献
第11章数据挖掘
11.1频繁项集挖掘
11.1.1市场-购物篮模型
11.1.2的基本定义
11.1.3关联规则
11.1.4频繁项集的计算模型
11.1.5运动
11.2查找频繁项集的算法
11.2.1频繁项集的分布
11.2.2寻找频繁项目集的朴素算法
11.2.3a?先验算法
11.2.4a?先验算法的实现
11.2.5更好地利用主内存
11.2.6什么时候用pcy算法?
11.2.7多级算法
11.2.8运动
11.3找到类似商品。
11.3.1相似性的Jaccard度量
11.3.2jaccard相似度的应用
11.3.3最小哈希
11.3.4最小散列和jaccard之间的相似性
11.3.5为什么最小哈希可以用来估计相似度?
11.3.6最小散列的实现
11.3.7运动
11.4本地敏感哈希
11.4.1lsh示例:实体解析
11.4.2标记的本地敏感哈希
11.4.3最小哈希方法和本地敏感哈希的组合
11.4.4运动
11.5大规模数据聚类
11.5.1聚类的应用
11.5.2距离的定义
11.5.3内聚聚类
11.5.4k?均值算法
大规模数据11.5.5 K?手段方法
11.5.6内存满点后的处理。
11.5.7运动
11.6汇总
11.7参考文献
12章数据库系统与互联网
12.1搜索引擎架构
12.1.1搜索引擎的组成
12.1.2网络爬虫
12.1.3搜索引擎中的查询处理
12.1.4排名网页。
用于识别重要网页的Pagerank。
12.2.1pagerank的直觉思维
12.2.2pagerank的递归公式——初步尝试
12.2.3履带陷阱和死角
12.2.4考虑爬虫陷阱和死角的pagerank
12.2.5练习
12.3特定主题的pagerank
12.3.1“长途移动”收藏
12.3.2计算与话题相关的pagerank。
12.3.3链接作弊
12.3.4主题相关的pagerank和链接作弊
12.3.5练习
12.4数据流
12.4.1数据流管理系统
12.4.2数据流应用
12.4.3数据流数据模型
12.4.4数据流转换成关系
12.4.5关系转换为数据流
12.4.6练习
12.5数据流挖掘
12.5.1动机
12.5.2二进制数字的统计
12.5.3计算不同元素的数量
12.5.4练习
12.6汇总
12.7参考文献