1、易维护，采用面向对象思想设计的结构，可读性高，由于继承的存在，即使改变需求，那么维护也只是在局部模块，所以维护起来是非常方便和较低成本的。
2、质量高，在设计时，可重用现有的，在以前的项目的领域中已被测试过的类使系统满足业务需求并具有较高的质量。
3、效率高，在软件开发时，根据设计的需要对现实世界的事物进行抽象，产生类。使用这样的方法解决问题，接近于日常生活和自然的思考方式，势必提高软件开发的效率和质量。
4、易扩展，由于继承、封装、多态的特性，自然设计出高内聚、低耦合的系统结构，使得系统更灵活、更容易扩展，而且成本较低。

内容	关系数据模型	面向对象数据模型
基本数据结构	二维表	类
数据标识符	码	OID
静态性质	属性	属性
动态行为	关系操作	方法
抽象数据类型	无	有
封装性	无	有
数据间关系	主外码联系，数据依赖	继承、组合
模式演化能力	弱	强

关系数据模型与OO模型的比较

❖OO模型的基本概念
▪ 对象
▪ 对象标识OID
▪ 封装
▪ 类
❖对象关系数据库系统中扩展的关系数据类型
▪ 大对象LOB
▪ BOOLEAN类型
▪ 集合类型ARRAY
▪ DISTINCT类型
❖对象关系数据库系统中扩展的对象类型
▪ 行对象与行类型
▪ 列对象与对象类型
▪ 抽象数据类型
❖关系对象数据库系统支持
▪ 继承
▪ 子表和超表

对象关系数据库系统中扩展的关系数据类型

❖扩展的类型：LOB、BOOLEAN、集合类型ARRAY、用户定义的DISTINCT类型等

❖面向对象的数据类型：行类型ROW TYPE、抽象数据类型（Abstract Data Type）

LOB

大对象LOB(Large OBject )类型
❖ LOB可存储多达十亿字节的串。
❖ LOB分类
▪ 二进制大对象BLOB(Binary Large OBject)
➢ BLOB用于存储音频、图像数据
▪ 字符串大对象CLOB(Character Large OBject)。
➢ CLOB用于存储长字符串数据

boolean

❖ 布尔类型，支持3个真值： true、 false和unknown
❖ 操作符： NOT、 AND、 OR、 EVERY、 ANY
例如 WHERE EVERY(QTY>200)
或WHERE ANY(QTY>200)
▪ QTY列为空值：返回unknown；
▪ QTY列为非空：
➢当该列的每一个值都使(QTY>200)为true时， EVERY返回true，
否则为false；
➢当该列的每一个值都使(QTY>200)为false时， ANY返回false，
否则为true。

集合类型array

❖ 相同类型元素的有序集合称为数组ARRAY
▪ SQL3新增的集合类型
▪ 允许在数据库的一列中存储数组
❖ SQL3的数组只能是一维的
▪ 数组中的元素不能再是数组

例：

创建表

CREATE TABLE SALES(
ITEM_NO CHAR(20)， /商品号/
QTY INTEGER ARRAY［12］， /整数数组，存放销售额/
PRIMARY KEY(ITEM_NO) )；
向SALES表插入一个元组：

INSERT INTO SALES(ITEM_NO， QTY)VALUES
(‘T-shirt2000’， ARRAY［200， 150， 200， 100， 50， 70，
80， 200， 10， 20， 100， 200］ )；
查找三月份销售额大于100的商品号：

SELECT ITEM_NO
FROM SALES
WHERE QTY［3］ >100；

自定义类型distinct

❖ SQL3新加了一种DISTINCT类型
❖ 定义DISTINCT数据类型语法

CREAT TYPE <type name>
AS <built in scalar type name> FINAL
[<cast option>]
[ <method specification commalist>];

例：

没有使用DISTINCT类型
▪ 例如，职工的智商字段(IQ)和鞋号字段(SHOE_SIZE)
定义成INTEGER类型
▪ WHERE SHOE_SIZE > IQ
使用DISTINCT类型
▪ 重新定义这两字段类型
➢CREAT TYPE SHOE_SIZE_TYPE AS INTEGER FINAL;
➢CREAT TYPE IQ_TYPE AS INTEGER FINAL;
▪ SHOE_SIZE_TYPE和IQ _TYPE成为两种不同的数据类型
表达式： WHERE SHOE_SIZE > IQ 是非法的
▪ 如果在定义类型时设置了选项<cast option>，下面用法也是合法
的： WHERE MY_SHOE_SIZE > CAST (MY_IQ AS SHOE_SIZE)

面向对象数据类型

❖ 在ORDBMS中，类型(TYPE)具有类(CLASS)的
特征，可以看成类

行对象与行类型 ROW TYPE

在ORDBMS中，类型(TYPE)具有类(CLASS)的特征，可以看成类。

◼ 定义行类型(ROW TYPE) ：
CREATE ROW TYPE <row_type_name>
(<component declarations>)；

◼ 创建行类型
［例3］

CREATE ROW TYPE Person_type
(pno NUMBER，
name VARCHAR2(100)，
address VARCHAR2(100) );

◼ 创建基于行类型的表

CREATE TABLE <table_name> OF <row_type_name>;
［例4］

CREATE TABLE person_extent OF Person_type
(pno PRIMARY KEY );

列对象与对象类型 COLUMN TYPE

◼ 可以创建一个对象类型，表的属性可以是该对象类型。
◼ 创建列对象语句如下:
CREATE TYPE <type_name> AS OBJECT
(<component declarations>);

［例5］

CREATE TYPE address_objtyp AS OBJECT
(street VARCHAR2(50), city VARCHAR2(50) );

CREATE TYPE name_objtyp AS OBJECT
(first_name VARCHAR2(30)，last_name VARCHAR2(30) ) ;

◼ 创建表，定义其中的属性是对象类型
［例6］

CREATE TABLE people_reltab (
Id NUMBER(10)，
name_obj name_objtyp，
address_obj address_objtyp);

抽象数据类型Abastract Data Type)

❖ 概念： SQL3允许用户创建指定的带有自身行为说明和内
部结构的用户定义类型称为抽象数据类型
❖ 定义ADT的一般形式为

