Databases

资料

  1. cs-self-learning/docs/数据库系统/15445.md at master · PKUFlyingPig/cs-self-learning
  2. Schedule | CMU 15-445/645 :: Intro to Database Systems (Spring 2023)

由于2022的有对应的网课， 我觉得使用2022的配套练习会比较合适。
Schedule | CMU 15-445/645 :: Intro to Database Systems (Fall 2022)
other year:CMU 15-445 :: Intro to Database Systems (Fall 2025)
discord Channel:
Discord | #welcome | CMU 15-445/645 (unofficial)

(16 封私信 / 42 条消息) 2022 CMU-15445 全总结 - 知乎
CMU15-445 数据库实验全满分通过笔记 2021 Fall bustub-cmudb lab_github cmu 15-445 2021-CSDN博客
Relational Data Model | open-courses

Lecture1

此课程重点是如何构建数据库，而不是如何使用数据库。

非官方学生通过这个来评测

测评：15-445/645 (Non-CMU) Dashboard | Gradescope

什么是数据库？
数据库是组织化的、相互关联的数据集合。
e.g:创建一个数字音乐商店数据库，包含艺术家和专辑信息。

关系模型：

  • 关系模型：基于关系的数据库抽象，避免维护开销。
  • 三个组成部分：
    • 结构：定义数据库的关系及其内容。
    • 完整性：确保数据库内容满足约束条件。
    • 操作：访问和修改数据库内容的编程接口。
  • 关系是一个无序的集合，包含代表实体的属性关系
  • 主键：唯一表示关系中的一个元组
  • 外键：指定一个关系中的属性必须映射到另一个关系中的元组

关系代数：

  • 关系代数：用于检索和操作关系中的元组的基本操作。
  • 操作符：
    • 选择（σ）：根据条件筛选元组。
    • 投影（π）：选择特定的属性。
    • 并集（∪）：合并两个关系的元组。
    • 交集（∩）：找出两个关系中共有的元组。
    • 差集（–）：找出第一个关系中有而第二个关系中没有的元组。
    • 笛卡尔积（×）：生成两个关系中所有可能的元组组合。
    • 连接（⋈）：根据共同属性组合两个关系的元组。
  • 额外操作符：重命名（ρ）、赋值（←）、去重（δ）、聚合（γ）、排序（τ）和除法（÷）。

Notes1：

FlatFile Strawman

数据库经常以CSV(comma-separated value)文件的形式存储，由DBMS进行管理。每次应用程序要读取或者更新记录时，都必须解析文件

以数字音乐商店的例子，会有两个文件，一是艺术家，二是专辑。

每个实体都有自己的属性集，所以在每个文件中，不同的记录都用新的行来划分，而一条记录中的每个相应属性都用逗号隔开

e.g:

1
2
3
Wu-Tang Clan, 1992, USA 
Notorious BIG, 1992, USA 
GZE, 1990, USA

Flat File：

  • Data Integrity 数据完整性
  • Implementation 实现
  • Durability 持久性

DBMS

DBMS(database management system): a software that allows applications to store and analyze infomation in a database

  • 允许增删查改
  • Data model：
    数据模型是描述数据库中数据的概念的集合。
  • Schema：
    模式是对基于数据模型的特定数据集合的描述。

关系模型

The relational model defines a database abstraction based on relations to avoid maintenance overhead. It has three key points:
• Store database in simple data structures (relations).
• Access data through high-level language, DBMS figures out best execution strategy.
• Physical storage left up to the DBMS implementation.

  • 用简单的数据结构保存，用高级语言来访问，让DBMS来执行最优策略以及处理物理层存储

关系模型定义的三个概念:

  • Structure：关系定义和内容。也就是关系具有的属性以及可以有的值。
  • Integrity：确保数据库的内容满足约束条件。比如：年份必须是数字。
  • Manipulation:如何访问和修改数据库的内容。

关系是一组无序的集合。因为是无序的，所以DBMS可以用它想要的任何方式存储它们，并允许优化。
元组指的是关系中的一组属性值
A relation with n attributes is called an n-ary relation、

键–Key

  • A relation’s primary key uniquely identifies a single tuple.
    一个关系的primary key唯一的定义了单个元组。很多DBMSs都支持autogenerated keys，所以程序就不需要手动增加了，但primary key还是在某些DBMSs是需要的。

  • Primary key：唯一的定义了单个元组。

  • Foreign key：指定一个关系中的属性必须映射到另一个关系中的元组。

