第一章： punched cards 的回响：关系模型的诞生与早期挑战 / Chapter 1: Echoes of Punched Cards: The Birth of the Relational Model and Early Challenges

1970年6月，IBM圣约瑟实验室的一间办公室里，一位名叫埃德加·科德（Edgar F. Codd）的研究员递交了一份长达23页的内部报告，标题为《大型共享数据库的关系模型》（A Relational Model of Data for Large Shared Data Banks）。这份报告最初并未引起太多轰动——在当时的IBM，层次数据库系统IMS（Information Management System）正为航空航天和银行领域提供着稳定的数据服务，而基于CODASYL标准的网状数据库也在逐步推广。然而，正是这份被一些人视为“过于理论化”的文档，悄然埋下了引爆数据库管理革命的火种。要理解科德的革命性，必须回到那个“打孔卡的回响”时代。20世纪60年代，企业数据主要存储在磁带上，通过打孔卡输入。数据记录之间通过物理指针（如IMS中的“前向/后向指针”或CODASYL中的“集合成员”）紧密耦合，应用程序必须像侦探一样沿着这些指针链条追踪数据。这种设计在当时看来高效直接，却埋下了致命的隐患：数据结构与程序逻辑深度绑定，任何微小的模式变更都需重写大量导航代码；跨实体查询（如“找出所有在纽约的客户及其订单”）需要复杂的多步遍历，程序员不得不手工编写繁琐的循环和条件判断。数据不再是一种资产，反而成了需要小心翼翼维护的脆弱链条。

层次模型（Hierarchical Model）以树形结构组织数据，每个父记录可拥有多个子记录，但子记录只能有一个父——这种严格的父子关系虽然简化了某些一对多的场景（如“部门-员工”），却无法自然表达多对多关系（如“学生-课程”）。为了克服这一限制，系统引入了冗余数据或额外的关联记录，导致数据不一致的风险陡增。IBM的IMS是这一模型的典范，它使用物理指针（如“前向/后向指针”）在磁带上链接记录，应用程序必须显式地`GU`（Get Unique）或`GN`（Get Next）来遍历数据。以下是一个简化的IMS数据访问伪代码，展示了其繁琐性：

```python

IMS风格：通过指针遍历部门及其员工

department_pointer = locate_department("NY_SALES") employee_pointer = department_pointer.first_child # 手工跟随指针 while employee_pointer != NULL: process(employee_pointer.record) employee_pointer = employee_pointer.next_sibling # 继续遍历 ```

网状模型（Network Model）通过“记录类型”和“集合”概念放宽了层次限制，允许记录拥有多个父记录，从而更灵活地建模多对多关系。CODASYL（Conference on Data Systems Languages）委员会于1971年发布的DBTG报告定义了这一标准。然而，自由度的提升带来了复杂性：应用程序必须声明“路径”（通过` FIND `语句指定集合名和持有者记录），并管理“当前记录”和“区域”等状态。一个典型的CODASYL查询需要多步导航：

```cobol

• CODASYL风格：查找纽约客户的所有订单

EXEC CICS SEND MAP('CUSTOMER_MAP') END-EXEC. MOVE 'NY' TO CUST-STATE. FIND CUSTOMER RECORD USING CUST-KEY. IF DB-STATUS = '0000' FIND ORDER SET ORDER-OWNER PERFORM UNTIL DB-STATUS NOT = '0000' DISPLAY ORDER-AMOUNT FIND NEXT ORDER IN ORDER-OWNER END-PERFORM. END-IF. ```

这种“过程式”的数据访问将如何获取数据与需要什么数据混为一谈。程序员必须熟知物理存储结构，任何查询的修改都可能引发连锁的程序变更。数据独立性（Data Independence）——即应用程序不受底层存储变化影响——成为遥不可及的梦想。