CREATE TYPE <type_name> (
所有属性名及其类型说明，
[定义该类型的等于＝和小于<函数， ]
定义该类型其他函数(方法));

NOTE:

▪ (1) ADT的属性定义和行类型的属性定义类同。
▪ (2) 在创建ADT的语句中，通过用户定义的函数比较对象的值。
▪ (3) ADT的行为通过方法(methods)、函数(functions)实现。
▪ (4) SQL3要求抽象数据类型是封装的，而行类型则不要求封装。
▪ (5) ADT有3个通用的系统内置函数
▪ (6) ADT可以参与类型继承

参照类型(Reference Type)

❖REF类型（参照类型、引用类型）
▪ 引入的原因：
类型之间可能具有相互参照的联系
▪ 形式
REF <类型名>
▪ 特点：
➢REF类型总是和某个特定的类型相联系。
➢它的值是OID

❖创建两个表： Employee和Company，两表之间存在相互参照关系，即某个职工在某个公司工作
▪ (1)创建行类型
［例7］

CREATE ROW TYPE employee_type(
name VARCHAR(35)，
age INTEGER );
CREATE ROW TYPE Comp_ type(
compname VARCHAR(20)，
location VARCHAR(20) );

▪ (2)创建基于行类型的表：

CREATE TABLE Employee OF employee_type;
CREATE TABLE Company OF Comp_ type

▪ (3)描述参照关系

CREATE ROW TYPE Employment type (
employee REF (employee_type)，
company REF (Comp type) );

CREATE TABLE Employment OF Employment _type

➢表Employment中某一个元组的employee属性值是某个职工的OID
➢company属性值是该职工所在公司的OID

［例8］

CREATE ROW TYPE employee_type(
name VARCHAR(35)，
age INTEGER，
emp_id REF(employee_type) );

［例9］

CREATE TABLE Employee OF employee_type
VALUES FOR emp_id ARE SYSTEM GENERATED;

❖ 建立参照属性：
<参照属性名>［REF(<类型名>)］ SCOPE IS <关系名>
［例10］

CREATE TABLE address_objtab OF address_objtyp ;

［例11］

CREATE TABLE people_reltab2 (
id NUMBER(4) PRIMARY KEY，
name_obj name_objtyp，
addresss_ref REF(address_objtyp) SCOPE IS address_objtab )

［例12］

CREATE INDEX address_ref_idx ON
people_reltab2(address_ref) ;

［例13］

SELECT id
FROM people_reltab2 p
WHERE p.address_ref.city=‘北京’ and p.address_ref.street=‘牛街’;

继承性

❖ ORDBMS应该支持继承性
▪ 一般是单继承性
❖ ［例14］
CREATE TYPE emp_type

UNDER person_type AS(
emp_id INTEGER，
salary REAL )
NOT FINAL;

◼ NOT FINAL：表示不是类层次结构中最后的“叶结点”
◼ FINAL：该类型是类层次结构的叶结点

子表和超表

❖ 超表、子表、子表的子表构成一个表层次结构
❖ 表层次和类型层次的概念十分相似

［例15］对于下面的类型层次，先定义这些类型TYPE，然后创建基于这些类型的表

CREATE TYPE person /创建person 类型，根类型/
(id INTEGER，
name VARCHAR(20)，
birthyear INTEGER，
address VARCHAR(40))
NOT FINAL； /NOT FINAL表示可以有子类型/

CREATE TYPE employee /创建person的子类型employee/
UNDER person /类型employee继承person的属性/
(salary INTEGER) /* employee定义自己的属性*/
NOT FINAL；

CREATE TYPE executive /创建employee的子类型executive/
UNDER employee
(bonus INTEGER)
FINAL；

CREATE TYPE student /*创建person的子类型student */
UNDER person
(major VARCHAR(10)， wage DECIMAL)
FINAL

［例16］ Department类型和employee具有相互参照的联系，使用REF来表示这种联系

CREATE TYPE department
(ID INTEGER，
manager REF(employee)，
Budget INTEGER);
ALTER TYPE employee
ADD ATTRIBUTE dept REF(department);

❖ 定义基于这些类型的基本表和表层次：

◼ CREATE TABLE person_table OF person
(name WITH OPTIONS NOT NULL);

◼CREATE TABLE exec_table of executive
UNDER employee_table

◼CREATE TABLE employee_table OF employee
UNDER person_table;

CREATE TABLE student_table OF student
UNDER person_table；

CREATE TABLE dept_table OF department
(manager SCOPE IS employee_table);

ALTER TABLE employee_table
ALTER COLUMN dept ADD SCOPE IS dept_table;

❖查询[例16]所创建的表
［例17］

SELECT name， address
FROM person_table
WHERE birthyear <=1970;

❖关闭子表的检索
［例18］

SELECT name， address
FROM ONLY person_table
WHERE birthyear <=1970;

INSERT、 DELETE、 UPDATE对子表和超表的操作规则
▪ INSERT：向子表插入一行时一般会在该子表的超表上也插入一行。
▪ DELETE：从表删除一行时一般会在该表的超表和子表上也删除相应的一行

数据文件的组织与索引技术

数据文件的组织

定长记录

高级数据库课程笔记

数据文件根据数据结构的定义，为每个字段分配固定长度的空间，将字段按顺序存放组成记录。最后在记录的头部再加上时间戳等信息。

NOTE：由于内存的寻址方式是以4kb为单位的进行，所以每个字段的长度拓展为4的倍数。

变长记录

高级数据库课程笔记

变长记录允许一个或多个字段的长度是不定的，这些变长记录会存储到定长记录之后，通过指针标识各个变长记录的起始位置。

大字段

对于图像、视频流等大字段数据，通常采用分割法把数据分割成适当大小的段，再与标识组成记录进行存储。

记录的存储

物理邻接

高级数据库课程笔记

将记录按顺序排列存储到相邻的物理空间中。

优点：寻址快、空间利用率高。

缺点：更新、插入、删除时代价高。

指针连接方式

元组链表

高级数据库课程笔记

优点：增删改代价小。

缺点：不支持随机访问。

