“数据库”学习笔记


概述

  • DB 是数据的集合,存储在磁盘中;
  • DBMS 称作数据库管理系统,是一个基础软件,用来存储和管理数据库;
  • DBS 数据库管理系统是针对一个用户的数据管理需求开发的应用系统。
  • 文件系统存储数据的缺点
    • 数据冗余和矛盾
    • 存取资料比较困难
    • 数据隔离
    • 数据合法性的约束
    • 数据修改的完整性
    • 多用户同时进入问题
    • 安全性问题
  • 数据库系统的构造(从用户角度出发)
    • view level :隐藏一些数据的类型和出于保密所需要的数据信息
    • logical level :描述数据库中的数据以及数据之前的关系
    • physical level :记录数据如何存储,一般有比较复杂的数据结构。
    • physical storage :物理存储介质。
  • 实例和模式
    • 实例:数据库中的实际数据;
    • 模式:数据库的逻辑结构。
  • 数据库的物理独立性:指的是修改数据库的物理模式不会影响数据库的逻辑模式的一种能力。
  • 数据库应用依赖的是逻辑模式。
  • 数据模型是描述数据和数据之间的关系、数据的一些约束的工具。
    • 关系模型、ER 模型、基于对象的模型、XML、JSON等
  • 数据库语言是一类访问数据库中数据的语言,具有数据定义和数据操纵的能力
    • Data Manipulation Language (DML): 执行数据库查询和修改操作
      • 过程语言:用户需要指出获取数据的方法
      • 非过程语言:用户无需指出获取数据的方法(例如 SQL)
    • Data Definition Language (DDL): 执行数据库模式定义操作
    • SQL: 结构化查询语言,但是不仅仅执行查询,包括定义数据库模式、修改数据库以及说明安全约束等都可以完成。
  • 数据库的设计方法
    • E-R模型:实例-关系 模型。
    • 形式化的方法
  • 存储管理模块提供了存储在数据库中的底层数据与应用程序以及提交到系统的查询的接口
    • 负责:与文件系统的交互、有效的数据存储、检索和修改
    • 解决的问题:存储访问、文件组织、索引和hash
  • 事务管理系统:包括事务管理和并发控制

关系模型

  • 关系数据库包括:关系名称、元组、属性名称
    • 属性有类型,描述的是每个属性允许取值的范围
    • 属性是原子不可分的
    • 属性可以取一个特殊的值: null
  • 关系模式 \(R=(A_1,A_2,\cdots , A_n)\) 是属性的集合;
  • 关系是 \(D_1\times D_2\times \cdots \times D_n\) 的子集
  • 键:唯一的编号不同的区分元组
    • 设 \(K\subseteq R\) ,\(R\) 是所有属性的集合
    • superkey:\(K\) 的取值足以唯一确定 \(R\) 的每一个可能的记录
    • candidate key:最小的 super key 集合
    • primary key:主码。多个 candidate key 中选一个作为主码,实现时用。应该选择属性值很少变化的属性
    • foreign key:外码。假设有 \(R\) 表和 \(S\) 表, \(R\) 表中的属性 \(A\) 在 \(S\) 表中是主码,那么这个 \(A\) 属性在 \(R\)表中是外码
      • \(R\) 称为 referencing relation
      • \(S\) 称为 referenced relation
      • 外码是一种数据的完整性约束,即在 \(S\) 中未出现过的 key 不能在 \(R\) 中被引用
  • 关系查询语言分为程序语言和非程序语言
  • 关系运算
    • select
      • Select tuples with \(A=B\) and \(D > 5\) \(\sigma _{A=B\; and \; D>5}(R)\)
      • Select \(A\) and \(C\) \(\prod _{A,C}(R)\)
    • join
      • \(r\times s\)
      • \(r\cup s\)
    • difference
      • \(r-s\)
    • intersection
      • \(r\cap s\)
    • natural join
      • \(r\bowtie s\)
      • \(r\cup s\) 但是合并的时候,只保留满足 \(r\cap s\) 的部分,例如:

SQL

  • SQL 有四个能力:
    • Data-definiton language (DDL)
    • Data-mainpulation language (DML)
    • Query language
    • Data-control language : 控制数据的权限以及完整性约束
  • SQL是非过程语言,及只需告诉要什么,而不需告诉如何得到
  • Data-definition 包括:
    • 定义每个属性的值域
    • 定义完整性约束
    • 定义每个关系的索引(可以加快查询速度)
    • 定义每个关系的安全和权限
    • 定义每个关系在磁盘上的物理存储结构
  • Data-definition 基础类型
    • char(n) 长度为 \(n\) 的字符串
    • varchar(n) 最长长度为 \(n\) 的字符串
    • int, smallint
    • numeric(p,d) 包含 \(p\) 位的浮点数,其中小数点右边有 \(d\) 位
    • real, double precision
    • float(n) 浮点数,至少有 \(n\) 位有效数字
  • 创建数据表
    • create table 表格名称
      • (属性名称 属性类型 ,
      • primary key (属性名称));
  • 删除数据表
    • drop 表格名称
  • 删除某个内容
    • delete 属性名称 from 表格名称
  • alter
    • alter table 表格名称 add A D
      • A 是属性名称
      • D 是属性类型
    • alter table 表格名称 drop A
      • A 属性名称
  • 查询数据
    • selete 属性名称
    • from 表格名称
    • while 约束
  • 数据去重
    • selete distinct 属性名称
    • from 表格名称
    • 会返回属性去重之后的结果
  • 也可以返回不去重的结果
    • selete all 属性名称
    • from 表格名称
  • 查询所有的属性
    • selete *
    • from 表格名称
  • 查询属性的结果可以使用四则运算
  • 可以查询表格 \(\times \)  的结果
    • selete *
    • from 表格1 , 表格2
  • 可以查询表格 natural join 的结果
    • selete *
    • from 表格1 nature join 表格2;
  • 在使用Natural join时需要注意:同名的不相关属性被错误地做相等判断。
  • 判断字符串
    • where name like ‘%aaa%’ (包含子串 aaa 的字符串)
    • ‘Intro%’ matches any string beginning with “Intro”.
    • ‘%Comp%’ matches any string containing “Comp” as a substring.
    • ‘_ _ _’ matches any string of exactly three characters.
    • ‘_ _ _ %’ matches any string of at least three characters.
  • 排序
    • selete 属性名称
    • from 表格名称
    • order by 属性名称1, 属性名称 2 (desc(倒序)/asc(默认,顺序))
  • 聚合函数
    • avg(属性名称), sum(属性名称), min(属性名称), max(属性名称)
    • count(属性名称)  例如 count (distinct ID),Count考虑取 null 值的记录
  • Group By 语句
    • 例如,求所有同一个学院的平均工资
      • select dept_name, avg (salary)
        from instructor
        group by dept_name;
    • 写带有group by的SQL时,group by之后的属性必须在 select 子句出现,其他属性出现没意义。
      • 例如下面这个例子是无意义的
      • select dept_name, ID, avg (salary)
        from instructor
        group by dept_name;
  • having 语句
    • select dept_name, avg (salary)
    • from instructor
    • group by dept_name
    • having avg (salary) > 42000;
  • 子查询
    • select count (distinct ID)
    • from takes
    • where (course_id, sec_id, semester, year) in
                                      (select course_id, sec_id, semester, year                                        from teaches                                        where teaches.ID= 10101);
  • some 只要有一个成立即成立
  • all 只要有一个不成立即不成立
  • Correlation Variables
    •   select course_id
      from section as S
      where semester = ’Fall’ and year= 2009 and
      exists
      (select *
      from section as T
      where semester = ’Spring’ and year= 2010
      and S.course_id= T.course_id);
    • 括号中的子查询的where子句用了外层SQL查询的关系名 \(S\) ,所以 \(S\) 称为 Correlation name
    • 这类查询称作correlated subquery
  • not exists (X except Y) 等价于查询 X 是 Y 的子集
  • unique
    • select T.course_id
      from course as T
      where unique (select R.course_id
      from section as R
      where T.course_id= R.course_id
      and R.year = 2009);
  • from 中进行子集查询
    • select dept_name, avg_salary
      from (select dept_name, avg (salary) as avg_salary
      from instructor
      group by dept_name)
      where avg_salary > 42000;
  • lateral
    • 查找老师及其薪水和所在系的平均薪水
      • select name, salary, avg_salaryfrom instructor I1, lateral (select avg(salary) as avg_salary
        from instructor I2
        where I2.dept_name= I1.dept_name);
  • With子句提供了一种定义临时关系的方法,这个临时关系可以用于查询,但是只对包含with子句的查询有效。通过例子我们来理解with子句的定义与使用。
    • with max_budget (value) as
      (select max(budget)
      from department)
    • select budget
      from department, max_budget
      where department.budget = max_budget.value;
  • Scalar Subquery:简单说就是返回单一值的子查询。返回的不是单一值,就会 RE。
    • select dept_name,  (select count(*)
      from instructor
      where department.dept_name = instructor.dept_name)  as num_instructors
      from department;
  • delete 删除信息
    •  delete from instructor
      where dept_name in (select dept_name
      from department
      where building = ’Watson’);
  • insert 插入信息
    • insert into course (course_id, title, dept_name, credits)
      values (’CS-437’, ’Database Systems’, ’Comp. Sci.’, 4);
  • select 信息,插入数据库,select查询语句全部执行完成之后再进行insert操作
    •  insert into student
      select ID, name, dept_name, 0
      from   instructor
  • update 修改数据,要注意修改的顺序。
    • update instructor
      set salary = salary * 1.03
      where salary > 100000;
  • case update
    • update instructor
      set salary = case
      when
      salary <= 100000 then salary * 1.05
      else salary * 1.03
      end