DML

  • Procedural: The query specifies the (high-level) strategy the DBMS should use to find the desired result based on sets / bags. (relational algebra)
    过程化DML：要求用户指定需要什么数据以及如何获得数据
  • Non-Procedural (Declarative): The query specifies only what data is wanted and not how to find it. (relational calculus)
    声明式DML：只要求指定需要什么数据

关系代数

一组基本操作，用于检索和操作关系中的图元。（跟离散数学关系比较大）

  • 操作符：
    • 选择（σ）：根据条件筛选元组。
    • 投影（π）：选择特定的属性。
    • 并集（∪）：合并两个关系的元组。
    • 交集（∩）：找出两个关系中共有的元组。
    • 差集（–）：找出第一个关系中有而第二个关系中没有的元组。
    • 笛卡尔积（×）：生成两个关系中所有可能的元组组合。
    • 连接（⋈）：根据共同属性组合两个关系的元组。

书本内容：

chap1

数据库管理系统（DBMS）由一个互相关联的数据的集合和一组用以访问这些数据的程序组成。这个数据集合称为数据库。

文件系统存储组织信息的弊端：

  • 数据的冗余和不一致：可能出现重复存储，这种冗余可能进一步导致不一致性
  • 数据访问困难
  • 数据孤立：数据分散在不同文件中
  • 完整性问题
  • 原子性问题
  • 并发访问异常
  • 安全性问题

数据视图

数据库给用户提供数据的抽象视图。
数据库可以分为三个层次：物理层、逻辑层和视图层
物理层描述了数据是如何存储的
逻辑层描述了数据库中存储什么数据以及数据之间的关系
视图层只描述整个数据库的某个部分

  • 视图层有多个视图，每个用户只需要访问数据库的一部分，通过划分视图来简化用户与系统的交互。

数据模型

数据模型：描述数据、数据联系、数据语义以及一致性约束的概念工具集合
数据模型提供了一种描述物理层、逻辑层以及视图层数据库设计的方式

数据模型可以分为四类：

  • 关系模型：用表的集合来表示数据和数据间的联系。是基于记录的模型的一种。
  • 实体-联系模型
  • 基于对象的数据模型
  • 半结构化数据模型

数据库语言

数据库系统提供数据定义语言来定义数据库模式，以及数据操纵语言来表达数据库的查询和更新

数据操纵语言DML

使得用户可以访问或操纵数据，进行增删查改
过程化DML：要求用户指定需要什么数据以及如何获得数据
声明式DML：只要求指定需要什么数据

数据定义语言DDL

用于定义数据库模式的实现细节

关系数据库
关系数据库基于关系模型。

Project 0

需要实现一个基于并发Trie（字典树）的键值存储系统。

项目要求：

  1. 单线程Trie实现
    • 实现 TrieNode 类：表示Trie中的单个节点，存储一个字符和子节点映射
    • 实现 TrieNodeWithValue 类：继承自 TrieNOde ，表示存储值的终端节点
    • 实现 Trie 类：支持插入、删除和查找操作
  2. 并发Trie实现
    • 使用读写锁实现线程安全
    • 查找操作获取读锁，插入和删除操作获得写锁

关键概念理解

Trie字典树，例如存储”HELLO”、”HAT”和”HAVE”

需要实现的功能：

  • 插入操作
    • 沿着键的字符便利Trie，必要时创建新节点
    • 处理三种情况
      • 终端节点不存在–创建新终端节点
      • 节点存在但不是终端节点–转换为终端节点
      • 已经是终端节点–返回失败（不允许重复键）
  • 删除操作
    • 找到键对应的终端节点
    • 将 is_end_ 标志为false
    • 递归删除没有子节点的空节点
  • 查找操作
    • 遍历Trie找到终端节点
    • 检查值类型是否匹配
    • 使用dynamic_cast检查类型

实现建议

  • 分步实现
    • 先完成单线程版本，再添加并发支持
    • 仔细处理unique_ptr的所有权
  • 并发控制
    • 使用读写锁保护根节点
    • 查找使用读锁，插入/删除使用写锁
    • 确保在函数返回前释放锁
学习笔记 > database
#学习笔记 #database
Databases
https://pqcu77.github.io/2025/07/17/databases/
作者
linqt
发布于
2025年7月17日
许可协议