科德的解决方案堪称数学的降维打击。他借鉴了1970年之前已成熟的关系代数（Relational Algebra，由E. F. Codd基于集合论和谓词逻辑提出）和关系演算（Relational Calculus），提出将所有数据统一为关系（Relation）——即二维表（Table），每行称为元组（Tuple），每列称为属性（Attribute）。表的本质是数学上的集合，其操作遵循严格的集合运算规则（并、交、差、笛卡尔积、选择、投影、连接）。这意味着： 1. 物理独立性：应用程序只关心“查询什么”，不关心“如何获取”。存储结构（索引、分区）的变化不影响SQL语句。 2. 逻辑独立性：表结构可演进（如增加列），只要保持原有列不变，旧查询仍可运行。 3. 声明式访问：用户只需描述目标数据集的特征，系统自动决定最优路径。

科德在论文中著名的“12条规则”（Codd's 12 Rules）系统化地定义了关系数据库管理系统（RDBMS）应具备的特性，从零级（仅支持关系）到完全级（支持全功能关系系统），为后来的系统评估提供了标尺。其中核心规则包括：

• **信息规则**：所有信息（包括元数据）都必须以关系形式显式表示，且唯一通过表值操作访问。
• **保证访问规则**：所有表必须通过关系代数能力（结合逻辑运算符）访问。
• ** Null 值规则**：系统必须支持缺失信息，且与真/假值逻辑一致。
• **动态联机目录**：数据库的描述（数据字典）必须像普通数据一样可查询。

然而，理论 elegance 不等于工程可行性。当IBM的 System R 项目（1974-1979）试图将科德的思想转化为第一个可工作的SQL引擎时，团队面临着三重挑战：查询语言的设计、查询优化的可行性、事务管理的实现。Donald Chamberlin 和 Raymond Boyce 在科德关系演算的基础上设计了 SEQUEL（Structured English Query Language，后因商标问题简化为SQL），旨在提供一种接近自然英语、非过程式的数据操作语言。一个简单的SQL查询：

```sql SELECT name, salary FROM employees WHERE dept = 'NY_SALES' AND salary > 50000; ```

对比等价的CODASYL或IMS代码，其简洁性一目了然。但System R的早期原型显示，这种“声明式”查询比手写导航代码慢几个数量级——这直接威胁到了系统的生存。如果关系模型只能带来开发效率却牺牲性能，企业用户不会买单。

查询优化器成为System R最关键的创新。其核心思想是：同一逻辑查询可以有多种物理执行计划，系统应选择代价最低者。优化器的工作流程可概括为： 1. 解析与规范化：将SQL解析为抽象语法树（AST），转换为关系代数表达式，并应用等价变换规则（如“选择下推”将`WHERE`条件提前到子查询执行）以减少中间结果集大小。 2. 计划生成：对每个关系操作（如连接），考虑不同算法（嵌套循环、排序合并、哈希连接）和不同索引使用方式，生成多个候选计划。 3. 代价估算：基于统计信息（表大小、列 Distinct 值数量、索引分布）估算每个计划的I/O、CPU成本。 4. 计划选择：选择总代价最小的计划。

下图以Mermaid展示了System R查询优化的简化流程，其中“等价变换”和“代价模型”是两大支柱：

```mermaid graph TD A[SQL查询文本] --> B[解析器<br/>生成抽象语法树] B --> C[规范化器<br/>应用等价变换] C --> D[逻辑计划树<br/>关系代数表达式] D --> E{计划生成器} E --> F[候选计划1<br/>嵌套循环+索引扫描] E --> G[候选计划2<br/>哈希连接+全表扫描] E --> H[候选计划3<br/>排序合并+索引扫描] F --> I[代价估算器<br/>基于统计信息] G --> I H --> I I --> J[选择最小代价计划] J --> K[物理执行引擎] ```

代价模型的准确性直接决定优化效果。System R引入了启发式规则（如“优先使用索引”）与基于统计的估算相结合的方法。例如，对于`WHERE salary > 50000`，优化器需估算满足条件的元组比例，这依赖于列直方图或均匀分布假设。早期系统统计信息不足，导致估算偏差，但“选择下推”等规则仍能带来显著收益。一个经典案例是：查询“找出在纽约且工资高于平均的销售员”，若先连接`employees`与`departments`再筛选，中间结果可能巨大；而先将`dept='NY_SALES'`下推到`departments`表，可大幅减少连接输入。