Join

分类

  • inner join:结果只保留匹配的元组,不保留未匹配的元组
  • outer join:通过在结果中保留包含空值元组的方式保留在连接中丢失的元组
    • left outer join:保留出现在左边关系中的元组
    • right outer join:保留出现在右边关系中的元组
    • full outer join:保留两个关系中的所有元组

Views

任何这样不是逻辑模型的一部分,但作为虚拟关系对用户可见的关系,称为视图。不是实际存在的关系。

  • 定义一个 views :create view v as < query expression >
  • 定义的时候,同样可以引用,已经定义过的 views

Materialized Views

物化视图,必须保证: 用于定义视图的实际关系改变,视图也随之改变。

物化视图的优势:频繁使用物化视图的应用,因为存储了视图关系,可以提高响应熟读。比如:一些基于聚合函数做统计计算查询的应用,可以定义有关聚合函数计算的物化视图,在物化视图上查询要快很多,避免读取规模大的实际关系表。常用于查询业务量较大的应用。

大部分的 SQL 只支持在简单的 views 上更新数据,因为数据的更新可能会产生不确实性问题。

当view满足一些条件时,可以对view进行增删改操作:

  1. from子句只有一个关系
  2. select子句中只包含关系的属性,不含其它的任何表达式计算或distinct说明
  3. 任何没有出现在select字句中的属性可以取null值
  4. 查询中没有group和having子句

Integrity Constraints

完整性约束何时说明:定义数据库schema的时候说明

完整性约束何时检验:修改数据库表的时候检验是否违反了完整性约束

  • 单个关系上的约束
    • not null
      • name   varchar(20) not null
    • primary key
    • unique
    • check (P), where P is a predicate
      • semester   varchar (6),
      • check (semester in (’Fall’, ’Winter’, ’Spring’, ’Summer’)));
  • Foreign key是一类完整性约束
    • create table course (
    •     course_id   char(5) primary key,
    •     title             varchar(20),
    •     dept_name varchar(20) references department)

数据类型

  • date
    • Example:  date ‘2005-7-27’
  • time
    • Example:  time ‘09:00:30’         time ‘09:00:30.75’
  • timestamp
    • Example:  timestamp  ‘2005-7-27 09:00:30.75‘
  • interval
    • Example:   interval  ‘1’ day
  • blob:binary large object
  • clob:character large object

数据类型转换

  • cast   <string-valued-expression> as date
  • 自己定义一个新的类型
    • create type Dollars as numeric (12,2) final
    • create domain person_name char(20) not null

权限

database 四种权限:

  • read
  • insert
  • update:allows modification, but not deletion of data.
  • delete

database schema  四种权限:

  • Index:allows creation and deletion of indices.
  • Resources:allows creation of new relations.
  • Alteration:allows addition or deletion of attributes in a relation.
  • Drop:allows deletion of relations.

授权方式

  • grant <privilege list>
  • on <relation name or view name>
  • to <user list>

privilege

  • select: allows read access to relation,or the ability to query using the view
    • grant select on instructor to U1, U2, U3
  • insert: the ability to insert tuples
  • update: the ability  to update using the SQL update statement
  • delete: the ability to delete tuples.
  • all privileges: used as a short form for all the allowable privileges

收回权限

  • revoke <privilege list>
  • on <relation name or view name>
  • from <user list>

基于角色的访问控制

基于角色的访问控制广泛应用于应用中,分配权限时针对角色分配。

  • create role teaching_assistant
  • grant teaching_assistant to instructor;

Views 也可以 grant 相应的权限

Functions

例如:

  • 定义部分
    • create function dept_count (dept_name varchar(20))
    • returns integer
    • begin
      • declare d_count integer;
      • select count (* ) into d_count
      • from instructor
      • where instructor.dept_name = dept_name
      • return d_count;
    • end
  • 调用部分
    • select dept_name, budget
    • from department
    • where dept_count (dept_name ) > 12
  • 返回值也可以是 relations
  • create function instructors_of (dept_name char(20))
  • returns table (
    • ID  varchar(5),
    • name varchar(20),
    • dept_name varchar(20),
    • salary  numeric(8,2));
  • return table (
    • select ID, name, dept_name, salary
    • from  instructor
    • where instructor.dept_name = instructors_of.dept_name);
  • select *
  • from table (instructors_of (‘Music’))

Procedures

  • 例如:
    • create procedure dept_count_proc (in dept_name varchar(20),
      • out d_count integer)
    • begin
      • select count(*) into d_count
      • from instructor
      • where instructor.dept_name = dept_count_proc.dept_name
    • end
  • 调用:
    • declare d_count integer;
    • call dept_count_proc( ‘Physics’, d_count);
  • 可以用来处理异常
    • declare out_of_classroom_seats condition
    • declare exit handler for out_of_classroom_seats
    • begin
      • sequence of statments
    • end

循环语句

  • while
    • declare integer default 0;
    • while n < 10 do
      • set n = n + 1
    • end while
  • repeat
    • repeat
      • set n = – 1
    • until n = 0
    • end repeat
  • for
    • for as
      • select budget
      • from department
      • where building=‘Watson’
    • do
      • set n = n + r.budget
    • end for

分支语句

  • if
    • if boolean expression
      • then statement or compound statement
    • elseif boolean expression
      • then statement or compound statement
    • else statement or compound statement
    • end if

Trigger

