第一章: 数据库系统概述

基本概念

  • 信息: 用于反映现实世界中事物的物理状态, 向人们提供一些已知的、客观存在的事实和知识
  • 数据: 是指具有一定的语义含义, 并且可以被记录下来的已知事实. 在计算机中, 数据被表示为具有一定格式（或结构）的符号串, 它是计算机软件中程序加工的原料与结果, 属于软件范畴
  • 数据是信息的载体, 信息则是数据的内涵

  • 数据的特性

    1. 表现的多样性
    2. 可构造性: 型(数据类型, 数据结构, 数据模式), 值
    3. 挥发性/持久性
    4. 私有性/共享性
    5. ‘量’的表示: 少量/大量/海量

  • 数据特性的变化

    1. 量: 少量->大量->海量
    2. 结构: 简单->复杂
    3. 服务范围: 私有->共享
    4. 在软件中的地位: 附属地位(程序是主体)->主导地位(数据为中心, 应用程序共享数据)

  • 数据库应用系统DBAS: 利用数据库系统作应用开发所构成的集成化的独立运行系统

    • 数据库系统DBS: 是一个以对海量的、具有复杂数据结构的、可以持久保存的、可供多 户共享的数据进行统一管理为目标的计算机系统
      • 数据库DB: 是数据集合, 具有统一的结构形式并存放于统一的存储介质内, 它由多种应用数据集成, 并可被应用所共享
      • 数据库管理系统DBMS:
        • 是管理数据库的系统软件
        • 特点: 管理持久性数据, 大量数据, 数据共享
        • 作用: 数据库应用程序与数据库的接口, 安全可靠+简明方便
        • 功能: 组织, 操纵, 维护, 控制及保护, 交换, 服务, 字典
        • 数据子语言: (SQL语言的组成部分
          • 数据定义语言: DDL
          • 数据操纵语言: DML
          • 数据控制语言: DCL
        • 数据子语言的使用方式: 交互式命令(终端直接操作), 宿主型(嵌入到宿主语言中)
      • 数据库管理员DBA: 对数据库进行规划、设计、维护、监视的专职人员
      • 软件平台: 操作系统, 语言, 数据库应用开发工具, 通用的数据库访问接口
      • 硬件平台
    • 应用软件, 应用界面
    • 数据库用户
      • 最终用户: 终端查询用户, 应用程序的使用者
      • 应用程序开发人员
      • 数据库管理员

  • 数据库应用系统层次结构(9)

    硬件平台->操作系统->数据->数据库管理系统->数据交换与中间件->开发工具->应用软件->应用界面->用户

数据库系统的发展及趋势

  • 数据管理技术的发展历史

    人工管理->文件系统管理->数据库系统管理

  • 数据库管理系统的发展阶段
    • 层次/网状数据库: 20世纪60年代~70年代
      • 从无到有, 简单的共享数据读写
    • 关系数据库: 20世纪70年代~
      • 从有到大规模商业化应用
      • 面向事务处理型引用OLTP
    • 数据仓库: 20世纪90年代~
      • 面向数据分析型婴童OLAP
    • 新型数据库管理系统: 21世纪
      • NoSQL数据库/大数据管理系统
  • 数据库系统的发展历史
    • 文件系统阶段: 仅是数据库系统的雏形
      • 优点: 利用文件系统来参与数据管理, 向用户提供简单的数据管理和共享能力
      • 缺点: 数据管理功能不完整不统一, 数据共享能力弱, 不利于数据库系统的移植
    • 层次数据库与网状数据库: 是真正的数据库系统
      • 优点: 统一的数据管理工具, 数据共享能力
      • 缺点: 受文件物理影响大, 数据构造繁琐
    • 关系数据库: 80年代潮流
      • 优点: 结构简单、使用方便、逻辑性强、物理性少
      • 缺点: 模型的描述能力不足, 数据操纵功能有待扩展
      • 扩充: 专用数据库系统: 专用性有余而通用性不足
    • 通用数据库系统: 90年代重点
      • 面向对象数据库系统
      • 知识库系统
      • 关系数据库系统扩充
    • 新一代数据库系统: 关系数据库系统的进一步扩充与改造
      • 对象关系数据库系统, 数据仓库(Data Warehouse), Web数据库, 安全数据库, (嵌入式数据库, 移动数据库, 实时数据库网格数据库, 传感器网络数据库

数据库系统的基本特点

  • 集成性: 集多种应用数据于一体
    • 统一的数据结构
    • 全局统一的数据模式
    • 根据应用需要构造局部模式
  • 高共享性与低冗余性
    • 数据共享
      • 多个应用程序使用, 可用于不同的目的
      • 已有的数据库系统上开发新的应用程序
      • 向外界提供信息服务功能
    • 数据冗余
      • 同一个数据在不同的地方重复存储
    • 减少不必要的存储空间, 避免数据的不一致性
  • 独立性
    • 数据或数据结构的改变不会导致对使用这些数据的应用程序的修改, 反之亦然
    • 物理独立性: 物理结构（包括存储结构、存取方式等）的改变, 不影响数据库的逻辑结构, 不致引起应用程序的变化
    • 逻辑独立性: 数据库总体逻辑结构的改变, 如修改数据模式、增加新的数据类型、改变数据间联系等, 不需要相应修改应用程序
  • 数据的统一管理与控制
    • 数据的完整性检查
    • 数据的安全性保护
    • 并发控制
    • 数据库故障恢复

数据库内部结构体系

  • 数据库系统的三级模式
    • 概念模式简称模式->概念数据库
      • 整个数据库中数据的全局逻辑结构的描述
      • 基于数据模型, 利用数据定义语言DDL描述
      • 数据类型, 长度, 特征, 数据间联系, 安全性完整性的要求
    • 外模式(子模式, 用户模式)->用户数据库
      • 是关于某个用户所需数据的逻辑结构的描述
      • 是概念模式的子集, 同一概念模式可有多个外模式, 针对用户
      • 简化用户接口易用, 降低冗余, 利于安全保密
    • 内模式(物理模式)->物理数据库
      • 是关于数据库中数据的物理存储结构和物理存取方法的描述
    • 物理数据库: 真实存在; 其他两种数据库由物理数据库通过数据库管理系统构造
  • 数据库系统的两级映射: DBMS提供
    • 概念模式到内模式: 物理独立性: 全局逻辑结构到数据的物理存储结构间的对应关系
    • 外模式到概念模式: 逻辑独立性: 一个概念模式中可以定义多个外模式, 而每个外模式是概念模式的一个基本视图
    • 两级映射建立三级模式间的联系与转换, 保证了数据库系统中数据独立性的实现

第二章: 数据模型

数据模型的基本概念

  • 数据: 现实世界中客体符号化抽象
  • 数据模型: 数据基本特征的抽象, 描述数据的结构, 定义在该数据结构上可以执行的操作以及数据之间必须满足的约束条件

    数据模型应该能比较真实地模拟现实世界, 易于人理解, 便于在计算机上实现

    • 数据结构: 数据的类型, 内容, 性质, 数据间联系
    • 数据操作: 操作类型, 操作方式
    • 数据约束: 数据结构内数据间的相互关系: 语法语义联系, 制约与依存, 动态变化规则
  • 数据模型的类型

    数据模型的核心是数据结构, 现实中数据及其关系到数据库, 有逐步转化的过程, 以数据模型表示其转化结果
    概念数据模型–>转化逻辑数据模型–>DBMS物理数据模型(可实现)

    • 概念数据模型: 面向客观世界, 面向用户, 无关于数据库管理系统和计算机平台
      种类: E-R模型, EE-R模型; 面向对象模型; 谓词模型
      描述客观对象的数据特征及相互关系
    • 逻辑数据模型: 面向数据库系统, 着重于DBMS实现, 承上启下
      种类: 层次, 网状模型; 关系, 面向对象, 谓词模型; 对象关系模型
      描述事物及关系在选定的DBMS中的实现结构, 即据DBMS定义事物及关系的实现结构
    • 物理数据模型: 面向计算机物理表示, 给出数据模型在计算机上的物理表示
      向用户提供与物理存储结构与存取方法相关的定义: 索引, 集簇, 存储区域的选择
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      客观世界                 用户1    ...   用户n
        |                        |              |
        |                        |              |
        |                        |              |
      概念模型   +----------->外模式1   ...  外模式n
        |       /                |              |
        |      /                 |              |
        |     /                  |              |
      逻辑模型--------------->概念模式---------+
        |                        |
        |                        |
        |                        |
      物理模型--------------->内模式

数据模型的四个世界

  • 现实世界: 客观世界中, 据用户需求目标, 划定边界的应用环境

    用户需求: 数据需求, 处理要求
    提供转换过程的: 客观基础, 启动环境

  • 概念世界: 基于现实世界, 进一步的抽象而形成

    基本术语: (实体, 属性, 联系)E-R模型, (对象, 类, 方法, 继承)OO模型
    无关于具体的DBMS和计算机

  • 信息世界: 基于概念世界, 用特定的DBMS构造而成的逻辑数据模型

    用特定的DBMS所提供的工具来定义逻辑数据模型, 侧重于概念数据模型的细化和在数据库系统一级的实现
    有关于具体的DBMS

  • 计算机世界: 基于逻辑数据模型在计算机中的物理实现, 形成物理数据模型

    侧重于数据库物理存储结构的描述: 存储结构设计, 存取路径设计, 存储空间分配
    DB的最终实现结构

概念世界与概念模型

  • 概念世界: 概念世界是一个较为抽象, 概念化的世界; 给出数据的概念化结构; 概念世界一般用概念模型表示
  • 概念模型种类: 实体-联系(E-R), 扩充的实体-联系(EE-R), 面向对象, 谓词模型

E-R模型

  • 概念化模型: 现实世界的要求 转化成 实体, 联系, 属性 及 两种基本关系; 用E-R图表示
  • 实体
    • 客观存在且又能相互区别的事物

      客观事物的抽象, 概念世界中的基本单位

    • 实体集: 具有共性的实体所构成的集合
  • 属性
    • 实体所具有的某种特性或特征

      属性有值, 取值集合为值域

    • 一个实体可有多个属性

      共性实体有相同的属性组成
      不同实体在其属性取值上有区别

  • 联系
    • 一个实体集中的实体与另一个实体集中的实体之间的对应关系
    • 种类(与联系相关的实体集数): 二元联系, 多元联系, 内部联系
    • 例子
      • 二元(隶属, 学习, 借阅)
      • 多元(供应: 工厂, 产品, 用户)
      • 内部(围棋比赛: 黑方, 白方)
    • 相同实体集之间的多种联系
      • 在同一组实体集之间可以存在多种联系
    • 联系的函数对应关系
      • 一一对应（one to one）
      • 一多对应（one to many, 多一对应（many to one）
      • 多多对应（many to many）
    • 联系所具有的特性
      • 因联系的发生而产生的特性可以通过联系上的属性来表示
  • 基本概念之间的连接关系
    1. 实体集（联系）与属性间的连接关系
    2. 实体集与联系间的连接关系
    • 实体(集), 属性及其连接关系的描述
      • 属性的描述: 属性名, 属性域
      • 实体的描述:
        • 实体名
        • 实体型: 实体名+一组属性名

          描述实体的组成结构信息

        • 实体值

          所有属性值的集合称为实体值, 又称元组

      • 实体集的描述
        • 属性集合+关键字

          关键字: 是可用于区分同一个实体集中不同实体的 ‘最小属性集合’

    • 联系及其与实体集之间的连接关系的描述
      • 联系名
      • 属性: 联系拥有属性

        由一个‘联系名’ + 与该联系相关的‘实体集的名称’, 以及联系上的属性, 从而构成联系及其与实体集之间的连接关系的描述

      • 函数对应关系
    • E-R图
      • 基本概念表示: 图形内写名称
        • 实体集: 矩形框
        • 属性: 椭圆
        • 关键字: 椭圆, 属性名加下划线
        • 联系: 菱形框
      • 联系表示: 无向线段

        每个属性只能隶属于一个实体集, 哪怕同名
        实体集与联系的连线旁边, 用数字标明涉及的实体数量

    • 设计E-R模型
      • 实体 or 属性

        考虑取值, 若某一性质仅有一个重要的信息, 则作为属性, 如仅使用身份证号码的身份证; 若有多个重要信息, 则作为实体, 这些信息作为属性, 如身份证与其号码, 有效期, 签发机关等

      • 实体 or 联系

        与多个对象有关, 往往是联系; 一些事件有相关的物品, 例如交易与其合同, 交易可作为关系, 也可用合同表示为实体

      • 二元 or 多元

        只需考虑两两关系且无歧义时, 多元可转化为多个二元

      • 属性依附对象

        实体的属性: 内在特征, 与联系无关; 联系的属性: 联系消失则消失的属性

EE-R模型

  • 扩充的内容
    • IS_A联系 (Generalization Hierarchies): 继承, 即超(实体)集与子(实体)集关系

      用子集到超集的有向箭头表示, 书中箭头带圈

      • 继承性: 子集继承超集中的所有属性, 亦可有自己专有的属性; 超集关键字也是子集关键字
      • 传递性
      • 优点: 更好地映射到面向对象方法; 统一共性, 又能体现差异, 更好地模拟现实世界
      • 覆盖约束: 所有子集的并集等价于超集, 一个实体至少属于一个子集
      • 不相交约束: 子集互不相交, 一个实体至多属于一个子集
    • 弱实体(Weak Entity): 某个实体依附于其他实体的存在

      用从弱实体集到联系的有向箭头表示

    • 属性的划分
      • Identifier（标识符）: 又称关键字
      • Descriptor（描述符）
      • a composite attribute（组合属性）: 一组简单属性, 组合为一个组合属性, 描述一个性质, 例如姓名=名+姓
      • a multi-valued attribute（多值属性）: 一个实体在一个属性有多个值
    • 属性基数 (Cardinality of Attributes): 二元组表示属性取值数量特征

      标注在属性到实体集的连线上

      • (0,?): 可取空值, 不加限制
      • (1,?): 不可空值
      • (?,1): 单值属性
      • (?,N): 可取空值, 至多N值
    • 实体在一个联系中的参与基数(Cardinality of Entity Participation in a Relationship)

      标注在联系到实体集的连线上

      • card(E,R) = (min-card(E,R), max-card(E,R)), 实体集E中一个实体, 通过联系R连接到实体集F中, 所能连接的实体数量范围
        • 单值参与: max = 1; 否则多值参与
        • 可选参与: min = 0; 否则强制参与
      • 用“参与方式”代替函数对应关系, 描述实体在联系中的数量对应关系
      • [解题技巧] 观察每个实体连了几根线, 这个数值的范围就是参与基数
  • | Classification | Description |
    | :-: | - |
    | Entity | A collection of distinguishable real-world objects with common properties. |
    | Attribute | A data item that describes a property of an entity or a relationship. |
    | Identifier | (set of attributes) | Uniquely identifies an entity instance or relationship occurrence. |
    | Descriptor | Non-key attribute, describing an entity or relationship. |
    | Composite attribute | A group of simple attributes that together describe a property of an object. |
    | Multi-valued attribute | An entity attribute that takes on multiple values for a single entity instance. |
    | Relationship | Named set of m-tuples, identifies subset of the Cartesian product E1×E2×…×Em |
    | Binary relationship | A relationship on two distinct entities |
    | Ring, recursive relationship | A relationship relating an entity to itself |
    | N-ary (N>2) relationship | A relationship on more than two entities |

面向对象模型

  • 概念
    • 面向对象技术引入到数据库领域, 借鉴面向对象的设计方法而发展起来的一种新的数据模型
    • 采用了面向对象方法中的基本概念和方法来构造数据库的数据模型
    • 提升了模型的表达能力, 特别是在表示非传统的、复杂数据关系方面具有极强的表达力
  • 对象
    • 客观世界中能够相互区别开来的事物(同E-R模型中实体定义)
    • 区别
      | | 对象 | 实体 |
      | - | - | - |
      | 描述特征 | 属性组成+行为特征 | 属性取值 |
      | 区分实体 | 对象标识符 | 属性取值 |
    • 组成
      • 标识符: OID: 每对象仅有一个, 用以相互区别
      • 静态特征: 属性, 反应状态与特性
      • 动态特性: 方法, 施加在对象上的程序, 可审视或改变属性值
    • 特点
      • 封装
        • [属性+方法]合为整体
        • 封装产生划分:
          • 内部表示: 属性的组成, 方法的实现
          • 外部表示: 方法的调用接口, 亦称对象界面
        • 优点: 利于保护, 力与维护, 提高可靠性和重用性
      • 标识符的独立性
        • 独立于属性, 由系统定义并赋值, 唯一标识一个对象
        • 特性: 唯一性, 持久性, 不可重用性
      • 属性值的多值性
        • 可以是: 单值, 值的集合, 另一个对象
  • 类(class)
    • 具有相同属性, 方法的对象集合
    • 定义类, 以描述其中对象的静态特性和动态特性
    • 实例: 类抽象为”类对象”, 而类的对象称为”实例”
    • 元类: 由所有类对象构成的对象集合
    • 类间关系
      • 继承: IS-A
        • 单向不循环的层次结构, 共享实现和定义
        • 普化: 子类到超类, 对象集合合并
        • 特化: 超类到子类, 对象集合分解
        • 单继承: 每个子类只有唯一的直接超类
        • 多继承: 每个子类可有多个直接超类
        • 继承的作用: 支持共享与重用, 有助于扩充
        • 问题
          • 重载: 解决在继承过程中, 超类与子类（或超类与超类）之间的冲突
          • 冲突: 方法或属性的名字相同但语义或实现不同
      • 聚合与分解: IS-PART-OF
        • 聚合: 若干个简单类聚合成一个复杂的类的过程
        • 分解: 复杂类分解成若干层次上的简单类的过程
        • 语义: 组成语义, 嵌套语义, 联系语义
      • 两种联系来构成类的层次结构, 描述复杂的数据关系, 以它们为主要手段来构造面向对象的数据模型
  • 消息
    • 对象协作机制
    • 发送消息以调用其他对象中的方法
    • 仅作用于对象界面
    • 用户操作也可看成消息
      • 消息组成: (type) A.Op(O1, O2, …, On) (形同函数调用)
      • 消息与方法: 方法是内部操作(接口+实现), 消息是跨对象的操作
  • C++与OODB
    | C++ | OODB |
    | - | - |
    | - | 有OID |
    | 管理对象 | 管理类 |
    | 关心继承 | 关心继承和合成 |
    | 挥发性 | 持久性 |
    | - | 重视安全, 完整, 并发和故障恢复 |

谓词模型

  • 概念
    • 谓词模型又称谓词逻辑模型, 使用一阶谓词演算公式表示数据模型
    • 用于构建: 概念数据模型 和 逻辑数据模型
  • 实体集
    • 谓词: 标识符号+若干变元, 变元取值, 判断是否成立
    • n个属性的实体集, 用含n个变元的谓词表示该实体集
    • 在此实体集中的元组, 使此谓词为真, 不在则为假
  • 属性
    • 用变元取值表示属性
    • 属性的域也可用谓词表示
    • 对变元的约束可用统一的约束谓词表示
    • n属性的实体集有此表示: $P(x_1,x_2,\cdots,x_n)\wedge C(x_1)\wedge C(x_2)\wedge\cdots\wedge C(x_n)$
  • 联系
    • 谓词来表示联系, 谓词中的变元由参与该联系的实体（通常用实体的关键字属性代替）以及联系本身所具有的属性组成
  • 操作
    • $x_i$为操作对象, $X$为结果: $Op(x_1,x_2,\cdots,x_n, X)$
  • 完整性约束
    • 谓词或谓词公式来表示属性间的完整性约束条件

信息世界与逻辑模型

  • 信息世界是数据库的世界, 它着重于数据模型在数据库系统一级的构造与操作
    • 信息世界用逻辑数据模型来进行描述

逻辑模型的分类

  • 层次模型和网状模型
  • 关系模型和对象关系模型
  • 面向对象模型
  • 谓词模型

简史

  • The ’60s: 数据库技术的萌芽阶段
  • 1961: IDS (Integrated Data Store)网络数据模型
  • 1965-1970: IMS (Information Management System)层次数据模型, 多用户
  • 1970: 关系数据模型
  • 1975: 著名的国际会议
    • SIGMOD: ACM Special Interest Group on Management Of Data
    • VLDB: Very Large Data Bases
    • ICDE: IEEE International Conference on Data Engineering
  • 1976: Entity-Relationship (ER) model
  • The ’80s: 商用关系数据库管理系统的兴起
  • The ’90s
    • 专用数据库系统
    • 商用面向对象数据库管理系统
    • 对象关系数据库管理系统
  • 新世纪以来
    • 数据仓库, 安全数据库, XML数据库, 嵌入式、移动、实时、内存, NoSQL ……
  • 早期有影响的研究工作
    • System R (IBM)
    • INGRES (University of California, Berkeley)
    • System 2000 (University of Texas, Austin)
    • Socrate Project (University of Grenoble, France)
    • ADABAS (Technical University of Darmstadt, W. Germany)
  • 数据库语言
    • SQUARE, SEQUEL (SQL), QBE, QUEL
  • 其它方向:
    • Expert Database Systems
    • Object-oriented DBMSs
  • 概念模型与逻辑模型对应关系表
    | 概念模型 | E-R模型 | EE-R模型 | 面型对象模型 | 谓词模型 |
    | - | - | - | - | - |
    | 逻辑模型 | 层次模型, 网状模型, 关系模型 | 对象关系模型 | 面型对象模型 | 谓词模型 |

关系模型

  • 概念: 关系模型是一种新的逻辑模型
  • 基本数据结构: 二维表(简称表)
  • 数据操纵: 表查询, 表的删除插入修改
  • 二维表
    • 二维表由表框架与元组所组成, 表框架由若干个属性组成
    • 存放于框架内的每‘一行数据’都被称为 ‘一个元组’ (Tuple), 或称‘行’(Row)
    • 一张二维表是由一个有n个属性的框架及m个元组组成
  • 关系
    • 由行和列组成的二维表格
    • 关系的约束
      • 同一表中的属性名各不相同
      • 表中的属性与属性的排放次序无关
      • 表中的元组均不相同
      • 表中的元组与元组的排列次序无关
      • 表中的每一分量必须是一个不可分割的基本数据项
    • 概念
      • 关系模式: 一个关系的关系名及其属性名的集合构成该关系的关系模式
      • 关系数据库模式: 该关系数据库中所有关系的关系模式的集合
      • 元组: 关系中的每一行
      • 关键字
        • 一个属性集的值能唯一标识关系中的一个元组, 且又不含多余的属性值
        • 每一个关系都有关键字
        • 一个关系也可以有多个关键字, 所以关键字也被称为‘候选关键字’
        • 主关键字: 关系的候选关键字中选取一个
        • 外关键字: 设关系R中的属性集F, 其取值来自于关系S中的主关键字K, 则称属性集F是关系R的外关键字(取值来自外部关键字 的 属性集)
    • 关系模型上的数据操作
      • 关系模型数据操作的对象是‘关系’；
      • 关系模型数据操作的结果也是一个‘关系’；
      • 关系模型的五种基本操作: 属性指定, 元组选择, 关系的合并, 元组插入, 元组删除

计算机世界与物理模型

  • 物理模型是面向计算机的模型, 它构作数据库系统的物理实现: 操作系统级文件组织, 硬件级数据组织

文件系统的组成

  • 文件系统的组成
    • 项 (Item) : 文件系统中最小基本单位, 项内符号是不能继续分割的
    • 记录 (Record): 由若干项组成, 记录内的各项间有内在语义联系
      • 记录有型与值的区别
    • 文件 (file): 记录的集合
      • 一般讲, 一个文件所包含的记录都是同型的
    • 文件集 (file set): 由若干个文件构成
  • 提高文件读写操作效率的方法
    • 索引(Index)
      • 将文件中的记录与其物理地址(即磁盘块)间建立一张对应关系表以便于快速查找, 这就是索引
      • 索引一般也是一个文件. 当数据文件中的记录数很大时, 索引文件本身也还需要建立索引, 这叫二级索引
      • 依此类推, 可以建立多级索引
      • B+树是关系数据库的物理实现中最常用的一种多级索引技术
    • hash法
      • 一种函数转换法, 其主要思想是: 通过一个hash函数将要查找的记录转换成该记录所在的物理地址, 然后可以直接进行记录的定位读取操作
    • 集簇(Cluster)
      • 在记录查找中往往需要按某项的项值查找, 将具有相同或相邻项值的记录聚集在相同磁盘块内或圆柱体内以减少读盘次数, 提高查找速度, 这被称为集簇

第三章: 关系数据库系统

关系数据库系统概述

关系数据库系统的优点

  1. 数据结构简单
    • 二维表: 记录-字段
  2. 使用方便
    • 不涉及物理结构, 非过程性数据子语言
  3. 功能强
    • 表达能力强, 便于修改数据间联系, 灵活选取数据存取路径, 高级的数据操纵语言
  4. 数据独立性高
    • 不涉及物理因素, 操作非过程性
  5. 理论基础深
    • 关系代数+关系演算理论->系统实现
  6. 可移植性好
  7. 标准化程度高
    • 数据子语言的标准化: SQL语言标准
  8. 分布式功能
    • Client/Server(C/S); Browser/Server(B/S); 分布式数据库
  9. 开放性
    • 数据访问接口实现与其它系统的互连: OBDC, JDBC
  10. 其它方面的功能扩展

关系数据库系统衡量准则

六条准则1974

提供高度的数据独立性
提供严格的数据视图
减轻DBA的工作
建立理论基础
事务管理与文件管理相结合: 为商业及其它行业的服务作准备
操作对象是记录集合, 而不是单个记录

完全关系型的12条严格标准1985

  1. 信息准则: 逻辑一级
    • 所有信息 -> 表中的值, 唯一且显式地表示
    • 结构描述信息 -> 组织成关系形式
  2. 确保访问准则
    • 表名+关键字值+列名 -> 访问到每一个原子数据
  3. 空值的关系处理准则
    • 空值: 无意义/当前未知
    • 系统应当可以处理有空值参与的: 比较运算, 表达式运算, 统计运算
  4. 基于资源管理的动态联机目录
    • 数据库的描述信息(数据字典) 与 用户数据 有 相同的表示形式和操作方式
    • 被授权用户可对 数据库的描述信息 进行 查询与扩充
  5. 统一易用的数据子语言: 至少一种子语言支持以下功能
    • 数据定义
    • 视图(view)定义
    • 数据操纵
    • 完整性约束能力
    • 授权机制
    • 事务处理能力
  6. 视图更新准则: 视图除查询外, 还可增加, 删除, 修改数据
  7. 高级的插入、删除及修改操作: 一条命令可以插入、删除及修改操作多条元组
  8. 物理数据独立性
  9. 逻辑数据独立性
  10. 数据完整性准则: 提供三类数据完整性约束的定义功能
  11. 分布独立性: 数据分布的改变不影响原有的应用程序
  12. 无损害原则: 对提供低级数据子语言的要求

关系数据库产品的类别划分

  • 半关系型系统
    • 基本数据结构: 关系
    • 满足12条准则中的 少量要求
  • 基本关系型系统
    • 基本数据结构: 关系
    • 满足12条准则中的 大部分要求
  • 完全关系型系统
    • 严格符合 上述的12条准则

关系模型数学理论 — 关系代数

关系模型

关系数据结构

  • 术语对应关系
    | 关系模型 | DBMS(SQL) | 文件系统 |
    | - | - | - |
    | Relation 关系 | Table 表 | File of Records |
    | Attribute 属性 | Column 列 | Field |
    | Tuple 元组 | Row 行 | Record |
    | Schema 模式 | Table Heading 表头 | Type of Record |
  • 表结构
    表 = n元表框架 + m个元组
    • 表框架
      属性组成表框架; n个属性 - 表的元数; 属性取值范围 - 值域
    • 元组
      行 - 元组; n元表 - 元组n个分量; m行 - 表的基数 - 元组数量
  • 关系
    • 被称为关系的二维表必须满足的性质
      • 元组: 个数有限, 唯一, 次序无关, 分量原子性, 分量值域同一
      • 属性: 名称唯一, 次序无关
    • 满足以上关系的二维表, 所建立的模型称为关系模型
    • 二维表 –(抽象)–> 关系; n个属性 - n元关系
    • 关系 - 关系名; 属性 - 属性名; 关系名($R$) + n*属性名($A_1, \cdots, A_n$) = 关系框架($R(A_1, \cdots, A_n)$)
  • 键
    • 键: 唯一最小标识元组的属性集, 每张表至少一个
    • 主键: 被选中的键; 候选键: 其他
    • 超键: 唯一标识元组的属性集(键是极小超键, 其任意子集均不能标识元组)
    • 外键: 如果表A中的属性集F是表B的键, 则称该属性集F为表A的外键

关系操纵

  • 查询
    • 单张表内
      • 目标: 某(行 - 元组)的(属性值 - 元组分量)
      • 过程: (纵向定位 - 行选择)选符合条件的元组 -> (横向定位 - 列指定)指定属性
    • 多张表
      • 先合并->单张表查询
  • 删除
    • 基本单位: 元组
    • 过程
      • 确定被删除的元组: 单个关系内的选择操作来确定
      • 删除操作: 一次操作只能删除一个关系内的元组
  • 插入
    • 一条操作只能向一个关系中增加新的元组
  • 修改
    • 修改不是基本操作, 修改 = 删除(旧元组) + 插入(修改后的新元组)
  • 小结: 关系-(操纵)->(新)关系
  • 五种基本操作
    • 元组选择: 选择满足条件的元组
    • 属性指定: 选择结果需要的属性
    • 关系合并: 多个关系两两合并, 最终合并为一个关系
    • 元组插入
    • 元组删除
  • 空值处理
    • 数据完整性约束: 主键不允许空值
    • 空值运算
      • 算数表达式中有空值, 则结果为空值
      • 逻辑表达式中有空值, 则结果为逻辑假
      • 统计计算:
        • 集合中的空值元素不计算在内: SUM, AVG, MAX, MIN, COUNT
        • 空集: [ SUM, AVG, MAX, MIN ] = 空元素; [ COUNT ] = 0

关系中的数据约束

  • 三类数据完整性约束
    • 实体完整性约束: 属性不为空值
    • 参照完整性约束: 外键要么取空值, 要么是被引用表中的主键值
    • 用户定义的完整性: 用户自己定义的属性取值约束
  • 关系代数
    • 关系的表示
    • 关系操纵的表示
    • 关系代数与关系模型
    • 关系代数的扩充运算

关系的表示

  • 笛卡尔积
    $D_1, D_2, \cdots, D_n$是$n$个集合
    $D_1\times D_2\times\cdots\times D_n=\{(d_1, d_2, \cdots, d_n): d_i\in D_i, i\in (1, 2, \cdots, n)\}$
    $|D_1\times D_2\times\cdots\times D_n| = \prod_{i=1}^n |D_i|$
  • 关系
    设属性域为$D_1, D_2, \cdots, D_n$
    关系$R\subseteq D_1\times D_2\times\cdots\times D_n$

关系操纵的表示

  • 对应关系
    | 关系基本操作 | 关系代数运算 |
    | :-: | :-: |
    | 元组选择 | 选择运算 |
    | 属性指定 | 投影运算 |
    | 关系合并 | 笛卡尔积 |
    | 元组插入 | 并运算 |
    | 元组删除 | 差运算 |
    注意运算的: 执行条件, 执行结果
  • 相容表/同类关系: 相同的表头: 同数量, 同名, 同值域
  • 关系运算
    • 交运算: 同类关系
      • 用$R\cap S = R-(R-S)$代替, 不是基本运算
    • 并运算: 同类关系: 交换律, 结合律
      • 关系模式不变, 属于$R$或者$S$
    • 差运算: 同类关系: 无交换律, 无结合律
      • 关系模式不变, 属于$R$且不属于$S$
    • 投影运算: $\pi_A(R)$: 无交换律
      • 略去某些列, 重排剩余列的次序
        关系$R$有属性$\{A_1,A_2, \cdots, A_n\}$, 在其中$m$个属性上的投影运算如下
        $\pi_{B_1, B_2, \cdots, B_n}(R), B_i\in\{A_1,A_2, \cdots, A_n\}$
      • 注意消除可能出现的重复元组
    • 选择运算: $\sigma_F(R)$: 交换律
      • 关系模式不变, 由属于$R$且满足条件$F$的元组构成
    • 笛卡尔乘积 - 关系的合并: 交换律, 结合律
      • 若有相同的属性名, 必须在结果关系中对其中一个换名
  • 关系操作
    • 插入: $R^*=R\cup R_{new}$
    • 删除: $R^* = R-R_{old}$
    • 修改: $R^* = (R-R_{old})\cup R_{new}$
    • 查询: $\pi_A(\sigma_B(R))$简写为$\pi_A\sigma_B(R)$: 不能交换位置

关系模型与关系代数

  • 关系: $n$元有序组的集合
  • 关系操纵: 关系上的集合运算
  • 关系代数: 关系集合$A$及5种基运算构成的代数
  • 关系模型
    • 关系模型的数据结构
    • 关系模型上的数据操纵
    • 关系模型上的数据约束

关系代数中的扩充运算

  • 交运算: 同类关系: 交换律, 结合律
    • 关系模式不变, 既属于$R$也属于$S$的元组组成的集合
    • 可由差运算实现: $R\cap S=R-(R-S)=S-(S-R)$
  • 除运算: $\textrm{Head}(S)\subset \textrm{Head}(R)$
    • 关系模式: $\textrm{Head}(T)=\textrm{Head}(R) - \textrm{Head}(S)$
    • 设$x\in T$, 则$\forall y\in S$, $(x,y)\in R$, 所有满足条件的$x$构成结果
    • 如果$R=T\times S$, 则$T=R\div S$, $S=R\div T$; 如果$T=R\div S$, 则$T\times S\subseteq R$
    • $R\div S=\pi_{A_1,\cdots A_n}(R)-\pi_{A_1,\cdots A_n}((\pi_{A_1,\cdots A_n}(R)\times S)-R)$
  • 联接运算
    • 根据联接条件合并: $R\bowtie_F S=\sigma_F(R\times S)$
    • 自然联接: $R\bowtie S$所有同名属性上的取值都一样, 就联接元组, 同名属性保留一份
    • 外联接: 有”外”的一侧, 其所有元组均出现, 另一侧无匹配元组就用null代替

关系代数实例

解题技巧

  • “所有A都…的B”, 用除法, 被除的对象应当先投影, 以免遗漏
  • 用公共属性查私有属性, 先笛卡尔积, 之后用选择, 条件设为同名属性取值相等, 最后投影
  • 正面难构造, 就构造反面, 然后用笛卡尔积减去反面
  • 最大值最小值, 例子: 取C中最大, C为key-value对
    $$D\coloneqq C$$
    $$M = C - \pi_{C.key,C.val}\sigma_{C.val < D.val}(C\times D)$$
    原理: 每取值跟所有取值比较, 存在更大就会保留, 找出所有的非最大值, 之后减去
  • 同时满足多个条件, 则取交; 满足多个条件中的一个, 则取并
  • 联接可以实现”之一”的效果, 也可以实现相等关系

解题步骤

  • 确定查询目标（结果关系中的属性）
  • 明确查询条件
  • 选择从条件到目标的查找路径，并据此确定操作对象，即:
    • 在操作过程中需要使用到那些关系?
    • 这些关系又是如何被联接成一个关系的?
  • 关系的合并
    • 根据步骤 3) 的分析结果进行关系的联接
  • 元组的选择
    • 根据步骤 2) 的分析结果(查询条件)进行元组的选择
  • 属性的指定
    • 根据步骤 1) 的分析结果执行投影操作

