大学课程基础知识整理:数据库原理

2014-10-10 • 技术文章评论

前言

大学行将结束,部分课程知识在未来还会应用到,特此整理为本系列博文,不求具体深入,点到为止。

键、最小依赖集和无损分解的判断

设R的属性集为U,X是U的一个子集。如果X→U在R上成立,则称X为R的一个超键。如果X→U在R上成立,但X是可能是最小的子集,则X为候选键。

最小依赖集应满足:最小集闭包=集合闭包,每个FD的右边都是单属性,最小集中没有冗余的FD,左边没有冗余的属性。最小依赖集不一定唯一。求法:拆成右边都是单属性的形式,删去冗余。

R有n个属性和k个分解集,做k行n列表,若属性在集中则标aj,否则标bij,对FD X→Y,如果表格中有两行在X值上相等,在Y值上不相等,那么这两行的Y值改成相同的值,若修改后的表有一行全是a,则无损。

三大范式与反范式

第一范式:如果关系模式R的每个关系r的属性值都是不可分的原子值,则称R为1NF。如R(NAME, MAIL),若一个人有多个邮箱,则要出现多个元组以便存储。

第二范式:在1NF基础上,每个非主属性完全函数依赖于候选键,则称R为2NF。旨在消除局部依赖。求法举例:R(WXYZ),主键是WX,R上存在X→Z的局部依赖,则分解为R1(XZ)和R2(WXY)。

第三范式:在1NF基础上,每个非主属性都不传递依赖于R的候选键,则称R是3NF。求法举例:R(WXY),主键是W,R上存在X→Y的传递依赖,这分解为R1(XY)和R2(WX),X依赖于R1

反范式:不严格按照范式化的设计,避免关联的存在,如果不存在关联,这对大部分查询最差的情况(如全表扫描,数据量比内存大)比关联要快一些,可以避免随机IO,提高性能。

事务

ACID:原子性,一致性,隔离性,持久性。

检查点机制:最后一个检查点前提交的不必管,最后一个检查点前未提交但故障前提交的重做,故障前未提交的撤销。REDO正向跑日志,UNDO逆向扫描日志。

丢失更新:读了同一个值,先后更改,先更改的被覆盖。

读脏数据:没有COMMIT却被另一个事务读到。

不一致:某事务进行中在读到某个数据前,另一事务已经对该数据的值提交了更新。

锁这个话题,联系到实践可能会非常复杂,这里仅仅简单依照基本理论介绍X所(排它锁,写锁)和S锁(共享锁,读锁)。

X锁独占,别的事务谁也不许加锁。数据加S锁后,仍允许其它事务加S锁,但所有的S锁释放掉前,决不允许任何事务加X锁。

活锁:一直等待却始终等不到封锁机会,如优先级太低,任何事务优先级都更高,轮不着其加锁。排队可以避免这种问题。

死锁:互相等待对方释放自己要的资源。必要时可以干掉一个不重要的事务来解决。

饿死:很多事务频繁地加S锁,总是没有都释放的时候,永远加不上X锁。

可串行化:某种并发执行结果与某一串行调度执行的结果一致,则称这种并发执行的调度为可串行化的调度。

行锁:Oracle和InnoDB提供,Oracle的行锁加在行对象上,InnoDB加在索引这个数据结构上,所以InnoDB加行锁必须要有索引这个前提。国产的达梦数据库也支持行锁。

为了避免资源竞争产生死锁,在S锁和X锁之外还有一种U锁(更新锁,意向锁)。首先判断一个事务中是否需要对数据进行写操作,如果需要则在一开始就加排它锁。

隔离级别

可串行化(Serializable):允许并发,排队走。

可重复读(Repeated Read,RR):只允许事务读已提交的数据,并且在两次读同一个数据时不允许其它事务修改它。应用了读写锁,读锁不能被写锁升级,读读可并行。这是InnoDB默认的隔离级别,通过Next-key锁策略防止幻读,提到这里还会有一些奇奇怪怪的不易发现的死锁问题值得研究,在此不再展开。

读提交数据(Read Committed,RC):允许读已提交的数据,但不要求RR。应用了读写锁,读锁能被写锁升级,读读并行,读写并行,但写读不能并行。这是Oracle默认的隔离级别。

读未提交数据(Read Uncommitted,RU):允许读未提交的数据,最低的一致性级别。只加写锁,读不加锁。读读、读写、写读都并行。