Trigger是一个语句,这个语句在满足一定条件时自动执行:当对数据库进行修改(增、删、改)时,记录的值满足特定条件时。

  • Trigger也称为event-condition-action规则。
  • 应用trigger可以使应用程序监控数据库的一些事件。
  • 应用trigger时要做两项工作
    1. 说明什么条件下执行触发器:引起触发器的事件(event)和触发器执行必须满足的条件(condition);
    2. 触发器执行时触发的动作。
  • 两张表中的属性是同一个,但是不能通过外键约束的时候,我们可以用 Trigger 机制
    • create trigger timeslot_check1 after insert on section
    • referencing new row as nrow
    • for each row
    • when (nrow.time_slot_id  not in (
      • select time_slot_id
      • from time_slot))
    •  begin
      • rollback //回滚,恢复插入之前的数值。
    • end;
  • referencing old row as   :  for deletes and updates
  • referencing new row as  : for inserts and updates
  • 可以修改值,以满足约束
    • create trigger setnull_trigger before update of takes
    • referencing new row as nro
    • for each row
    • when (nrow.grade = ‘ ‘)
    • begin atomic
      • set nrow.grade = null;
    • end;
  • 根据激活触发器的语句所执行的操作不同,SQL Server会自动创建一个或两个临时表:inserted和deleted表可直接引用
    • 插入时:创建 inserted 表,存储插入的记录
    • 删除时:创建 deleted 表,存储删除的记录
    • 更新数据时:创建 inserted 表,存储修改后的数据;创建 deleted 表,存储修改前的数据
    • create trigger overdraft-trigger on account
    • for update
    • as
    • if  inserted.balance < 0
    • begin
      • sequence of statments
    • end
  • trigger有很多合适的应用场景,但有些场景最好不用。例如早期维护物化视图,但是新版本支持自动维护;早期的复制和维护数据,现在则有专门的内置数据库复制工具;
  • 写trigger时要特别小心,因为运行期间一个trigger错误会导致引发该trigger的action语句失败,而且一个trigger的动作可以引发另一个触发器,最坏情况下,会导致一个无限的触发链。
  • 如果有其他替代方法最好不用trigger,可以用存储过程来实现相应的功能。

Formal Relational Query Languages

  • 形式化语言有三种(“Pure” languages)
    • Relational algebra
    • Tuple relational calculus
    • Domain relational calculus
  • 关系代数的类型
    • 常用的集合运算
      • union \(\cup \)
      • intersection \(\cap\)
        • \(A \cap B=A-(A-B)\)
      • difference \(-\)
      • rename
        • \(\rho _{x} E\) 将关系代数表达式 \(E\) 的结果(依然是一个关系)命名为 \(x\)
    • 从关系中去掉一部分数据
      • selection \(\sigma \)
        • \(\sigma _{\text{dept_name=“Physics”}}(\text{instructor})\)
        • \(\wedge\) (and), \(\vee\) (or), \(\) (not)
      • projection \(\prod\)
        • Project投影运算的结果是关系表中记录若干属性列的数据留下来,纵向选择数据,并会去重
        • \(\prod _{\text{ID,name,salary}}(\text{instructor})\)
    • 两个关系的运算
      • Cartesian product \(\times\)
      • join
        • Natural-Join \(\bowtie \)
          • 两个关系先做Cartesian-Product,然后查询得到相同属性列上值相等的记录,最后的结果关系的属性是两个关系属性集合的并集
        • theta join
          • 条件 join
        • Outer Join
          • 保留所有元组,用 NULL 补齐
          • left outer join \(=\bowtie \)
      • 除法运算
        • 查询请求是查找拥有所有账户类型的账户所有人。查询中有“All”这个需求,查询的结果要输出owner,这时候可以用除法。
        • \(\prod _{\text{ Owner, Type(Account)}}\div \text{Account-types}\)
      • 赋值运算 \(\leftarrow \)
        • 优势通过临时关系变量赋值的方法来写关系代数表达式会很方便。
      • 广义投影
        • 广义投影允许在投影列表中使用算术运算和字符串函数等对投影进行扩展。

数据库设计

数据库设计的不同阶段:

  1. 最初需求分析阶段:完整刻画用户的的数据管理需求,交付物是用户需求说明书,可以用图示的方法;
  2. 概念设计阶段:设计者选择数据模型,并根据所选择的概念模型的概念将需求转化为数据库的概念模式,比如我们本章采用的E-R模型,用实体(Entity)和联系(Relationship)的术语来表达数据以及数据和数据之间的关系,还有约束等信息;
  3. 模式精化阶段:最终数据库要落地实现,这个阶段将E-R模型转换为关系模式(一些关系表的定义),并检查关系模式是否存在冗余以及修改异常等问题;
  4. 物理设计和调优:关注查询效率以及系统负载,进一步精化数据库模式设计,比如文件组织形式、索引结构与定义等。

E-R 模型

E-R 模型有三个基本概念:实体集、联系集和属性,此外还有一个相关联的图形表示 E-R 图。

数据库可以描述为:

  • 实体的集合;
  • 实体之间的关系;

Entity

  • 实体(Entity):是现实世界课区别于所有其它对象的事物或对象,例如特定的人、计算机等;
  • 实体具有属性:例如公司有公司名、Id等;
  • 实体集合时具有相同类型,即相同性质的实体的结合,如公司集合;
  • 实体和对象的区别:实体是静态的,和对象不同,没有针对实体的操作(method),只有属性描述。

Relationship Sets

  • 联系指多个实体之间的关联。 例如:学生和教师之间的关系是指导和被指导的关系等;
  • 联系集:相同类型联系的集合。规范地表达:联系集是 \(n\ge 2\) 个实体集上的数学关系。
  • 联系集合也可以有属性,例如教师指导学生需要记录指导时间,比如大家毕业论文时需要填写指导教师每次指导同学的时间,这个时间属性就是联系的属性。
  • 联系的度表达了参与联系的实体集的数目:常见的2元联系,还有3元联系等,大多数是2元联系。

Attributes

  • 实体有由属性集合来表达,来刻画,是实体集合中所有成员都具备的特征,例如教师有ID和姓名等;
  • Domain表达是每一个属性允许取值的范围,值域。
  • 属性可以按照如下方式来划分类型:
    • 简单和复合属性(是否可以拆分成几个子部分):例如身份证号是简单属性,地址是复合属性;
    • 单值和多值属性(可能有多个这样的属性):例如 salary 是单值属性,电话号码是多值属性;
    • 派生属性:例如年龄属性可以由出生日期推导出来。

Constraints

Mapping Cardinality

对于给定的二元联系集合,映射基数是以下四种之一:

  • 1:1(1对1)
  • 1:N(1对多)
  • N:1(多对一)
  • N:M(多对多)
Participation Constraints

参与约束是指实体集合中的实体参与联系时是否全体参与还是部分参与。

Key
  • Super key:实体集合的 super key 指足以区分实体集合中不同实体的属性,同样,联系集合中的联系也要有相应的机制来区分每一个联系。
  • Candidate key 是最小的 super key 。
  • 选择一个 candidate key 作为 primary key 。
  • 联系集合中的联系同样需要区分,联系的primary key由参与联系的实体的primary key组合而成,依赖于联系集的映射基数。

E-R 图

  • 矩形框表示实体集
  • 菱形框表示联系集
    • 可用虚线连出矩形小框,表示联系的属性
    • 基数约束的表达:箭头和不带箭头的横线。箭头所指实体集表示映射的“1”一方,线段对应的实体集表示映射的“多”一方
    • 全参与与部分参与的表达:如果是全参与,连线用双线;如果是部分参与,连线用单线
    • 一名学生只能被一位教师指导,1..1表示基数的最大值和最小值都是1,;一位教师可以知道多名学生,也可以不指导学生,只做研究,用0..*表示
  • 属性在矩形框中罗列(类图)
    • 组合属性 缩进
    • 多值属性 {phone_number}
    • 导出属性 age()
  • primary key用下划线标识
  • E-R图中弱实体的标注:以教材采用的规范为例,联系是双线,弱实体一方的连线是双线

Weak Entity Sets

  • 从实际意义上来讲,弱实体集的存在依赖于一个实际存在的、确定的实体集(称作强实体集)
  • 弱实体没有primary key来区分每个实体,但是有区分符,若要唯一区分弱实体,需要其依赖的强实体的 key +弱实体的区分符