更多技巧

  • 差运算
    • 当查询条件带有‘否定’语义，或者具有明显的‘排它性’的时候，通常需要使用两个子查询之间的‘差’运算
    • ‘差’运算的运算对象（关系）中，通常需要包含其关键字

  • “笛卡尔积/θ-连接/自然连接”的使用方法

    • 都是关系的合并运算
      • 笛卡尔积是基本运算，θ-连接和自然连接则是扩充运算, 请注意三者的结果关系的关系模式之间的区别
    • 笛卡尔积
      • 是实现跨不同关系表进行数据访问的基础, 在笛卡尔积的结果关系中，存在着很多无意义的结果元组，通常需要通过后续的选择运算过滤掉
    • θ-连接
      • 相邻的“笛卡尔积+选择运算”可以合并为一个θ-连接
    • 自然连接
      • 如果连接条件是基于“两张表中的所有同名属性的相等比较”，可以将θ-连接进一步简写为自然连接
    • 一般方法: 笛卡尔积+选择 or θ-连接
      • 不存在同名属性，或者连接条件不是基于同名属性的相等比较
      • 在结果关系中可能存在同名属性，需要加以区别
    • 常用方法: 自然连接
      • 连接条件是隐含的（所有同名属性的相等比较）
      • 如果在两个关系之间存在多对‘同名属性’，而本次查询又不需要‘所有’的同名属性都相等，此时有两种选择:
      • 采用前述的一般方法来实现关系的合并
      • 先对其中的一个关系执行投影运算，过滤掉其中不需要相等的那些同名属性，然后再使用自然连接运算
    • 难点: 关系的自连接
      • 使用赋值运算定义‘同质不同名’的两个中间关系(元组集合相同，但关系名不同)，当然也可以对中间关系中的属性进行重命名
      • 然后再使用前述的一般方法实现两个中间关系的合并

  • 除

    • ‘除’ 运算与‘联接’运算的区别
    • 我们将查询的结果关系称为‘目标对象’，用于定义查询条件的关系称为‘条件对象’
    • 在决定某个元组t是否属于结果关系时，
      • 如果只需要从条件对象中找到一个元组c并使得查询条件成立，那么就直接使用‘联接’运算（包括笛卡尔积、θ-连接和自然连接）
      • 如果需要条件对象集中的所有元组都能使得查询条件成立，那么就使用‘除’运算
    • ‘除’ 运算表达式的表示方法
      • 被除数关系中必须包含目标对象和条件对象的关键字
      • 除数关系中只含条件对象的关键字
      • 被除数和除数关系中不能含其它‘不必要’的多余属性, 先投影再除

