本笔记中 key 翻译为 ”码“，熟悉”键“说法的同志可以自行转译

  • 教材：数据库系统概论（第六版） 王珊
  • CMU15445

系统概论

  • 数据 - 数据库 - 数据库管理系统 - 数据库系统

  • 概念：

    • 实体 Entity
    • 属性 Attribute
    • 码 Key
    • 域 Domain
    • 实体类型 Entity Type
    • 实体集 Entity Set
    • 联系 Relationship

  • ER 图

    • Entity: 矩形
    • Attribute: 椭圆
    • Join/Relationship: 菱形，标注类型 (1:1, 1:n, m:n)；联系也有属性
    • Edge: 直线（无向！）
    • 三关联：仅“两两之间存在联系”且描述用一句话完成

  • 数据模型

    • 组成
      • 数据结构：联系的意义；常用于命名数据模型（层次，关系）
      • 数据操作：CURD，and more…
      • 完整性约束
    • 层次模型：树状
      • 特点：parent 唯一，仅一对多，需要完整路径，约束需要 parent 存在 (on delete cascade)
    • 网状：层次的扩展
    • 关系模型：
      • Relation, Tuple (Row), Attribute (Column)
      • 关系：元组的集合
      • Key, Domain, Component,
      • 数据结构
        • 实体：用关系表示
        • 一对一/一对多：隐含在 Attribute
        • 多对多：新关系
      • 完整性：实体完整，参照完整，属性完整，用户定义的完整性

  • 数据库系统模式

    • Type-Value
    • Schema: 数据库全体数据的逻辑结构和特征的描述；描述语言：DDL
    • Instance of Schema: 模式的一个具体值；数据库某一刻状态
    • 三级模式：
      • External Schema 外模式: 对应视图（用户使用的局部数据）；一个数据库可以有多个外模式；外模式与应用一对多
      • 模式/逻辑模式：存储
      • Internal Schema 内模式: 数据物理结构和存储方式的描述；一个数据库只有一个 IS
    • 二级映像：
      • 外模式/模式映像，模式/内模式映像
      • 保证数据的物理独立性
    • 数据库管理员：
      • 确定数据库中的信息内容和结构
      • 决定数据库的存储结构和存取策略
      • 定义数据的安全性要求和完整性约束条件
      • 监控数据库的使用和运行
      • 数据库的改进和重组
      • 数据库重构

关系模型和理论

  • 关系数据模型
    • 数据结构：关系（实体/联系）（逻辑结构：二维表）
    • 操作：
      • 查询：select, map, join, union
      • 更新：insert, delete, update
  • 关系：
    • Domain 域：一组具有相同数据类型的值的集合 （对应数据类型）
    • Cartesian Product 笛卡尔积：合成元组
    • Cardinal number 基数
    • Relation 关系：$R\subseteq D_1\times D_2\times\cdots\times D_n$ （$n$ 为 degree 目/度）
      • $n=1$: unary relation
      • $n=2$: binary relation
    • Tuple 元组 $t\in R$
      • 视语境可能不是笛卡尔积元组，而是 Attribute-keyed dict，因此元素间可无序
    • Relation Representaion: 以 tuple 为 row 的二维表
    • Attribute: 为加以区分为 column 起名
    • key 码：作为标识的某 attribute
      • Candidate key 候选码：某 attribute group 能唯一标识而子集不能
      • All key 全码：Candidate key = R
      • Primary key: 多个 candidate 选一；其组成 attribute 为 prime attribute
      • 不在任何 candidate 中的 attribute 是 non-key attribute
    • 分类：
      • 基本表：存储表
      • 查询表：查询结果对应表
      • 视图表：查询结果
  • 关系模式：
    • R(属性，域，属性->域，属性间数据依赖)
    • 简记为 $R(A_1,A_2,\cdots,A_n)$, $A_k$ 为属性名
    • 关系模式和关系往往统称为关系，通过语境区分
  • 关系操作：
    • 操作：选择、投影、连接、除、交、并、差、笛卡儿积、插入、删除、修改
    • 特点：集合
    • 语言：关系代数（用集合）/关系演算（用谓词）
      • 元组关系演算语言 APLHA, QUEL
      • 域关系演算语言 QBE
      • 关系代数语言 ISBL
      • 关系代数+关系演算 SQL
      • 特点：非过程化，能嵌入高级语言，三种能力等价
  • 完整性：实体，参照，用户定义
    • 实体完整性：所有主属性非空
    • 参照完整性：外码
      • 外码可以为空（但注意主属性有实体完整性）
      • F是R的非主属性，若F是S的主码 Ks，则 F 为 R 外码
        • R 为参照关系 referencing relation, S 为被参照关系 referenced relation / 目标关系 target relation
        • R 可能 = S
        • F 域 Ks 域相同，名可能不同
    • 用户定义完整性：依赖数据库实现，如非空、唯一…
  • 关系代数：
    • 运算符：并差交积，选择、投影、链接、除，与或非
    • $R, t\in R, t[A_i]$: 关系，元组，分量
    • $A, t[A], \bar A$: 属性组，分量，剩余属性组
    • $\overparen{t_r t_s}$: 元组连接
    • 象集 $Z_x={t[Z] | t\in R, t[X] = x}$ (select Z where X=x)
    • 运算
      • 并 union，差 diff，交 intersection：关系同外模式
      • 广义笛卡尔积
    • 关系运算
      • selection / restriction 选择：取行； $\sigma_F(R)={t|t\in R \wedge F(t) = True}$
      • Projection 投影：取列
      • join / theta join：从笛卡儿积选择元组 $R \bowtie_{A\theta B} S$
        • 等值连接
        • 自然连接：去掉重复列
        • 外连接：保留舍弃元组、其他填空
      • 除 $R\div S$：对于 R(X,Y), S(Y,Z)
        • SELECT DISTINCT X FROM R R1 WHERE NOT EXISTS (
        • SELECT Y FROM S EXCEPT
        • SELECT Y FROM R AS R2 WHERE R2.X = R1.X)
        • Aliternative:
        • SELECT R.X FROM R JOIN S ON R.Y = S.Y GROUP BY R.X HAVING
        • COUNT(DISTINCT R.Y) =
        • (SELECT COUNT(DISTINCT Y) FROM S);