E-R 模型转换为关系模式

  • 实体
    • 强实体转换为一个关系模式,关系名即实体名,如 student、course ,属性即实体属性,key 采用实体的 key
    • 弱实体没有key 但是有 discriminator ,依赖于一个强实体,例如 section 。转换为一个关系,关系名即弱实体名,属性除了自己的属性外,加一个所依赖的强实体的 key ,最终弱实体转换的关系的 key 为强实体的 key+discriminator 组成
  • 属性
    • 组合属性:不为单独的复合属性创建一个属性,如关系模式中 name ,而是将组合属性的每一个部分作为关系模式的一个属性,如 first_name , middle_name 和 last_name 。
    • 多值属性:通常建立一个新的关系模式,如捐赠品实体集,其中属性“捐赠品种类”是一个多值属性,这时可以另外建一张表
      • 一般性地,对于多值属性M,构建一个关系模式R,包含对应M的属性A,以及对应M所在实体集/联系集的主码
    • 联系
      • 如果联系是N:M映射,那么联系转换为一个关系,关系名为联系名,属性为关联的两个实体的 key +联系的属性。
      • 如果联系是 1:N 映射或 N:1 映射,不需要转为一个关系。这时候需将“1”方的实体的key加入到“N”方实体对应的关系属性中,外键约束。
    • 采用E-R模型设计时的一些问题:实体集与联系集的选择?
      • 【指导性原则】:当描述实体间的行为时采用联系集。

E-R 模型的拓展

  • 特化
    • 在实体集内部进行分组的过程。
    • 分析时采用自顶向下的分析过程,从初始实体集到一系列不同层次的实体子集的细化,低层的实体集继承高层实体集的属性。
  • 概化
    • 自底向上的过程将多个实体集共同具有的特征综合成一个较高层次的实体集。
    • 转化为关系的方法:
      • 方法1:构建一个高层实体对应的关系模式,为每一个低层实体构建关系模式,包括高层实体的primary key和本地属性,如person,student和instructor
        • 缺陷:访问一个记录的信息时需要访问两个表
      • 方法2:对每一个实体集构建关系模式,包含所有本地的核继承的属性
        • 缺陷:属性冗余
  • 高层和低层实体
    • 高层实体与低层实体集也称为超类和子类
  • 属性继承
  • 聚集
    • 构建一个关系模式,包含聚集联系的primary key、关联的实体集的primary key以及任意描述的属性。

E-R 关系设计原则

  • 忠于需求规格说明
  • 避免冗余(规范化设计)
  • 保持简单,避免不必要的实体/联系
  • 选择正确的要素:名词表达的对象常常用作实体

关系数据库的设计

不好的关系数据库设计会导致:

  • 信息重复存储
  • 不能恰当表达特定的信息

First Normal Form

  • 一个关系模式R的所有属性的域都是原子的,那么R是1范式。
    • 如果域的元素是不可分的,就称其为原子的。
  • 非原子的值增加了存储的复杂性和数据冗余

Functional Dependencies

  • 函数依赖是精化和建立“好”关系模式的形式化方法,可以解决:
    • 数据冗余问题
    • 修改异常问题
    • Null问题
  • 设 \(R\) 是属性模式,即 \(R=\{A_1,A_2,\cdots ,A_n\}\) ,现在有 \(\alpha \subseteq R \beta \subseteq R\)
  • 函数关系依赖是 \(\alpha \rightarrow \beta \) ,意思是如果 \(\alpha\) 的值确定了,\(\beta\) 的值也就确定了(\(\alpha\) 的值唯一关联 \(\beta\) 的值)。
  • 关系数据库中Key这个约束与函数依赖的关系
    • 如果 \(K\) 是 superkey ,当且仅当\(K \rightarrow R\)  成立
    • 如果 \(K\) 是candidate key,当且仅当 \(K \rightarrow R\) 成立而且不存在 \(\alpha \subset K\) ,且 \(\alpha \rightarrow R\) 成立
    • 函数依赖可以表达 superkey 无法表示的约束
    • 有些约束无法用 key 来表达
    • 当我们发现关系模式中存在 superkey 无法表达的约束时,考虑将这个关系模式分解
  • 用途
    • 检测关系实例在给定的函数依赖集合 \(F\) 下是否是合法的:如果是合法的就称 \(r\)  满足 \(F\) 即判断关系实例是否满足 \(F\)
    • 说明一个合法关系上的约束:如果 \(R\) 的所有关系实例满足函数依赖 \(F\)  ,则表示 \(F\)  在 \(R\) 上成立

Trivial functional Dependencies

  • 函数关系依赖是 \(\alpha \rightarrow \beta \),如果他是平凡的,当且仅当 \(\beta \subseteq \alpha \)

Closure of a Set of Functional Dependencies

 

  • 给定一个函数依赖集合 \(F\) ,能够从 \(F\) 逻辑推断的的所有函数依赖的集合称作 \(F\) 的闭包,记做 \(F^{+}\)

关系数据库的设计目标

  • 这个关系模式符合BCNF(BC范式)且能依赖保持(第一选择)
    • 符合BCNF的条件是
      • 对于 \(F^{+}\) 中所有的函数依赖 \(\alpha \rightarrow \beta ,\alpha , \beta  \subseteq R \) 以下至少一项成立
        • \(\alpha \rightarrow \beta\) 是平凡函数依赖
        • \(\alpha\) 是 \(R\) 的一个 superkey
      • 如果一个函数依赖 \(\alpha \rightarrow \beta\)  导致 \(R\) 不是 BCNF,则分解 \(R\)  为 \(R1=\alpha \cup \beta\)  和 \(R2=(R-(\beta – \alpha))\)
      • BCNF的定义可以直接用来检查一个关系是否属于BCNF,仅需检查给定给函数依赖集合F中的函数依赖是否违反BCNF即可
        • 检验一个非平凡函数依赖\(\alpha \rightarrow \beta\) 是否违反BCNF
          • 计算 \(alpha\)的闭包
          • 检验闭包是否包含的 \(R\)
      • 当无法达到BCNF和依赖保持这个目标时,就考虑“弱”一点的范式:3NF
    • 达不到的话,就满足3NF(3范式)且依赖保持
      • 对于 \(F^{+}\) 中所有的函数依赖 \(\alpha \rightarrow \beta ,\alpha , \beta  \subseteq R \) 以下至少一项成立
        • \(\alpha \rightarrow \beta\) 是平凡函数依赖
        • \(\alpha\) 是 \(R\) 的一个 superkey
        • \(\beta – \alpha\) 中的每个属性都包含 \(R\) 的一个 candidate key 中(每个属性可以包含在不同的candidate key中)
      • 符合3NF的关系模式,数据会存在一定的冗余
      • 判断一个关系是否是3NF,只需检测F中的函数依赖是否破坏了3NF
        • 应用属性闭包计算方法检测每一个函数依赖 \(\alpha \rightarrow \beta\),判断 \(\alpha\) 是否是 super key
        • 如果 \(\alpha\) 不是 super key,则需要检测 \(\beta\) 中的每个属性是否包含在 \(R\) 的 candidate key 中。
      • 3NF的优点是总可以在满足无损并保持依赖的前提下得到3NF模式
      • 缺点是可能不得不用NULL表示数据项间的某些可能有意义的关联,并且存在数据冗余
  • 有损分解和无损分解
    • 如果关系模式R被分解为R1和R2,如果R1和R2自然连接后的结果与R相等,那么这个分解是无损分解
    • 反过来有损分解指的是R1和R2自然连接后产生了多余的元组
  • 对于 \(F\) 找到所有的 \(F^{+}\)
    • 自反:如果 \(\beta \subseteq \alpha \) 则 \(\alpha \rightarrow \beta \)
    • 增补:如果 \(\alpha \rightarrow \beta \)  则 \(\gamma \alpha \rightarrow \gamma \beta \)
    • 传递:如果 \(\alpha \rightarrow \beta . \beta \rightarrow \gamma \) 则 \(\alpha \rightarrow \gamma \)
  • 属性闭包作用
    • 判断一个属性集合 \(\alpha \) 是否是 super key :计算 \(\alpha ^{+} \) ,然后检查 \(\alpha ^{+} \) 是否包含 \(R\) 的所有属性。利用了 Key 与函数依赖的关系。
    • 判断函数依赖是否成立:判断函数依赖 \(\alpha \rightarrow \beta\)  成立,只需要检查是否 \(\beta \subseteq \alpha ^{+}\)
    • 计算 \(F^{+}\)
  • Canonical Cover
    • 函数依赖 \(F\) 的正则覆盖是最小函数依赖集合且和 \(F\) 等价
  • 无关属性
    • 如果去除函数依赖中的一个属性,不改变该函数依赖集的闭包,则称该属性是无关的
    • 如果 \(A\in \alpha\) 且 \(F\) 蕴含 \((F-\{ \alpha \rightarrow \beta \} ) \cup \{(\alpha – A) \rightarrow \beta \}\) 则属性 \(A\) 在 \(\alpha\) 中是无关的
    • 如果 \(A\in \beta\) 且 \(F\) 蕴含 \((F-\{ \alpha \rightarrow \beta \} ) \cup \{\alpha  \rightarrow (\beta -A ) \}\) 则属性 \(A\) 在 \(\beta\) 中是无关的
  • 无损连接分解和有损连接分解
    • \(R1,R2\) 是 \(R\) 的无损分解,但且仅当以下两个函数依赖之一属于 \(F^{+}\)
      • \(R1\cap R2 \rightarrow R1\)
      • \(R1\cap R2 \rightarrow R2\)
  • 依赖保持
    • 令 \(F\) 是关系模式 \(R\) 上的一个函数依赖集, \(R1,R2,\cdots ,Rn\) 为 \(R\) 的一个分解
      • 如果 \((F1\cup F2 \cup \cdots \cup Fn)^{+}=F^{+}\) 则这个分解是依赖保持的

