Weekly Assessment 错题知识点复习

Week 1

insert语句语法

insert into table_name VALUES (value1, value2)

创建外键语法

CONSTRAINT fk_name FOREIGN KEY (从表的属性名) REFERENCES 主表(主表的属性名)

有两个表A(a), B(b)。a是主键，b通过外键连向a，即B表索引自A表。此时，只有对B表进行删除操作是肯定可行的。

其余操作：

1. 在A表中插入一个值：可能会打破主键约束。
2. 从A表中删除一个值：可能会打破外键约束。
3. 从B表中插入一个值：可能会打破外键约束。

Week 2

week2主要是sql语句查询，没啥好注意的，发现了再说吧。

Week 3

事务的四个隔离级别：

1. 读未提交(Read Uncommitted)：可以读还没被提交的数据（可以说是根本没隔离）
2. 读已提交(Read Committed):读的都是已经提交的数据
3. 可重复读(Repeatable Read)：事务一旦开始，事务进行过程中读取的所有数据不允许被其他事务修改。
4. 序列化(Serializable)：指事务的操作按顺序执行，不可以插队。（这个概念总是忘，写在这记录一下）

Week 4

2PL：

1. 锁+读写操作
2. 解锁+读写操作

注意：

1. 看清解锁后是否有上锁行为
2. 重点：一定要看清上锁的事务和数据项以及对应解锁的事务及数据项，很容易在这里出问题。

Week 5

Redo日志如何执行？

和Undo日志相反

1. 先找出redo日志中所有的COMMIT。
2. 从第一项到最后一项遍历日志。
3. 如果看见<T, x, v>，并且该事务T有COMMIT标记，那么把磁盘上X的值改为v。
4. 对于未完成的事务T，将<abort T>写入磁盘上的日志。

有关checkpoint

现在有一个Undo/Redo log，使用了ARIES checkpoints。当发生崩溃时，我们需要最先看哪一行

<START T1>
<T1,X,1,2>
<START T2>
<T2,Y,5,1>
<START T3>
<COMMIT T1>
<CHECKPOINT(T2,T3)>
<COMMIT T2>
<END CHECKPOINT>

显然，checkpoint出现在第7行，并且end checkpoint出现在第9行，T1和T2已经被commit，所以应该返回第5行，即<START T3>，还没有被提交的事务。

strict schedule

Strict schedule 一定满足哪个隔离级别？

一定满足Read Committed，因为Strict Schedule要求是无级联，只允许读取已经提交的值。所以它一定满足level2 Read Committed，但是不一定满足level 3，Repeatable Read。因为没有对可重复读作出要求、

可重复读指：事务一旦开始，事务进行过程中读取的所有数据不允许被其他事务修改。

时间戳

timestamp属于一种预防死锁的机制，当一个事务对一个数据拥有锁，而另一个事务试图访问这个数据时，才会激发预防死锁的机制，也就是说，时间戳才能派上用场。否则任何事务都不会重新启动。

Week6

第六周主要是知识点需要学明白，索引（B树，B+树）

create index
    on Students using btree
    (programme, year);

B树（B-树）

为什么选择B树这种数据结构？

众所周知，大部分树状的数据结构都是二叉树，这就是一个致命缺点。当数据量过于庞大的时候，二叉树会变的很深，而想要搜索值，就要进行很多次磁盘I/O，把数据加载到内存中，这是十分浪费时间的。 而B树（B+树）恰好解决了这一个痛点，这种数据结构可以在每一层的每个节点上存放好多数据，这就会明显减少树的深度，也就是减少了磁盘I/O的次数，当数据量十分庞大时，会节省很多的时间。

B+树

选择n值使得该节点适合单个磁盘块。n的计算方法： 一个节点中有n个value和n+1个指针。所以 Disk block size>=n*(value_size + pointer_size) + pointer_size。

Leaves

叶子节点中并不是所有的空间都要被使用 只要确保有floor((n+1)/2)个指针被使用就可以了，只有一片叶子这种情况除外。指向下一个叶子节点的指针也算是指针。

Inner nodes

内部节点也并不是所有空间都要被使用 要确保有ceil((n+1)/2)个指针被使用 例外：根节点必须有2个以上节点