指针表

高级数据库课程笔记

用指针指向元组，用一个顺序表管理指针。

优点：支持随机访问，更新记录代价小。

缺点：增删代价依然大。

指针表与链表结合

高级数据库课程笔记
用链表的形式管理指针表。

优点：增删改代价小，管理方便。

缺点：不支持随机访问。

数据文件的存储方式

数据文件在磁盘上的组织方式主要有堆文件，顺序文件，散列文件和按列存储等。

顺序文件

高级数据库课程笔记
将记录按照搜索码排序进行组织存储。

优点：按搜索码进行检索效率非常高。

缺点：插入删除代价高。

散列文件

高级数据库课程笔记
直接存取文件或哈希文件，通过哈希将具有相同搜索码的记录散列到同一个存储范围中。

优点：记录随机存储，不需要进行排序，支持随机检索，增删的代价小。

缺点：只支持随机检索，不能进行范围检索；哈希函数选择难度大。

聚簇文件

高级数据库课程笔记

将多个有关联的表（关系）存储到同一个磁盘块中。

优点：多表查询效率高。

缺点：降低单表查询的效率。

按列存储

高级数据库课程笔记

将一个表分成若干的小表，分别进行存储。

优点：减少无用数据读入量，减少磁盘访问次数，增加特定属性读取效率。适用于数据仓库，数据挖掘。

索引技术

索引分类：稠密索引、稀疏索引；聚集索引，非聚集索引；有序索引，散列索引；

稠密索引为每个记录建立索引；稀疏索引为每个磁盘块建立索引；
聚集索引在一个列上建立有序索引，这个索引顺序与记录的存储顺序是相同的，因为存储顺序只有唯一，故聚集索引每张表只能有一个。；非聚集索引除了聚集索引之外的索引都是非聚集索引，索引顺序与存储顺序是不一致的；
有序索引在一个列上简历顺序索引；散列索引将搜索码值散列到不同的哈希桶中，索引值是无序的；

B+树索引

高级数据库课程笔记

B+树索引将列值以B+树的结构进行存储，叶子节点的指针指向对应记录的物理地址。

B+树索引的维护代价低，查询效率高。

散列索引

散列索引就是将搜索码散列到不同的哈希桶中建立的索引，根据哈希桶的数量是否固定可以将散列分为静态散列和动态散列。

静态散列

——

动态散列

动态散列有可扩展散列技术、线性散列技术以及分段散列技术。

可扩展散列

桶数量随者记录数增长,但总大小是2的幂。
多个桶可以共享存储块。
桶数量的确定方法:将散列函数的值转化成N个二进制位，用该二进制序列的前i位, i<N ,表示桶的数目, i将随记录的增加而增大,随着记录的减少而减小。

例：

规定一个桶占一个盘块，一个盘块可以存储2条记录。将搜索码值二进制化，二进制序列的前1位作为散列值。则0000，0001散列到0号桶，1111散列到1号桶。

此时插入搜索码1001，则直接散列到1号桶。如果插入0102，散列到0号桶，但此时0号桶已经满了，则将散列码扩展到前2位，对记录进行重新散列：0000，0001，散列到0号桶，0102散列到1号桶，1111散列到3号桶，此时2号桶是空的，它可以与3号桶共享一个磁盘块，待有记录插入时再申请新的磁盘块。

线性散列

——

分段散列

——

查询处理及优化

——

查询处理过程

——

查询优化

——

事务并发与封锁

并发调度

概念

并发是指在某一时间段内,多个事务同时存取相同的数据库数据。
并发操作时由于不能隔离而产生的问题:修改丢失、脏读、不可重复读。
修改丢失：事务A和B并发，事务A和B同时读取了数据C，A修改了数据C，紧接着B修改了C，导致A的修改没有意义，造成修改丢失。
脏读：事务A读取了数据A后，事务B进行了回滚，数据A回滚到了原来的值。此时事务A读到的值是不存在的，这种现象称为脏读。
不可重复读：指事务A多次读取同一个数据得到的值不一致。
并发调度：若T ={T1, T2, … }是一组并发执行的事务,则T中各事务的重要操作按时间排序的一个序列，记S = {ΣTi…},是T的一个调度。
串行调度：事务之间串行执行。
一致性调度：如果执行一个调度S，使数据库从一个一致性状态转入另一个一致性状态，则称S是一个一致性调度。

可串行化调度

T ={T1, T2, … }是一组并发执行的事务, S是T的一个串行调度,而S '是T的一个调度。若S '是与S有着相同一致性状态的一个调度,则称S '是一个可串行化调度。一致性状态相同是指事务执行过程中，变量的状态变化相同。

冲突可串行化调度

某并行调度S经过非冲突指令转换成串行调度 ,且与该申行调度的执行结果一致，则S是冲突可串行化的。

构造冲突可串行性调度,允许不同事务上的非冲突操作交换执行次序。
冲突可串行调度必定是一致性调度。
冲突可串行性不是可串行性的必要条件。即,可串行性不一定是冲突可串行性。

基于封锁的并发控制

概念

锁的基本模式
*共享锁( Shared—S锁) :允许执行读操作
*排它锁( Exclusive—X锁) :允许执行读/写操作

锁的调度策略
*解除一个数据对象的排它锁之前,其它事务不能对它加任何锁
*一个数据对象允许加几个共享锁,但不能在共享锁之上,加排它锁

锁的相容矩阵

	S	X
S	T	F
X	F	F

不正确结果：加锁错误导致结果错误。

死锁现象：两个事务相互等待数据，进入死锁状态。

饿死现象：一个事务一直在获取锁，其他事务一直占用该数据。比如写锁一直在等待其他读锁解除，而一直有新的事务加读锁。解决办法是增加优先权。

两阶段锁协议

两阶段锁协议将所有事务分成两个阶段发出加锁解锁请求：增长阶段，缩减阶段。

遵循了两阶段锁协议的并发控制算法所产生的调度是冲突可串行调度。即解决了第一个问题,但仍然存在死锁现象,级联回滚可能发生。

级联回滚是指一个事务执行完后的数据被读取了，而该事务进行了回滚，此时脏读了数据的相关事务都要进行回滚。