存储和文件结构

物理存储介质的分类

  • 大多数计算机系统存在多种数据存储类型,可以根据访问数据的速度配置不同的存储介质。
  • 根据一下性质进行分类
    • 存储介质的访问速度
    • 成本
    • 可靠性
  • 存储介质的另外一种分类
    • 易失性存储介质:依赖于电力支持,没电了,其中存储的数据就丢失了,例如主存 RAM
    • 非易失性存储介质:存储的数据持久存储,不受电力影响:例如磁盘、磁带、flash memory
  • 代表性的存储介质有:高速缓存、主存、flash Memory(USB driver/手机的存储等)、磁盘、光学存储(CD/DVD)、磁带。按照顺序,存储速度越来越小,成本越来越小。
  • 磁盘是主要的用于持久存储数据的介质,通常这个数据库都存储在磁盘上。为了能够访问数据,系统必须将数据从磁盘移到主存中,完成相应的数据处理后再讲结果写回磁盘。
  • 读写磁盘中的数据是随机读写,相比磁带的顺序读写,读写性能高了很多。

RAID:磁盘阵列

  • 磁盘的每一个盘片(platter)是扁平的圆盘,上下两面覆盖着磁性材料,信息记录在上面,盘片早期是塑料,现在多是金属铝合金或或玻璃制成。
  • 当磁盘被使用时,驱动马达使磁盘高速旋转,盘片的表面逻辑上被划分为过个同心圆,称作磁道,磁道有被划分为扇区,扇区从磁盘读写数据的最小单位有一个读写头位于每个盘片的表面上方,通过翻转磁性物质磁化的方向,读写头将信息磁化存储到扇区中。
  • 所有读写头安装在一个称为磁盘臂的的单独装置上,是机械装置,并且一起移动。
  • 所有盘片的第i个磁道合在一起称为第i个柱面。
  • 为了增大记录的密度,读写头尽可能第靠近磁盘盘面的表面。读写头损坏是磁盘常见的故障,读写头一般浮于盘片表面之上几微米,如果接触表面会刮坏磁盘上的存储介质,破坏数据。
  • 磁盘控制器:是作为计算机系统和实际磁盘驱动器硬件之间的接口,在磁盘驱动单元内部实现,接受高层的读写扇区的命令,然后开始如下的动作,如移动机械臂到正确的磁道、读写数据,为所写的每个扇区附加校验信息。
  • 磁盘通过高速互联通道连接到计算机系统,有大量的通用接口用于连接磁盘到计算机,常用的接口:SATA(很常用),IDE(早期,现在也有用)、SAS(串行SCSI)、SCSI和光纤通道接口(服务器和大型存储的接口)
  • 磁盘的容量计算:磁盘的总容量=记录盘面数*每记录盘面的磁道数*每磁道的盘块数*每盘块的字节数
  • 定位的数据,需要移动到读写头才可以访问
  • 磁盘的性能度量
    • 四个指标:磁盘的容量、访问时间、数据传输速度和可靠性
      • 访问时间=寻道时间+旋转等待时间
      • 磁盘可靠性用平均故障时间MTTF来评估:期望磁盘无故障连续运行的时间,一般3-5年
    • 基于目前的计算机体系结构(冯诺依曼),数据的处理需要在内存中完成。那么大量数据持久在磁盘中存续,就需要在磁盘和内存之间进行传输和交换,以块为单位
      • 块的大小可以定义,不一定是一个扇区对应一个块,通常是磁道上连续的扇区构成,比如512字节到几个KB。块定义的太小,传输频率高,太大,浪费空间(只访问块中的部分信息的话),一般块大小定义为4-16KB
    • 为了提高数据块访问的速度,产生了很多技术:
      • 缓冲技术:磁盘读取的数据暂存在内存缓冲区中以满足将来的访问需要
      • 预读技术:当一个磁盘块被访问时,相同磁道上的数据一起被读到内存缓冲区中。
      • 调度技术:根据磁盘的运转机理,如果需要访问的数据块分布在不同的柱面上,可以针对磁盘的机器臂进行优化,使机械臂按照移动距离最短的顺序发出访问请求,通常使用电梯算法
        • 电梯算法:只向一个方向移动,处理完当前方向所有请求后反向
      • 文件组织技术:为了减少块的访问时间,按照与预期数据访问方式最接近的方式组织磁盘上的块。
      • 非易失性缓冲区:利用non-volatile RAM(例如利用备用电源支持的RAM),当数据库请求写一个数据块到磁盘上时,磁盘控制器将这个数据块写到non-volatile RAM上,然后通知写操作完成,只有当non-volatile RAM满了才会有一个延迟。当non-volatile RAM满了或磁盘访问空闲时间的时候,磁盘控制器将数据块写入到磁盘相应的目标位置,减少了机械臂的移动。异步写的方式。
      • 日志磁盘技术:一种专门用于写顺序日志的磁盘,所有访问都是都是顺序的,根本上消除了寻道时间,一次可以连续读多个数据块。
  • RAID ,通常称作磁盘冗余阵列,简称磁盘阵列。
    •  数据组织技术,用多个较小且廉价的磁盘构成的磁盘系统来代替大而昂贵的磁盘系统。两项重要的技术:冗余和并行。
      • 冗余:通过数据冗余存储提高可靠性,如果一个磁盘出现故障,可以从其他磁盘恢复数据
        • 最直接的方法是镜像的方法,即复制一张磁盘,全盘复制,很昂贵。每一次写分别在两张磁盘上各写一次,如果一张磁盘故障,另一张仍然可访问。
        • 采用镜像技术的磁盘平均故障时间依赖单张磁盘的平均故障时间和平均修复时间。平均数据丢失时间依赖于平均故障时间和平均修复时间。
      • 并行:通过并行技术提高访问性能,并行访问多个磁盘。
        • 通过将数据拆分至多个磁盘上,同时利用多张磁盘的读取接口提高数据传输效率。在多个磁盘上Striping(条带化)数据访问来改善传输率。
        • 常用拆分数据的方式:块级别的条带化。假设 \(n\) 个磁盘做RAID,那么文件的i个数据块存储放在 \((i\; mod\; n) + 1\) 磁盘上,如果需要访问的数据分布在不同的磁盘上,这时并行访问这些磁盘。
    • 在实际应用中,根据数据访问的性质不同,比如以查询为主还是以修改为主来选用不同的RAID level,成本和性能有差异。
      • RAID级别的含义:通过条带与校验位结合,在成本和性能之间权衡,以较低成本提供数据冗余的方案。
        • RAID 0:块级拆分但没有冗余。
        • RAID 1:块级拆分的镜像磁盘。
        • RAID 2:Memory-Style Error-Correcting-Codes (ECC) with bit striping.
        • RAID 3:在位级别拆分,使用校验信息来检测数读扇区是否出错,需要单独的磁盘来存储校验信息。
        • RAID 4:Block-Interleaved Parity; uses block-level striping, and keeps a parity block on a separate disk for corresponding blocks from \(N\)  other disks.
        • RAID 5:采用了块级拆分且校验信息分布式存储,即数据和其他的数据的校验信息可以存储在同一个磁盘上,但是该数据自己的校验信息不能和自己存储在用一块磁盘上,和RAID3不同,不需要单独的磁盘来存储校验信息。
        • RAID 6:在RAID 5的基础上进行了改进,采用双校验,可靠性更高,但成本也更高,应用不广泛。
      • 有些厂商用RAID1+0或RAID10 表示具有块拆分的镜像,RAID1指无拆分的镜像
    • RAID level选择从以下几个方面考虑:
      • 成本
      • 性能
      • 磁盘故障时的性能
      • 磁盘故障后数据重建的性能
    • RAID 0用于安全性不是很高但对数据读性能要求高的高性能应用。RAID2~4几乎不用。常见的是RAID 1(有些厂商称作1+0)和RAID5之间挑选。
      • RAID 1的【】性能比RAID 5的好。但采用RAID5时,每写一个块,需要两次块读(读校验+读之前得到校验的块)和两次块写操作(写新的校验和新的块),对于写密集型应用,比如数据修改操作较多的应用,RAID5的写延迟高,适用于低修改率的一些应用。
      • RAID 1更适用于写密集型的应用。RAID 1比RAID 5 的存储成本高。因为镜像需要额外的存储,需要额外的资金投入到存储上。
  • 热交换:系统运行过程中不需要关闭电源就可以替换磁盘。
  • 磁带的特点
    • 价格便宜
    • 存储量大
    • 访问速度慢
    • 常用于备份

