关系模型与 SQL

SQL 说"要什么"，优化器决定"怎么做"——声明式查询是关系模型最重要的承诺。本章讲关系与键、范式与反范式、关系代数与 SQL 的对应、连接算法与查询优化，最后看 NoSQL 各模型放弃了什么、换来了什么。

关系与键

关系（relation）= 集合论意义上的元组集合——无序、无重复（这正是"关系代数"的数学根，也是 SQL 语义的来源）；
键：主键（唯一标识元组）、外键（引用完整性）；
NULL：三值逻辑（TRUE/FALSE/UNKNOWN）——NULL = NULL 是 UNKNOWN，是无数查询 bug 的来源。

范式与反范式

范式减少冗余、避免更新异常：

1NF：属性原子；2NF：非键属性完全依赖主键；3NF：消除传递依赖；BCNF：每个决定因素都是键。

规范化到 3NF/BCNF 是 OLTP 的默认；范式减少冗余，反范式换读性能——把连接的结果冗余存一份（读多写少的报表、计数器字段），代价是写时要维护一致性。判断标准：读写的比例与一致性要求。

关系代数与 SQL

SQL 是关系代数的声明式封装。核心运算：

关系代数	SQL	复杂度（朴素）
选择 $\sigma$	WHERE	$O(n)$ 扫描 / 索引
投影 $\pi$	SELECT 列	$O(n)$
连接 $\bowtie$	JOIN	见下
聚合	GROUP BY	排序或哈希
排序	ORDER BY	$O(n \log n)$

SQL 说"要什么"，优化器决定"怎么做"：你写逻辑关系，优化器选物理执行计划（索引、连接顺序、连接算法）。

连接算法

三种物理连接，各有适用：

嵌套循环（nested loop）：外表每行扫内表—— $O(nm)$ ，内表有索引时 $O(n \log m)$ ：小表驱动大表 + 索引，OLTP 的主流；
哈希连接：小表建哈希，大表探测—— $O(n + m)$ ，等值连接大表的主流（分析查询）；
排序归并：两边排序后归并—— $O(n \log n + m \log m)$ ，已排序或要排序输出的场合自然。

查询优化器

把声明式 SQL 变成执行计划：逻辑优化（谓词下推、投影裁剪）+ 基于代价的物理优化（枚举连接顺序与算法，代价模型估计 I/O 与 CPU）。优化器不是万能的：代价模型失准（数据倾斜、相关子查询）时计划走偏——看 EXPLAIN 是 DBA 与工程师的基本功（→ 索引与 B+ 树）。

NoSQL：放弃了什么、换来了什么

模型	代表	放弃	换来
文档	MongoDB	连接与强 schema	灵活 schema、整文档读
键值	Redis、DynamoDB	查询与关系	极简、可扩展
列族	Cassandra、HBase	随机写的事务	海量写的扩展性
图	Neo4j	集合运算	深度遍历的自然表达

共同的模式：用关系代数的表达力，换水平扩展或特定负载的性能。放弃不是免费的：连接在应用层做、聚合在代码里写、一致性自己管（→ 复制与分片）。判断标准不是流行度，是你的查询模式是否真的用不到关系。

本章要点

SQL 说"要什么"，优化器决定"怎么做"；关系代数是 SQL 的数学根
连接算法：嵌套循环（+索引，OLTP）、哈希（等值大表）、排序归并（已排序）
范式减少冗余，反范式换读性能；判断看读写比例与一致性要求
NULL 是三值逻辑，NULL = NULL 是 UNKNOWN
NoSQL 用表达力换扩展性；判断标准是查询模式是否用得到关系