Database System course notes.
1. relation model
1.1. schema & instance
Def: dabase table(instance)
Def: database schema,就是设计模式,抽象的东西。
Def: superkey (is a set),一个超码是多个属性的集合,能够唯一标示一个元组
Def: candidate key (is a set),一个候选码是某一个超码的子集,且真子集不是超码,意思就是不能再减少属性的超码,毕竟超码可能有冗余。所有候选码是所有超码的子集
Def:primary key 是从候选码里选一个。
- Note: pk \(\in\) candidate \(\in\) super
Def: foreign key,x参照y是因为y在r2是主码。r1是y的参照关系,r2是y的被参照关系。
Def:参照完整性约束
r1 在 k 属性上的取值是r2 在 k 属性(属性名称可能不一样)上取值的子集。就是如果你包含别的模式的主码,你的取值不能超过该主码在自己模式的取值范围。
1.2. schema diagram
2. SQL
2.1. basic structure
2.1.1. create
Def: create table
CREATE TABLE Persons ( PersonID int, LastName varchar(255), constraint_name FirstName varchar(255), constraint_name Address varchar(255), constraint_name City varchar(255) constraint_name );
Note: constraint
在 SQL 中,我们有如下约束:
- NOT NULL - 指示某列不能存储 NULL 值。
- UNIQUE - 保证某列的每行必须有唯一的值。
- PRIMARY KEY - NOT NULL 和 UNIQUE 的结合。确保某列(或两个列多个列的结合)有唯一标识,有助于更容易更快速地找到表中的一个特定的记录。
- FOREIGN KEY - 保证一个表中的数据匹配另一个表中的值的参照完整性。
- CHECK - 保证列中的值符合指定的条件。
- DEFAULT - 规定没有给列赋值时的默认值。
Def: create index
CREATE UNIQUE INDEX index_name ON table_name (column_name)
2.1.2. select
Def:
SELECT [DISTINCT/ALL] column_name AS alias_name,column_name
FROM table_name as...
[WHERE] column_name (一条比较一条)
OPERATOR SOME/ALL (嵌套子查询)
OPERATOR value
LIKE pattern
BETWEEN value1 AND value2/
)
[WHERE] column_name (一条比较一个集合)
IN (一条对比嵌套子查询)
UNIQUE (一条插入嵌套子查询)
EXISTS(一条插入嵌套子查询)
)
[AND/OR]
(当使用aggregate函数的时候才能用) [GROUP BY] column_name;
(当使用了group by,且想) [HAVING] SUM(access_log.count) > 200;
[ORDER BY] column_name,column_name ASC|DESC;
[LIMIT] 2;
[INTO] newtable [IN externaldb]
- 可以用with 做一个临时table
- 可以用from(from)操作,里面是一个小table
- 可以用集合函数来操作嵌套子循环
- Def:运行顺序:
- from... where...group by... having.... select ... order by... limit
2.1.3. insert
Def:
INSERT INTO table_name (column1,column2,column3,...) VALUES (value1,value2,value3,...);
2.1.4. update
Def:
UPDATE table_name SET column1=value1,column2=value2,... WHERE some_column=some_value [AND/OR]
2.1.5. delete
Def:
DELETE FROM table_name WHERE some_column=some_value [AND/OR]
2.1.6. join
Def: join
[INNER] JOIN access_log ON/USING Websites.id=access_log.site_id;
2.1.7. alter
Def:
ALTER TABLE Persons
ADD DateOfBirth date(type)
DROP COLUMN DateOfBirth
2.1.8. functions
- Def: aggregate 函数计算从列中取得的值,返回一个单一的值。
- AVG() - 返回平均值
- COUNT() - 返回行数
- FIRST() - 返回第一个记录的值
- LAST() - 返回最后一个记录的值
- MAX() - 返回最大值
- MIN() - 返回最小值
- SUM() - 返回总和
- Def: SQL Scalar 函数基于输入值,返回一个单一的值。
- UCASE() - 将某个字段转换为大写
- LCASE() - 将某个字段转换为小写
- MID() - 从某个文本字段提取字符,MySql 中使用
- SubString(字段,1,end) - 从某个文本字段提取字符
- LEN() - 返回某个文本字段的长度
- ROUND() - 对某个数值字段进行指定小数位数的四舍五入
- NOW() - 返回当前的系统日期和时间
- FORMAT() - 格式化某个字段的显示方式
2.2. view
- Def:理解为一个临时表格。只有满足一些条件才能更新,
2.3. transaction
2.4. 授权图
- Def:
2.5. function
2.6. trigger
## algebra
2.7. 实现
- Def: https://www.cnblogs.com/Dhouse/p/6734837.html
3. database design
3.1. E-R
3.1.1. entity
3.1.2. relationship
Def: relationship
3.1.3. attributes
3.1.4. E-R map
Def:
Def; 弱实体集就是没有主码,因为这个唯一主码体现了和别的集合的关系,如果去掉主码就雪崩;如果去掉联系集就不是好的ER图。所以这时候把主码去掉,然后把弱实体双线全部连接到主实体集,意思就是一个主实体对应多个弱实体。
3.1.5. relation model & E-R model
3.1.5.1. simple_a & strong_e
3.1.5.2. multi_a & string_a
3.1.5.3. weak entity
3.1.5.4. relationship
3.2. decomposition
3.2.1. why?
Def : failed decomposition,分解后信息不对称了。所谓范式是针对依赖集和关系模式而定的,一个关系模式具有好的依赖集可能就会属于好的范式,分解之类的操作就会好。
Def: 保持依赖:分解后原依赖集 = 后依赖集(后依赖集等于限定的并)
Def:无损分解:分解后笛卡尔积不变。
3.2.2. 1nf
3.2.3. dependency
Def: candidate key
Def: 依赖关系:a -> b 意思是a指挥b,意思就是如果两个元祖中a相等,那么b一定相等。
Def:怎么推函数依赖,公理
Def: 依赖集合
Def: 依赖集合的闭包:所有可推出的函数依赖集合。
- Def:依赖集合的无关属性:去掉该属性不改变闭包
- Qua: 怎么计算?用闭包;F可以推出用除了该条依赖并上左边减掉后;用除了该条依赖并上右边减掉后 推出Fz
Def:依赖集合的最小覆盖er
Def: 依赖集合的正则覆盖,是一个和原依赖集相互推出的一个依赖集合,意思就是等价。而且包含一些性质(去掉了无关属性,左半部是唯一的)
3.2.4. 3nf
Def: BCNF放宽,函数依赖左侧可以是超码,也可以是多了一个条件,多了一个条件就是没有传递函数依赖。
3.2.5. BCNF
Def: 所有依赖左边都是超码。
4. index
Def: mysql 中的索引
主键(聚集)索引:屋里顺序和搜索码排序一致;一个表就一个,主键默认索引所以也叫主键索引。
1
create clustered index clustered_index on table_name(colum_name)
聚集索引就是按照每张表的主键构造一颗B+?树,同时叶子节点中存放的即为整张表的记录数据。
非聚集索引:物理顺序不按搜索码排序。
- 全文索引:
- 唯一索引:
- 普通索引
区别:通过聚集索引可以查到需要查找的数据, 而通过非聚集索引可以查到记录对应的主键值 , 再使用主键的值通过聚集索引查找到需要的数据。二次查询问题也是从这来的。
1
select username, score from t1 where username = '小明'
假如score没有索引、username是非聚集索引,那么就先找到主键id,然后通过主键找score。如果select是username + id的话,就没有二次查询了。
4.1. 全文索引
Def:为了模糊搜索(match(content),like)
通过数值比较、范围过滤等就可以完成绝大多数我们需要的查询,但是,如果希望通过关键字的匹配来进行查询过滤,那么就需要基于相似度的查询,而不是原来的精确数值比较。全文索引就是为这种场景设计的。
4.2. 覆盖索引
- Def:包含了select/where涉及的列。
## 最左前缀
Def:最左前缀原则
而最左前缀原则指的是,如果查询的时候查询条件精确匹配索引的左边连续一列或几列(顺序无所谓),则此列就可以被用到。如下:
1
2
3
4
select * from user where name=xx and city=xx ; //可以命中索引
select * from user where name=xx ; // 可以命中索引
select * from user where city=xx ; // 无法命中索引在创建联合索引时,索引字段的顺序需要考虑字段值去重之后的个数,较多的放前面。ORDER BY子句也遵循此规则。
5. transaction
5.1. transaction
Def: 事务的性质
- 原子性,要么反应要么不反应,不能再分
- 一致性,保持数据库(应用系统从一个正确的状态到另一个正确的状态)也就是在给定的约束下,数据库语句总能得到正确的结果。
- 隔离性,事务之间觉察不到存在
- 持久性,永久的
Def: 事务的状态
Def:sql隔离等级如下。数据库并发控制的目的是,让所有尽可能调度都和串行等价,因为串行一定是正确的解。
5.2. 隔离性
Def:为什么要并发(注意是并发不是并行)?
- 吞吐率(事务数/时间),CPU和IO可以并行执行,比如T1先来一个CPU,T2来一个IO然后就可以增加吞吐量。
- 减少等待时间(事务完成-提交),其实和上面类似的。
Def: 并发隔离级别:就是对调度的约束。
可串行化(针对所有):这个是最高级别的了,也就是调度等价于串行,但是约束也很大。
可重复读(针对脏读+不可重复):只允许读已提交数据,一个事务两次读一个数据期间其他事务不得更新。
已提交读(针对脏读):只允许读已提交数据。
未提交读:允许读未提交数据。
Def:不同隔离级别可能的问题
5.2.1. schedule
Def: 调度和串行:
- 调度:一个调度指的是很多个process的按照时间线来的操作。
串行指的是一个调度中,所有来自相同事务的聚在一起。
Def: 冲突等价和冲突指令:
- 冲突等价:就是等价
- 冲突指令:指的是一条包含write,一条不包含,这样两个不能交换。
Def:可串行化:和某一个串行调度等价
5.2.2. 可恢复 schedule
Usage:为什么需要这个定义?
因为可恢复+无忌廉能够使得rollback操作容易完成,使得更好的满足隔离性和原籽性。
Def:可恢复:
如果i读取了j写过的数据,那么i比j提前提交(这是因为如果i还没交就挂了,我们需要rollback j,但是j已经交了就完蛋了)
Def:无及联:
如果i读取了j写过的数据,那么i在j的第一个读操作前提交。
5.2.3. lock实现
5.2.3.1. 2-phase
Def: 两阶段协议(保证serialization )
- 以第一个释放锁为节点,不能再获得新锁。
- 锁升级只能发生在节点以前
- 锁降级只能发生在节点以后
Def: 严格两阶段(serialization + no cascade ,)
- 加上所有X锁必须在提交后释放。
Def: 强两阶段(serialization + no cascade + no deadlock)
- 所有X,S锁必须在提交后释放。
Def:一个通用的加锁方法
- 读之前加S锁
- 写之前要么升级,要么加X锁
- commit后所有锁被释放
5.2.3.2. 乐观锁
Def:乐观锁(处理写写冲突)
总是假设最好的情况,每次去拿数据的时候都认为别人不会修改,所以不会上锁,但是在更新的时候会判断一下在此期间别人有没有去更新这个数据,可以使用版本号机制和CAS算法实现。乐观锁适用于多读的应用类型,这样可以提高吞吐量,像数据库提供的类似于write_condition机制,其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。
- 加一个版本号表示被修改的次数,当被修改时,修改前后版本号相等才更新否则回滚。
5.2.3.3. 行锁和表锁
Def: myISAM
- 用表级锁。
Def:innodb
Def:什么时候用表锁?
第一种情况是:事务需要更新大部分或全部数据,表又比较大,如果使用默认的行锁,不仅这个事务执行效率低,而且可能造成其他事务长时间锁等待和锁冲突,这种情况下可以考虑使用表锁来提高该事务的执行速度。
第二种情况是:事务涉及多个表,比较复杂,很可能引起死锁,造成大量事务回滚。这种情况也可以考虑一次性锁定事务涉及的表,从而避免死锁、减少数据库因事务回滚带来的开销。
5.2.3.4. 间隙锁
Def: 间隙锁
当我们用范围条件而不是相等条件检索数据,并请求共享或排他锁时,InnoDB会给符合条件的已有数据的索引项加锁;对于键值在条件范围内但并不存在的记录,叫做“间隙(GAP)”,InnoDB也会对这个“间隙”加锁,这种锁机制就是所谓的间隙锁(Next-Key锁)
Example:
举例来说,假如emp表中只有101条记录,其empid的值分别是1,2,...,100,101,下面的SQL:
1
SELECT * FROM emp WHERE empid > 100 FOR UPDATE
是一个范围条件的检索,InnoDB不仅会对符合条件的empid值为101的记录加锁,也会对empid大于101(这些记录并不存在)的“间隙”加锁。
Note: 为什么?
- 防止幻读,以满足相关隔离级别的要求,对于上面的例子,要是不使用间隙锁,如果其他事务插入了empid大于100的任何记录,那么本事务如果再次执行上述语句,就会发生幻读
- 为了满足其恢复和复制的需要。有关其恢复和复制对机制的影响,以及不同隔离级别下InnoDB使用间隙锁的情况。
5.2.4. graph 实现
Def: 图协议:serialization + no deadlock
- 首先设计一个图,然后保证 一个T
- 对子节点加锁必须有父节点锁
- 加锁解锁后不能再加锁。
commit前不允许释放X锁(附加这一条可以保证可恢复性+无忌廉)
5.2.5. deadlock
5.2.5.1. prevention
5.2.5.2. detection
5.2.5.3. recover
5.2.6. timestamp实现
Def: 时间戳实现(serialization + no deadlock)
- Def:thomos 写规则(上述的改进)
- 写的话
- 如果小于写时间戳,则wirte忽略而不是拒绝。
- 写的话
5.2.7. mvcc 实现
Def: mvts 同样也是保证隔离性的机(serialization)
- 每个数据项有一个版本序列<Q1...Qn>,每个版本Q = <值,创建时间戳W,读取最大时间戳R>
- 每个事务通过write(Q) 创造一个新版本Qi,WR初始化为T,R会随着读取更新。
- 如果是读的话
- 返回Qmax,更新R。
- 如果是写
- 如果小于R,回滚
- 如果等于R,覆盖Q的值
- 如果大于R,创建新Q连到后面
- 如果是删除
- 小于R/W回滚,否则直接标记为删除即可。
- 如果某数据的两个版本W都小于最大事务时间戳,那么两个版本中旧版本可以删除。
- Note
- 好的特性,读不用等待!
- 坏的特性,读会两次磁盘访问;冲突必须回滚。
- Def:mvcc针对读写冲突的协议,保证read-committed
- 没有版本序列,而是加入“删除列”
- Q = <值,W,D> D表示删除的id,这个删除并不只是指那些delete操作,也包括了update,update实质是新插入一行,并且标记原有行为删除,这样才能让某一些事务只能读到以前的值
- update的事务提交执行以后,
- 新增一行,然后附上自己的事务id
- 再标记之前的那行数据的删除id。
- read的事务执行时
- 更新id小于等于当前id/删除id大于当前id, 读。只能读取“更新id小于等于当前id”可以保证repeatable read特性
- 否则回滚
- Note:保证read-committed,因为只有commit之后才写?
5.2.8. 快照实现
5.3. 隔离性:recover
5.3.1. 应该产生什么样的调度
- Def:可恢复,如果i读取了j写过的数据,那么i比j提前提交(这是因为如果i还没交就挂了,我们需要rollback j,但是j已经交了就完蛋了)
- Def:无及联,如果i读取了j写过的数据,那么i在j的第一个读操作前提交。
5.3.2. storage
5.3.3. log
5.3.4. 恢复算法
Def:redo重做:
Def:undo回滚:从后往前,恢复旧值,写一个log表示已经undo,直到start写一个abort。
Def:恢复算法:没有commit/abort就撤销,有就重做。
具体来说,先从后到前扫重做一遍,然后找到没有commit/abort的操作,这是redo阶段。
在undo阶段一旦找到undolist中的东西就undo,遇到start就去掉,直到所有都undo完。
5.3.5. 检查点算法
- Usage:恢复算法需要搜索一边太麻烦
- Def:检查点干什么:
- 把所有log输出到disk
- 把所有修改的块输出到disk
- 写一个<checkpoint T1~Tn>表示检查时正在活跃的事务。
- Def:检查点算法:找到最后一条检查点,然后对检查点中涉及到的和之后才开始的事务进行恢复算法。
6. interview
6.1. 主从分离
Def:graph
https://blog.csdn.net/itcats_cn/article/details/82155651
Def: 主从复制:是一种数据备份的方案。
简单来说,是使用两个或两个以上相同的数据库,将一个数据库当做主数据库,而另一个数据库当做从数据库。在主数据库中进行相应操作时,从数据库记录下所有主数据库的操作,使其二者一模一样。
Note: 具体怎么做?
1) 在每个事务更新数据完成之前,master在二进制日志记录这些改变。写入二进制日志完成后,master通知存储引擎提交事务。
2) Slave将master的binary log复制到其中继日志。首先slave开始一个工作线程(I/O),I/O线程在master上打开一个普通的连接,然后开始binlog dump process。binlog dump process从master的二进制日志中读取事件,如果已经跟上master,它会睡眠并等待master产生新的事件,I/O线程将这些事件写入中继日志。
3) Sql slave thread(sql从线程)处理该过程的最后一步,sql线程从中继日志读取事件,并重放其中的事件而更新slave数据,使其与master中的数据一致,只要该线程与I/O线程保持一致,中继日志通常会位于os缓存中,所以中继日志的开销很小。
Def:读写分离:是一种让数据库更稳定的的使用数据库的方法。
是在有从数据库的情况下使用,当主数据库进行对数据的增删改也就是写操作时,将查询的任务交给从数据库。
- Note: 什么意思?简而言之就是把读操作分摊到各个从数据库上。写的时候显然所有都不能读,这个操作时间无法分摊,但是读操作是可以分摊的。
6.2. delete truncate drop
https://blog.csdn.net/GRAY_KEY/article/details/86742248
- Note: 区别
- 删除的内容
- 是否可以回滚:delete可以,其他不行
- 是否触发触发器,维持约束性:delete可以,其他不行。
6.3. explain、慢查询日志、show profile等)
Def: mysqldumpslow慢日志
从慢查询日志中,我们可以看到每一条查询时间高于1s钟的sql语句,并可以看到执行的时间是多少
Def:Explain+SQL语句
使用EXPLAIN关键字可以模拟优化器执行SQL查询语句,从而知道MySQL是 如何处理你的SQL语句的。分析你的查询语句或是表结构的性能瓶颈。
Def:show profile
Show Profile是MySQL提供可以用来分析当前会话中语句执行的资源消耗情况,可以用于SQL的调优测量 默认关闭,并保存最近15次的运行结果
Def:count
加索引
Def;子查询的优化
变成join