File Organization

  • 一个数据库有多个表,被映射到多个不同的文件中,这些文件由底层的文件系统来负责维护,持久存储在磁盘上。
    • 数据库映射为多个文件,每个文件是多个记录的序列,这些记录映射到磁盘块上,可以理解为file={blocks},是磁盘块的集合。块是存储分配和数据传输的基本单位
    • 每个记录是一系列field的序列,具体到某个数据集,这些field有具体的数据类型和具体的数据,要占存储空间。
    • 将数据库映射为文件的方法
      • 文件中每个记录的大小固定
      • 每个文件只存储特定类型的记录
      • 不同的关系用不同的文件
  • Fixed-Length Records
    • 删除记录会有问题,这时删除记录得到的空闲空间要由其他记录来填充,或者加删除标记,忽略这个记录。
  • Variable-Length Records
    • 如何表示变长记录是关键。表示一个变长记录包括两个部分:
      • 开始部分是定长属性的数据,如日期、数值型、定长字符串。
      • 第二部分是变长属性的数据,如变长字符串。
    •  有一个字节(实际只用4位,称作null bitmap)用来说明一个记录某个属性是否存在null值
  • Slotted-Page Structure
    • 每个块的头部记录以下信息:记录个数、块的的free space的末端地址、每个记录的位置和大小
    • 当插入一条记录时,从空间空间的末端开始,插入数据,然后在块的头部记录新插入的记录的开始位置和大小
    • 当删除记录时,释放记录的存储空间,修改块头部该记录的信息,如将大小修改为-1,然后左边的记录向右移动填补空间,使得左右的记录仍然紧连,同时修改块头开始的记录个数以及free space的末端地址。
  • Organization of Records in Files
    • 堆文件组织:记录可以放置在文件中任意的空闲存储空间中,数据记录无序存放。
    • 顺序文件组织:记录按照一个属性的值有序存放(search key是查询时关注的属性)
    • hash文件:根据一个hash函数对每个记录的一些属性值进行计算,得到的值对应到数据记录应该存储的数据块

Data-Dictionary Storage

  • 关于关系的数据称为“元数据”。关于关系的关系模式和其他元数据存储在称作“数据字典”或系统目录的结构中。
  • 系统必须存储的信息包括
    • 关于关系的信息:关系的名字、每个关系的属性名和类型、在数据库上定义的视图和视图的定义、完整性约束
    • 用户和审计信息
    • 统计数据和描述数据
    • 物理文件组织信息
    • 索引信息
  • 数据库系统的一个设计目标是尽量减少磁盘和内存之间传输的块数,减少磁盘访问次数的常见方法是在内存中保留尽可能多的数据块,这样就不用反复内存外存间交换数据,从而减少I/O。但是内存中保留所有的块是不可能的,所以需要管理内存中用于存储块的可用空间的分配。
  • 块:磁盘空间固定大小的存储单元,数据存储分配和传输的单位。
  • Buffer:内存中用于存储磁盘块拷贝的部分空间。
  • Buffer manager:负责在内存中分配buffe的子系统
    • Buffer manager的存储管理技术:当buffer中没有空间时,需要将一些块移出buffer。
      • buffer替换策略:类似OS的LRU
        • 改进LRU的策略:
          • 立即丢掉策略
          • MRU策略:Most recently used strategy,
          • Buffer manager 可以使用一个查询请求引用特定关系的概率这样的统计信息来制定更优化的策略。
      • Pinned block:为了能够使数据库系统从系统崩溃中恢复,限制一些块写回磁盘,这些块称作被定住的块。
      • 块的强制写出:为了保证数据的持久性存储,需要强制将数据块写回磁盘。

Indexing and Hashing

  • Search key:一个关系中一个或多个属性,常用于查找文件中的数据记录。
  • Index文件:一个特殊的文件,由一些记录构成,称作索引项(index entries),包含两个部分
    • search key
    • pointer,指向数据文件中search key对应的数据记录
  • Index的种类
    • 顺序索引:基于记录中某个属性值的顺序建立的索引
      • 主索引Primary index(聚集索引clustering index)
        • 主索引指的是索引项中的search key是数据文件中排序的属性,而且顺序与数据文件一致
      • 辅助索引Secondary index(非聚集索引non-clustering index)
        • 当数据文件中的记录顺序与索引文件中索引项的顺序不一致时,这个索引是辅助索引
      • 稠密索引 Dense index :索引文件中search key所有取值都出现在索引文件中
      • 稀疏索引Sparse Index:索引项中只包含search key的部分取值。
      • 稀疏索引的空间开销比稠密索引小,定位数据比稠密索引慢。将两种索引结合起来形成多级索引Multilevel Index 
    • hash索引:根据记录的查找键的值,使用一个函数计算得到的函数值作为磁盘块的地址,对记录进行存储和访问,通常用桶作为基本的存储单位,一个桶可以存放多个记录

B+ Tree Index Files

  • B+树是一种最广泛使用的索引文件结构之一,采用平衡树结构,是在数据插入和删除的情况下仍能保持执行效率的结构,只需很小的、局部的变化自动重组文件。
  • B+树的缺点:会有插入数据和删除数据的额外开销,增加空间开销。
  • 结构
    • 从树根到树叶的每一条路径长度相等
    • Each node that is not a root or a leaf has between \(\left \lceil \frac{n}{2} \right \rceil\) and \(n\) children.
    • A leaf node has between \(\left \lceil \frac{n-1}{2} \right \rceil\) and \(n-1\) values
    • Special cases:If the root is a leaf (that is, there are no other nodes in the tree), it can have between \(0\) and \((n–1)\) values.
    • leaf nodes
      • Pi指向具有 search-key值Ki的文件记录
      • 叶子节点的指针Pn有特殊作用,每个叶子节点的Pn指针指向下一个叶子节点,将所有的叶子节点按照search-key值的顺序链起来,提高对文件的顺序处理效率
    • non-leaf nodes
      • B+树非叶子结点(也称内部结点)形成叶子结点上的多级稀疏索引
      • fan-out:结点的指针数

Hash-Based Index Files

  • 顺序文件组织的一个缺点是必须通过访问索引来定位数据,或者使用二分法来搜索,导致过多的I/O
  • bucket桶:表示存储一个或多个记录的存储单位。通常一个桶就是一个磁盘块,但也可以小于或大于一个磁盘块
  • K表示Search-key的集合,另B表示所有桶的地址,hash函数h是从K到B的一个映射