关系规范化

  • 关系模式：R(U 属性，D 域，DOM 属性->域，F 属性间数据依赖)（简化：R(U, F)）
  • 数据依赖：限制取值范围，定义相互关联，函数依赖/多值依赖（一对一/一对多）；会导致表设计问题
    • 函数依赖 X->Y：在一个关系的属性中，X 可以推导 Y，则Y函数依赖于X；X 为 determinant 决定因素
    • 由语义设计定义，决定表设计而非数据库约束
    • 平凡函数依赖：X 可以推导 Y，因为/且 Y 为 X 子属性组
    • 完全函数依赖：X -F-> Y, X 子属性组 -\> Y （不完全: X-P->Y）
    • 在关系模式$R(U)$中，如果$X \rightarrow Y (Y \subsetneq X)$，$Y \nrightarrow X$，$Y \rightarrow Z (Z \subsetneq Y)$，则称$Z$对$X$传递函数依赖，记为$X \xrightarrow{\text{传递}} Z$。注：如果$Y \rightarrow X$，即$X \leftrightarrow Y$，则$X \xrightarrow{\text{直接}} Z$。
  • 码：默认为候选码
    • 候选码 $K$：$R(U,F)$ 中，$K\subseteq U$，$K \xrightarrow{F} U$
    • 超码 $K$：$R(U,F)$ 中，$K\subseteq U$，$K \xrightarrow{P} U$
    • 其余见 关系模型-关系-码
  • 范式
    • 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。
    • 1NF: 所有属性都不可分，同一列中的所有值必须是相同数据类型，每个字段只能存储一个值. *jsonb 类型
    • 2NF: 每一个非主属性都完全函数依赖于 R 的码；消除非码部分依赖
    • 3NF: 无（非主属性对码）传递函数依赖；消除非主对非主（非主对码的传递）
    • BCNF：所有非平凡 X->Y 有 X 包含候选码；消除主属性对非主依赖（主对码的传递）
    • 4NF: 消除非平凡且非函数依赖的多值依赖
  • 候选码求解：分 L, R, N, LR，遍历 $L,N \subseteq K \subseteq L,LR,N$
  • Armstrong公理系统：$F\to F^+$ 是有效且完备的
  • 最小依赖集求解：
    1. 分解右边 $X\to Y_1Y_2$ 为 $X\to Y_1, X\to Y_2$
    2. 去除依赖冗余：逐个去掉求闭包
    3. 去除左边冗余：逐个减左求闭包
  • 分解标准：无损连接性，函数依赖性 （等价）