严格两阶段锁协议

严格两阶段锁协议要求事务提交之后才能释放排它锁。

解决了级联回滚问题，但降低了并发程度。大部分商业数据库采用的是严格两阶段锁协议。

强两段锁协议

强两阶段锁协议要求事务提交前不释放任何锁。

锁转换机制

锁转换机制是指在写的时候将S锁升级成X锁，写完后降级成S锁，提高了事务并发程度。

多粒度锁与意向锁

多粒度树

高级数据库课程笔记

多粒度锁

多粒度锁的两种方式：

显式加锁：树上每个结点都可以单独加锁。

隐式加锁：对当前结点加锁会导致隐式地对全部后代结点加上同类型的锁。

检查锁冲突时，必须先检查祖先、后代节点的锁。如果每个节点都单独加锁，那么每次加锁都要对所有祖先的锁进行检查。为了减少锁检查的代价，可以增加意向锁。

意向锁:一个事务对一个数据对象显式加锁之前,必须对它的全部祖先结点加对应类型的意向锁。

Tips：如果一个节点有意向锁，则它的后代节点必有被显示加锁。

意向锁

意向锁分类:

IS锁(Intent Share Lock):若对某结点加IS，那么将对后代结点显式地加S锁。
IX锁(Intent Exclusive Lock):若对某结点加IX锁,那么将对后代结点显式地加X锁。
SIX锁(Share Intent Exclusive Lock):若对某结点加SIX锁,则对该结点不仅显式地S锁,而且还对它加了IX锁。即，SIX= S + IX

锁相容矩阵

T1\T2	X	SIX	S	IX	IS
X	N	N	N	N	N
SIX	N	N	N	N	Y
S	N	N	Y	N	Y
IX	N	N	N	Y	Y
IS	N	N	Y	Y	Y

可串行性多粒度锁协议:
➢必须遵守锁类型的相容性矩阵。
➢根结点必须首先加锁。
➢任何事务都必须遵守两阶段锁协议。
➢任何事务加锁都必须按从根到叶子顺序进行。
➢任何事务开锁都必须按从叶子到根顺序进行。

多粒度锁协议的优点:增加并行性,减少锁开销。
多粒度锁协议在由如下事务类型混合而成的应用中有用:
➢只存取几个数据项的短事务
➢由整个文件或一组文件形成报表的长事务

封锁机制的实现是由锁管理器执行,锁管理器通过维护锁表控制加锁机制。

死锁的处理

处理死锁方法:
引入死锁预防协议,使系统不进入死锁状态:通过对加锁请求进行排序,一事务开始前要锁定所有的数据项。

允许系统进入死锁状态,引入死锁检测和死锁恢复机制进行恢复。

死锁的预防

抢占与事务回滚技术：每一个事务赋予一个时间戳。若一个事务回滚,则当重启该事务时,必须保持原时间戳。然后采用以下机制:

wait-die:如果T1申请的数据被T2持有时, 则只有:T1>T2时, T1等待,否则回滚；
wound-wait:与前面条件相同时,只有:T1<T2时, T1等待,否则回滚

基于超时的机制：事先给出事务的等待的时间，超时即回滚。

死锁的检测与恢复

系统定期通过等待图检查死锁，如果出现环则出现了死锁，回滚代价较小的事务进行死锁恢复。

高级数据库课程笔记
从死锁中恢复:选择事务回滚
➢选择代价最小的事务，
➢回浪事务
➢防止饿死,将回浪次数考虑在代价中
➢基于锁的协议开销较大，井发的提升有限度。

分布式数据库

基本概念

产生原因

经济发展：随着经济发展，企业机构在不同地方设置分机构。
计算机网络和硬件发展。

发展历程

产生于20世纪70年代末期，成长于80年代。
第一个分布式数据库系统SDD-1是美国计算机公司( CAA )于1976年-1978年设计，79年在DEC 10/20上实现。
德国斯图加特大学研制的porel系统
美国IBM的R*和system R
美国加大学伯克利分校的Ingres
1987年，C.J Date提出了分布式数据库的12条规则：本地自治性、分布式查询独立性、不依赖于中心站点、分布式事务管理、可连续操作、硬件独立性、位置独立性、操作系统独立性、数据分片独立性、网络独立性、数据复制独立性、DBMS独立性。

定义

分布式数据库：是一个数据集合 ,这些数据分布在由计算机网络连接起来的若干节点上，每个节点可以管理本地的数据应用,也可以参与全局数据应用。同时这些数据在逻辑上形成一个整体,由统一的数据库管理系统进行管理。
站点:计算机连接的个逻温单位，称为一个站点。
本地(局部)用户、本地应用:一个用户或应用只访问他所注册的那个站点。
全局用户、全局应用:一个用户访同涉及两个或两个以上的站点中的数据。
全局数据库（GDB）、局部数据库（LDB）

基本特点

**结构特点**：物理分布，逻辑相关。 **应用特点**：站点自治。 **数据分布透明性**：用户感知不到数据分布在哪个站点。数据的物理独立性内容更丰富,增加了数据分布透明性。 **集中与自治兼备的数据库系统控制机制**,**实现两个层次的数据共享**：局部/全局数据共享。 **增加数据冗余度**：提高系统可靠性、可用性和系统性能。 **事务管理的分布性**:分布环境下，维护事务的原子性、一致性、隔离性和持久性。

分类

按局部数据库的数据模型分类：同构型（数据模型相同，再根据DBMS是否相同分为同质同构，异质同构），异构型（数据模型不同）。
按全局控制系统类型分类：全局控制集中型、全局控制分散型、全局控制可变型。
全局控制集中型：DDBS的全局控制机制及数据字典位于一个中心站点,由中心站点完成全局事务的协调和局部数据库的转换等所有控制功能。
全局控制分散型：DDBS的全局控制机制及数据字典分散在网络的各个站点上，每个站点都能完成全局事务的协调和局部数据转换。
全局控制可变型：将站点分成两组，一组都包含全局控制机制和数据字典，另一组为辅助站点，只包含自己的数据应用。

模式结构

高级数据库课程笔记

