数据库是数据的集合，用于描述一个或多个相关组织的活动 数据库管理系统是辅助用户管理和利用大数据集的软件。 数据库管理系统的优点： P7 数据独立性 有效的数据存取 数据完整性和安全性 数据管理 并发存储和故障恢复 减少应用程序开发时间 完整性约束是关系中的记录必须满足的条件，通过说明完整性约束，可以使学生集合的描述更精确。 P9 码约束：关系具有一个特定的最小字段集合，通过它可以惟一确定每条记录。 P47 外码约束：为保持数据一致性事先指定的关系间的约束，是涉及两个关系的最普通的完整性约束。 P48 数据库设计的步骤 P20 1、需求分析 2、概念数据库设计 3、逻辑数据库设计 4、模式的细化 5、物理数据库设计 6、应用与安全设计 ER图 P20~33 实体用矩形框，属性用椭圆框，联系用棱形框 主键用下划实线标识，部分码用虚线标识 关系代数 P75 选行操作符σ 投影列操作符π 重命名操作符ρ 连接操作符 ⋈ 关系演算 P85 关系代数的另一种形式，形如集合。 SQL P96始 存储与索引 P208 磁盘是最重要的外存设备。它允许以一个固定的代价来检索每一页。但是，如果我们按照页面存储的物理顺序连续读取若干页，所花的代价可能比以任意的顺序读取同样的页面要小得多。 磁带是顺序访问设置，这就强迫我们必须一页一页地读。它们通常用于不常用数据的存档。 文件中的每一个记录都有一个惟一的标示符，称为记录id，简称rid。一个rid有一个属性，可以用它来识别包含该记录的页在磁盘上的地址。 索引是磁盘上组织数据记录的一种数据结构，它用于优化某类数据检索的操作。索引使得我们能够有效地检索满足索引的搜索码字段上的搜索条件的那些记录。 我们使用术语数据项来指代存储在索引文件中的记录。作为索引的数据项存储可以是以下3种方式： 数据项k*是一个真正的数据记录。 数据项是一个对，其中rid是搜索码值为k的数据记录的记录id。 数据项是一个对，其中rid-list是搜索码值为k的数据记录的记录id的列表。 聚簇索引：数据记录的顺序与某一索引的数据项顺序相同或类似，我们就称这一索引是聚簇索引。故上面三种方式，第一种方式的索引是聚簇的，而第二种和第三种方式的索引只有当数据记录按照搜索码排序时才是聚簇索引。 主索引：建立在包含主码的字段集合上的索引。其它索引则称为次索引。 索引数据结构：基于哈希，基于树 P211~212 不同文件组织的比较 代价模型： P213 堆文件，排序文件，聚簇文件，具有非聚簇树索引的堆文件，具有非聚簇哈希索引的堆文件…… IO代价的比较 P219 存储数据：磁盘和文件 P230 数据以磁盘块为单位存储在磁盘上。磁盘块是字节的一个连续序列，是从磁盘读/写数据的单位。 通过把缓冲区划分为页集来管理可获得的请在，这些页集通常称为缓冲池。缓冲池中的请在页称为帧，即存放页的槽。 P239 （帧存放页，槽存放元组） 缓冲区替换策略，LRU，FIFO，MRU，随机策略…… P241 树结构索引 索引顺序存取方法（ISAM） P255 主叶子页的数目在文件创建期间是固定的，插入和删除只影响叶子页的内容。为了加快插入操作，溢出链常常不保持顺序。 当数据和大小相对稳定而使得溢出链很少时，ISAM将优于B+树。 B+树 P257 树的秩d，节点容量的度量，对于每个非根节点满足d<=m<=2d，根节点只需满足1<=m<=2d。m为每个节点包含的项数。 插入删除重分布参照书上栗子 块加载（bulk loading） P268 将数据项排序再加载 基于哈希的索引 1、静态哈希 P278 传统的哈希方法，有溢出链 2、可扩展哈希 P279 取二进制某n位分桶（据老师说这可能会出陷阱，未必是后n位） 每个桶维护一个局部深度，仅当桶的局部深度等于全局深度且要分裂时，目录加倍，否则仅分裂桶。 3、线性哈希 P283 以round-robin方式选择，故溢出链在达到多于1个或两个页长度之前，溢出链中的数据项就开始重新分布了。 在Level循环期间，仅使用哈希函数h_level,h_level+1。 在第Level次循环时，NEXT仅扫描0~N_LEVEL-1号桶(N_LEVEL=N*2^Level，N为Level=0时的初始桶数)。 仅当溢出页被创建时，NEXT指向的桶被分裂，NEXT+=1。 在查询时，先使用h_level函数，如果值在[NEXT,N_LEVEL)，则直接找到，否则还要用h_level+1函数来确定它是在该桶中还是在映像桶中。 当NEXT==N_LEVEL-1并发生分裂（有溢出页被创建），则LEVEL+=1,NEXT=0。 具体看书上栗子 外排序 P316 有序的子文件称为段 外归并排序： N为页数，B为主存页数。 第0遍预处理，生成[N/B]个段。其后用B-1个缓冲区输入一个缓冲区输出，同时归并B-1个有序段。 遍数：[log(B-1,[N/B])]+1 总IO次数=2*页数*遍数 块IO，方法基本一样，注意缓冲区块数计算时要向下取整，F=【B/b】-1（有一个作输出缓冲区）。 P321 查询优化 P357始 优化分类：代数优化（表达式的优化），物理优化（存取路径和底层操作算法选择） 连接操作实现： 嵌套循环(nested loop) 排序-合并(sort-merge join) 索引连接(index join) 哈希连接(Hash join) 关系代数恒等式： 选行选列的级联（串接） 选行的交换 笛卡尔积的交换，结合 σ(R⋈S)≡σ(R)⋈S but only if the selection doesn’t refer to S 查询结果大小的估计： 结果元组的最大数目乘以约简因子 P361 函数依赖 P455 X->Y：X决定Y，对于给定的r中的两个元组，若字段x的值相同则字段y的值也相同。 超码：共找到三种不同的定义…… 课件上，如果K->R的所有属性，则K为R的超码 课本上，如果X的子集V->R，则X为超码 度娘上，K为R的超码的条件是：K是R的子集，任意合法关系r(R)中不能有两个元组在属性集K上有相同的值 函数依赖集的闭包 P456 强壮的手臂公理三条 自反律：X⊇Y，则X->Y 增补律：X->Y，则XZ->YZ 传递律：X->Y且Y->Z则X->Z 合并：X->Y且X->Z，则X->YZ 分解：X->YZ,则X->Y且X->Z 平凡的函数依赖指右边只有一个属性，且它也出现在左边。 属性闭包X+，用于推导X->Y是否在F+中只需算X+。 范式： P458 BCNF，鲍依斯·柯德 Boyce-Codd： 对于每个R上成立的函数依赖X->A，都有A∈X或X是超码。 确保只使用函数依赖不能再检测出冗余。 3NF，第三范式： BCNF+"A是R的码的一部分" 无损连接分解：能够根据分解后的关系恢复原来的关系。 测试某分解（R分解为R1,R2）是否无损的充要条件：R1和R2的公共属性或者包含R1的码(R1∩R2->R1)，或者包含R2的码(R1∩R2->R2)。 保持依赖分解的算法： 若(Fx∪Fy)+ = F+，则模式R分解为X和Y的分解是保持依赖分解。 Fx是F+中只包含X的属性的函数依赖集合。 分解为BCNF： P463 若R不是BCNF，则存在X->A是一个违反BCNF的函数依赖，将R分解成R-A和XA。递归。 分解为3NF 上面的方法同样适用，若要保持依赖，则要再补充下面的。 对于不在Fi并集闭包中（即前面提到的(Fx∪Fy)+ ）的依赖X->A，添加关系模式XA到R中。 得到最小覆盖的算法 P465 1、将所有函数依赖变成标准形式：右边为单属性 2、最小化每个依赖的左边 3、删除冗余的函数依赖 分解为3NF方法二 得到一个最小覆盖，使用保持依赖的算法得到关系模式，若不是无损连接的则再加入只包含码中的属性的关系模式。 事务管理 ACID属性 P390 atomicity 原子性 日志保证 consistency 一致性 isolation 隔离性 durability 持久性 日志保证 可串行化调度：调度执行结果对应的数据库实例和按照某种串行顺序执行这些整条得到的结果相同。 可恢复的调度：如果一些事务读了由另一些事务修改了的数据，那么它们的提交必须放在另一些事务的提交之后。 两阶段加锁 two-phase locking P397 读前获得共享锁，写前获得互斥锁。 开始释放锁就不能再申请获得锁。 事务完成时释放所有锁。 严格的两阶段加锁 上面+仅在事务完成时释放锁 可解决级联中止。 死锁 prevention：操作系统的一般方法 detection：维护一个wait-for图，周期性地检查是否有环 avoidance：wait-die，高优先级等低优先级否则中止；wound-wait，高优先级踢低优先级否则等待 崩溃恢复 P403 偷帧stealing frame：提交前将修改写回磁盘 强制写页forcing page：提交时将所有修改立刻写入磁盘 大多数系统使用偷帧，非强制写页的方法。恢复算法ARIES analysis：哪些页脏了，哪些事务正在执行 redo：从最老的记录开始往后将脏页全部重写 undo：从崩溃时间开始往前，将正在执行的事务的写操作撤销