Bitmap Indices

  • 位图索引是一种特殊类型的索引,通常用于多个key上的查询应用,常用于取值较少的属性上

Query Processing

  • 查询处理指的是从数据库中提取数据所涉及的一系列活动,包括以下几个步骤:
    • 将SQL表达的查询转换成可以直接访问文件系统的表达,高级语言代码
    • 查询优化
    • 执行查询
  • 查询处理的框架,包括三个部分:语法解析和翻译、优化以及执行
  • 查询代价可以通过该查询对各种资源的使用情况来度量,如磁盘访问、CPU时间,甚至网络传输时间(分布式数据库会考虑网络因素)
    • 磁盘访问,通常在大型数据库系统中是最主要的代价
      • 查找次数(寻道的数量)×平均查找时间
      • 读数据块的个数×平均读数据块的代价
      • 写数据块的个数×平均写数据块的代价
    • basic algorithm
      • \(t_T\) – time to transfer one block
      • \(t_S\) – time for one seek
      • Algorithm A1 (linear search)
        • 应用线性扫描算法时可以不考虑选择条件、文件中记录的顺序以及是否有索引。
        • Cost estimate = \(b_r\) block transfers + 1 seek( \(br_ \times  t_T + t_S\) )
        • average cost = (\(br /2\)) block transfers + 1 seek
      • A1’ (binary search).
        • Cost estimate = \(\left \lceil log_2(b_r) \right \rceil \times (t_T+t_S)\)
      • A2 (primary index, equality on key).
        • 总代价=访问数据索引块的代价+访问数据块的代价
        • Cost estimate = \(h_i\times (t_T+t_S)+(t_T+t_S)\) \(h_i\) 是B+树的高度
      • A3 (primary index, equality on nonkey)
        • Cost estimate = \(h_i\times (t_T+t_S)+b\times t_T+t_S\) \(h_i\) 是B+树的高度
      • A4 (secondary index, equality).
        • 如果search-key是candidate key,查询结果返回一个记录
          • Cost estimate =\(h_i\times (t_T+t_S)+ t_T+t_S\) \(h_i\) 是B+树的高度
        • 如果search-key不是candidate key,查询结果返回多个记录,且这些记录不连续存储
          • Cost estimate =\((h_i+n)\times (t_T+t_S)+ t_T+t_S\) \(h_i\) 是B+树的高度,有 \(n\)个满足条件的记录
      • A5 (primary index, comparison).
        • 对于 \(\delta _{A\ge V}(r)\),使用 index 找到第一个符合要求的,顺序扫描
        • 对于 \(\delta _{A\le V}(r)\),不需要使用 index,只需从文件头开始扫描直到\(A> v\) 的记录出现
      • A6 (secondary index, comparison).
        • 对于 \(\delta _{A\ge V}(r)\),使用 index 找到第一个符合要求的,顺序扫描
        • 对于 \(\delta _{A\le V}(r)\),只需要访问索引的叶子结点,扫描叶子结点,直到\(A> v\) 的记录出现
      • A7 (conjunctive selection using one index).
        • 首先判断是否存某个简单条件中的某个属性上的存储路径,若存在,则选择A2~A6之一的算法检索满足该条件的记录,最后检查是否满足要求
      • A8 (conjunctive selection using multiple-key index)
        • 应用合适的组合索引(在多个属性上建立的一个索引)
      • A9 (conjunctive selection by intersection of identifiers).
        • 查询条件涉及到的属性上要求有索引,利用这个索引查找满足相应条件的记录的指针,进行交集,然后找到相应的数据记录
      • A10 (disjunctive selection by union of identifiers).
        • 如果所有的析取选择条件上均有索引,利用这个索引查找满足相应条件的记录的指针,进行并集,然后找到相应的数据记录
  • sorting
    • 数据库排序采用的是外部排序算法,典型的是external sort-merge
      • 外部排序归并分两个阶段:建立排好序的归并段(run)阶段和归并阶段
        • 在建立排好序的归并阶段,要读入关系(待排序的关系表)的每一个块并写出,因此块传输为 \(b_r+b_r=2b_r\)
        • 在归并阶段传输的数据块数与归并的趟数有关。归并的次数(趟数)计算。每一趟归并,归并段数减少为上一次的\(1/(M-1)\),因此归并的次数为 \(\left \lceil log_{M-1}(b_r/M) \right \rceil \)
        • 最后一趟不计算写代价,即最后的排序结果不写回磁盘,只需传输\(b_r\)块
        • 因此,总的传输数据块数为: \(2b_r \left \lceil log_{\left \lfloor M/b_b \right \rfloor -1}(b_r/M) \right \rceil +b_r\)
      • 最后,总的seek次数为\(2 \left \lceil (b_r/M) \right \rceil + \left \lceil (b_r/b_b) \right \rceil (2 \left \lceil log_{\left \lfloor M/b_b \right \rfloor -1}(b_r/M) \right \rceil -1)\)
        • Buffer size: \(b_b\)
  • Join
    • 关系 \(r\) 和关系 \(s\) 进行 natural join 计算
      • 假设 \(r\) 有 \(n_r\) 个记录,占用磁盘存储空间 \(b_r\) 个块; \(s\) 有 \(n_s\) 个记录,占用磁盘存储空间 \(b_s\) 个块。
      • Nested-Loop Join
        • 通过二重循环实现
        • 传输块数为 \(b_r+n_r\times b_s\)
        • Seek次数为 \(n_r+b_r\)
      • Block Nested-Loop Join
        • 块嵌套循环join实现算法
        • 最坏情况
          • 传输块数为 \(b_r+b_r\times b_s\)
          • Seek次数为 \(b_r+b_r\)
        • 最好情况
          • 内存能够容纳内层关系的所有数据块
          • 传输块数为 \(b_r+ b_s\)
          • seek次数为 \(2\)
        • 优化改进
          • 读入外层关系的数据块时,可以按照内存大小 \(M\) (设内存大小为 \(M\) 个块),一次读入外层关系的 \(M-2\) 个数据块,然后读内层关系的每一块与 \(M-2\) 个数据块的数据进行 join 条件的匹配计算
          • 传输块数为 \(\left \lceil \frac{b_r}{M-2} \right \rceil \times b_s+b_r\)
          • seek 次数为 \(2 \left \lceil \frac{b_r}{M-2} \right \rceil \)
      • Indexed Nested-Loop Join
        • 如果内层关系上建立了索引,索引项是join的属性,可以将之前的文件扫描替换为index扫描
        • join 的代价 \(b_r\times t_T+b_r \times t_s+n_r\times c\)
        • 传输块数为 \(b_r\)
        • seek次数为 \(b_r\)
      • Sort-Merge-Join
        • 设 \(b_b\) 是为每个关系分配的缓冲块数
        • 传输块数为 \(b_r+b_s\)
        • seek 次数为 \(\left \lceil \frac{b_r}{b_b} \right \rceil + \left \lceil \frac{b_s}{b_b} \right \rceil \)
      • Hash-Join
        • 如果没有递归划分
          • 传输块数为 \(2\times (b_r+b_s)\)
          • seek 次数为 \(2(\left \lceil \frac{b_r}{b_b} \right \rceil + \left \lceil \frac{b_s}{b_b} \right \rceil )\)
        • 如果有递归划分
          • 传输块数为 \(2\left \lceil log_{M/b_b-1}(b_s/M) \right \rceil (b_r+b_s)+b_r+b_s\)
          • seek 次数为 \(2(\left \lceil \frac{b_r}{b_b} \right \rceil + \left \lceil \frac{b_s}{b_b} \right \rceil ) \left \lceil log_{M/b_b-1}(b_s/M) \right \rceil  \)
  • 表达式的计算方法
    • 可以将每一种计算的结果物化到一个临时关系中备用,但是需要建立临时关系,而且这个关系必须写到磁盘上,产生I/O代价
      • Materialization
        • 将表达式计算表达为一个运算符树,采用物化的方式时,自底向上运算,每一个计算的结果存储在临时关系中,高层使用临时关系进行计算直到树的根结点
        • 物化方法的计算代价不仅仅是所涉及的计算的代价的总和,而且还要加上将中间结果写到临时关系的代价
        • 双buffer技术的应用:一个用于连续执行算法,另一个用于写出结果,提高算法执行效率
    • 用流水线的方法,同时计算多个运算,将运算结果传递给下一个运算,不必保存临时关系
      • Pipelining
        • join产生的一个结果记录时,马上输入给投影操作去处理,避免存储中间结果,直接得到最终结果的记录
        • 流水线方式比物化方法的优点在于不需要建立临时关系,减少了读写临时关系的代价和查询代价
        • 流水线的实现有两种方法:
          • 需求驱动demand driven
            • 系统不断地向位于流水线顶端的操作发出需要记录的请求,每当一个操作收到需要记录的请求,就计算下一个记录并返回。系统需要记录目前为止已经返回了哪些记录
          • 生产者驱动
            • 采用iterator算子来实现