遇到B+树题思考过程：

1. 确定n值，value有几个方块就是几个n
2. 根据n值计算出每个内部节点和叶子节点需要至少有几个pointers

寻找值：

1. 从树的root节点开始
2. 如果当前节点不是叶子节点
   • 如果要找的值比第一个小，直接传到第一个子节点
   • 否则找到一个最大的i使得ai<=v，然后传到其对应的子节点
3. 如果当前节点是叶子节点
   • 如果v出现在叶子中，则跟随对应的指针输出
   • 若不在叶子中，则返回"v不存在当前索引中"
4. Running time: O(h*log(n)) 其中log以2为底

插入值/指针对

下面几步我愿称其为法宝（老师的summary并不完整，这里有所补充）

1. 找到一个应该包含这个值的叶子节点

2. 如果这个叶子节点没有满，则插入在该节点合适的位置

3. 如果这个叶子节点满了 (找传递的下一个叶子节点，如果下一个也是满的，则👇)

   • 拆分叶子节点给即将插入的值创造空间，并且把该节点一半数量的指针移植到新节点。
   • 插入值/指针对
   • 把叶子节点连到对应的父节点上（也可能会出现新的父节点）

4. 如何更新祖先节点？

   • 应该更新的祖先节点的值是空的
   • 向右侧指向的下一级
   • 接着一直向左侧指向的下一级
   • 直到到达叶子节点，将找到的叶子节点中最左侧（最小）的值更新在祖先节点上。

   PS：如果只更新一级就到叶子节点了呢？那就找到当前叶子节点中最左侧的值更新在其父节点上

5. Running time: O(h*log(n)) 其中log以2为底

删除值/指针对

1. 找到包含这个值的叶子节点
2. 移除这个值/指针对
3. 假设现在这个节点是C
   • x=2 如果C是根节点
   • x=ceil((n+1)/2) 如果C是内部节点
   • x=floor((n+1)/2) 如果C是叶子节点
4. 如果C的指针数量超过x个，修补祖先节点，结束。
5. 如果C是根节点而不是叶节点，移除该节点，并且让其子节点称为新的根节点
6. 否则，检查相邻节点是否有至少x+1个指针
   • 相邻节点：相同深度，共同祖先，且这个共同祖先在这两个子代节点中间没有任何子代。
7. 如果有，拿走一个，修复祖先节点，结束。
8. 否则，合并兄弟姐妹节点，并转到第三行，父节点为当前节点。

这是老师的方法👆，我觉得不是很好理解，下面自己总结一下👇

1. 找到包含这个值的叶子节点
2. 移除这个值/指针对
3. 看当前叶子节点的指针数量是否满足要求(>=floor((n+1)/2))。
   • 这里要注意：指向下一节点的指针也算是指针,即使是叶子节点中的最后一个节点（最后一个节点是没有指向下一个节点的指针的，但是也要看做是有指向下一个节点的指针）这是老师回答我的，我觉得很不解和震惊，但是只能妥协。毕竟这不是我发明的数据结构:)
4. 如果移除值后，该叶子节点的指针数量不满足要求，则要从相邻节点”偷“指针过来
   • 相邻节点至少有floor((n+1)/2) +1个指针。因为只有这样才能保证被偷走一个指针后，自己的指针还够用。
   • 相邻节点：相同深度，共同祖先，且这个共同祖先在这两个子代节点中间没有任何子代。
5. 修复祖先节点，口诀right-left-left-left直到找到叶子节点结束。
6. 相邻节点的指针数也太少了，偷不过来怎么办？
   • 选择一个相邻节点进行合并
   • 内部节点更新也是如此，内部节点需要从相邻节点（指针数>=ceil((n+1)/2)+1）偷一半过来，更新。
7. 记得一层一层更新，直到更新到根节点，最后一定检查有没有漏掉的！！！

注意：对于相同的一些值，也会有不同的B+ tree的写法 (example: insert & delete 42)

查询过程如图所示

Week7

查询优化的启发式方法（Heuristics for query optimization）