6级模式5级映射：全局模式定义了整个分布式系统的全局数据模式，通过数据分片将数据分配到各个站点，再通过分配模式将数据模式分配到各个站点上，各个站点再有局部模式进行分布式数据交换，局部内模式进行数据存储。每个响铃模式之间存都存在一个映像。

功能结构

包含集中式数据库的功能：增删查改、事务管理、并发控制、数据恢复。
数据跟踪：
分布式数据查询处理能力
分布式事务管理能力
复制数据的能力：分布式数据库要有数据冗余，需要数据复制。
安全性控制：每个环节，每个节点上都要有数据保障，比集中式数据库的安全控制复杂很多。
分布式目录管理

分布式系统存在的技术问题

设计方法

设计方法、内容和目标

设计方法

根据设计是基于现存的数据系统还是构造一个全新的数据库系统,有两种方法创建分布式数据库: 组合法和重构法。
高级数据库课程笔记

设计内容

需求分析（设计基础）包括数据需求和应用需求。
高级数据库课程笔记
数据库设计（核心任务）全局模式设计、分片模式设计、局部数据库设计以及片段位置分配设计。

设计目标

确保数据库数据和应用具有最大程度的本地性：确保应用请求尽量在本地完成，减少跨站请求。
分布式数据的可用性和可靠性
工作负荷分布：均衡各个站点的负荷，避免一个站点高压而其他一个站点空闲。
存储的能力和费用：分布式数据库的存储能力要比较强，同时也要兼顾费用问题。

设计步骤

高级数据库课程笔记

数据分片

概念

片段指在分布式数据库系统中，某一站点上存储的数据集合.
分片设计的目的是产生全局数据的一个合理的划分,从而使每个站点只获得它所需要的数据,最大可能保证应用的本地性。

数据分片的规则

分片应遵循的一般规则:完整性、可重构性、不相交性。
设: R= { R1, R2, … Rn }，这三种性质定义如下：
高级数据库课程笔记

分片的基本类型和操作

分片的类型有水平分片、垂直分片和混合分片，水平分片又分为初级分片和导出分片。
水平分片:对全关系进行选择操作,把具有相同性质的元组进行分组,构成若干不相交的子集。即将元组进行分组，类似于分表。水平分片又分为初级分片和导出分片

初级分片：用自身关系的属性进行分组，如学生表可以根据学生性别分组。
导出分片：用其他关系的属性进行分组；如学生成绩表可以按照学生表的性别属性进行分组。
垂直分片：利用投影操作把全关系的属性分成若干组,目标是把频繁使用的属性聚集在一起,且各片段只在键属性下重叠。类似于按列存储的思想。
混合分片：混合分片就是将水平分片和垂直分片进行混合使用，比如先进行水平分片，再对某一个片段进行垂直分片。

片段位置和分配设计

分配方式

非冗余分配：将一个片段映射到一个节点。
冗余分配：将一个片段映射到多个节点。
片段分配先进行非冗余分配，再进行冗余分配。非冗余分配保证了数据库的完整性，而冗余分配则是实现应用最大本地化的手段，也更加复杂。

分配算法

非冗余的最佳适应算法：通过统计某个片段在各个站点上的访问次数，将片段分配到最需要它的站点上。算法定义如下。
高级数据库课程笔记
冗余分配算法一般采用最佳站点得益法，附加复制法进行估算。

最佳站点得益法：计算量大，代价高。

对所有站点确定非冗余分配方案
从全部结点中选择一组站点，使得给这组站点分配片段Ri的一个拷贝所得到的检索效益,大于从其它站点对Ri实施更新的代价
把片段Ri拷贝分配给该组站点

附加复制法：

对所有站点确定非冗余分配方案
计算把片段Ri分配给所有站点所能得到的总效益fi (以及一个站点分得Ri所得到的效益)
从分得片段Ri能够获取最大益处的站点起,对各站点依次附加片段Ri的一个拷贝，直到增加片段Ri不能使系统得到明显效益(或者说效益增大"接近" fi )为止。

查询机制

分布式查询处理的步骤和代价

查询步骤

查询分析 — 查询分解 — 查询本地化 — 全局查询优化 — 局部优化

查询分析：若该查询属于局部查询,则执行局部查询处理后，即可结束，此时与集中式数据库基本一致；如果是全局查询则把全局查询或远程查询转换成定义在全局关系上的关系代数表达式,并优化该表达式，再往下执行本地化、全局优化。

查询分解、查询本地化：把一个全局关系上的查询,转化为对片段的局部查询。即把查询命令转化成各个站点的子查询命令（本地化）。

全局查询优化：找出对各个片段局部查询结果之间的最佳操作次序,使得代价最小。其重点在连接运算和并运算的优化。

局部优化：查询片段所在的站点执行查询前进行查询优化。

代价测量

集中式数据库的代价主要来源于IO，而分布式数据库的查询代价除了IO，更多的是通讯代价。分布式数据库查询代价公式： $QC=I/O代价 + 通讯代价T$

通讯代价T的估算： $T = Σ传输次数(每次传输延迟时间 + 每次传输数据量/传输速率) = Σ传输次数(C_{0} + X/D)$

基于等价变换的查询优化

分布式数据库基于等价变换的查询优化与集中式数据库是基本一致的，不同的在于分布式优化是将选择条件推到相关节点，相关节点再根据选择条件去掉无关的片段，减少无用数据的传输带来的代价。

下面给出优化片段查询树的规则：
a.对于水平分片,检查选择运算( σ)与水平分片的条件(谓词)，无关片段直接忽略。
b.对于垂直分片,注意消去不提供连接运算后所需要属性的分支。
高级数据库课程笔记 ### 基于半连接算法的查询优化

半连接定义

半连接运算是由投影和连接操作导出的一种关系代数操作，定义如下：

设:关系R和S在属性R. A=S.B上的半连接操作记为: $R∝_{A=B}S = π(R∞_{A=B}S) = R∞_{A=B}(π_B(S))$

利用半连接运算进行优化

半连接实现连接运算： $R∞_{A=B}S = (R∝_{A=B}S)∞_{A=B}S$ 或者 $R∞_{A=B}S = (S∝_{A=B}R)∞_{A=B}R$

