哈工大数据库系统MOOC笔记:(一)基本知识与关系模型

写在前面:

本文为哈尔滨工业大学战德臣老师《数据库系统》系列课程MOOC的听课记录,原版视频链接为:https://next.xuetangx.com/course/HIT08091000101/4227172

第一讲 初步认识数据库系统

数据库就是相互有关联关系的数据的集合,起源于规范化“表”的处理

表:以按行按列形式组织及展现的数据,包含的要素:表名、表标题(格式)、表内容(值)。表名和表标题合称(关系)模式,整张表又可称为关系。

每一行内容叫行/元组/记录,每一列内容叫列/字段/属性数据项。在一列中,分为列名和列值

那么数据库就可以重新定义为相互之间又关联关系的表的集合

数据库系统(工作环境)=数据库(DB)+数据库管理系统(DBMS)+数据库应用(DBAP)+数据库管理员(DBA)+计算机基本系统

从用户角度看数据库管理系统的功能:

  1. 数据库定义:定义数据库中表的名称、标题等。DBMS给用户提供一套数据定义语言(DDL:data defibition language)。
  2. 数据库操纵:向数据库的表中增加/删除/更新数据以及对数据进行查询、检索、统计等。DBMS给用户提供一套数据操纵语言(DML)。
  3. 数据库控制:控制数据中数据的使用权限。DBMS给用户提供一套数据控制语言(DCL)。
  4. 数据库维护:转储/恢复/重组/性能监测/分析等。DBMS提供一系列维护数据库的功能程序给用户(这里一般是DBA)。

数据库语言:使用者可通过数据库语言利用DBMS操作数据库,包括上面的DDL, DML, DCL,三者联合起来就是结构化的数据库语言,即SQL语言。

一般一条数据库语言的语句相当于高级语言的一个或多个循环,同时数据库语言可以嵌入到高级语言(宿主语言)中使用。

从系统角度看数据库管理系统的功能:

DBMS为了完成DB管理,在后台运行着一系列程序:语言编译器、查询优化(执行引擎)与查询实现(基本命令的不同执行算法)、数据存储与索引、通信控制、事务管理、故障恢复、安全性控制、完整性控制、数据字典管理、应用程序接口等

典型的DBMS:Oracle、DB2、Sybase、MS SQL Server、MS Access、MS Foxpro等


第二讲 数据库系统的结构抽象与演变

数据系统的标准结构

1)数据库系统的分层抽象

DBMS管理数据的三个层次:

  1. 外部层次/用户层次:某一用户只能看到全局数据中的某一部分
  2. 概念层次/逻辑层次:从全局角度理解/管理的数据,含相应的关联约束
  3. 内部层次/物理层次:存储在介质上的数据,含存储路径、存储方式、索引方式。

2)数据(视图)与模式

视图View/数据Data:某一种表现形式下表现出来的数据库种的数据

模式Schema:对数据库种数据所进行的一种结构性的描述

3)三级模式

对应DBMS管理数据的三个层次,相应有三个模式:

  1. 外模式/用户模式:某一用户能看到与处理的数据的结构描述
  2. 概念模式/全局模式:从全局角度理解/管理的数据的结构描述,含相应的关联约束,体现数据之间的内在本质联系
  3. 内模式/物理模式:存储在介质上的数据的结构描述,含存储路径、存储方式、索引方式等

当然对应的也有三级视图,命名方法通模式。

特别的,如果只说模式,一般指全局模式;但如果只说视图,一般指直接面向用户的外视图。

4)两层映像

  1. 外模式到概念模式:E-C 映像(External-Conceptual Mapping)。将外模式映射为概念模式,从而支持实现数据概念视图向外部视图的转换,便于用户观察和使用
  2. 概念模式到内模式:C-I 映像(Conceptual-Internal Mapping)。将概念模式映射为内模式,从而支持实现数据概念视图向内部视图的转换,便于计算机进行存储和处理

5)数据库系统的标准结构

image-20200608164216305

6)两个独立性

