开始的话

我要学的是CMU-15445，数据库系统导论。

正文

DATABASE

DEFINITION:organized collection of inter-related data that models some aspect of the real world.

Databases are the core componenet of most computer applications.

DATABASE EXAMPLE

Create a database that models a digital music store to keep track of artists and albums.

Things we need:

• Information of artists
• albums those artists realsed

store our databased as comma-separated value(CSV) files that we manage ourselves in our application code:

• –>use a separate file per entity
• –>The application must parse the files each time they want to read/update records

here is the file:

# Artists(name,year,country)
"wutong clan",1992,"USA"
"notorious BIG",1992,"USA"
"GZA",1992,"USA"

here’s the code(python,aim to find the birth year of “GZA”):

for line in file.readlines()
    record = parse(line)
    if record[0]=="GZA"
        print(int(record[1]))

这个代码很糟糕，因为它慢，而且不可靠

FLAT FILES : DATA INTEGRITY

flat files:平面文件，eg:CSV,JSON,XML,日志等

它有如下弊端：

• 数据冗余不一致（浪费空间，插入异常，删除异常，更新异常）
• 数据访问困难（需要full file scan）
• 并发访问困难（需要应用程序设计一个复杂的并发处理机制）
• 原子性问题（比如转账，需要实现事物的原子性）
• 安全性和权限控制（对于文件来说，用户要么能读取整个文件，要么完全不能读。）

WE NEED DBMS(database management system)!!!

DBMS通过提供以下核心功能，系统性地解决了平面文件的问题：

• 数据模型 (Data Model): 如关系模型，结构化地组织数据，减少冗余。
• 查询语言 (Query Language): 如SQL，让复杂的数据访问变得简单高效。
• 并发控制 (Concurrency Control): 保证多用户同时访问数据时的一致性。
• 事务管理 (Transaction Management): 保证操作的原子性（ACID特性中的’A’）。
• 数据持久化和恢复 (Durability & Recovery): 确保系统崩溃后数据不会丢失或损坏。
• 安全和权限管理 (Security & Authorization): 提供精细的访问控制。

DBMS

DBMS:solfware that allows application to store and analyze information in a database.

A general-purpose DBMS supports the follow:

• definition
• creation
• querying
• updating
• administration

DBMS IS IN ACCORDANCE WITH DATA MODEL!

DATA MODEL

• Relational：数据被组织在一系列二维的表 (Table/Relation) 中。每个表由行 (Row/Tuple) 和列 (Column/Attribute) 组成。通过键 (Key) 和外键 (Foreign Key) 来建立表与表之间的关系。
• Key/Value：这是最简单的数据模型。数据以键值对 (Key-Value Pair) 的形式存储。你可以把它想象成一个巨大的哈希表 (Dictionary/Map)。
• Graph：直接以节点 (Node/Vertex) 和边 (Edge/Relationship) 的形式来存储数据，专门用于表示实体之间的复杂关系。
• Document/XML/Object： 数据以独立的文档 (Document) 形式存储，最常见的格式是 JSON 或 BSON (Binary JSON)。每个文档都是一个自包含的数据单元，可以有复杂的嵌套结构。
• wide-column/Column-family：可以看作是二维的键值模型。数据存储在表中，但表的列不是固定的。每行可以有不同数量、不同名称的列。
• Array/Matrix/Vectors：将数据存储为多维数组 (Array) 或矩阵 (Matrix)。每个元素可以通过其坐标进行高效访问。近年来，向量 (Vector) 模型也因AI而兴起。
• Hierarchical：数据被组织成一个树状结构。每个记录只有一个父节点，但可以有多个子节点。
• Network：是层次模型的扩展，允许一个记录有多个父节点。数据结构是一个有向图。
• multi-value：是关系模型的一个变种，允许一个属性（字段）存储多个值，而不是像关系模型那样要求原子性（1NF）。

有关relational的重点：

• ACID: 保证事务的原子性、一致性、隔离性、持久性。这是关系型数据库的基石。
• 范式 (Normalization): 如第一范式(1NF)、第二范式(2NF)、第三范式(3NF)，是一套减少数据冗余、保证数据一致性的设计理论。
• SQL (Structured Query Language): 用于操作和查询关系数据的标准语言。
• 索引 (Indexing): 通常使用B+树等结构来加速数据检索。

典型的系统有：MySQL, PostgreSQL, Oracle, SQL Server, SQLite.

有关数据模型和模式

一个很好的比喻是建房子

数据模型 (Data Model) -> 建筑风格/蓝图的规则 (The Rules of Architecture)

包括元素、关系和约束

模式 (Schema) -> 具体房子的设计图

假设我们要为一个大学课程注册系统设计数据库，我们选择了关系模型 (Data Model)。
那么，这个系统的模式 (Schema) 可能就是下面这样的描述：

1. 学生表 (Students Table):
   • 包含三个字段：student_id (整数, 主键), name (字符串), email (字符串)。
   • 约束：student_id 必须唯一且不能为空。email 必须唯一。
2. 课程表 (Courses Table):
   • 包含三个字段：course_id (字符串, 主键), title (字符串), credits (整数)。
   • 约束：course_id 必须唯一。credits 必须是正数。