以上是SQL92标准的几个隔离级别,但目前主流的数据库一般采用了快照隔离(Snapshot Isolation)、多版本并发控制(MVCC)机制,针对读多写少情景优化,可在事务进行过程中从回滚段中找相应版本的状态读取数据,隔离级别很高,并行度可达到甚至超过RU级别。

此外,还可以了解一下,Oracle的SCN、MySQL的Trx_id是怎么回事。

表的联接

内联接(INNER JOIN):结果为两个联接表中的匹配行的联接。

左外联接(LEFT OUTER JOIN):包括左表全部行,右表不满足的NULL之。右外联接不再赘述。

完全外联接(FULL OUTER JOIN):根据左外联接和右外联接应该明白了。

交叉联接(CROSS JOIN):返回的是笛卡尔积,即所有可能的行组合。

NEST LOOP:有两个表,驱动表和被驱动表。驱动表做一次遍历,被驱动表做多次遍历。返回第一条记录速度很快,不需要排序。可以使用非等值连接。MySQL支持NEST LOOP。

SORT MERGE:两个表地位一样,要先排序,然后进行合并,返回记录集。排序首先在内存中进行,能在内存中完成的叫In-Memory Sort;如果需要借助磁盘缓冲,叫External Sort。MySQL不支持。

HASH JOIN:对驱动表的连接字段进行哈希操作,再依次对被驱动表每条记录的连接字段执行相同的哈希函数,和驱动表的哈希结果进行匹配。内存消耗远小于SORT MERGE,也不需要密集的CPU操作,普遍优于SORT MERGE算法。MySQL官方版本暂不支持,但MariaDB已经支持。

半联接:针对IN、EXISTS等,在进行连接查询的时候,内层如果有相应的记录及返回一个TRUE,而不需要访问余下的行,如果内层表特别巨大的时候将会大大节省时间。系统参数控制或HINT控制(semijion-强制使用;no_semijion-不使用;nl_sj-进行嵌套半联接;hash_sj-进行散列半联接;merge_sj-进行排序半联接)。半联接条件是语句必须使用in(=any)或exists,语句必须在in或exists中有子查询,使用exists必须使用关联子查询,in或者exists字句不能在OR分支中。

反联接:原理和半连接一样,在not in和not exists中使用。有一点要注意,如果NOT IN 的时候子查询返回有NULL值。系统参数控制或HINT控制(antijoin-强制使用;nl_aj-进行嵌套反联接;hash_aj-进行散列反联接;merge_aj-进行排序反联接)。反联接条件为语句必须使用NOT IN (!=ALL) 或NOT EXISTS,语句必须在NOT IN或NOT EXISTS子句有一个子查询,NOT IN或NOT EXISTS子句不能包含在OR分支中,NOT EXISTS子句中的子查询必须与外层查询相关,注意NOT IN子查询不要返回空值。

索引

B+树索引:传统关系型数据库主要的索引结构使用的都是B+树。更有甚者,InnoDB引擎的表数据,整个都是以B+树的组织形式存放的。数据库中B+树索引又分为聚集索引和非聚集索引。

聚集索引:键值的逻辑顺序决定了表中相应行的物理顺序,即表中数据按主键顺序存放。聚集索引就是按每张表的主键构造一颗B+树,并且叶节点存放整张表的行记录数据,每张表只能有一个聚集索引(一个主键)。好处是它对于主键的排序查找和范围查找的速度非常快,叶节点的数据就是我们要找的数据。对于主键索引,MySQL在添加和删除操作时先创建一张临时表,然后把数据导入临时表,再删除原表,把临时表重命名为原表。

非聚集索引(辅助索引):叶级别不包含行的全部数据,该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同。叶级别除了包含行的键值以外,每个索引行还包含了一个书签,该书签告诉InnoDB引擎哪里可以找到与索引对应的数据。非聚集索引的存在并不影响数据在聚集索引中的组织,因此一个表可以有多个非聚集索引。当通过非聚集索引查找数据时,会遍历非聚集索引并通过叶级别的指针获得指向主键索引的主键,然后再通过主键索引找到一行完整的数据。

哈希索引:将索引键通过哈希运算之后,将运算结果的哈希值和所对应的行指针信息存放于一个哈希表中。它只能是等值过滤,无法避免排序,无法直接完成查询还是得访问表中的实际数据,哈希重复度高时效率低。

R树索引:适用于高维空间搜索问题,它把B树的思想很好的扩展到了多维空间。R树是B树在高维空间的扩展,是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针,当我们需要进行一个高维空间查询时,我们只需要遍历少数几个叶子结点所包含的指针,查看这些指针指向的数据是否满足要求即可。