事务管理

  • 数据库系统通常会被多个用户或进程访问。
  • 当多个用户或进程并发访问数据库时,当系统出现故障时(天灾人祸)会导致数据库中刚出现不一致的数据或错误的数据,这样用户看到的数据就不正确。
  • 因此,需要数据库具有并发控制机制和故障恢复机制。
  • 达到的目标:
    • 高事务吞吐率,快速响应;
    • 提高系统资源的利用率;
    • 系统故障时保护数据,系统恢复时保持数据一致性。
  • A transaction is a unit of program execution that accesses and  possibly updates various data items.  (事务是构成单个逻辑工作单元的操作集合)
  • 在事务执行期间数据库可能不一致,但是一旦事务执行完毕,数据库一定是一致的
  • 事务的四个基本特征:ACID特征(重点)
    • 原子性:执行事务的所有操作或者全部执行成功,或者一条指令都不执行。
    • 一致性:隔离执行的一个事物保持数据库的一致性。即数据是正确的,符合应用逻辑的。
    • 隔离性:这个并发执行的事务感觉不到其他事务的执行。自己执行自己的逻辑。
    • 持久性:当事务成功执行后,他对数据库的修改必须持久存储,即使系统出现故障也不会丢失。
  • 和事务管理相关的子系统(从DBMS系统实现的视角来看):查询处理器、事务管理器、日志管理器、恢复管理器。涉及到的数据包括具体数据和日志数据。
  • 事务必须处于五个状态之一
    • 活动状态(Active):初始状态,事务执行时的状态,执行对数据库的读写操作
    • 部分提交状态(Partially committed ):事务的最后一个语句执行之后进入部分提交状态,数据在缓冲区中
    • 失效状态(Failed):正常的执行无法继续后的状态
    • 中止状态(Aborted):事务回滚且数据库恢复到事务执行之前的状态
    • 提交状态(Committed):事务成功执行后的状态
    • Active->Partially committed
    • Active->Failed
    • Partially committed->Failed
    • Failed->Aborted(事务进入失效状态,这样的事务必须必须rollback,系统进入中止状态。此刻系统有两种选择:rollback;kill
    • Partially committed->Committed
  • Concurrent Executions
    • 多个事务并发执行时,如果是对数据进行更新,倘若没有形影的控制机制,会引起数据一致性问题。
      • 如果强制多个事务串行执行,管理简单,但是系统的资源利用率和效率将会大大降低。
      • 在时间维度上充分调度计算机的资源,多个事务同时运行时应用不同的资源,充分利用计算机的资源,不让计算机闲着
  • Schedules
    • 章调度指并发执行的事务的指令执行顺序,表示指令在系统中执行的 chronological 序。
    • 针对一组事务的调度必须包含这些事务的全部指令,并且保持事务中指令原来的顺序,即不能改变事务指令的顺序。如果破坏了事务指令的顺序,就破坏了事务的逻辑。
      • 一个事务成功执行后,最后要有一条commit语句
      • 如果事务没有成功执行,最后要有一条abort语句
  • Serializability(串行化)
    • 如果一个调度在某种意义上等价于一个串行调度,那么这个调度称作可串行化调度。我们重点关注冲突可串行化的等价方式。
  • Conflicting Instructions(冲突指令)
    • 如果两个指令是冲突的,当且仅当两个指令是连续的(时间上),且都访问数据项 \(Q\),且至少一条指令是针对 \(Q\) 的 write 指令。
    • 如果一个调度 \(S\) 通过一系列非冲突指令的交换变换为调度 \(S’\) ,那么可以说调度 \(S\) 和调度 \(S’\) 是冲突等价的。
    • 如果一个调度冲突等价与一个串行调度,那么这个调度是冲突可串行化的。
  • Precedence graph(优先图)
    • 是一个有向图,顶点集是所有参与调度的事务,边集是满足下列条件之一的边 \(T_i  \rightarrow T_j\)  组成:
      • 在 \(T_j\)  执行 read(Q) 之前, \(T_i\)  执行 write(Q) ;
      • 在 \(T_j\)  执行 write(Q) 之前, \(T_i\)  执行 read(Q) ;
      • 在 \(T_j\)  执行 write(Q) 之前, \(T_i\)  执行 write(Q) ;
    • 一个调度是冲突可串行化的,当且仅当优先图有环。无环则是冲突可串行化的。
  • Recoverable Schedules 可恢复调度
    • 在事务并发执行的过程中,事务发生故障读调度会产生影响。 如果事务发生故障,进入fail状态,必须撤销这个事务的影响确保原子性,事务rollback。
    • 在允许并发执行的系统中,如果 \(T_1\) 事务发生故障被撤销,依赖 \(T_1\) 的任何事务也要中止
    • 概念:一个可恢复调度满足:对于每对事务 \(T_i\) 和 \(T_j\)  ,如果 \(T_j\)  读取了由 \(T_i\)  所写的数据项,则 \(T_i\)  要先于 \(T_j\) 提交。
  • Cascading Rollbacks(级联回滚)
    • 一个事务的失效导致一系列并发执行的事务回滚的现象
  • Cascadeless schedules无级联调度
    • 级联回滚导致撤销大量事务的工作,因此需要加以限制,避免这种现象的发生。因此调度应为无级联调度。
    • 无级联调度:对于每对事务 \(T_i\) 和 \(T_j\)   , 如果 \(T_j\)  读取 \(T_i\)  之前修改后的数据,那么 \(T_i\)  要在 \(T_j\) 这个读数据操作之前提交。
  • Weak Levels of Consistency
    • 对于某些应用,希望保持较弱的数据一致性,允许调度不一定可串行化。例如,涉及统计计算的事务,统计结果数据是近似值,不要求精确结果时,不要求强一致性。这样可以提高系统的性能
  • 事务隔离性级别有以下规定:
    • 串行化:默认级别
    • 可重复读:只允许读已提交的数据,而且一个事务两次读取一个数据项期间,其他事务不得更新该数据,但该事务不要求与其他事务可串行。
    • 已提交读:只允许读取已提交的数据,但不要求可重复读。
    • 未提交读:允许读未提交的数据。SQL允许的最低一致性级别。
  • DBMS应提供并发事务的控制机制。保证调度室重复可串行化或视图可串行化,而且是可恢复的,最好是无级联的。
  • 常用的并发控制机制有:锁机制、时间戳、多版本和快照隔离。
  • SQL标准没有定义事务开始的语句,具体的DBMS自己来定义
    • 。结束语句都是需要用户显式地给出,COMMIT或ROLLBACK。
      • COMMIT:结束当前的事务,开始新的
      • ROLLBACK:当前事务中止,数据恢复到执行之前的状态。
  • 如果没有显式地指令说明事务开始,如何知道事务开始执行了呢?如何区分各个事务呢?
    • 每个SQL是一个事务
    • 直到用户执行COMMIT或ROLLBACK为止算一个事务

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 53,556

Categories

Archive

Comments