关系演算

一阶谓词演算

  • 命题: 可以判断真假的语句
    • 个体词: 可以独立存在的客体
      • 个体常量: $a,b,c,\cdots$: 具体特定
      • 个体变元: $x,y,z,\cdots$: 抽象泛指
      • 个体域: 指个体变元的取值范围
      • 全总个体域: 由宇宙间的一切事物组成
    • 谓词: 个体性质或个体间关系: $P(x_1,x_2,\cdots,x_n)$
      • 常项/变项: 具体性质或关系/抽象泛指的性质或关系
      • n/0元谓词: 含n个/不含个体变元的谓词
      • 根据变元的取值来判断其是否成立
  • 指派: $(v_1,v_2,\cdots,v_n)$为$P(x_1,x_2,\cdots,x_n)$的指派, $x_i$取值$v_i$
    • 成真指派/成假指派: $P(v_1,v_2,\cdots,v_n)$为逻辑真/假
  • 量词: 个体常量或个体变元之间数量关系
    • 全称/存在量词: 每一个/至少有一个 个体域中的个体满足谓词
    • 约束/自由变元: 受到/不受量词约束的变元
    • 顺序: 既有全称量词也有存在量词，那么它们的书写顺序是相关的, 无括号则从左到右依次处理
    • 指派: 只对自由变元取值
  • 连接符
    • 非, 与, 或, 蕴含