访问方法的选择同样关键。System R采用了B树索引（B-Tree Index）作为主要索引结构，其平衡性保证了O(log n)的查找、插入、删除性能。B树的节点设计允许高扇出（fan-out），减少磁盘I/O。一个简化的B树节点结构如下（PlantUML类图）：

```plantuml @startuml class BTreeNode { + is_leaf: boolean + keys: List<KeyType> + child_pointers: List<Pointer> + search(key): Integer + insert(key, value): void } class LeafNode extends BTreeNode { + values: List<Value> } class InternalNode extends BTreeNode { + child_nodes: List<BTreeNode> } BTreeNode <|-- LeafNode BTreeNode <|-- InternalNode @enduml ```

然而，索引并非万能。对于`SELECT * FROM large_table`这类全表扫描查询，索引反而增加I/O。优化器必须权衡：当筛选条件选择性高（返回少量行）时，索引扫描更优；当选择性低或需访问大部分列时，全表扫描更优。System R通过“索引覆盖”（Index-Only Scan）进一步优化：若查询所有列均包含在索引中，则无需回表。

事务管理是另一道难关。科德在1970年论文中已隐含了原子性（Atomicity）和一致性（Consistency）需求，但具体实现留给了工程团队。System R引入了两阶段锁协议（Two-Phase Locking, 2PL）保证可串行化：事务在释放任何锁之前必须获取所有所需锁（增长阶段），一旦释放锁则不能再获取新锁（缩减阶段）。这防止了死锁但可能引发死锁等待，因此需配合死锁检测（通过等待图）或超时机制。此外，Write-Ahead Logging（WAL）被用于保证持久性：在数据页写入磁盘前，日志必须先持久化。日志记录包含旧值（用于回滚）和新值（用于重做），确保系统崩溃后能恢复一致状态。

```mermaid sequenceDiagram participant T as Transaction participant L as Lock Manager participant D as Data Manager participant Log as Write-Ahead Log

T->>L: 请求锁（如X锁） L-->>T: 授予锁 T->>D: 修改数据页（内存中） T->>Log: 写入日志记录（旧值、新值） Note over Log: 日志必须先刷盘 T->>D: 提交请求 D->>Log: 强制日志刷盘（WAL） Log-->>D: 确认 D->>D: 标记事务提交 D->>L: 释放所有锁 ```

这些机制奠定了ACID（原子性、一致性、隔离性、持久性）的工程基础，但代价高昂：锁竞争降低并发，日志写入增加I/O。System R的工程师们在性能与正确性间反复权衡，例如引入锁粒度（行锁、页锁、表锁）和锁升级策略以平衡开销。

System R的攻坚不仅是技术胜利，更是组织创新的典范。团队打破了IBM传统的“大教堂”式开发，采用快速迭代、用户反馈驱动的“集市”模式。他们邀请内部用户（如IBM财务部门）试用原型，根据实际查询模式优化。1975年，System R发布了第一个支持多用户、SQL的版本，尽管当时仅支持有限的数据类型和简单查询。1979年，Oracle（前身Relational Software, Inc.）推出了首个商业SQL数据库，直接受益于System R的论文和原型。随后，IBM将System R技术商业化，诞生了DB2（1983年）；Ingres（加州大学伯克利分校项目）也采用了类似架构。关系数据库在80-90年代统治了企业市场，其核心——SQL与基于代价的优化——成为行业标准。

然而，System R的成功并非没有代价。早期版本在复杂连接查询上仍显吃力，内存有限导致频繁磁盘I/O；统计信息收集需手动运行，且无法反映实时数据分布；事务隔离级别默认可串行化，但许多应用实际只需“读已提交”（Read Committed），过度锁定抑制了并发。这些问题催生了后续的优化技术：动态统计信息、多版本并发控制（MVCC）、物化视图、并行执行等。但更深刻的挑战在远方：当数据量突破单机磁盘容量，当网络延迟成为瓶颈，当硬件故障成为常态，关系模型的“单一逻辑视图”将面临分布式世界的撕裂。科德的理论城堡需要新的砖石来加固——而这正是本书后续章节将探讨的：从B树到LSM树，从两阶段提交到分布式共识，数据之魂在规模与容错的洪流中不断演化。