3. 注册表 (Enrollments Table):
   • 包含两个字段：student_id (整数), course_id (字符串)。
   • 这是用来连接学生和课程的关系表。
   • 约束：(student_id, course_id) 的组合必须唯一。student_id必须是学生表中存在的值（外键约束）。course_id必须是课程表中存在的值（外键约束）。

this can call a schema

History of the relational model

Early database applications were difficult to build and maintain on available DBMS in 1960s.

–>example:IDS,IMS,CODASYL

–>computer is expensive and labor is cheap

Ted Codd,a mathematician at IBM research in late 1960s.He is a genius.He invented relational model and conviced others to apply it.After that,IBM released SQL.Today, most of databases use relational model.

RELATIONAL MODEL

1.

关系（relation）–> 元组集合or表（table）

元组（tuple）–> 记录or行（roe）

属性（attribute）–> 列（column）

域：属性的取值范围，比如数据结构INT,FLOAT之类的

2.键（特殊的属性）

主键：一个或者多个属性集合，唯一明确表示表中的每一个元组

1.唯一性 2.非空性

外键：一个表中一个或者多个属性，其值引用了另一个或者同一个表中的主键

当我们谈论外键时，其实涉及了三个关键元素：

1. 子表/引用表 (Child/Referencing Table)：包含外键列的表。
2. 父表/被引用表 (Parent/Referenced Table)：外键所引用的主键所在的表。
3. 外键约束 (Foreign Key Constraint)：一个施加在子表列上的规则，确保它的值在父表的主键列中存在。

超键：一个或者多个属性的集合，其值能够唯一标识表中的一行

students表中，student_id是超键，（student_id,name）也是超键。

候选键：一个最小的超键（其任何真子集都不是超键）

它和主键的区别是一张表中有很多候选键，仅有一个主键

3.约束

1)域约束：属性的取值应该在指定域内

age：INTGER gender:{‘male’,’female’,’other’}

2)NOT NULL约束

3)唯一约束

4)检查约束：

CHECK(price>0)

CHECK(end_time>=start_time)

5)引用完整性约束，也叫外键约束

级联操作：

ON DELETE CASCADE

主表中的行被删除，所有表中的相关记录被同时删除

ON DELETE SET NULL

主表中的行被删除，该记录的外键被列为NULL

DATA MANUPULATION LANGUAGE(DML)

Procedural:

–>The query specifies the (high level) strategy to find the desired reslut based on sets/bags.

relational algebra关系代数

Non-Procedural:

–>The query specifies only what data is wanted and not how to find it.

relational caclcus关系演算

RELATIONAL ALGEBRA

基于集合论、过程式、查询语言

operator

1.select($\sigma$)

从一个关系中筛选出特定的行

$\sigma_predicate(R)$

eg：$\sigma_{gpa>3.5}(students)$

2.投影（projection,$\pi$）

从一个关系中选出特定列并且自动去除重复行

$\pi_{a_1,a_2,…,a_n}(R)$

3.并（Union,U）

合并两个具有相同结构的关系（列数和类型相同）并且去除重复行

4.差（Set Difference,-）

返回第一个关系中存在，第二个关系中不存在的行

5.笛卡尔积（Cartesian Product,x）

将两个关系中的所有行两两组合，形成一个更大的关系

6.重命名（Rename,\rho）

为关系或者属性赋予了新的名字，用于处理复杂查询（自连接）时非常有用

复合运算符

连接：（Join）

两个关系通过某个共同的条件（通常是外键和主键相等）合并起来

$\sigma_{R.key=S.key}(RxS)$

一个例子，查询CMU-15445所有学生的名字

\sigma_{course_id}='15445'
(result_step1) JOIN Enrollments
(result_steo2) JOIN Students
\pi_{name}{result_step3}

对于我们使用的SQL,我们提交一个SQL,查询引擎生成一个或者多个等价的关系代数执行计划

RELATIONAL CALCULUS

值得注意的是关系演算和关系代数等价。以下两种类别也是等价的。

1.元组关系演算（TRC）

寻找符合特定条件的元组

{t|P(t)}

“寻找满足P条件的元组”或者“返回所有的元组t,使得谓词(Predicate)P(t)为真”

原子形式：

• R(t): 元组 t 属于关系 R。
• t.A op s.B: 元组 t 的属性 A 与元组 s 的属性 B 满足 op 操作（op 可以是 =, <, >, ≠ 等）。
• t.A op c: 元组 t 的属性 A 与常量 c 满足 op 操作。

量词：

存在量词和全称量词

假设我们有两个关系：

• Students(sID, name, major)
• Enrolled(sID, cID)

查询所有计算机专业学生：

TRC写法：

{ t.name | t ∈ Students ∧ t.major = "CS" }

SQL写法：

SELECT S.name
FROM Students AS S
WHERE S.major = 'CS';

2.域关系演算（DRC）

DRC 的核心思想是“寻找由域变量 (domain variables) 组成的元组，这些域变量的值需要满足特定条件”。

同样的例子DRC写法：

{ <n> | ∃id, m ( <id, n, m> ∈ Students ∧ m = "CS" ) }

返回所有由单个值 ＜n＞ 组成的元组，要求存在某个 id 值和 m 值，使得：

1. 由 ＜id, n, m＞ 构成的元组属于 Students 关系。
2. 并且 m 的值等于 “CS”。”

DRC 是查询语言 QBE (Query-By-Example) 的理论基础。

掌握了用这两种方法说出我们的要求，就能够写好SQL.