为什么要分层抽象呢?主要是分层独立后,系统便于维护:

  1. 逻辑数据独立性:当概念模式变化时,可以不改变外部模式(只需改变E-C映射),从而无需改变应用程序
  2. 物理数据独立性:当内部模式变化时,可以不改变概念模式(只需改变C-I映射),从而不改变外部模式

数据模型

数据模型是规定模式统一描述方式的模型,包括:数据结构、操作和约束

数据模型是对模式本身结构的抽象,模式是对数据本身结构形式的抽象

三大经典数据模型:

  1. 关系模型:表的形式组织数据
  2. 层次模型:树的形式组织数据
  3. 网状模型:图的形式组织数据

层次模型和网状模型都有实体型和系型。实体型之间用系型连接。

数据库系统的演变与发展

几个重大发展:

  1. 从文件系统到数据库:好处是由DBMS统一存取、维护数据组织形式及语义,可较强地独立于应用程序
  2. 由层次模型数据库、网状模型数据库到关系数据库:层次和网状模型结构描述复杂,不能有效支持记录集合的操作。关系数据库消除了指针因而结构简单,不依赖于路径信息或过程信息,有效支持记录集合的操作
  3. 由关系数据库到对象关系数据库、面向对象数据库:关系数据库需要按行按列组织数据,数据项不可再分;对象关系数据库可有复合属性和多值属性。面向对象数据库还引入了OO技术,支持复杂的数据类型,支持面向对象的一些特性:类、继承、封装、多态等。
  4. 由多种多样的数据库到多数据库开放式互连:多种数据库通过统一的接口面向不同的应用程序,接口叫做开放数据互连(Open Database Connection, ODBC)
  5. 由普通数据库到与各种先进技术结合所形成的新型数据库

第三讲 关系模型之基本概念

什么是关系模型?

一个关系就是一个表

关系模型就是处理表的,由三部分组成:

  1. 描述DB各种数据的基本结构形式(表/关系)
  2. 描述表与表之间所可能发生的各种操作(关系运算)
  3. 描述这些操作所应遵循的约束条件(完整性约束)

关系模型的三个要素:

  1. 基本结构:关系/表

  2. 基本操作:关系操作

    基本关系操作:并,差,乘积,选择,投影

    扩展关系操作:交,连接,除

  3. 完整性约束:实体完整性、参照完整性和用户自定义的完整性

关系运算:关系代数和关系演算。关系演算:元组演算和域演算

关系代数:基于集合的运算

操作对象是集合,是一次一集合的操作,非关系型的数据操作是一次一记录的操作

元组演算:基于逻辑的运算

域演算:基于示例的运算

数学语言 计算机语言
关系代数 基于关系代数设计的数据库语言(ISBL)
元组演算 基于元组演算演算设计的数据库语言(Ingres系统的QUEL)
域演算 QBE:Query By Example

什么是关系?

首先定义每一列元素的取值集合,称为“域Domain”,集合种元素的个数叫基数

那么所有元组可能的取值范围就是域的笛卡尔积

D1×D2×...×Dn={(d1,d2,...,dn)diDi,i=1,...,n}D_1 \times D_2 \times ... \times D_n = \{(d_1,d_2,...,d_n)|d_i\in D_i, i=1,...,n\}

d_i是元组的一个分量

但是实际取值一般不是所有值,而是笛卡尔积的子集,所以定义了关系Relation。也就是笛卡尔积中有意义的元组被取出称为关系。由于关系的不同列可能来自于同一个域,为了区分,关系中每个列会单独取一个列名(属性名)

关系的结构可以用

R(A1:D1,A2:D2,...,An:Dn)R(A_1:D_1,A_2:D_2,...,A_n:D_n)

表示,也可简记为

R(A1,A2,...,An)R(A_1,A_2,...,A_n)

这种描述又称为关系模式Schema或表标题head,同一关系模式下可有很多关系,关系模式只是关系的结构。

R是关系的名字,A_i是属性,D_i是属性对应的域,n是关系的度或目,关系中元组的数目称为关系的基数