利用上式对站点间的连接操作进行优化：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cfck6jyn-1590374748389)(imgs/image-20200522193005999.png)]

站点2与站点1的表做自然连接请求时，先将S表进行投影，再发送数据，减少了无关数据的传输。中间表R’回传时也少传了一次S的其他列数据。通过半连接运算的优化，大大节省了通讯代价。

基于直接连接算法的查询优化

利用站点依赖进行优化

站点依赖：
高级数据库课程笔记

对于关系 $R_1$ 和关系 $R_2$ 在属性A上站点依赖，则F11,F12,F21,F22四个片段满足：

$π_A(F11)∩π_A(F12) = φ$

$π_A(F21)∩π_A(F22) = φ$

$π_A(F11)∩π_A(F22) = φ$

$π_A(F12)∩π_A(F21) = φ$

定义：设 Ri[A]、Rj[A]、 Si[A] 、Sj[A]分别表示关系R、S在站点i、j的A属性上的取值。若对于i≠j,有: Ri[A] ∩ Sj[A] = φ.则称关系R和S在属性A上站点依赖。

性质：若关系R和S在属性A上满足站点依赖，则 $R∞S = ∪_i(R_i∞S_i)$

利用这个性质，在两个站点进行连接运算是，两个关系可以分别在不同站点上进行自然连接操作，将结果返回到请求站点上再做一次连接操作，即可得到连接结果。请求不需要数据通信，省去了连接请求时发送数据的通信代价，且可以并行计算，甚至可以利用本地索引加速节点上连接运算。缺点是条件苛刻，分片设计和分配困难。

利用分片与复制优化

当查询不能在无数据传送方式下处理,可采用分片和复制算法

算法的原理:
选择一组站点,将查询中的某一个关系的所有片段分布到这些站点上,然后把查询中的其余关系复制到每一个选定的站点上。
高级数据库课程笔记
优化算法：在站点上分别计算 $R_1$ 片段和 $R_2$ 的自然连接结果，最后收集结果即可。

优点：可以并行计算；利用本地索引加速；实现较简单，应用广泛。

缺点：相比站点依赖方法有较大数据冗余

事务管理

——

并发控制

——

大数据

大数据数据特征

多样性(Variety)，变化快(Velocity)，大容量(Volume)，质量弱(Veracity)。

多样性：数据多样性指当前数据的种类多，包括用户数据、媒体数据、传感器采集数据等等。
变化快：数据增长速度快。数据的产生或存储速度要求高，对当前数据处理能力产生挑战。
容量大：指数据容量相当巨大，这个大是具有相对性的，有当前技术的数据处理能力决定。数据摩尔定理：每18个月产生的数据量是此前产生所有数据量之和。
质量弱：数据库对数据质量具有一定的容忍性，入库数据的质量无法保证，需要进行数据清洗。

大数据系统特征

大数据系统=大数据+大数据管理系统。
高级数据库课程笔记
大数据数据特征隐含了对大数据系统的技术要求

影响数据管理系统的三大要素：数据应用、数据平台、数据。

三大要素反应的问题：

从封闭世界到开放世界：

封闭的数据世界，查询不到的数据就是不存在；封闭的数据来源封闭，局限于事先规定好的系统；封闭的模式，模式也是实现规定的；封闭的代数系统，只能进行关系操作。

开放世界下，查询不到的数据定义为未知数据，存储模式不固定，操作可以进行拓展。
从量的管理到质量管理

数据清洗将成为核心，信息检索代替信息查询，使用数据分析/机器学习技术将对劣质数据具有一定容忍性。
从数据管理到知识管理

关系数据库的数据是需要模式进行解释的，而大数据具有自描述的，不需要在数据本身的管理上花费过多精力，大数据价值的关键转移到如何从大数据中获取知识。

大数据应用特征

大数据作为一种新的战略资源，要重视对数据对象的管理、重视对数据的治理。
- 数据作为一种资源，需要进行有效的控制和管理。
- 数据可以“零成本“复制
- **数据资源的价值在于知识发现。**三种发现手段：
- 数据服务
- 数据分析（描述分析、诊断分析、预测分析、策略分析）
- 数据探索
大数据作为一种新的研究方法，已经在许多科学领域取得成效：第四研究范型。
大数据是未来科学研究的重要手段。人类科学研究范型发展：
- 实验观察（几千年）
- 理论推导（几百年）
- 计算机仿真（几十年）
未来的发展方向必然是以大量的数据为基本，利用计算机与数学分析技术进行科学研究。要作为科学研究的手段，必须严谨、真实，所以必须进行数据的控制与管理。
大数据作为一种新的信息化思维，强调跨界应用，数据整合基础上的创新。

大数据+行业是信息化的第三阶段，在数据整合的基础上的智能计算阶段，取代一些人类难以分析的业务研发环节。

打破数据孤岛，实现信息共享。

数据仓库

概述

传统DBMS的主要目的是解决业务问题，现在传统的数据库已经在数据存储与管理、事务管理与业务应用上取得了巨大成功。此时数据库中存储的大量数据蕴含着极大的价值，随着数据记录，分析的需求逐渐增长，建立在事务处理环境中的数据分析效果差强人意，数据仓库应运而生。

定义

数据仓库就是一个用以更好地支持企业或组织的决策分析处理的、面向主题的、集成的、不可更新的、随时间不断变化的数据集合。

数据仓库的四个基本特征：

数据仓库的数据是面向主题的
数据仓库的数据是集成的
数据仓库的数据是不可更新的
数据仓库的数据是随时间不断变化的

体系结构

高级数据库课程笔记
简单地说，数据从操作型数据库、文件、网络等数据源，通过ETL集成工具进行数据抽取、清洗、转换、加载等工作，进入到数据仓库和数据集市中，进而通过OLAP服务器支持前台的多维分析、查询报表、数据挖掘等操作。

OLAP联机分析处理技术

多维数据模型

数据仓库和OLAP服务器基于多维数据模型。
多维数据模型将数据看作数据方体(DataCube),它通过维(dimension)和度量(measure)进行定义。
维度可以有层次

