本文对数据结构的知识进行了全面梳理和总结，一篇文章就让你学会“数据结构”。
关注公众号【你好编程】，更多计算机知识任你淘~
一、数据模型
两大数据模型
- 概念模型：按用户的观点来对数据来对数据和信息建模，主要用于数据库设计。
- 逻辑模型：主要包括层次模型、网状模型、关系模型，它是按照计算机系统的观点对数据建模，主要用于DBMS的实现。
数据模型的组成要素：数据结构、数据操作、完整性约束
- 数据结构：数据库组成对象以及对象之间联系的描述。
- 数据操作：对数据库中各种对象的实例允许执行的操作的集合。
- 完整性约束：数据模型要满足的约束条件。包括实体完整性、参照完整性、用户定义完整性。
二、关系数据库标准语言SQL——SQL概述
SQL的组成
- 数据定义（Data DeFinition）：用来定义数据库结构，包括定义表、视图和索引。
- 数据操作（Data Manipulation）：包括数据查询和数据更新两大操作。数据更新包括插入、删除和修改操作。
- 数据控制（Data Control）：包括对数据的安全性控制、完整性规则的描述以及对事务的定义、并发控制和恢复。
SQL的特点
- 综合统一：SQL中的DDL、DML、DCL语言风格统一，可以独立完成数据库生命周期中的全部活动。
- 高度非过程化：SQL进行数据操作，只要提出做什么，不需要指明怎么做。操作过程由系统自动帮助你完成。
- 面向集合的操作方式
- 以同一种语法结构提供多种使用方式：既是独立的语言，又是嵌入式语言。
- 语言简洁、易学易用。
三、关系数据库标准语言SQL——数据定义
模式的定义与删除
//如果语句里面没有模式名，则默认模式名为用户名
create scheme <模式名> authorization <用户名>
drop scheme <模式名> <cascade|restrict>
//cascade：表示删除模式时同时把该模式下的所有数据库对象全部删除
//restrict:表示如果该模式下已经定义了数据库对象，则拒绝删除该模式基本表的定义、删除、修改
create table student(
sno varchar(50) primary key,//列级完整性约束，主码
sname varchar(50) unique,//取唯一值
ssex int,
sage smallint，
sdept char(20),
//primary key(sno),表级完整性约束
foreign key sdept references school(sdept)//外码
);数据类型：
模式与表：定义基本表时定义其模式
//第一种方法，显示的定义
create table S-T student(....)
//第二种方法，在创建模式语句的同时创建表修改基本表
alter table <表名>
[add <新列名> <数据类型> [完整性约束]] //增加新列，并指定数据类型和完整性
[drop <完整性约束名>] //删除某列的完整性
[column <列名> <数据类型>]; //修改列的数据类型删除基本表
drop table <表名>; //一旦删除基本表，则表中的所有数据都被删除索引的建立和删除：建立索引是加快查询速度的有效手段
create [unique][cluster] index <索引名>
on <表名> （<列名> [<次序>].....）
- 索引可以建立在表的一列或多列上，每个列名的次序指定索引值的排序次序，包括ASC和DESC，缺省为ASC
- unique表明此索引的每一个索引值只对应唯一的数据记录;cluster表示要建立的索引是聚簇索引，即表中记录的物理顺序与索引值的顺序一致。
- 删除索引
drop index <索引名>RDBMS中索引一般采用B+树、HASH索引来实现。B+树具有动态平衡的有点，HASH索引具有查找速度快的特点。
四、关系数据库标准语言SQL——数据查询
单表查询
目标表达式不仅可以是表中的属性，也可以是算数表达式；目标表达式不仅可以是表达式，还可以是字符串常量、函数等。
//目标列表达式
select sno,2016-sage
from student;
//字符串常量
select 'number:',sno,'age:',sage
from student;
//更改查询结果的列名
select sno number,sage age
from student;消除重复的行：distinct
select distinct sname
from student;查询满足条件的元组：where
//比较大小
select sname,sage
from student
where sage<20;
//确定集合
select sname
from student
where sdept in('CS' ,'MA');
//字符串匹配，%表示任意长度的字符串，_表示任意单个字符
select sname
from student
where sname like '林_ _'; //汉字要占两个字符，所以要两个_
//escape '\' 表示'\'为转换字符，这样紧跟在\之后的通配符就不具有通配符的含义，只是普通的字符
select cno
from course
where cname like 'db\_design' escape '\';
//空值查询
select sno,cno
from sc
where grade is null;
//多重条件查询使用and和ororder by子句：表示对查询结果按照一个或多个属性列的升序（ASC）或降序（DESC）排列，缺省值为升序。
select sno,grade
from sc
where cno='3'
order by grade desc;聚集函数：
select count(*)
from student
where sname like 'lin%';group by子句：查询结果按某一列或多列的值分组，值相等的为一组。对查询结果分组目的是为了细化聚集函数的作用对象。如果未对查询结果分组，聚集函数将作用于整个查询结果。分组后聚集函数将作用于每一个组，即每一组都有一个函数值。Having语句是对分组后的组按一定的条件进行筛选，最终只输出满足指定条件的组。
//求student表中同名的人
select sname
from student
group by sname
having count(*)>1;where子句与having短语的区别在于作用对象不同，where子句作用于基本表或视图，having短语作用与组。
连接查询
等值于非等值连接查询
//[<表名1>.]<列名1> <比较运算符> [<表名2>.]<列名2>
//比较运算符有：= > <等
//=时为等值连接，其他的运算符为非等值连接
select student.*,sno.*
from student,sc
where student.sno=sc.sno;select与where子句的属性名都加上表名前缀，是为了避免混淆。如果属性名在参加连接的各表中是唯一的，则可以省略表名前缀。
自身连接
连接操作不仅可以在两个表之间进行，也可以是一个表与其自己进行连接。
//同一个表进行连接，需要为表另取名
select first.cno,second.cpno
from course first,course second
where first.cno=second.cpno;外连接：在连接谓词的某一边加符号*
- 外连接就好像是为符号*所在边的表增加一个“万能”的行，这个行全部由空值组成。它可以和另一边的表中所有不满足连接条件的元组进行连接。
- 连接符出现在右边称为右外连接，出现在左边称为左外连接。
select student.*
from student,sc
where student.sno=sc.sno(*);复合条件连接
where子句中可以有多个连接条件，成为复合条件连接。
select student.sno,sname
from student,sc
where student.sno=sc.sno and
sc.cno='2' and
sc.grade>90;两个表以上进行连接，可以成为多表连接。
select student.sno,sname,cname,grade
from student,sc,course
where student.sno=sc.sno and sc.cno=course.cno;嵌套查询
将一个查询块嵌套在另一个查询块的where子句或having短语的条件中的查询成为嵌套查询。
SQL语言允许多层嵌套查询。子查询select语句中不能使用order by子句，该子句只能对最终查询结果排序
select sname
from student
where sno in
(select sno
from sc
where cno='2')子查询结果往往是一个集合，所以谓词in是嵌套查询中最经常使用的谓词。
带有比较运算符的子查询：可以使用> < =等比较运算符
select sname
from sc x
where grade >
(select avg(grade)
from sc y
where x.cno=y.cno)带有any或all谓词的子查询
select sname,sage
from student
where sage<any (select sage
from student
where sdept='cs');带有EXISTS谓词的子查询：不返回任何数据，只产生逻辑真“true”或逻辑假“false”。EXISTS引出的子查询，其目标列表达式通常为*，因为其结果为真假值，给出列名没有意义。
select sname
from student
where exists
(select *
from sc
where sno=student.sno and cno='1');集合查询
并（UNION）、交（INTERSECT）、差（EXCEPT）
//参加UNION操作的各结果表的列数必须相同，对应项的数据类型也必须相同
select *
from student
where sdept='cs'
union
select *
from student
where sage>19;五、关系数据库标准语言SQL——数据更新
插入数据
insert
into <表名> [<属性列1> [,<属性列2>]...]
values(<常量1> [,<常量2>]...)
insert
into student
values('lin',16,'cs'....);
insert
into student(sname,sage,sno)
values('lin',16,'cs');插入元组
insert
into student
select *
from student
where sage>19;修改数据
update <表名>
set <列名>=<表达式> [,<列名>=<表达式>]...
[where <条件>]
update student
set sage=22
where sno='12346';删除数据
delete
from <表名>
[where <条件>]
//删除某一个值
delete
from student
where sno='123456';
//删除多个元组的值
delete
from student;六、关系数据库标准语言SQL——视图
视图概念
视图是从一个或几个基本表中导出的表，它是一个虚表。数据库只存放视图的定义，不存放视图对应的数据，其数据依旧存在数据库表中。所以数据库表中的数据发生变化，从视图中查询的数据也将发生变化。
定义视图
create view <视图名> [(<列名> [,<列名>]...)]
as <子查询>
[with check option]
- 子查询可以是任意复杂的select语句，但通常不允许含有order by子句和distinct短语。
- with check option表示对视图进行update、insert、delete操作时要保证更新、插入、删除的行满足视图定义中的谓词条件。
- 组成视图的属性列名或者全部指定或者全部省略，没有第三种选择。如果省略了各个属性列名，则隐含该视图由子查询中select子句目标列中的诸字段组成。
create view is_student
as
select sno,sname,sage
from student
where sdept='cs'
with check option;视图可以建立在多个基本表上，也可以建立在一个或多个视图上。
删除视图
drop view <视图名>视图的查询和更新
操作与数据表基本类似，但是还是有一些不同
六、数据库安全性
数据库安全性控制
用户标识和鉴别、存取控制、操作系统安全保护、数据密码存储
数据库存取控制方法
用户权限由两个要素组成：数据对象和操作类型
数据库存取控制方法——授权与回收
定义一个用户的存取权限就是要定义这个用户可以在哪些数据对象上进行哪些类型的操作。在数据库系统中，定义存取权限成为授权。
GRANT授权
grant <> [,<>]...
on <对象类型> <对象名> [,<对象类型> <对象名>]...
to <用户> [,<用户>]...
[with grant option]将对指定操作对象的指定操作权限授予指定的用户，发出该grant语句的可以是DBA，也可以是已经拥有该权限的用户。接收权限的用户可以是一个或多个具体用户，也可以是PUBLIC，即全体用户。指定WITH GRANT OPTION子句，则获得某种权限的用户还可以把这种权限授权给其他用户.
grant all privileges
on table student,sc
to user1
with grant option;REVOKE回收
revoke <> [,<>]...
on <对象类型> <对象名> [,<对象类型> <对象名>]...
from <用户> [,<用户>]...cascade会级联：依次向下收回权限
revoke insert
on table student
from user1 cascade;创建数据库模式的权限
create user <username>
[with] [dba|resource|connect]
审计
- 审计功能吧用户对数据库的所有操作自动记录下来放入审计日记中。DBA可以利用审计跟踪的信息，重现导致数据库出现现有状况的一系列事件，中出非法存取数据的人、时间和内容等。
- 审计通常是费时间和空间的，一般主要用于安全性要求较高的部门。
- 审计一般可以分为用户级审计和系统级审计。
- AUDIT语句用来设置审计功能，NOAUDIT用来取消审计功能。
audit alter,update
on student;
noaudit all
on student;七、数据库完整性
数据库的完整性
是指数据的正确性和相容性。包括：实体完整性、参照完整性、用户定义完整性。
实体完整性
- 一种定义为列级约束条件，另一种定义为表级约束条件。在create table中用primary key定义。
- 完整性检查和违约处理。
参照完整性
- 在create table中用foreign key短语定义哪些列为外码列，用references短语指明这些外码参照哪些表的主码。
- 对被参照表和参照表进行增删改查操作时很有可能破坏参照完整性，必须进行检查。
- 违约处理：reject（拒绝执行）、cascade（级联）、set-null（设置为空）
用户定义完整性
针对某一具体应用的数据必须满足的语义要求
列值非空：NOT NULL短语
create table sc(
sno char(7) not null,
sname char(10) not null);列值唯一：UNIQUE短语
create table student
(sname varchar(50) unique,
sage int);check：指定列值应该满足的条件
create table student
(sage int check(sage>19),
ssex char(10) check(ssex in ('男','女')));完整性约束命名子句
提供constraint，用来对完整性命名
constraint <完整性约束条件名> [PRIMARY KEY短语|FOREIGN KEY短语|CHECK短语]八、数据库恢复技术
事务的基本概念
事务时一系列的数据库操作，是数据库应用程序的基本逻辑单元。事务时用户定义的一个数据库操作序列，这些操作要么全做要么全部做，是一个不可分割的工作单位。
begin transaction
....
数据库操作
commoit事务具有以下特性：原子性、一致性、隔离性和持续性。
数据库恢复的实现技术
数据转储：定期将整个数据库复制到磁带或另一个磁盘上保存起来的过程。这些备用的数据文本成为后备副本或后援副本
登记日志文件：用来记录事务对数据库的更新操作的文件。
九、并发控制
并发控制概述
- 丢失修改：两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。
- 不可重复读：事务T1读取数据后，事务T2执行更新操作并写回数据库，使T1无法再现前一次读取结果。
- 读“脏”数据：事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销，T2这时读到的数据就与数据库中的数据不一致。
并发控制的主要技术是封锁。
封锁
- 排它锁：又成为写锁（X锁）。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。
- 共享锁：又称为读锁（S锁）。若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。
- 常用XLOCK表示对A上加X锁，SLOCK表示对A加S锁，UNLOCK A表示释放A上的封锁。
封锁协议
- 一级封锁协议：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。其解决了丢失修改的问题。在一级封锁协议中，如果仅仅是读数据，不对数据进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。（只有在修改数据是才加上X锁，读数据时加S锁）
- 二级封锁协议：一级封锁协议加上事务T在读取数据R之前必须现对其加S锁，读完后即可释放S锁。其解决了丢失修改和读脏数据。由于读完数据后即可释放S锁，所以它不能保证可重复读。
- 三级封锁协议：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。其解决了丢失修改、读脏数据和不可重复读。
并发调度的可串行性
- 多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度策略为可串行化的调度。
- 可串行性是并发事务正确性的准则。按这个准则规定，一个给定的并发调度，当且仅当它是串行化的，才认为是正确调度。
封锁的粒度
封锁对象的大小称为封锁粒度。封锁的粒度越大，数据库所能封锁的数据单元越少，并发度就越小，系统开销越小。
十、数据库范式
数据依赖
是一个关系内部属性与属性之间的一种约束关系，这种约束关系是通过属性间值得相等与否体现出来的数据间相关联系。数据依赖中最重要的是函数依赖和多值依赖。
函数依赖
设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U)的任意一个可能的关系实例r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不能，则称X函数确定Y或者Y函数依赖于X，记作X->Y。
第一范式（1NF）：如果一个关系模式R的所有属性都是不可分的基本数据项，则R为第一范式。（也就是不能出现表中表的情况，不满足第一范式则就不是关系数据库）。
第二范式（2NF）：关系模式R是第一范式，并且每一个非主属性都完全函数依赖于R的码，则R为第二范式。消除了非主属性对候选码的部分依赖。
第三范式（3NF）：关系模式R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。显然R也属于第二范式。
BC范式（BCNF）：R属于第一范式，如果对于R的每个函数依赖X->Y，并且Y不包含于X，则X必含有候选码，那么R属于BCNF（即R中的每一个决定因素都包含候选码）
- BC范式既检查非主属性，又检查主属性。当只检查非主属性时，就成了第三范式。满足BC范式的关系都必然满足第三范式。
- 符合3NF，并且，主属性不依赖于主属性。
- 所有非主属性都完全函数依赖于每个候选码。
- 所有主属性都完全函数依赖于每个不包含它的候选码。
- 没有任何属性完全函数依赖于非码的任何一组属性。
第四范式（4NF）：消除了多值依赖。 |