关系的表示

关系->谓词
关系操作->关系演算公式

  • 关系演算系统
    • 元组关系演算: 变元取值为元组, 元组变量
      $n$元关系$R$->谓词$R(t)$, $t$为元组变量, $t(i)$为关系$R$中第$i$属性
    • 域关系演算: 变元取值为单个属性值, 域变量
      $n$元关系$R$->$n$元谓词$R(x_1,x_2,\cdots,x_n)$, $x_i$为属性变量, 为关系$R$中第$i$属性
  • 关系表示
    • 关系$R$中的每个元组都是成真指派, 其他不出现在$R$中的任何元组都是成假指派
    • 元组关系演算: $R=\{t|P(t)\}$
    • 域关系演算: $R=\{<x_1,x_2,\cdots,x_n>|P(x_1,x_2,\cdots,x_n)\}$

关系操纵的表示

  • 并
    $$R\cup S=\{t|R(t)\vee S(t)\}$$
  • 差
    $$R-S=\{t|R(t)\wedge \neg S(t)\}$$
  • 选择
    $$\sigma_F(R)=\{t|R(t)\wedge F\}$$
  • 投影
    $$\pi_{A_{i_1},A_{i_2},\cdots,A_{i_k}}(R)=\{u^{(k)}|\exists t, (R(t)\wedge \bigwedge^ku(k)=t(i_k))\}$$
  • 笛卡尔积
    $$R\times S=\{t^{(m+n)}|\exists u\exists v, (R(u)\wedge S(v)\wedge\bigwedge_{i=1}^m t(i) = u(i)\wedge \bigwedge_{j=1}^n t(m+j)=v(j))\}$$
  • 关系演算表达式
    $\{t|\phi(t)\}$, 简写为$\phi(t)$
  • 公式, 原子公式: 见数理逻辑
  • 优先顺序
    • 比较运算符>量词>否定操作>逻辑运算符, 有括号的优先