多维模型实现方式

基于关系数据库：

星形模式
雪片模式
事实群模式

基于多维数组

基于关系模型	基于多维数组
适应性、伸缩性和扩展性好不存在稀疏数据问题访问速度不如多维数组快	存储效率高访问速度快不同维的访问效率差别很大在数据稀疏的情况下，由于大量无效值的存在，存储效率下降

星形模式

高级数据库课程笔记
将一个表按维度切分成多个子表，由事实表进行维度标记。事实表通过表连接操作可以还原维度信息表。

优点是方便进行维度分析，可以减少无关维度信息的读入量；

缺点是需要大量连接操作。

雪片模式

高级数据库课程笔记
在星形模式中，如地区维，会有许多重复的属性，将重复的属性抽取出来，建立一个子表进行存储。

优点：相比星形模式节省了存储重复信息的空间，减少信息冗余。

缺点：增加了表连接操作代价。

事实群模式

有多个事实表，他们一些相同的属性可以共享一个维度表。

多维数组存储

多维数组只存储数据方体的度量值，维值由数组的下标隐式给出。

按行访问时速度快，按列访问时效率差

解决方法：将一个n维数组分成n个小的n维数据块，类似表的分表操作。
稀疏数据导致空间利用率低

使用稀疏存储进行压缩。

多维分析操作：

聚集操作
切片/切块操作
钻取操作
旋转操作

OLAP SERVER

OLAP用于解决多维数据存储以及多维数据操作问题。OLAP的主要实现方式有以下三种：

ROLAP

高级数据库课程笔记
ROLAP服务器将关系存储交给关系数据库，将用户请求转化成SQL查询，再对查询结果进行分析处理返回结果。

MOLAP

用多维数组的方式存储多维数据，自己管理和操作存储数据。

HOLAP

是MOLAP和ROLAP的结合，使用混合的方式存储数据，将细节数据存储在关系数据库中，而将综合数据存储在MOLAP服务器中。

CUBE计算技术

实体化视图技术

类似缓存技术，提前将方块视图进行实体化，数据操作时节省视图查询的开销。

精简数据方体技术

索引技术

NOSQL

概念

NOSQL，即not only sql，泛指非关系型的数据库。一般是牺牲关系数据库的一些功能来换取性能。

分类：键值(Key-Value)存储数据库、文档型数据库、图数据库、列存储数据库。

分类	Examples举例	典型应用场景	数据模型	优点	缺点
键值（key-value）	Tokyo Cabinet/Tyrant， Redis， Voldemort， Oracle BDB	内容缓存，主要用于处理大量数据的高访问负载，也用于一些日志系统等等。	Key 指向 Value 的键值对，通常用hash table来实现	查找速度快	数据无结构化，通常只被当作字符串或者二进制数据
列存储数据库	Cassandra， HBase， Riak	分布式的文件系统	以列簇式存储，将同一列数据存在一起	查找速度快，可扩展性强，更容易进行分布式扩展	功能相对局限
文档型数据库	CouchDB， MongoDb	Web应用（与Key-Value类似，Value是结构化的，不同的是数据库能够了解Value的内容）	Key-Value对应的键值对，Value为结构化数据	数据结构要求不严格，表结构可变，不需要像关系型数据库一样需要预先定义表结构	查询性能不高，而且缺乏统一的查询语法。
图形(Graph)数据库	Neo4J， InfoGrid， Infinite Graph	社交网络，推荐系统等。专注于构建关系图谱	图结构	利用图结构相关算法。比如最短路径寻址，N度关系查找等	很多时候需要对整个图做计算才能得出需要的信息，而且这种结构不太好做分布式的集群方案。

特点

对于NoSQL并没有一个明确的范围和定义，但是他们都普遍存在下面一些共同特征：

易扩展

NoSQL数据库种类繁多，但是一个共同的特点都是去掉关系数据库的关系型特性。数据之间无关系，这样就非常容易扩展。无形之间，在架构的层面上带来了可扩展的能力。

大数据量，高性能

NoSQL数据库都具有非常高的读写性能，尤其在大数据量下，同样表现优秀。这得益于它的无关系性，数据库的结构简单。一般MySQL使用Query Cache。NoSQL的Cache是记录级的，是一种细粒度的Cache，所以NoSQL在这个层面上来说性能就要高很多。

灵活的数据模型

NoSQL无须事先为要存储的数据建立字段，随时可以存储自定义的数据格式。而在关系数据库里，增删字段是一件非常麻烦的事情。如果是非常大数据量的表，增加字段简直就是——个噩梦。这点在大数据量的Web 2.0时代尤其明显。

高可用

NoSQL在不太影响性能的情况，就可以方便地实现高可用的架构。比如Cassandra、HBase模型，通过复制模型也能实现高可用。

适用场景

NoSQL数据库在以下的这几种情况下比较适用：
1、数据模型比较简单；
2、需要灵活性更强的IT系统；
3、对数据库性能要求较高；
4、不需要高度的数据一致性；
5、对于给定key，比较容易映射复杂值的环境。

KV数据库

概念

键值对数据库/键值对系统的定义:一个针对关联数组(字典或Hash表)提供高吞吐数据服务(存储、读取和管理)的数据库系统。

关联数组包含了很多记录，每个记录又有不同的属性。
系统通过唯一标识记录的键(key)来迅速存储和读取单行记录中的数据，实现对关联数组高并发读写服务。

特点

高级数据库课程笔记

数据模型

高级数据库课程笔记

持久化的、分布式的、多维Hashtable
键值排序(实现按键的快速数据检索)
列族、Tablet (分片)、Timestamp

API操作接口

get(key), put(key, value), delete(key)
execute(key, operation, parameters)
指定列的数据读取
有的允许在一定范围内的键值读取rowkey与columnkey

原理

高级数据库课程笔记
kv数据库牺牲了一致性，满足了可获取性和数据划分。

在一致性上，kv数据库采取的是最终一致性，即在数据库不繁忙的时候数据会逐渐收敛到一致性状态。