关系模式中属性向域的映像在很多DBMS中一般直接说明为属性的类型、长度等,如Student(S# char(8), Sname char(10), Sage integer)

关系的特性:

  1. 列是同质:每一列的分量来自于同一个域
  2. 不同列可来源于同一域,可用属性名区分
  3. 关系和行列位置无关,有列位置互换性和行位置互换性(就像python里字典只依赖于键一样)
  4. 关系由集合定义,关系的任意两个元组不能完全相同。但是现实生活中,表Table就不一定遵循这个特性(这是关系和表的区别)
  5. 需满足关系第一范式:属性不可再分。符合第一范式可称Table,不满足第一范式叫Not Table

关系的几个重要概念:

  1. 候选码/候选键:关系中的一个属性组,其值能唯一标识一个元组,若从该属性组中去掉任何一个属性,它就不具有这一性质,这样的属性组叫候选码
  2. 主码/主键:当有多个候选码,可选定一个作为主码。DBMS以主码为主要线索管理关系中的各个元组
  3. 主属性和非主属性:包含在任何一个候选码中的属性称为主属性,其他属性叫非主属性。如果所有属性构成了候选码,就叫全码All-Key
  4. 外码/外键:关系R中的一个属性组,它不是R的候选码,但它与另一个关系S的候选码相对应,则称这个属性组为R的外码或外键。两个关系通常靠外码连接起来。

关系模型的完整性:

  1. 实体完整性:关系的主码中的属性值不能为空值。空值就是不知道、不存在或无意义的值
  2. 参照完整性:如果关系R1的外码Fk域关系R2的主码Pk相对应,则D1中的每一个元组的Fk值或者等于R2中某个元组的Pk值,或者为空值
  3. 用户自定义完整性:用户针对具体的应用环境定义的完整性约束条件

实体完整性和参照完整性由DBMS系统自动支持,用户自定义完整性可以由DBMS提供的机制自行定义


第四讲 关系模型之关系代数

什么是关系代数

关系代数的基本思维:以集合为中心

关系代数操作可分为两类:

  1. 集合操作:并、交、差、笛卡尔积
  2. 纯关系操作:投影、选择、连接、除

五种基本操作:并,差,乘积,选择,投影

某些关系代数操作,如并、差、交等,需满足并相容性

并相容性定义为:假设R(A1,A2,…,An),S(B1,B2,…,Bm),若R和S满足n=m且Domain(Ai)=Domain(Bi),则满足并相容性。

关系代数操作

基本操作:

  1. 假设关系R和S并相容,则它们的并运算结果也是一个关系,记作RUS,它由或者出现在R中,或者出现在S中的元组构成

    R\cup S = \{t|t\in R \or t \in S\}
  2. 假设关系R和S并相容,则它们的差运算结果也是一个关系,记作R-S,它由出现在R中但不出现在S中的元组构成

    R- S = \{t|t\in R \and t \notin S\}
  3. 广义笛卡尔积

    关系R和关系S的广义笛卡尔积也是一个关系,由关系R中的元组与关系S的元组进行所有可能的拼接构成。由于行列位置无关性,R乘S和S乘R是相同的

    R\times S = \{|\in R \and \in S\}
  4. 选择

    给定一个关系R,同时给定一个选择条件con,选择运算结果也是一个关系,由从关系R中选择出满足条件con的元组构成

    \sigma_{con}(R)=\{t|t \in R \and con(t)=True\}

    特别的,条件运算符的优先次序从高到低是:括弧>比较运算符>非>交>并

  5. 投影

    给定一个关系R,投影运算结果也是一个关系,由从关系R中选出属性包含在A中的列构成:

    ΠAi1,Ai2,...,Aik(R)={<t[Ai1],t[Ai2],...,t[Aik]>tR}\Pi _{A_{i1},A_{i2},...,A_{ik}}(R)=\{<t[A_{i1}],t[A_{i2}],...,t[A_{ik}]>|t \in R\}

    说白了选择是选行,投影是选列。若投影后有重复元组,应去掉。

扩展操作:

  1. 假设关系R和S并相容,则它们的交运算结果也是一个关系,它由同时出现在R中和S中的元组构成

    R\cap S = \{t|t\in R \and t \in S\}

    交运算可以通过差运算实现:

    RS=R(RS)=S(SR)R \cap S=R-(R-S)=S-(S-R)

  2. 连接操作

    连接操作里有很多种类:

    1. θ-连接(θ-Join)

      投影和选择只是对单个关系(表)进行操作,而实际应用中往往涉及多个表之间的操作,这就需要θ-连接操作

      给定关系R和关系S,它们的θ连接运算结果也是一个关系,由它们笛卡尔积中,选取R中属性A与S中属性B之间满足θ条件的元组构成

      RSAθB=σt[A] θ s[B](R×S)\begin{matrix} R \Join S\\ {A \theta B} \end{matrix} = \sigma_{t[A]\ \theta\ s[B]} (R \times S)

      当θ取等号时,称为等值连接操作。广义积的元组组合并不都有意义,且数目庞大,因此采用θ-连接/等值连接可以大幅降低中间结果的保存量,提高速度

    2. 自然连接(Natural-Join)

      给定关系R和S,它们自然连接的结果也是一个关系,由R和S的笛卡尔积中选取相同属性组B上值相等的元组组成

      RS=σt[B]=s[B](R×S)R \Join S = \sigma_{t[B]=s[B]} (R \times S)

      是一组特殊的等值连接,要求R和S有相同的属性组B。因此要在结果中去除重复的属性列。因此自然连接不保证目数和R和S的目数直接相关。

复杂扩展操作:

  1. 除法运算常用于求解“查询…全部的…”问题

    前提条件:给定关系R(A1,A2,…,An),S(B1,B2,…,Bm)。如果可以进行R和S的除运算,当且仅当:属性集{B1,B2,…,Bm}是属性集{A1,A2,…,An}的真子集,即m<n

    定义:关系R和关系S的除运算结果也是一个关系,记作R÷S,分两部分定义:

    1. 结果属性:设属性集{C1,C2,…,Ck}={A1,A2,…,An} - {B1,B2,…,Bm},则有k=n-m,则R÷S结果是一k度关系,由{C1,C2,…,Ck}属性构成
    2. 元组:R÷S中每一个元组与S中每一个元组组合形成的新元组都是R中的某一个元组
    R \div S = {t|t \in \Pi_{R-S}(R) \and \forall u \in S(tu \in R)}\\ = \Pi_{R-S}(R)-\Pi_{R-S}((\Pi_{R-S}(R)\times S)-R)

    第二行用基本操作表示的除法的物理含义是,减法后的那个式子找出了和S乘积后不在R中的,属性为R-S的关系,让R在R-S属性组上的投影减去它就是和S乘积后在R中的。

  2. 外连接

    外连接的引入是为了解决连接时失配元组丢失的问题

    定义:两个关系R与S进行连接时,如果R中的元组在S中找不到相匹配的元组,为了避免该元组信息丢失,从而将该元组与S中假定存在的全为空值的元组形成连接,放在结果关系中。

    外连接 = 自然连接(或θ连接)+失配的元组(与全空元组形成的连接)。根据失配元组的位置,可分为左外连接,右外连接,全外连接

    image-20200611164551975


第五讲 关系模型之关系演算

关系演算是以数理逻辑中的谓词演算为基础的,按照谓词变量不同,分为关系元组演算和关系域演算

关系元组演算

基本形式:

{tP(t)}\{t|P(t)\}

表示所有使谓词P为真的元组t的集合,其中公式P(t)可以递归构造:

三种形式的原子公式:

  1. sRs \in R

  2. s[A] θ cs[A]\ \theta \ c

  3. s[A] θ u[B]s[A]\ \theta\ u[B]

如果P是公式,那么非P也是公式;如果P1,P2是公式,则P1与P2,P1或P2也是公式

如果P(t)是公式,R是关系,则

\exist(t \in R)(P(t)) \ \ 和\ \ \forall (t \in R)(P(t))

都是公式。元组变量t前有存在量词或全称量词,则该变量称为“约束变量”,否则称为“自由变量”。

需要的时候可以加括号,则运算次序从高到低是括号>θ>存在>任意>非>且>或

公式只限于以上形式

用元组演算公式可以实现关系代数

  1. 并运算

    R \cup S=\{t|t \in R \or t \in S\}
  2. 差运算

    R - S=\{t|t \in R \and t \notin S\}
  3. 交运算

    R \cap S=\{t|t \in R \and t \in S\}
  4. 广义笛卡尔积

    R(A) \times S(B)=\{t|t\exists(u \in R)\exists(s \in S)(t[A]=u[A]\and t[B]=s[B])\}
  5. 选择运算

    \sigma_{con}(R)=\{t|t \in R \and F(con)\}
  6. 投影运算

    πa(R)={t[A]tR}\pi_{a}(R)=\{t[A]|t \in R\}

关系域演算

基本形式:

{<x1,x2,...,xn>P(x1,x2,...,xn)}\{<x_1,x_2,...,x_n>|P(x_1,x_2,...,x_n)\}

xi代表域变量或常量

三个形式的原子公式:

  1. <x1,x2,...,xn>R<x_1,x_2,...,x_n> \in R

  2. x θ cx\ \theta \ c

  3. x θ yx\ \theta\ y

如果P是公式,那么非P也是公式;如果P1,P2是公式,则P1与P2,P1或P2也是公式

如果P是公式,x是域变量,则

\exist(x)(P(x)) \ \ 和\ \ \forall (x)(P(x))

都是公式。

需要的时候可以加括号,则运算次序从高到低是括号>θ>存在>任意>非>且>或

公式只限于以上形式

按示例查询QBE

QBE:Query By Example,操作框架由四部分构成:

  1. 关系名区:用于书写待查询的关系名
  2. 属性名区:用于显示对应关系名区关系的所有关系名
  3. 操作命令区:用于书写查询操作的命令
  4. 查询条件区:用于书写查询条件

image-20200614164535580

QBE的操作命令:

  1. Print或P. :显示输出操作
  2. Delete或D. :删除操作
  3. Insert或I. :插入操作
  4. Update或U. :更新操作

QBE的查询条件:

  1. 简单条件

    即θ参量,参量可以是常量也可以是变量

  2. 不同属性上的与条件

    不同属性上的条件写同一行表示与操作

  3. 示例元素与投影

    条件θ参量中的参量可以是域变量,用任何一个值带有下划线表示,被称为实例元素。实例元素下划线上面的值不起作用,被当成域变量名称来对待,只用于占位或连接条件。

  4. 示例元素实现与运算和或运算

    当书写或运算时,可采用在多行书写,然后打印命令后使用不同的示例元素来表征
    image-20200614165847966

    如果一批与运算分多行书写,则相互存在与关系的行要采用相同的示例元素

    image-20200614165903311

  5. 相当于括号的条件表示

    当把与或非条件写在操作命令区时,对整行条件而言相当于将该行条件放在括号中一样。

  6. 用示例元素实现多个表的连接

    当检索涉及多个表时,可以利用统一连接条件使用相同的示例元素,来实现多个表的连接

关系运算的安全性

不产生无限关系和无穷验算的运算被称为是安全的

关系代数是一种集合运算,本身是安全的;但关系演算不一定安全,比如一个有限关系取非运算就是是无限关系。

想要保证安全性,就需要要对关系演算施加一个在集合范围内操作的约束,而不是不加约束在无限范围内操作

由此定义安全约束有限集合DOM

DOM(ψ)是一个有限集合,其中的每个符号要么是ψ中明显出现的符号,要么是出现在ψ中的某个关系R的某元组的分量

满足下面三个条件的元组表达式{t|ψ(t)}称为安全表达式:

  1. 只要t满足ψ,t的每个分量就是DOM(ψ)的一个成员

  2. 对于ψ中形如

    (\exist u)(\omega(u))

    的子表达式,若u满足ω,则u的每个分量都是DOM(ω)中的成员

  3. 对于ψ中形如

    (u)(ω(u))(\forall u)(\omega(u))

    的子表达式,若u满足ω,则u的每个分量都是DOM(ω)中的成员

安全域演算表达式可以类推

关系运算 操作对象
关系代数 集合
元组演算 元组
域演算

关系运算安全的元组演算安全的域演算是等价的,如果一个数据库语言能等价地实现这三种关系运算,则可称该语言是完备的