回望1970年的那篇报告，科德或许未曾完全预见其思想将如何重塑数字世界。他当时只是试图为“共享数据库”找到一个数学上坚实、工程上可行的基础。但正是这种用数学简洁性对抗工程复杂性的信念，点燃了数据库领域的持续创新。每一代系统——从System R到现代云原生数据库——都在重复同样的核心博弈：在抽象与性能、统一与扩展、理论优雅与工程妥协之间寻找新的平衡点。而这一切，都始于打孔卡时代那些繁琐指针链条中，一个数学家对“表”的纯粹想象。

一、混乱的指针迷宫：层次与网状模型的工程困境

在科德提交那份划时代报告之前的十年，企业数据管理正深陷于一种被称为“过程式导航”的泥潭。应用程序员不再是在编写业务逻辑，而是在扮演数据侦探——他们的代码充斥着对物理存储结构的依赖，每一行代码都在诉说着“如何”而非“什么”。这种困境在两大主流模型中体现得淋漓尽致：IBM的层次模型（IMS） 和CODASYL标准的网状模型（如IDMS、ADABAS）。

1.1 层次模型：树的枷锁

层次模型以严格的树形结构组织数据，每个子记录（child）有且仅有一个父记录（parent），而父记录可拥有多个子记录。这种设计天然适合一对多关系（如“公司-部门-员工”），但面对现实世界中普遍存在的多对多关系（如“学生-课程”）时，便显得捉襟见肘。

以大学选课系统为例，若用层次模型实现：

• 根记录：`Student`
• 子记录：`Enrollment`（选课记录）
• `Enrollment`的子记录：`Course`

问题即刻显现：一门课程（`Course`）被多个学生选修，按照层次模型，该`Course`记录必须作为每个相关`Enrollment`记录的副本被重复存储。这不仅造成数据冗余，更埋下更新异常的隐患——若课程名称变更，必须更新所有相关的`Course`副本，稍有不慎即导致数据不一致。

IMS通过物理指针实现这种逻辑树。每个记录在磁盘上连续存储，并通过“前向/后向指针”链接。一个典型的IMS程序使用`GU`（Get Unique）和`GN`（Get Next）原语遍历：

```cobol

• IMS程序片段：遍历某部门所有员工

GU DEPARTMENT SEGMENT, DEPT-KEY = 'NY_SALES'. GN EMPLOYEE SEGMENT, WITHIN DEPARTMENT. PERFORM UNTIL IMS-STATUS = 'END-OF-SET' DISPLAY EMPLOYEE-NAME, EMPLOYEE-SALARY GN EMPLOYEE SEGMENT, WITHIN DEPARTMENT. END-PERFORM. ```

这种代码的脆弱性显而易见：

• **结构依赖**：若在`DEPARTMENT`和`EMPLOYEE`之间插入`TEAM`层，所有`GN`语句必须重写。
• **路径硬编码**：程序显式声明了遍历路径（`WITHIN DEPARTMENT`），若物理存储重组（如按员工而非部门聚簇），程序可能失效。
• **多对多模拟**：需引入冗余的“关联记录”（如`ENROLLMENT`），应用程序必须手动维护其完整性。

1.2 网状模型：自由的枷锁

CODASYL网状模型试图通过“集合”（Set）概念解放层次束缚。一个集合由持有者（Owner）记录类型和成员（Member）记录类型构成，成员可属于多个集合，从而支持多对多关系。以“学生-课程”为例，可定义两个集合：

• `COURSE-ENROLLMENT`：持有者=`Course`，成员=`Student`
• `STUDENT-ENROLLMENT`：持有者=`Student`，成员=`Course`

看似灵活，实则引入了更复杂的导航状态。CODASYL程序必须维护“当前记录”（Current of Set）和“区域”（Area）上下文，并通过`FIND`、`GET`、`STORE`等命令显式操作。以下是一个查找“纽约学生所选所有课程”的CODASYL COBOL程序：

```cobol WORKING-STORAGE SECTION. 01 STUDENT-RECORD.