很长时间没有数据更新后，最终所有更新会传播到整个系统，所有节点的数据保持一致
如果一个节点没有离开服务，最终系统接受的和这个节点数据相关的更新操作会作用在该节点上
BASE协议(Basically Available, Soft state, Eventualconsistency),区别于ACID
■数据的副本之间可能不一致
■该数据没有更新，最终副本之间会一致

牺牲掉以下数据库特性，换取高性能、高吞吐、可扩展和高容错的键值对数据读写解决方案
■链接操作
■group by
■order by
■ACID事务处理
■SQL

典型实现

大Hashtable
Amazon S3 (Dynamo), Voldemort, Scalaris
列族
Cassandra, BigTable, HBase, Sherpa/Pnuts, Hypertable
内存型
Redis, Memcached…

文档数据库 MangoDB

概述

MangoDB是一个开源的高性能无模式文档型数据库
■面向文档(document-oriented):数据库中的每条记录是一个文档对象，采用类JSON的文档格式，非常接近真实对象模型
■无模式(Schema-less):每个文档格式都可以不同没有严格的模式定义，灵活方便
■高性能:拥有卓越的读写性能，并具有高可用副本集和可扩展分片集群技术，从先天上支持数据库的高扩展性和高伸缩性

特点

适用场景：

●网站数据: MongoDB非常适合实时的插入，更新与查询，并具备网站实时数据存储所需的复制及高度伸缩性
●缓存:由于性能很高，MongoDB适合作为信息基础设施的持久化缓存层。
●高伸缩性的集群场景:适合由数台服务器组成的大规模数据存储
●用于对象及JSON数据的存储:MongoDB的BSON数据格式非常适合文档格式化的存储及查询

图数据库

概念

属性图

属性图由顶点、边、标签、和属性组成
顶点可以包含一组属性，每个属性由键值对组成，即属性名和属性值
顶点可以被赋予一个或多个标签，每个标签代表该顶点的类别
边是有方向的，边vi >vj表示源点vi到终点vj的联系
类似于顶点，边也可以包含属性和标签

数据模型

数据模型由数据结构、数据操作、数据的完整性约束条件组成。

图数据库的数据模型是属性图。
高级数据库课程笔记

优点

图数据库在处理如社交网络等图数据时，具有性能和灵活性的有点。

性能

高级数据库课程笔记
关系数据库

关系数据库查找某个用户的朋友的朋友的数量，需要做多次表连接操作，效率低下。

图数据库
高级数据库课程笔记
图数据库为每一类对象单独存成文件，每个对象的大小固定，如顶点文件;联系文件;标签文件;属性文件等

图数据库只需找到用户顶点，按照边的联系进行查找，效率高。

灵活性

关系数据库	图数据库
事先建立完整关系模式	无需事先建立模式
模式修改代价大	图结构的变化不影响已有的查询和应用程序
互联网应用需要频繁修改模式	-

主要功能

面向事务的图数据库能够支持:

■数据对象(顶点与边)及其属性的增删改操作
■支持ACID事务处理并提供定制的查询语言来支持管理、分析和检索操作
■数据的备份与恢复

内存数据库

概念

定义:使用内存作为常规数据存储设备的数据库系统，简称为IMDB(In-MemoryDatabase)或MMDB(Main-Memory Database)
高级数据库课程笔记

内存数据库 != cached磁盘数据库

磁盘数据库的缓冲区是磁盘数据在内存的副本，采用与磁盘存储一致的基于page-slot的数据结构，当内存足够将全部磁盘数据缓存在缓冲区时，数据访问只是相当于在内存磁盘(RAMDisk)上的访问。
内存数据库的存储和访问算法以内存访问特性为基础，实现处理器对数据的直接访问，在算法和代码效率上高于以磁盘I/O为基础的磁盘数据库。
在内存数据库中，数据和索引结构都存储在内存中，使用针对内存访问特性进行优化的T树索引和hash索引、面向cache优化的索引算法和多种面向连接操作的优化技术，进一步优化了内存数据库的性能。
与数据全部缓存到内存的磁盘数据库相比，内存数据库的性能仍然超出数倍。

特点

基本特点：

内存为主要存储设备
磁盘为后备存储和持久化设备
查询优化面向内存访问，而不是I/O

	内存数据库	磁盘数据
存储结构	内存数据库在内存中按行或列存储，数据访问的单位为cache line(64字节)	磁盘数据库在磁盘为page(页)为单位存储数据, 一次I/O访问一个数据page(4KB或8KB)
索引结构	内存CSB+Tree索引:以cache line为存储和访问单位，优化指针存储; CSB+树的eachs优化技术: 1.节点大小与cache linc 一致 2.内部节点对应的子节点存储在连续区域	磁盘B+Tree索引:以page为单位存储索引节点，索引访问涉及多个I/O操作；磁盘B树优化技术: 1.节点大小与page一致； 2.内部节点多指针减少I/O访问代价
查询处理	内存数据库查询优化以cache line miss为基础，目标是提高cache利用率，降低内存访问延迟，提高处理器的并行处理效率 ●适合cache line大小的数据存储和数据访问结构 ●将大表划分为适应cache大小的分区 ●优化数据访问，提高cache利用率 ●优化并行查询处理性能	磁盘数据库查询优化以I/O估算为基础，目标是提高缓冲区利用率，减少IO代价

应用领域

内存数据库管理系统 In-Memory Database Management Systems:

应用于内存事务处理面向高吞吐、低延迟、高响应事务处理应用
可以作为独立的内存数据库事务处理引擎，也可以作为磁盘数据库引擎的高速cache

基于内存数据库的数据分析 In-Memory Analytics:

应用于内存分析处理
面向大数据、内存实时分析处理应用
主要面向数据仓库和联机分析处理应用

应用架构

目前内存数据库的应用架构主要有三种：

独立的内存数据库
作为传统磁盘数据库的前端Cache数据库
集成的内存数据库引擎

代表产品

代表性内存OLAP数据库

学术系统: MonetDB, Hyper
向量处理技术内存数据库: Vectorwise
内存分析加速技术: IBM BLU Acceleration
内存分析引擎: Oracle Database In-Memory, SQL Server, MEMSQL
OLTP&OLAP内存数据库: SAP HANA
MPP内存数据库: EXASOL