SQL

  • Structured Query Language
  • Table
    • CREATE SCHEMA myschema AUTHORIZATION john;
    • DROP SCHEMA myschema CASCADE;
    • `CREATE TABLE users (
      • `id INT PRIMARY KEY, name VARCHAR(50) NOT NULL,
      • CONSTRAINT fk_dept FOREIGN KEY (dept_id) REFERENCES departments(id));
    • ALTER TABLE users
      • ADD COLUMN email VARCHAR(100),
      • ADD CONSTRAINT unique_email UNIQUE (email),
      • DROP COLUMN phone CASCADE,
      • DROP CONSTRAINT pk_users CASCADE,
      • ALTER COLUMN name TYPE VARCHAR(100);
    • DROP TABLE users RESTRICT;
  • Index
    • CREATE [UNIQUE] [CLUSTER] INDEX ON <name> (col [ASC|DESC]...)
    • ALTER INDEX <name> RENAME TO <name>
  • Select
    • Basic
      • SELECT DISTINCT department, COUNT(*) AS emp_count FROM employees
      • WHERE salary > 50000
      • GROUP BY department
      • HAVING COUNT(*) > 5 (per group)
      • `ORDER BY emp_count DESC
      • LIMIT 114 OFFSET 514;
    • Condition
      • = > < >= <= != <> !> !<
      • NOT, BETWEEN AND, IN, IS NULL, AND, OR
      • LIKE <match> [ESCAPE <char>]；%: .*, _: .,
      • Calc: COUNT, SUM, AVG, MAX, MIN （注意 count(col) ignores null，可 DISTINCT）
    • Case
      • SELECT (CASE department WHEN 'IT' THEN 'Technology' END) AS dept_name FROM employees;
      • 可以用于不能使用 where/having 的地方（纯值）
    • Join
      • INNER|LEFT|RIGHT|FULL OUTER|CROSS|SELF|NATURAL JOIN
      • SELECT cid, uid FROM courses c LEFT JOIN users u ON u.uid = c.manager
      • 等值 SELECT cid, uid FROM courses c, users u WHERE uid = c.manager
      • 重复时取笛卡尔积
      • 集合相等
        • NOT EXISTS (SELECT s FROM S WHERE NOT EXISTS(SELECT t FROM T WHERE s = t))
        • COUNT(SELECT DISTINCT t FROM T WHERE t IN (SELECT s FROM S)) = (SELECT COUNT(DISTINCT *) FROM S)
    • Chain
      • IN, ANY, ALL, EXISTS （不同于 <ANY 之类）
      • 比较（单值）：一定要在比较符后
      • <cond> ANY|ALL(<subq>)
      • FROM (<subq>) AS <name>(<cols>)
    • Set
      • UNION [ALL], INTERSECT, EXCEPT
  • Update
    • INSERT INTO employees (id, name) VALUES (101, 'John Doe'), (102, 'Ben Dan');
    • INSERT INTO archived_orders (data) SELECT order_date FROM orders';
    • UPDATE products SET price = price * 1.1, stock = 0 WHERE category = 'ee';
    • DELETE FROM employees WHERE id = 101;
  • Null
    • unique, not null, pk are nonnull
    • algebra: null; compare: unknown (or 短路)
  • View
    • 视图实体化法/视图消解法
    • CREATE VIEW ds (name, count, salary) AS SELECT department, COUNT(*), AVG(salary) FROM employees GROUP BY department WITH CHECK OPTION;
    • DROP VIEW ds [CASCADE]
  • Auth
    • CREATE USER john WITH DBA|RESOURCE|CONNECT PASSWORD 'secret123';
    • CREATE ROLE admin_user
    • GRANT admin_user TO wsm
    • GRANT ALL PRIVILEGES ON DATABASE company_db TO admin_user;
    • GRANT SELECT, UPDATE(uid) ON TABLE sales_report TO manager WITH GRANT OPTION; （可以再授予）
    • GRANT EXECUTE ON FUNCTION calculate_bonus TO PUBLIC;
    • REVOKE SELECT, INSERT ON TABLE employees FROM user1 CASCADE;

数据库设计

  • 方法论：New Orleans, ER Model, 3NF, ODL
  • 需求分析：
    • 结构化分析方法：抽象为信息要求、处理要求，分解处理功能和数据，迭代
    • 数据字典：数据项 数据结构 数据流 数据存储 处理过程
  • 概念结构设计：E-R 图
    • 方法：自顶向下，自底向上，逐步扩张，混合策略
    • 抽象：分类 (member of，实体)，聚集 (part of，属性)，概括 (subset of，子类)
    • 局部视图设计->整体概念结构
    • 属性：不可分割，不与其他联系
    • 合并：一次集成/逐步累积式
    • 冲突：属性（空间/单位），命名，结构（同实体 属性次序/个数，联系，抽象）
    • 冗余：逻辑分析/规范化（消除可推导联系）
  • 逻辑结构设计：关系模式
    • 实体/联系
    • 合并：同码，1:1/1:n 联系
    • 规范化：数据依赖，冗余联系，范式，分解
    • 分解：水平分解（分表），垂直分解（属性分解）
  • 物理设计：索引和聚簇
    • 加 btree index：作为条件/连接，求最大/最小，有排序 order/group
    • hash index：等值连接/条件

信息安全

  • 安全级别
    • 1991 TCSEC/TDI；安全级别划分 (L- DC(123)B(123)A -H)
    • CC标准 (L - EAL1-7 -H)
  • 安全性控制：用户，存取控制，视图，审计，密码
  • MAC：分级，可写高读低，标记数据绑定
  • 统计数据库：何意味