关系演算的例子

  • 投影
    $$\pi_{A_{1},A_{2},\cdots,A_{k}}(R)=\exists x_{k+1},x_{k+2},\cdots ,x_n(R(x_1,x_2,\cdots,x_n))$$
  • 选择
    $$\sigma_F(R)=R(x_1,x_2,\cdots,x_n)\wedge F$$
    • 相等比较可以直接用常量代替: $\sigma_{x_1=’a’}(R)=R(‘a’,x_2,\cdots,x_n)\wedge F$
  • 笛卡尔积
    $$R\times S = R(p)\wedge S(q)$$
  • $\theta$-联接
    $$R\underset{F}{\bowtie} S = R(p)\wedge S(q)\wedge F$$
  • 自然联接
    $$R\bowtie S = R(x,y,z)\wedge S(t,u,v)$$
  • 自联接, 重命名
    $$R(x, g_1)\wedge R(x, g_2)$$
  • 除法
    $$R\div S=\forall y(S(y)\rightarrow R(x,y))$$
  • 删除
    $$R-S = R(u)\wedge \neg S$$
  • 插入
    $$R\cup S = R(t)\vee S(t)$$
  • 修改 = 删除再插入

关系演算的安全限制

  • 无限性问题
    • 无限关系: 无限个元组
    • 无穷验证: 量词引发无穷验证
  • 安全公式: 不产生无限性问题的公式
  • 约束集: $\text{DOM}(\phi)$
    • 构成: 公式中出现的关系中的某些分量, 公式中显式出现的常量符号
    • 以公式$\phi$作特性可以构造出一个元组集合，其中的每个元组只能由出现在$\text{DOM}(\phi)$中的符号构成，则这样的公式$\phi$是安全的
  • 判定条件
    • 如$t$满足公式$\phi$，则$t$的每个分量必定是$\text{DOM}(\phi)$的元素
      不产生无限关系
    • 对$\phi$中每一个形为$\exists t(W(t))$的子公式，若 t满足 W, 则$t$的每个分量一定属于$\text{DOM}(\phi)$
      不因为量词$\exists$而无穷验证
    • 对$\phi$中每一形为$\forall t(W(t))$的子公式，如果t 的任一分量不在 $\text{DOM}(\phi)$中，则$t$必定满足W
      不因为量词$\forall$而无穷验证

关系代数与关系演算

  • ‘关系代数’ 等价于 ‘安全的关系演算’
    • 用关系演算表达式可以表示关系代数中的五种基本运算
    • 用关系代数表达式可以表示安全的关系演算
      • 可以将一个安全的关系演算公式转换成等价的一个关系代数表达式
      • 关系演算公式的构成方式: 原子公式, 原子公式的量词和演算
      • 原子公式的表示: 量词/属性间比较/属性与常量比较
  • 公式的表示
    • $\phi_1\wedge\phi_2$
      • 有公共变元, 等价于自然联接$R_1\bowtie R_2$
      • 无公共变元, 等价于笛卡尔乘积$R_1\times R_2$
    • $\phi_1\vee\phi_2$: $R_1\cup R_2$
    • $\phi_1\rightarrow\phi_2$: $R_2\div R_1$
    • $\neg\phi$: $(\prod^nD_i)-R$, $D_i$为第$i$个自由变元的值域
    • $\exists r(\phi)$: $\pi_{A_1,A_2,\cdots,A_k}(R)$
    • $\forall r(\phi)$: $R\div S$
  • 完备系统
    • 能够提供关系代数的五种基本运算功能的关系模型系统
    • 具有安全的关系演算功能的关系模型系统