索引的原则:最左匹配原则(遇到范围查询(>、<、between、like)就停止匹配)、=和in可以乱序(优化器自己优化)、尽量选择区分度高的列作为索引、索引列尽量不参与计算、尽量扩展索引而不是新建。

SQL优化

首先,确保设计SQL时尽量最优。然后对于固定下来的SQL,会有很多种可能的执行路径,查找SQL最优的执行路径,使得用户能够更快的得到SQL执行的结果是我们的目标。SQL的每一种执行路径,均可计算一个对应的执行代价(CPU和IO都要考虑)。代价越小,执行效率越高;反之则反之。除了代价优化模型还有规则优化模型。

show status可以大致上看看各类操作的执行次数,操作影响的行数等,但意义不大,适合看大致情况。

慢查询:给MySQL配置参数--log-slow-queries[=filename]启动,会写慢查询日志。对于正在执行的情况可以用show processlist来看目前正在执行的线程,是否锁表等执行情况。

SQL分析:可以查看执行计划,看怎么联接表,怎么扫描,使用到的索引以及统计信息,根据表的记录数和索引情况,改写SQL,调整索引,使用HINT,优化SQL的执行路径。

一些注意事项:少用*;尽量避免多表;尽量避免DISTINCT(可用EXISTS替代)、INTERSECT等耗费时间的操作;避免索引列上使用函数、NOT、IS NULL;避免前置通配符;尽量避免类型合适转换;调整连接顺序;WHERE代替HAVING提前过滤;NOT EXTSTS(有效利用索引)替代NOT IN(执行内部的排序合并);>=或<=代替>、<或NOT;尽量避免子查询;外联接代替NOT IN;删除表数据用TRUNCATE;及时提交数据释放资源。

NoSQL

这不是课程范围之内的东西,加之个人用得不多,所以简单介绍。一开始非常火,捧得特别高,现在人们对于NoSQL心态普遍正常了很多。关系型数据库中的表都是存储一些格式化的数据结构,每个元组字段的组成都一样,即使不是每个元组都需要所有的字段,但数据库会为每个元组分配所有的字段,这样的结构可以便于表与表之间进行连接等操作,但从另一个角度来说它也是关系型数据库性能瓶颈的一个因素。而非关系型数据库以键值对存储,它的结构不固定,每一个元组可以有不一样的字段,每个元组可以根据需要增加一些自己的键值对,这样就不会局限于固定的结构,可以减少一些时间和空间的开销。这里仅举两个例子。

Redis:它通常被称为数据结构服务器,因为值可以是字符串、哈希Map、List、集合和有序集合等类型。微博在大规模地用。

MongoDB:支持的数据结构非常松散,是类似JSON的BJSON格式,因此可以存储比较复杂的数据类型。最大的特点是支持的查询语言非常强大,语法有点类似于面向对象的查询语言,几乎可以实现类似关系数据库单表查询的绝大部分功能,而且还支持对数据建立索引。

结语:别名的奇技淫巧

本来还想涉及一点分布式的内容,可惜自己又没有太多实践经验,只照本宣科地写出来没意思,所以来讨论点好玩的。MySQL doesn’t yet support ‘LIMIT & IN/ALL/ANY/SOME subquery’,如子查询中不能使用LIMIT,但是这样select * from table where id in (select t.id from (select * from table limit 10) as t)就可以通过。

问与答

MySQL的配置文件叫什么名字,如果通过命令登录?答:my.ini或my.cnf,其中有端口号、字符集、连接数、缓存大小、线程控制、事务控制、默认存储引擎等配置项,此外还有bin、data、lib目录。使用mysql -u[username] -p[password]命令来登录。

Oracle中NULL怎么和实际值比较大小?答:视为最大值。

Oracle中NVARCHAR2、VARCHAR2类型的区别是什么?答:NVARCHAR2中存储中文字时,一个中文字当一个字符来处理;而VARCHAR2中一个中文字按照字符集单字所占字符数处理。

表TABLE(userid,logintime,dat),userid为用户名(KEY),logintime为登录时间,dat为某些数据,请写SQL语句返回每个有记录的用户在最后一次登录所产生的userid,dat结果集。答:略。

微博每天产生大量的数据,假设一台机器的数据库只能存a亿条微博,但每年要产生a*50亿条微博,因此不得不将数据存储到多台机器上,请设计实现一种可行的存储方式,并说明如何实现查询需求。答:略。