1. 把selections尽可能的向树的底端推移（目的是尽早摆脱不相关的tuple）
2. 把projections尽可能的向树的底端推移
3. 用equijoins符号代替跟在selection+✖️，因为equijoins比selection+✖️要更快

从初始查询集开始，使用这三种启发式方法，如果我们以所有可能的方式重复应用它们，最终会得到什么结果？

该集合可能包含多个最优化的查询，但由于管道的存在，它们对于物理查询计划是等效的

物理查询计划

物理查询计划目的是添加执行优化查询计划所需的信息

如何将信息从一个操作符传到另一个？

1. Materialisation: 将中间结果写进磁盘
2. Pipelining: 中间selection的结果会被写进内存中的buffer，projection符号将会读取并直接处理这些元组。（Tuple是行，Attributes是列）

2PC/3PC 协议

因为BASE(Basically Available, Soft state, Eventually consistent)理论需要在一致性和可用性方面作出权衡，因此出现了许多关于一致性的协议，其中就有2pc(2 phase commitment protocol)/3PC协议。

2PC

• Decide when to commit or abort.
• Commit or abort.

3PC

• Decide when to commit or abort.
• Prepare to Commit
• Commit

三段提交就是把2段提交的第二步拆成了两个步骤，可以说是更详细了，解释一下3PC的第二步Prepare to Commit：

• 协调器给各个节点发送commit或abort的message。
• 各个节点进入prepare to commit状态。

协调者：在一些节点上执行，并且决定本地事务是否提交和何时提交。是事务管理器。

参与者：就是一些节点，也是资源管理器。

在每个节点本地都会写入日志，无论是发送message还是从其他节点接收message。

Phase 1: When to commit

1. 协调器发起询问：问各个节点是否想提交，向各个节点发送<prepare T>
2. 各个节点决定是提交(Commit)还是废弃(Abort)
   • 想提交，向协调器发送<ready T>，并且自身进入precommitted状态，一旦进入这个状态，就只有协调器才能废弃这个事务。
   • 不想提交，发送<don't commit>到协调器并且废弃本地事务。
   • 可以delay，但一定要告诉协调器一个准确答案，提交or废弃。

Phase 2: Commit or abort

(假设在给定超时前未回复的节点希望中止)

1. 如果所有节点都希望commit，协调器发送<commit T>给所有的节点，节点收到消息后进行提交。
2. 如果有节点不想提交，那么协调器发送<abort T>到所有节点，节点收到消息后将事务废弃。

有关提交日志

Phase1

Phase2

如果日志中< COMMIT T >是日志的最后一条，就知道事务是被提交了，如果登入日志和send commit T之间发生failuer，则进行redo T1（T1是节点上的事务）操作就可以。< ABORT T >同理

计算题（一次查询中，计算两个site之间传输的数据大小）

双站点题

已知A站和B站，A站存了一张表R，B站存了一张表S，在B站上进行一次查询（需要用到A站中存的信息），问A向B站传输的数据是多少

分别计算A->B和B->A->B传输的数据大小，然后进行比较。

Week8

1. 2PC协议中，<PRECOMMIT T>不会被写进日志中。第七周的知识点，被出到了第八周的题里，又狠狠被他水到了，可恶

2. …E[i]:现在这个节点是E的第i个子节点

   …E[*[i]]:拿到E的第i个子节点向下的所有Element

Week9

<pair>{$item},{$title}</pair>，每个title和每个item都要匹配，最终输出<pair></pair>ELement的数量为title的数量✖️item的数量

Week10

1. OLAP: Online Analytic Processing, 指的是分析存在数据仓库里的复杂数据的过程。经常会使用where和group by子句。
2. OLTP: Online Transaction Processing, 传统的DBMS的任务，能被快速执行的查询和更新；影响数据库的一小部分。
3. Market-basket model (Data mining)
4. Association Rules (Data mining)
   • 经常买尿布的人也经常买啤酒，General form: {尿布} => 啤酒
   • 置信度(Confidence)：{i1, i2, ..., in}集合中包含j的概率。 support of {i1, ..., in, j}/support of {i1, ..., in}
5. A-priori ALgorithm: 计算支持>=s的所有数据项J
   • 如果J的支持>=s, 那么J的所有子集的支持都>=s。