System R：
数据库管理的关系方法

关键词与短语： database, relational model, nonprocedural language, authorization, locking, recovery, data structures, index structures
CR 分类： 3.74, 4.22, 4.33, 4.35

1. 引言

Codd [7] 于 1970 年引入关系数据模型，旨在为数据库管理中的各类问题提供解决方案。特别是，Codd 着眼于提供一种与实现考量相分离的数据模型或视图（即数据独立性问题），以及为数据库用户提供一种非常高层次、非过程化的数据子语言用于访问数据。

在很大程度上，关系方法的接受度和价值取决于能否证明可以构建一个能够在真实环境中解决真实问题的系统，且其性能至少可与现有系统媲美。本文的目的是描述一个名为 System R 的实验性原型数据库管理系统的整体架构和设计方面的问题。该系统目前正在 IBM 圣何塞研究实验室实现与评估中。在撰写本文时，设计已经完成，系统的主要部分已经实现并运行。然而，整个系统尚未完成。我们计划对系统进行完整的性能评估，结果将在后续论文中公布。

System R 项目并非关系方法的首次实现 [12, 30]。然而，我们尚不知道有任何其他关系系统能够提供完整的数据库管理能力——包括应用程序编程、查询能力、并发访问支持、系统恢复等。其他关系系统主要聚焦于并证明了解决各类特定问题的技术的可行性。例如，IS/1 系统 [22] 证明了支持关系代数 [8] 的可行性，并开发了代数表达式求值的优化技术 [29]。Smith 和 Chang 在犹他大学也开发了关系代数优化技术 [27]。IBM 剑桥科学中心开发的扩展关系内存 (XRM) 系统 [19] 已被其他关系系统 [2] 用作单用户访问方法。SEQUEL 原型 [1] 最初作为单用户系统开发，用于证明支持 SEQUEL [5] 语言的可行性。然而，该系统已被 IBM 剑桥科学中心和 MIT 斯隆学院能源实验室扩展，允许一种简单的并发类型，并被用作 MIT 正在为能源相关应用开发的通用管理信息系统 (GMIS) [9] 的一个组件。加州大学伯克利分校正在开发的 INGRES 项目 [16] 证明了将 QUEL 语言中的关系表达式分解为"单变量查询"的技术 [28]。此外，该系统还研究了使用查询修改 [28] 来实施完整性约束和用户授权约束。将高层次用户语言翻译为低层次访问原语的问题也在多伦多大学进行了研究 [21, 26]。

架构与系统结构

我们将从两个视角描述 System R 的整体架构。首先，我们将描述单事务视角下的系统，即一种整体式描述。其次，我们将探讨其多用户维度。图 1 给出了系统的功能视图，包括其主要接口和组件。

关系存储接口 (RSI) 是一个内部接口，处理对基关系单条元组的访问。该接口及其支持系统——关系存储系统 (RSS)——实际上是一个完整的存储子系统，因为它管理设备、空间分配、存储缓冲区、事务一致性与锁定、死锁检测、回退、事务恢复和系统恢复。此外，它维护基关系选定字段上的索引，以及跨关系的指针链。

关系数据接口 (RDI) 是可从编程语言直接调用的外部接口，或用于支持各种仿真器和其他接口。支持 RDI 的关系数据系统 (RDS) 提供授权、完整性实施，以及对数据替代视图的支持。高层次 SEQUEL 语言嵌入在 RDI 中，作为所有数据定义和操纵的基础。此外，RDS 维护外部名称的目录，因为 RSS 仅使用系统生成的内部名称。RDS 包含一个优化器，从 RSS 支持的路径中为任何给定请求选择合适的访问路径。

该实验系统的当前操作系统环境是 VM/370 [18]。为了支持 System R 的多用户环境，对该虚拟机设施做了若干扩展 [14]。特别是，我们实现了跨任意数量虚拟机选择性共享读写虚拟内存，以及通过处理器中断在虚拟机之间高效通信的技术。图 2 说明了使用多个虚拟机支持共享数据上并发事务的方式。

为每个登录用户提供专用数据库机器的设计意味着数据库系统无需提供自己的多任务处理来处理并发事务，而是可以使用宿主操作系统在虚拟机级别进行多线程处理。此外，操作系统可以利用分配给多个虚拟机的多处理器，因为每台机器都能提供所有数据管理服务。单服务器方法将消除这一优势，因为大部分处理活动将集中在单一机器上。

除数据库机器外，图 2 还说明了监控机器 (Monitor Machine)，它包含许多系统管理功能，例如控制登录授权、初始化每个用户的数据库机器、调度定期检查点、维护使用和性能统计以用于重组和计费目的。

2. 关系数据系统 (RDS)

关系数据接口 (RDI) 是 System R 的主要外部接口。它提供高层次、数据独立的数据检索、操纵、定义和控制功能。RDI 的数据定义功能允许在通用底层数据上定义各种替代关系视图。关系数据系统 (RDS) 是实现 RDI 的子系统。

RDS 包含一个优化器，为每个 RDI 命令规划执行方案，从关系存储系统 (RSS) 提供的路径中选择低成本的数据访问路径。

RDI 由一组可从 PL/I 或其他宿主编程语言调用的运算符组成（参见附录 I）。SEQUEL 数据子语言 [5] 的所有功能均可通过名为 SEQUEL 的 RDI 运算符在 RDI 中使用。（SEQUEL 的 BNF 语法见附录 II。）SEQUEL 语言可以通过一个简单的程序（在 RDI 之上编写，处理终端通信）作为独立接口支持。这种独立 SEQUEL 接口（称为用户友好接口，或 UFI）作为 System R 的一部分提供。此外，可以在 RDI 之上编写程序来支持其他关系接口，如 Query by Example [31]，或模拟非关系接口。

本节中使用的示例均基于以下员工与部门数据库：

EMP(EMPNO, NAME, DNO, JOB, SAL, MGR)
DEPT(DNO, DNAME, LOC, NEMPS)

宿主语言接口

RDI 的功能基本上就是 SEQUEL 数据子语言的功能。自该语言早先发布以来，SEQUEL 已做了一些变更。

RDI 通过一种称为游标 (cursor) 的概念将 SEQUEL 与宿主编程语言接口。游标是一个名字，在 RDI 中用于标识一组元组（称为其活动集，例如查询的结果），并在该集合的某条元组上维护一个位置。游标通过 RDI 运算符 SEQUEL 与一组元组关联；元组随后可通过 RDI 运算符 FETCH 逐条检索。

示例：绑定程序变量并执行查询

CALL BIND('X', ADDR(X));
CALL BIND('Y', ADDR(Y));
CALL SEQUEL(C1, 'SELECT NAME:X, SAL:Y
                  FROM EMP
                  WHERE JOB = ''PROGRAMMER''');

此 SEQUEL 调用将游标 C1 与满足查询的元组集合关联，并将其定位在第一条元组之前。优化器被调用以选择访问路径，但在 SEQUEL 调用响应中不会实际物化任何元组。元组的物化是在通过 FETCH 运算符逐条调用时完成的。每次 FETCH 调用将活动集的下一元组投递到程序变量 X 和 Y 中：

CALL FETCH(C1);

使用程序变量内容构造 SEQUEL 谓词：

CALL BIND('X', ADDR(X));
CALL BIND('Y', ADDR(Y));
CALL BIND('Z', ADDR(Z));
CALL SEQUEL(C1, 'SELECT NAME:X, SAL:Y
                  FROM EMP
                  WHERE JOB = ''PROGRAMMER''
                  AND DNO = Z');
CALL FETCH(C1);

有些程序可能事先不知道查询返回元组的度和数据类型（例如支持交互式用户的程序）。这种程序无需在 SEQUEL 调用中指定结果投递的变量。程序可以发出 SEQUEL 查询，随后使用 DESCRIBE 运算符获取度和数据类型：

CALL SEQUEL(C1, 'SELECT *
                   FROM EMP
                   WHERE DNO = 50');
CALL DESCRIBE(C1, DEGREE, P);

P 是指向数组的指针，该数组中将返回 C1 活动集的描述。RDI 在 DEGREE 中返回活动集的度，在数组元素中返回元组分量的数据类型和长度。如果数组（包含描述自身长度的条目）太短，无法容纳元组的描述，调用程序必须分配更大的数组并重新调用 DESCRIBE。

获取元组描述后，调用程序可分配结构来容纳元组，并在 FETCH 命令中指定该结构的位置：

CALL FETCH(C1, Q);

Q 是指向指针数组的指针，指定元组各分量应投递的位置。如果 FETCH 命令中存在此"目标"参数，它将覆盖 SEQUEL 命令中定义 C1 活动集时可能已指定的任何目标。

此外，提供了一个特殊的 RDI 运算符 OPEN 作为快捷方法，将游标与整个关系关联：

CALL OPEN(C1, 'EMP');

等价于：CALL SEQUEL(C1, 'SELECT * FROM EMP');。使用 OPEN 略优于使用 SEQUEL 打开关系上的游标，因为 OPEN 避免了使用 SEQUEL 解析器。

一个程序可以同时有多个活动游标。每个游标保持活动状态，直到对其发出 RDI 运算符 CLOSE 或 KEEP。CLOSE 仅停用游标。KEEP 使游标标识的元组被复制，形成数据库中具有指定关系名和字段名的新的永久关系。

RDI 运算符 FETCH-HOLD 以与 FETCH 完全相同的方式操作，但还会获取对所返回元组的"持有"锁，阻止其他用户更新或删除它，直到显式释放或持有事务结束为止。元组可以通过 RELEASE 运算符释放，该运算符接收一个定位在待释放元组上的游标作为参数。如果未提供游标，RELEASE 运算符将释放当前用户持有的所有元组。

查询功能

本节仅描述 SEQUEL 查询功能自最初发布 [5] 以来最重要的变更。一个重要变更是关于块标签的处理。

示例 1(a)（原始版本——使用块标签）： 列出工资高于其经理的员工姓名。

SELECT NAME
FROM EMP
WHERE SAL >
      SELECT SAL
      FROM EMP
      WHERE EMPNO = Bl.MGR

块标签表示法有三个缺点：(1) 无法从内部块中选择数据；(2) 查询是非对称表达的，优化器被迫偏向某种执行策略；(3) 人因研究表明块标签对非程序员来说很难学习 [24, 25]。

因此，块标签被以下更对称的表示法取代，允许在 FROM 子句中列出多个表并可选择用变量名引用：

示例 1(b)： 对于所有工资高于其经理的员工，列出员工姓名及其经理姓名。

SELECT X.NAME, Y.NAME
FROM EMP X, EMP Y
WHERE X.MGR = Y.EMPNO
AND X.SAL > Y.SAL

此示例展示了 SEQUEL 中 JOIN 运算符的表示法。待连接的表列在 FROM 子句中。每表可选择关联一个变量名（如 X 和 Y 所示）。连接行的标准在 WHERE 子句中给出。查询中出现的字段名可单独出现（如果无歧义）或用表名限定（如 EMP.SAL）或用变量限定（如 X.SAL）。

WHERE 子句原本用于两个目的：限定个别元组和限定元组组。现在通过将组限定谓词移至单独的 HAVING 子句消除了这种歧义。查询按以下顺序处理：(1) WHERE 子句选择元组；(2) GROUP BY 子句形成分组；(3) HAVING 子句选择满足条件的分组。

示例 2： 列出具员超过十人的部门的 DNO。

SELECT DNO
FROM EMP
WHERE JOB = 'CLERK'
GROUP BY DNO
HAVING COUNT(*) > 10

另外新增了两个查询功能。第一个允许用户为查询结果指定值排序：

示例 3（排序）： 列出部门 50 的所有员工，按工资排序。

SELECT *
FROM EMP
WHERE DNO = 50
ORDER BY SAL

第二个新功能主要对 RDI 的宿主语言用户有用，允许查询通过比较与某个活动游标的当前元组来限定元组：

示例 4（游标引用）： 查找游标 C5 所指示部门中的所有员工。

SELECT *
FROM EMP
WHERE DNO = DNO OF CURSOR C5 ON DEPT

此游标 C5 内容引用的求值发生在查询执行时（通过 SEQUEL 调用）。此后，移动游标 C5 不会影响查询定义的元组集。可选的短语 "ON DEPT" 向优化器指示它可以期望游标 C5 定位在 DEPT 表的元组上。此信息可能有助于为查询选择访问路径。

由于从查询结果中消除重复是高成本过程且并非总是必要，RDS 不会消除重复，除非显式请求。例如，"SELECT DNO, JOB FROM EMP" 可能返回重复对，但 "SELECT UNIQUE DNO, JOB FROM EMP" 只返回唯一对。类似地，"SELECT AVG(SAL) FROM EMP" 允许重复工资值参与平均值计算，而 "SELECT COUNT(UNIQUE JOB) FROM EMP" 只返回不同岗位类型的计数。

数据操纵功能

RDI 的元组插入、删除和更新功能也通过 SEQUEL 数据子语言提供。SEQUEL 既可以一次操纵一条元组，也可以用单条命令操纵一组元组。特定游标的当前元组可通过特殊谓词 CURRENT TUPLE OF CURSOR 选择用于某些操作。

示例 5（面向集合的更新）： 给部门 50 的所有员工加薪 10%。

CALL SEQUEL('UPDATE EMP
              SET SAL = SAL * 1.1
              WHERE DNO = 50');

示例 6（单条更新）： 使用程序变量的值。

CALL BIND('PVSAL', ADDR(PVSAL));
CALL SEQUEL('UPDATE EMP
              SET SAL = PVSAL
              WHERE CURRENT TUPLE OF CURSOR C3');

示例 7（单条插入）： 新元组部分由常量构造，部分来自程序变量内容。

CALL BIND('PVEMPNO', ADDR(PVEMPNO));
CALL BIND('PVNAME', ADDR(PVNAME));
CALL BIND('PVMGR', ADDR(PVMGR));
CALL SEQUEL('INSERT INTO EMP:
  (PVEMPNO, PVNAME, 50, ''TRAINEE'', 8500, PVMGR)');

SEQUEL 中的插入语句可以只提供新元组的部分值，用字段名指定提供了哪些字段。未提供的字段设为空值。

示例 8（面向集合的删除）： 删除在 Evanston 工作部门的所有员工。

CALL SEQUEL('DELETE EMP
              WHERE DNO =
                    SELECT DNO
                    FROM DEPT
                    WHERE LOC = ''EVANSTON''');

示例 9（赋值）： 创建一个新表 UNDERPAID，包含工资低于 $10,000 的程序员的姓名和工资。

CALL SEQUEL('UNDERPAID(NAME, SAL) ←
       SELECT NAME, SAL
       FROM EMP
       WHERE JOB = ''PROGRAMMER''
       AND SAL < 10,000');

新表 UNDERPAID 代表赋值执行时刻从 EMP 拍摄的快照。之后 UNDERPAID 成为独立关系，不反映 EMP 后续的任何更改。

数据定义功能

System R 对数据操纵、定义和控制采取统一方法。与查询和面向集合的更新一样，数据定义功能通过 RDI 运算符 SEQUEL 调用。

SEQUEL 语句 CREATE TABLE 用于创建新的基（即物理存储的）关系。对于新关系的每个字段，指定字段名和数据类型。支持的数据类型包括：INTEGER、SMALL INTEGER、DECIMAL、FLOAT 和 CHARACTER（定长和变长）。如果希望，可以在创建时指定新关系的某些字段不允许空值。除非查询带有 ORDER BY 子句，否则在关系上执行的查询将以系统决定的顺序（取决于优化器选择的访问路径）返回结果。当基关系不再有用时，可以通过执行 DROP TABLE 语句删除。

System R 当前依赖用户不仅指定要存储的基表，还指定要在其上维护的 RSS 访问路径。（自动化和适应这些决策的数据库设计功能也在研究中。）

访问路径 包括映像 (images) 和二元链接 (binary links)（一元链接见第 3 节，仅供系统内部使用，不在 RDI 中暴露）。映像由 RSS 使用多级索引结构在基关系上维护的值排序。映像提供对一个或多个字段（称为映像的排序字段）的关联和顺序访问。映像可声明为 UNIQUE，强制排序字段值的每个组合在关系中唯一。每个关系最多有一个映像可具有聚集 (clustering) 属性，使排序字段值接近的元组在物理上存储得彼此靠近。

二元链接是 RSS 中将一个关系的元组通过指针链连接到另一个关系的相关元组的访问路径。在 System R 中，二元链接始终以值依赖方式使用：用户指定关系 1 的每条元组应连接到关系 2 中在某些字段上具有匹配值的元组，且链接上的元组按某种值依赖方式排序。例如，用户可指定从 DEPT 到 EMP 的链接，通过匹配 DNO，且链接上的 EMP 元组按 JOB 和 SAL 排序。此链接由系统自动维护。通过声明从 DEPT 到 EMP 匹配 DNO 的链接，用户隐式地声明这是一对多关系（即 DNO 是 DEPT 的键）。任何违反此规则定义链接或插入/更新元组的尝试都将被拒绝。与映像一样，链接也可声明聚集属性，使每条元组在物理上存储在其链接前序遍历中的邻近元组附近。

需要特别注意的是，任何访问路径（映像和二元链接）都不包含除数据值本身可导出的逻辑信息之外的任何信息。这与关系数据模型一致，后者将所有信息表示为数据值。RDI 用户对映像和链接中元组的放置没有显式控制（不同于 DBTG 提案 [6] 的"手动系"）。此外，RDI 用户不能显式使用映像或链接访问数据；所有访问路径选择由优化器自动完成。

SEQUEL 的查询能力可用于将一个视图 (view) 定义为从一个或多个其他关系导出的关系。然后可以以与基表相同的方式使用此视图（可以针对它写查询、在其上定义其他视图，以及在满足条件的情况下更新它）。任何 SEQUEL 查询都可以通过 DEFINE VIEW 语句用作视图定义。视图是数据库上的动态窗口，因为对基表的更新通过基于这些基表定义的视图立即可见。在支持视图更新的情况下，它们是通过对底层基表的更新来实现的。定义视图的 SEQUEL 语句被记录在系统维护的目录中，授权用户可以检查它。当授权用户执行 DROP VIEW 语句时，该视图和所有基于它定义的其他视图从此用户和所有其他用户的系统中消失。

如果对视图发出修改，只有当视图的元组一对一地关联到某个底层基关系的元组时才能支持。一般来说，这意味着视图必须涉及单个基关系并包含该关系的一个键；否则修改语句将被拒绝。如果视图满足一对一规则，SEQUEL 修改语句的 WHERE 子句与视图定义合并；结果被优化，并对基关系的相关元组执行指定的更新。

还有两个 SEQUEL 命令完善了数据定义功能。第一个是 KEEP TABLE，它使临时表（例如通过赋值创建的）变为永久表。（临时表在创建它们的用户注销时被销毁。）第二个命令是 EXPAND TABLE，它向现有表添加新字段。在原始表上定义的所有视图、映像和链接都得以保留。所有现有元组在扩展字段中的值被视为空值，直到显式更新。

数据控制功能

RDI 的数据控制功能有四个方面：事务、授权、完整性断言和触发器。

事务 是用户希望作为原子行为处理的一系列 RDI 调用。"原子"的含义取决于用户指定的一致性级别。最高级别——级别 3——要求用户的事务与并发用户的事务序列化执行。用户在事务中可以通过 RDI 运算符 SAVE 指定保存点。只要事务处于活动状态，用户可以使用 RESTORE 运算符回退到事务开头或任何内部保存点。

System R 的授权方法 在 [15] 中描述。System R 不需要特定个人担任数据库管理员，而是允许每个用户通过执行 SEQUEL 语句 CREATE TABLE 和 DEFINE VIEW 创建自己的数据对象。新对象的创建者获得对该对象执行所有操作的完全授权。用户随后可以通过 SEQUEL 语句 GRANT 将对对象的选定能力授予其他用户。每表或视图可独立授予以下能力：READ、INSERT、DELETE、UPDATE（按字段）、DROP、EXPAND、IMAGE 规格、LINK 规格和 CONTROL。

System R 主要依赖视图机制进行读授权。关键字 USER 始终解释为当前用户的用户标识。因此以下 SEQUEL 语句定义了与当前用户同一部门的所有员工的视图：

DEFINE VIEW VEMP AS:
       SELECT *
       FROM EMP
       WHERE DNO =
             SELECT DNO
             FROM EMP
             WHERE NAME = USER

完整性断言 [10]：任何 SEQUEL 谓词都可以声明为关于基表或视图中数据完整性的断言。在做出断言时（通过 SEQUEL 中的 ASSERT 语句），检查其真值；如果为真，则断言会自动执行，直到通过 DROP ASSERTION 语句显式删除。任何违反活动完整性断言的用户数据修改都将被拒绝。

示例 10（转换断言）： 每位员工的工资必须不减。

ASSERT ON UPDATE TO EMP: NEW SAL ≥ OLD SAL

除非另行指定，完整性断言在每个事务结束时检查并执行。如果事务被指定为 IMMEDIATE，则不可在事务内挂起，而是在每次数据修改后执行。

触发器 是断言概念的泛化。触发器使预设的 SEQUEL 语句序列在触发事件发生时执行。例如，在我们的示例数据库中，DEPT 表的 NEMPS 字段表示每个部门的员工数。可以通过以下三个触发器自动保持其最新：

DEFINE TRIGGER EMPINS
  ON INSERTION OF EMP:
    (UPDATE DEPT
     SET NEMPS = NEMPS + 1
     WHERE DNO = NEW EMP.DNO)

DEFINE TRIGGER EMPDEL
  ON DELETION OF EMP:
    (UPDATE DEPT
     SET NEMPS = NEMPS - 1
     WHERE DNO = OLD EMP.DNO)

DEFINE TRIGGER EMPUPD
  ON UPDATE OF EMP:
    (UPDATE DEPT
     SET NEMPS = NEMPS - 1
     WHERE DNO = OLD EMP.DNO;
     UPDATE DEPT
     SET NEMPS = NEMPS + 1
     WHERE DNO = NEW EMP.DNO)

RDS 自动维护一组描述系统已知的关系、视图、映像、链接、断言和触发器的目录关系。每个用户可以访问包含与他相关信息的一组系统目录视图。对目录关系的访问方式与其他关系完全相同（即通过 SEQUEL 查询）。当然，没有用户被授权直接修改目录内容，但任何授权用户可以通过创建表等操作间接修改目录。此外，用户可以通过 COMMENT 语句（语法见附录 II）在各种目录条目中输入注释。

优化器

优化器的目标是找到执行 SEQUEL 语句的低成本方法，给定可用的数据结构和访问路径。优化器试图最小化语句执行期间预期从辅助存储读入 RSS 缓冲区所需的页面数。仅考虑在 RSS 显式控制下进行的页面获取。如有必要，RSS 缓冲区将被固定在实存中，以避免 VM/370 操作系统引起的额外分页活动。CPU 指令的成本通过可调系数 H 考虑在内，H 与元组比较操作数相乘以转换为等价的页面访问数。H 可根据系统是计算密集还是磁盘访问密集进行调整。

由于优化器的成本度量基于磁盘页面访问，数据库中元组的物理聚集至关重要。如前所述，每个关系最多有一个聚集映像，具有聚集映像排序中彼此邻近的元组在数据库中物理存储得彼此靠近。要理解聚集属性的重要性，设想我们想要按某个映像的顺序扫描关系的元组，且 RSS 缓冲页面数远少于存储该关系所用的页面数。如果该映像不是聚集映像，元组的位置将彼此独立，通常每条元组都需要从磁盘获取一个页面。另一方面，如果该映像是聚集映像，每个磁盘页面将包含多条（通常至少 20 条）相邻的元组，页面获取次数将按相应因子减少。

优化器首先将给定的 SEQUEL 语句分类为若干语句类型之一，依据其中是否存在各种语言特性（如 join 和 GROUP BY）。然后优化器检查系统目录以找到与给定语句相关的映像和链接集合。接着执行一个粗略的决策过程以找到执行语句的"合理"方法集合。如果存在多个"合理"方法，对每个方法求值预期成本公式，选择成本最低的方法。成本公式的参数（如关系基数和每页元组数）从系统目录中获取。

优化方法（单关系查询示例）：

示例 11： 列出工资超过 $10,000 的程序员的姓名和工资。

SELECT NAME, SAL
FROM EMP
WHERE JOB = 'PROGRAMMER'
AND SAL > 10,000

优化器考虑以下参数：R（关系基数）、D（数据页数）、T（每页平均元组数，R/D）、I（映像基数）、H（CPU 成本系数）。

如果一个映像的排序字段正是谓词测试的字段，则称该映像匹配该谓词。例如，EMP 关系上按 JOB 排序的映像（我们称其为"EMP.JOB 上的映像"）将匹配示例 11 中的谓词 JOB = 'PROGRAMMER'。为了使映像匹配谓词，谓词必须是字段与值的简单比较。更复杂的谓词，如 EMP.DNO = DEPT.DNO，不能被映像匹配。在示例 11 这样的单关系简单查询的情况下，优化器将可用映像与查询的谓词进行比较，以确定以下八种方法中哪些可用：

选择规则： 1. 如果方法 1 可用，则选择它。 2. 如果方法 2、3、5、7 中恰有一种可用，则选择它。如果此类中有多种方法，则评估成本公式并选择最小成本方法。 3. 如果以上方法均不可用，选择方法 4（如果可用）；否则方法 6（如果可用）；否则方法 8。

连接查询优化（示例 12）： 列出位于 Evanston 的程序员的姓名、工资和部门名。

SELECT NAME, SAL, DNAME
FROM EMP, DEPT
WHERE EMP.JOB = 'PROGRAMMER'
AND DEPT.LOC = 'EVANSTON'
AND EMP.DNO = DEPT.DNO

优化器考虑四种连接执行方法：

方法 1（在连接字段上使用映像）： 同时扫描 DEPT.DNO 和 EMP.DNO 上的映像。

方法 2（排序两个关系）： 使用聚集映像扫描 EMP 和 DEPT，创建临时文件 W1 和 W2，在 DNO 上排序，然后执行连接。

方法 3（多趟扫描）： 扫描 DEPT 并在主存中构建工作文件 W，多次扫描 EMP 进行匹配。

方法 4（TID 算法）： 使用索引获取满足限制条件的元组的 TID，排序 TID，同时扫描连接字段映像进行匹配。

这四种方法应视为优化器考虑技术中的示例。优化器将从更大的方法集合中选择，包括使用链接来执行连接的方法。一种方法只有在适当的访问路径可用时才能应用。例如，方法 4 仅当 EMP.DNO 和 EMP.JOB 以及 DEPT.DNO 和 DEPT.LOC 上都有映像时才适用。此外，方法的性能很大程度上取决于关系相对于访问路径的聚集情况。我们在四种假设情况下考虑优化器如何在这四种方法中选择。这些选择基于成本公式，详情将在后续论文中详述。

四种方法的优化选择取决于具体情况：

分析任何 SEQUEL 语句后，优化器生成一个优化包 (Optimized Package, OP)，包含分析树和执行计划。如果是查询，OP 用于按 FETCH 命令调用时的增量方式物化元组（查询结果尽可能增量式物化）。如果是视图定义，OP 以预优化包 (Pre-Optimized Package, POP) 形式存储，每次通过该视图访问时可获取并使用。如果对基表的结构或其上维护的访问路径（映像和链接）做了任何更改，所有基于该基表定义的视图的 POP 将失效，每个视图必须从其定义的 SEQUEL 代码重新优化以形成新的 POP。

当通过 RDI 运算符 OPEN 和 FETCH 访问视图时，视图的 POP 可直接用于物化视图的元组。然而，查询或另一个视图定义常常是依据现有视图编写的。如果查询或视图定义很简单（例如投影或限制），有时可以与现有视图组合（即它们的分析树可以合并并一起优化，形成新查询或视图的新 OP）。在更复杂的情况下，新语句不能与现有视图定义组合。在这些情况下，现有视图的 POP 被视为物化元组的公式。为新语句形成新的 OP，将现有视图视为一张表，只能以一种方式获取元组：通过解释现有的 POP。当然，如果视图在多个层级上级联到其他视图，可能存在多个层级的 POP，每个层级引用下一层级。

修改游标

System R 的插入、删除和更新功能的使用引发了许多问题。当对游标活动集中的某条元组进行修改时，修改可能改变元组在活动集中的序位，甚至使其完全失去活动集资格。此处应指出，在级别 3 一致性下操作的用户自动受到保护，其游标不受其他用户修改的影响。然而，即使在级别 3 一致性下，用户也可能做出影响自己活动游标之一的修改。

如果相关游标是在基关系上打开的，情况很简单：修改完成并立即可通过游标看到。让我们考虑游标不在基关系上，而是在 SEQUEL 查询结果上的情况。假设已执行以下查询：

SELECT *
FROM EMP
WHERE DNO = 50
ORDER BY SAL

如果系统没有按 SAL 排序的映像，它可能通过查找 DNO = 50 的员工并按 SAL 排序来创建有序的答案元组列表。与此列表一起，系统将保留派生该列表的基关系列表（本例中仅为 EMP）。其效果类似于在底层基关系上执行 DBTG KEEP 动词 [6]：如果任何底层关系中的元组被修改，答案列表被标记为"可能无效"。现在，从此列表的任何获取都将返回警告码，因为返回的元组可能不是最新的。如果调用程序希望保证其结果的准确性，必须在收到此警告码时关闭其游标并重新求值查询。

非关系数据模型的模拟

RDI 的设计使得可以在其之上编写程序来模拟"导航式"数据库接口（层次式 [17] 或网络式 [6]）。这些接口通常以连接的记录集合为特征，形成层次 [17] 或网络 [6] 结构，并具有在结构中建立一或多个"当前位置"的概念（如 DBTG 的货币指示器）。一般策略是将每种记录类型表示为一个关系，并将记录之间的排序和连接信息表示为显式字段。所有通过导航式接口插入的信息（包括排序和连接信息）均可供直接使用底层关系的其他用户使用。数据库中的一个或多个"当前位置"可以通过一个或多个 RDI 游标来模拟。

我们通过一个示例来说明这个模拟过程。假设我们希望模拟图 3 所示的数据库结构，并希望在该结构中维护一个"当前位置"。从 DEPT 到 EMP 以及从 DEPT 到 EQUIP 的层次连接可能在层次式系统（如 IMS [17]）中未命名，或者可能表示网络型系统（如 DBTG [6]）中的命名系类型。

                    ┌─────────┐
                    │  DEPT   │
                    └────┬────┘
                         │
            ┌────────────┼────────────┐
            ▼            │            ▼
       ┌─────────┐       │      ┌─────────┐
       │   EMP   │◄──────┘      │  EQUIP  │
       └─────────┘              └─────────┘

在数据库定义时，为模拟每种记录类型创建一个关系。DEPT 关系必须有一个序号字段来表示 DEPT 记录的顺序。EMP 和 EQUIP 关系除了序号字段外，还必须有一个或多个字段来唯一标识它们的"父"或"所有者"记录（假设 DEPT 的键是 DNO）。如果一条记录在不同系类型中有多个"所有者"，则必须在对应关系中包含多个"所有者键"字段。

此外，在数据库定义时，向系统中输入视图定义，表示每个关系中在任何时刻"当前可见"的元组。我们示例中的视图定义如下：

DEFINE VIEW VDEPT AS
         SELECT *
         FROM   DEPT
         ORDER BY (序号字段)
DEFINE VIEW VEMP AS
         SELECT *
         FROM   EMP
         WHERE  DNO = DNO OF CURSOR C1 ON DEPT
         ORDER BY (序号字段)
DEFINE VIEW VEQUIP AS
         SELECT *
         FROM   EQUIP
         WHERE  DNO = DNO OF CURSOR C1 ON DEPT
         ORDER BY (序号字段)

VEMP 和 VEQUIP 的定义要求 EMP 和 EQUIP 中与游标 C1 具有相同 DNO 的元组；此外它们承诺在使用这些视图时，游标 C1 将活跃在 DEPT 关系上。这些视图定义被解析和优化，并以 POP 形式存储。在此优化过程中，将发现对层次结构的任何直接物理支持（例如从 DEPT 到 EMP 通过匹配 DNO 的链接）。

在运行时，当需要在 DEPT 记录上建立位置时，在视图 VDEPT 上打开游标 C1。如果"当前位置"随后向下移动到 EMP 记录，则打开视图 VEMP。这次视图打开所展示的 EMP 元组确切子集取决于游标 C1 在"父"关系中的位置。如果"当前位置"再次向上移动到 DEPT，则关闭视图 VEMP，稍后按需重新打开。对层次结构发出的任何插入、删除或更新操作都通过对相应关系的 SEQUEL INSERT、DELETE 和 UPDATE 操作来模拟，必要时由模拟程序生成适当的序号和父键值。在事务结束时，所有游标关闭。

按照这个总体方案，预计可以在 RDI 之上模拟面向层次或面向网络的接口。特别需要注意的是，响应移动"当前位置"的命令时不进行解析或优化；系统仅使用在数据库定义时已优化的视图的 POP。对于以二元链接形式获得直接物理支持的连接，优化器将利用该链接提供良好性能。系统还能够模拟没有直接物理支持的连接，因为优化器会自动找到合适的访问路径。

3. 关系存储系统 (RSS)

关系存储系统 (RSS) 是为 System R 提供底层支持的数据库管理子系统。RSS 支持 RSI，提供基关系上层简单的、逐元组的运算符。还支持数据恢复、事务管理和数据定义的运算符。

RSS 有许多功能可在其他系统中找到，无论是关系型还是非关系型，例如索引和指针链结构的使用。RSS 中强调并扩展的领域包括：新数据类型和访问路径的动态定义、磁盘空间到数据段的动态绑定和解绑定、进程内事务的多点恢复、新颖高效的系统检查点与重启技术、与其他并发用户的多级隔离、以及在段、关系和单条元组级别的自动锁定。

段 (Segments)

在 RSS 中，所有数据存储在称为段 的逻辑地址空间集合中，用于控制物理聚集。段用于存储用户数据、访问路径结构、内部目录信息和 RDS 生成的中间结果。任何关系的所有元组必须驻留在 RDS 选择的单个段内。然而，一个给定段可以包含多个关系。

支持多种段类型，每种类型有其自身的功能和开销组合。一种类型用于存储共享数据，具有并发访问、事务回退和段内容恢复到先前状态的功能。另一种类型用于低开销临时关系存储，无并发访问或段恢复功能。

RSS 负责将逻辑段空间映射到磁盘存储上的物理区段，并支持段恢复。每个段由等大小页面的序列组成。物理页槽在首次引用时动态分配给段。这种动态分配方案允许定义许多大尺寸段，以容纳大的中间结果和增长的数据库。提供了在物理介质上聚集页面的功能，以便顺序或局部访问段时可以高效处理。

RSS 为每个段维护一个页图，用于将每个段页面映射到其在磁盘上的位置。这样的映射图维护为多个等大小块的集合，这些块是静态分配的。页面请求通过在所有并发用户间共享的主存缓冲区中分配空间来处理。实际上，管理着两个独立的缓冲区：一个用于页图块，一个用于段页面本身。页面和块都被固定在其缓冲区槽中，直到被 RSS 组件显式释放。释放页面使其可用于替换，当需要空间时，缓冲区管理器替换最近最少请求的已释放页面。

RSS 为每个可恢复段维护两个页图（当前和备份），提供了一种新颖的段恢复技术。当发出 OPEN-SEGMENT 使段可用于处理时，这些页图有相同的条目。当 RSS 组件随后请求访问页面并带有更新意图（在获取适当锁之后），RSS 检查这是否自 OPEN 或上次 SAVE-SEGMENT 操作以来对该页面的首次更新。如果是，则在磁盘上附近分配新的页槽，从其原始磁盘位置访问页面，然后修改当前页图指向新的页槽。当页面随后从缓冲区替换时，它将被定向到新位置，而备份页面和备份页图保持完整。当发出 SAVE-SEGMENT 时，通过写出所有已更新的缓冲区页来更新绑定到段的磁盘页面。然后扫描两个页图，释放自上次保存点以来修改的任何页面的旧页槽。最后将备份页图条目设置为等于当前页图条目，循环完成。RESTORE-SEGMENT 则简单地设置当前页图等于备份页图，释放新分配的页槽。

SAVE SEGMENT 和 RESTORE SEGMENT 函数对于恢复私有数据的先前版本以及支持系统检查点和重启（如下所述）很有用。然而，恢复公共数据段的效果可能是撤销多个事务所做的更改，因为在段上次保存后每个事务都可能修改了数据。因此，使用了一种完全不同的机制来仅回退单个事务所做的更改，如下所述。请注意，我们的恢复方案依赖于每个段两个页图的高度风格化管理，以及我们控制页面何时从主存写出到磁盘的能力。这些特殊需求导致了我们决定自己处理 RSS 段的存储管理和 I/O，而不是依赖操作系统中虚拟内存的自动分页。

关系 (Relations)

RSS 的主要数据对象是 n 元关系，包含随时间变化的若干条元组，每条元组包含 n 个字段。新关系可随时在任何 RDS 选择的段内定义。

支持两种字段类型：定长和变长。对应两种类型，RSI 使用特殊协议生成未定义值。当用户向现有关系添加新字段时，每个现有元组中新字段的值被视为未定义，直到显式更新。

运算符包括 INSERT、DELETE（单条元组）和 FETCH、UPDATE（元组的任意字段组合）。还可通过 RSS 游标或扫描 (scan) 沿访问路径获取元组序列。每次扫描由 RSS 通过执行 OPEN-SCAN 运算符创建，用于在特定访问路径上获取元组。然后通过该扫描上的一系列 NEXT 操作来访问路径上的元组。支持的访问路径包括通过使用映像的值决定排序、通过使用链接的 RDS 决定排序（见下文的映像和链接讨论）、以及 RSS 决定的元组排序。对于所有这些访问路径，RDS 可以为每个 NEXT 操作附加一个搜索参数。搜索参数可以是任何析取范式表达式，其中每个原子表达式的形式为（字段编号，运算符，值）。值由 RDS 提供的显式字节串，运算符为 '='、'≠'、'<'、'>'、'≤' 或 '≥'。

与关系中的每条元组关联的是元组标识符 (TID)。每个 TID 由 RSS 生成，可供 RDS 作为元组的简洁高效寻址手段。TID 也在 RSS 内部用于从索引结构中引用元组，以及维护指针链。TID 的实现采用混合方案，类似于 IDS [11] 和 RM [20] 等系统中使用的方案，结合了字节地址指针的速度和间接寻址的灵活性。TID 是段内页码与距页面底部的字节偏移量的拼接。偏移量指向包含元组在该页中字节位置的特殊条目或"槽"。该技术允许数据页内空间高效利用，可紧凑存储空间并移动元组，只需局部更改槽中指针。槽本身从不在每个数据页底部的固定位置上移动，因此现有 TID 仍可用于访问元组。在极少见的情况下，当元组被更新为更长的总值且其页面上空间不足时，提供了一种溢出方案将元组移动到另一页。这种情况下 TID 指向一个标记溢出记录，该记录用于引用另一页。如果元组再次溢出，原始溢出记录被修改为指向最新位置。因此，通过 TID 访问元组几乎总是涉及一次页面访问，且绝不涉及超过两次页面访问（加上可能的页图块访问）。

为了调整数据库以适应特定环境，RSS 在 INSERT 操作期间接受物理分配的提示，形式为试探性 TID。如果空间充足，新元组将被插入到与该 TID 关联的页面中。否则，RSS 选择附近的页面。使用此功能使 RDS 能够根据某种标准（如一个或多个字段上的值排序）聚集给定关系的元组。另一个用途是将一个关系的元组聚集在另一关系的特定元组附近，因为某些字段中的值匹配。这种聚集规则将为关系连接操作以及支持层次和网络应用带来高性能。

映像 (Images)

RSS 中的映像是 n 元关系相对于一个或多个排序字段中值的逻辑重排序。映像结合扫描提供沿值排序扫描关系的能力。更重要的是，映像提供关联访问能力。RDS 可以通过排序字段值快速从映像中获取元组。RDS 还可以在映像的特定点打开扫描，并检索具有给定排序值范围的元组或子元组序列。由于映像包含关系中的所有元组和所有字段，RDS 可以在扫描期间使用析取范式搜索参数来进一步限制返回的元组集。该功能在 SEQUEL 搜索谓词涉及关系的多个字段且至少其中一个有映像支持时特别有用。

新映像可随时在关系中的任意字段组合上定义。每个字段可指定为升序或降序。一旦定义，映像在 INSERT、DELETE 和 UPDATE 操作期间由 RSS 自动维护。映像也可随时删除。

RSS 通过多页索引结构维护每个映像。每个索引由段内的一或更多页组成，组织为平衡层次结构，类似 B 树 [3] 和 VSAM 的键序列数据集 [23]。每页是层次结构中的节点，包含有序的索引条目序列。非叶节点的条目由（排序值，指针）对组成。指针指向同一结构中的另一页，该页可以是叶页或另一个非叶页。目标页包含排序值小于或等于给定值的条目。对于叶节点，条目是排序值与具有这些确切排序值的元组的 TID 升序列表的组合。叶页以双向链表链接，因此可以从一叶到另一叶支持顺序访问。为高效处理变长、多字段索引，在字段值上使用了一种特殊的编码方案，使生成的拼接结果可以与其他结果进行排序和搜索比较。这种编码消除了对每个字段进行高成本填充和逐字段缓慢比较的需要。

链接 (Links)

RSS 中的链接是用于连接一或两个关系中元组的访问路径。RDS 通过显式的 CONNECT 和 DISCONNECT 操作确定哪些元组将在链接上以及它们的相对位置。RSS 维护内部指针，以便新连接的元组链接到前一个和后一个兄弟，并且当元组断开连接时前后兄弟互相链接。链接可以使用一系列 OPEN SCAN 和 NEXT 操作以及上述可选的搜索参数进行扫描。

一元链接 涉及单个关系，提供部分定义的元组排序。一元链接可用于维护 RSS 不支持的元组排序规格（即非值排序）。另一种用途是提供穿越关系所有元组的高效访问路径，避免了内部页面扫描的时间开销。

二元链接 更为重要，提供从一个关系（父）中的单条元组到另一关系（子）中元组序列的路径。RDS 通过 CONNECT 和 DISCONNECT 运算符确定哪些元组将成为给定父元组下的子元组及其相对顺序。然后可以使用运算符扫描父元组的子元组或从子元组直接沿链接到其父元组。一般来说，父关系中的元组可以没有子元组，子关系中的元组可以没有父元组。此外，关系中的元组可以是不同数量不同链接中的父和/或子。唯一限制是给定元组在给定链接中只能出现一次。二元链接类似于 DBTG 网络数据模型规范 [6] 中的 owner coupled set with manual membership 概念。

在 System R 中，二元链接的主要用途是基于一或多个字段中的值匹配将子元组连接到父元组。借助这种结构，RDS 可以访问一个关系中的元组（例如 Employee 关系），通过匹配 Department 关系中元组的 Department Number 字段。该功能对于支持关系连接操作以及通过层次和网络数据模型支持导航处理尤为重要。链接提供从 Department 元组直接访问正确 Employee 元组的能力（反之亦然），而使用映像可能涉及访问索引中的多个页面。当子元组已被聚集在与父元组相同的页面上时，相对于映像获得了显著优势——使用链接不触碰额外页面，而大索引可能触碰三个或更多页面。

链接的另一个重要特性是在不使用额外索引的情况下提供对关系的相当快的关联访问。在上述示例中，如果 Department 关系在 Department Number 上有映像，则 RDS 可以通过使用 Department 关系映像和二元链接获得对给定 Department Number 值的 Employee 元组的关联访问——即使最终用户未引用 Department 元组。

链接在 RSS 中通过在元组前缀中存储 TID 来维护。新链接可随时定义。当为关系定义新链接时，分配前缀的一部分来保存所需条目。此操作不需要访问任何现有元组，因为现有元组的新前缀空间仅在元组连接到链接时才被格式化。必要时，通过用于更新和新数据字段的正常机制来扩大前缀长度。现有链接也可随时删除。发生时，RSS 访问对应关系中的每条元组，以使现有前缀条目失效并让空间可供后续链接定义使用。

事务管理

RSS 的事务是代表一个用户发出的一系列 RSI 调用。它也作为一致性和恢复的单位。RSS 事务由 RDS 生成以执行单一 System R 事务中的所有 RDI 运算符（包括授权、目录访问和完整性检查等 RDS 内部功能）的调用组成。一个 RSS 事务由 START-TRANS 和 END-TRANS 运算符标记。使用下述锁定技术为事务分配各种资源。此外，提供了一个事务恢复方案，允许事务增量回退到任何中间保存点。这种多点恢复功能在涉及较长事务的应用中很重要，当由于用户或 RDS 检测到的错误、RSS 检测到的死锁或 Monitor 检测到的长时间不活动或系统拥塞而需要备份时。

事务保存点通过 SAVE-TRANS 运算符标记，该运算符返回一个保存点编号供后续引用。一般来说，保存点可以由 RSS 上方的任何层生成。RDI 用户可以在其事务中的方便位置标记保存点以处理回退和重试。RDS 可以为每个面向集合的新 SEQUEL 表达式标记保存点，以便如果任何 RSI 调用未能完成，支持该表达式所需的 RSI 调用序列可以被回退以自动重试。

事务恢复发生在 RDS 或 Monitor 发出 RESTORE-TRANS 运算符（以保存点编号为输入参数）时，或当 RSS 发起处理死锁的过程时。

效果是撤销自给定保存点以来该事务对可恢复数据所做的所有更改。这些更改包括 INSERT、DELETE 和 UPDATE 操作引起的所有元组和映像修改，CONNECT 和 DISCONNECT 操作引起的所有链接修改，甚至包括定义新关系、映像和链接的所有声明。为了帮助 RDS 继续事务，可恢复数据上的所有扫描位置自动重置为它们保存时刻所指向的元组。最后，释放自给定保存点以来获取的可恢复数据上的所有锁。

事务恢复功能通过维护日志条目的时间有序列表来支持，记录每次对可恢复数据更改的信息。每事务的条目链接在一起，包括所有已修改可恢复对象的旧值和新值以及操作代码和对象标识。对索引结构的修改不记录日志，因为它们的值可以从数据值和索引目录信息中确定。

在每个事务保存点，存储包含事务使用中所有扫描状态的条目以及最近获取的锁的标识。在事务恢复期间，以后进先出顺序读取事务的日志条目。使用特殊例程来撤销所有列出的修改直到记录的保存点，并恢复扫描和释放保存点后获取的锁。

日志条目本身存储在专用段中，用作环形缓冲区。该段被视为简单的线性字节空间，条目跨越页面边界。条目也归档到磁带上以支持审计和系统故障后的数据库重建。

并发控制

由于 System R 是并发用户系统，必须使用锁定技术解决各种同步问题，包括关系和元组等对象的逻辑级别和页面的物理级别。

在逻辑级别，必须处理诸如"丢失更新"问题等经典场景：确保两个并发事务不会读取相同的值然后尝试写回递增后的值。如果这些事务未同步，第二次更新将覆盖第一次，而一次递增的效果将丢失。类似地，如果用户希望只读取"干净"或已提交的数据，而不是已被仍在进行中的事务更新且可能被回退的"脏"数据，则必须调用某种机制来检查数据是否为脏。再举一例，如果事务恢复只影响单个用户的修改，则需要机制确保被某个正在进行中的事务（如 T1）更新的数据不被另一个事务（如 T2）更新。否则，事务 T1 的回退将撤销 T2 的更新，从而违反我们隔离回退的原则。

在页面的物理级别，需要锁定技术确保 RSS 内部组件给出正确结果。例如，一个数据页可能包含多条元组，每条元组通过其元组标识符访问，这需要跟随数据页内的指针。即使两个事务之间没有逻辑冲突——因为每个事务访问不同的关系或同一关系中的不同元组——在物理级别也可能出现问题，如果一个事务跟随指针访问某页上的元组，而另一个事务更新同一页上的第二条元组并导致数据压缩例程重新分配元组位置。

System R 的一个基本决策是在 RSS 内处理逻辑和物理锁定需求，而非将其拆分到 RDS 和 RSS 子系统之间。物理锁定通过在单个 RSI 操作执行期间设置并保持一或多页上的锁来处理。逻辑锁定通过在段、关系、TID 和键值区间等对象上设置锁来处理，保持到显式释放或事务结束。做出此决策的主要动机是便于探索替代锁定技术。（一种特定的替代方案已作为调优选项包含在 RSS 中，据此段中最细粒度的锁定级别可以扩展到整个数据页，而非单个元组。该选项允许页面同时用于逻辑和物理目的锁定，通过变化锁的持续时间。）其他动机是简化 RDS 的工作，以及开发一个完整、支持并发用户的 RSS，可针对未来的研究应用进行定制。

另一个基本决策是自动化所有锁定功能（逻辑和物理），以便用户可以访问共享数据并将部分或全部锁协议委托给系统。对于最终用户或 RDS 检测到的需要锁定大聚合体的场景，RSS 还支持在整段或整关系上放置显式共享或排他锁的运算符。

一致性级别： RSS 支持多个一致性级别，控制用户与其他并发用户行为的隔离程度。当在 RSI 启动事务时，必须指定以下三个级别之一：

• 级别 1： 最低隔离，最低开销和锁争用。可能访问脏数据，同一事务内可能读取同一数据项的不同值。适用于从大型数据库收集统计信息且无需精确结果的场景。
• 级别 2： 确保读取的每个项都是干净（已提交）的。但不对后续访问同一项的值或关联访问提供保证。读取后其他事务可能修改数据。使用 HOLD 选项防止丢失更新。
• 级别 3： 用户看到逻辑上等价于单用户系统的视图。每个读项都是干净的，后续读取产生相同的值（可重复读）。消除了丢失更新问题，保证读取任何元组集合的逻辑一致版本。

RSS 自动设置锁以保证各种一致性级别的逻辑功能。例如，在某些情况下 RSS 必须在元组上设置锁（如当它们被插入或更新时），在另一些情况下必须在索引值或索引值范围上设置锁（即使这些值当前不在索引中——如上述 'Smith' 案例的处理）。在这两种情况下，RSS 还必须在一个或多个页面上获取物理锁，这些锁至少在每次 RSI 操作执行期间保持，以确保数据和索引页面被正确访问和维护。

RSS 采用单一锁机制同步对所有对象的访问。此同步由每个 RSS 激活中的一组过程处理，这些过程在共享读/写内存中维护一组称为门 (gates) 的队列结构。其中一些门是编号的，按约定与缓冲区内容表或数据库的可处理性等资源关联。然而，为了处理像元组本身这样可能非常庞大的对象集合上的锁，RSS 还包含一个命名门 (named gate) 设施。内部组件可以通过提供对象的八字符名称（如元组标识符、索引值或页码）来请求锁。如果命名资源已被锁定，它将有门。如果没有，则从编号门的特殊池中分配一个命名门。当命名门的队列变空时，命名门被释放。

内部的锁请求有若干参数：对象名称、锁模式（共享、排他或下述其他各种模式）、以及锁持续期间的指示，以便 RSS 可以快速释放为单个 RSI 调用持有的所有锁，或为整个事务持有的所有锁。锁的持续时间也用于调度目的，例如在检测到死锁时选择事务进行回退。

锁持续时间的选择受若干因素影响，如用户请求的操作类型和事务的一致性级别。如果元组在任何一致性级别被事务插入或更新，则在事务结束前必须在元组（或某个超集）上持有排他锁。如果元组被删除，则在事务期间必须在元组的 TID 上持有排他锁，以保证在事务回退期间删除可以被正确撤销。对于这些情况以及下文所述的情况，通常在页面本身上设置一个额外的锁，以防止物理级别的事务冲突。然而，这些页面锁在 RSI 调用结束时释放。

对于级别 3 一致性的事务，必须在事务期间在所有被读取的元组和索引值上保持共享锁，以确保可重复性。对于级别 2 一致性的事务，读访问需要具有即时持续时间的共享锁。这样的锁请求排在较早的排他锁请求之后，以确保用户读取到干净数据。然后锁在请求被授予后立即释放，因为读操作不需要可重复。最后，对于级别 1 一致性的事务，读操作不需要锁，除了页面上的短锁以确保读操作正确。

数据项可以在各种粒度上锁定，以确保各种应用高效运行。例如，单条元组上的锁对访问少量数据的事务有效，而整关系或甚至整段上的锁对导致 RDS 访问大量数据的事务更合理。为适应各种应用需求，开发了动态锁层次协议，可使用少量锁来锁定少数或多量对象 [13]。基本思想是每个粒度级别（段、关系、元组）关联单独的锁。意图锁 (intent lock) 用于在细粒度级别获取锁之前隐式锁定粗粒度级别的协议。如果 RDS 以共享或排他模式请求整个段的锁，则段中每个关系的每条元组都被隐式地以相同模式锁定。如果 RDS 请求单个关系的锁（比如排他模式），但不希望排他访问整个段，则 RSS 在请求关系排他锁之前，首先生成在段上以意图排他模式自动请求锁。此意图排他锁与其他意图锁兼容，但与共享和排他锁不兼容。相同的协议通过自动获取段和关系上的意图锁，扩展到在共享或排他模式下获取单个元组上的锁。

由于锁是动态请求的，RSS 的两个或多个并发激活可能死锁。RSS 被设计为在请求被阻塞时检查死锁情况，并在检测到死锁时选择一个或多个牺牲者进行回退。检测由 Monitor 定期执行，通过查找用户-用户矩阵中的循环。牺牲者的选择基于每个死锁循环中事务的相对年龄以及锁的持续时间。一般来说，RSS 选择最年轻的事务，其锁为短持续时间（即为单个 RSI 调用的持续时间持有），因为部分完成的调用可以很容易被撤销。如果循环中没有任何锁是短持续时间的，则选择最年轻的事务。然后使用上述事务恢复方案，将该事务回退到违规锁请求之前的保存点。

系统检查点与重启

RSS 提供在系统崩溃时将数据库恢复到一致状态的功能。所谓一致状态，是指如果一组事务已完成且没有其他事务在进行中，所产生的一组数据值。在此状态下，所有映像和链接指针在 RSS 级别是正确的，更重要的是所有用户定义的数据完整性断言在 RDS 级别是有效的，因为 RDS 在事务边界保证所有完整性约束。

在 RSS 中，特别注意减少从磁盘到磁带进行完整数据库转储以完成系统检查点的需要。数据库转储技术有若干困难：由于将数据库复制到磁带的时间可能很长（对于大型数据库），检查点可能不频繁地进行（如过夜或每周）。系统重启则是一个耗时的过程，因为必须从系统日志重建许多数据库更改以恢复最近的数据库状态。此外，在执行检查点之前，所有进行中的事务必须首先完成。如果其中任何事务很长，则在长事务完成且数据库转储完成之前，不允许启动新事务。

在 RSS 中开发了两种系统恢复机制以缓解这些困难。第一种机制使用磁盘存储在"软"故障（导致主存内容丢失）时恢复；它面向频繁检查点和快速恢复。第二种机制使用磁存储在相对罕见的磁盘存储被破坏的情况下恢复；它面向较不频繁的检查点。在两种机制中，检查点可以在事务仍在进行中时进行。

磁盘导向恢复 严重依赖于上述段恢复功能和事务日志的可用性。Monitor Machine 负责基于系统启动时设置的参数调度检查点。当需要检查点时，Monitor 在物理一致性点停顿 RSS 内的所有活动：事务可能仍在进行中，但不得正在执行 RSI 操作。停顿 RSS 活动的技术是获取一个特殊的 RSS 锁（排他模式），每个 RSS 代码激活在执行 RSI 操作之前以共享模式获取此锁，操作结束时释放。然后 Monitor 发出 SAVE-SEGMENT 运算符，使所有相关段的磁盘副本更新。最后释放 RSS 锁，事务恢复。

当软故障发生时，使用 RESTORE-SEGMENT 运算符恢复所有已保存段的内容。回忆一下，恢复功能相对简单，涉及将当前页图值设置为等于备份页图值，并释放自保存点以来分配的页面。日志段比普通数据段更频繁地保存（在每次事务结束时有效保存），并包含修改数据的"之后"值以及"之前"值。因此，在最后一次数据库保存之后但在最后一次日志保存之前完成的事务可以被自动重做。此外，事务日志用于回退在检查点处未完成且无法重做的事务，以到达一致的数据状态。

磁带导向恢复 是上述方案的扩展。为了在磁盘数据丢失时恢复，需要某种技术将足够的数据和日志信息副本获取到磁带上。我们选择的技术是让 Monitor 将某些检查点调度为"长"检查点而非标准短检查点。长检查点执行上述通常的段保存操作，但也启动一个将保存的页面从磁盘复制到磁带的过程。因此到磁带的检查点是增量的。

4. 总结与结论

我们描述了 System R 的整体架构及两个主要组件：关系数据系统 (RDS) 和关系存储系统 (RSS)。

RSS 是支持 System R 的并发用户数据管理子系统。RSI 具有单条元组级别操作，使用多级索引结构自动维护任意数量的值排序（称为映像）。RSS 还通过维护称为链接的指针链结构支持从一个关系的元组到另一关系的元组的高效导航。映像和链接，连同通过 RSS 页面的物理扫描，构成了 RDS 高效支持关系、层次和网络数据模型运算符的访问路径原语。此外，为方便逐步数据集成和变化的性能需求，RSS 支持关系和索引和链接的动态添加与删除（完全空间回收），以及向现有关系添加新字段——全部无需特殊工具或数据库重组。

RSS 的另一个重要方面是通过共享读/写内存中的门结构完全支持多处理器环境中的并发访问。提供多个一致性级别以控制每个用户与其他用户的交互。锁在 RSS 内自动设置。这些锁设置在各种粒度的数据对象上，以适应各种应用环境类型。

在恢复领域，事务回退提供到任意数量的用户指定保存点中任一点的回退，以辅助长应用程序的恢复。提供了一种新的系统级恢复方案，使检查点和重启操作均可高效执行。

RDS 支持 System R 的外部接口 RDI，为用户提供数据检索、操纵、定义和控制的一致功能集。RDI 设计为一组可从宿主程序直接调用的运算符。预期将在 RDI 之上编写程序以实现各种独立关系接口和其他可能非关系型接口。

RDS 最重要的组件是优化器，它使用 RSS 访问路径原语规划高层次操作的高效执行。在优化查询时，元组在物理存储中的排列方式至关重要。RDS 在插入操作期间向 RSS 提供聚集提示，使关系的元组按某种值排序物理聚集，或沿二元链接放置在与关联元组相近的位置。给定已存储关系的聚集属性，优化器使用一种主要强调减少主存与在线直访存储之间 I/O 操作次数的访问路径策略。

除优化器外，RDS 还包含其他各种功能的组件：授权组件允许关系或视图的创建者授予或撤销各种能力。完整性系统自动执行通过 SEQUEL 命令输入的关于数据库值的断言。触发器机制在检测到给定操作时触发一或多条数据库操作。SEQUEL 语言也可用于将任何查询定义为命名视图，物化此视图的访问计划由优化器选择，并可存储为预优化包 (POP) 供后续执行。POP 对重复运行的事务尤为重要，因为它们避免了通常与高层次数据独立性相关联的大部分开销。

附录 I. RDI 运算符

方括号 [ ] 表示可选参数。

数据定义和操纵运算符：

SEQUEL ( [ <游标名>, ] <任何 SEQUEL 语句> )
FETCH ( <游标名> [, <指向 I/O 位置的指针>] )
FETCH-HOLD ( <游标名> [, <指向 I/O 位置的指针>] )
OPEN ( <游标名>, <关系或视图名> )
CLOSE ( <游标名> )
KEEP ( <游标名>, <新关系名>, <新字段名列表> )
DESCRIBE ( <游标名>, <度>, <指向 I/O 位置的指针> )
BIND ( <程序变量名>, <程序变量地址> )

事务和锁运算符：

BEGIN-TRANS ( <事务 id>, <一致性级别> )
END-TRANS
SAVE ( <保存点名称> )
RESTORE ( <保存点名称> )
RELEASE ( <游标名> )

附录 II. SEQUEL 语法

以下为 SEQUEL BNF 语法的精简版本。方括号 [ ] 表示可选结构。

语句 ::= 查询 | DML语句 | DDL语句 | 控制语句

DML语句 ::= 赋值 | 插入 | 删除 | 更新

查询 ::= 查询表达式 [ ORDER BY 排序规格列表 ]

赋值 ::= 接收者 ← 查询表达式
接收者 ::= 表名 [ ( 字段名列表 ) ]

插入 ::= INSERT INTO 接收者 : 插入规格
插入规格 ::= 查询表达式 | 文字

删除 ::= DELETE 表名 [ 变量名 ] [ WHERE子句 ]

更新 ::= UPDATE 表名 [ 变量名 ] SET子句列表 [ WHERE子句 ]

WHERE子句 ::= WHERE 布尔表达式
            | WHERE CURRENT [ TUPLE ] OF [ CURSOR ] 游标名

查询表达式 ::= 查询块
             | 查询表达式 集合操作 查询块
             | ( 查询表达式 )

集合操作 ::= INTERSECT | UNION | MINUS

查询块 ::= SELECT子句 FROM 来源列表
           [ WHERE 布尔表达式 ]
           [ GROUP BY 字段规格列表 [ HAVING 布尔表达式 ] ]

SELECT子句 ::= SELECT [ UNIQUE ] 选择表达式列表
             | SELECT [ UNIQUE ] *

来源列表 ::= 表名 [ 变量名 ]
           | 来源列表 , 表名 [ 变量名 ]

布尔表达式 ::= ... (比较、AND、OR、NOT 等)

比较 ::= = | ¬= | > | >= | < | <= | CONTAINS | DOES NOT CONTAIN | IN

集合函数 ::= AVG | MAX | MIN | SUM | COUNT

DDL语句 ::= CREATE TABLE | EXPAND TABLE | KEEP TABLE
           | CREATE IMAGE | CREATE LINK | DEFINE VIEW
           | DROP | COMMENT

CREATE TABLE ::= CREATE [永久/临时] [共享/私有] TABLE 表名 : 字段定义列表

字段定义 ::= 字段名 ( 类型 [ , NONULL ] )
类型 ::= CHAR(整数) | CHAR(*) | INTEGER | SMALLINT
        | DECIMAL(整数,整数) | FLOAT

控制语句 ::= ASSERT | ENFORCE INTEGRITY | DEFINE TRIGGER
            | GRANT | REVOKE

GRANT ::= GRANT [ 授权 ] 表名 TO 用户列表 [ WITH GRANT OPTION ]

操作 ::= READ | INSERT | DELETE | UPDATE [ (字段名列表) ]
        | DROP | EXPAND | IMAGE | LINK | CONTROL

附录 III. RSI 运算符

RSI 运算符面向格式化控制块的使用。方括号 [ ] 表示可选参数。

段上的运算符：

OPEN-SEGMENT ( <段id> )
CLOSE-SEGMENT ( <段id> )
SAVE-SEGMENT ( <段id> )
RESTORE-SEGMENT ( <段id> )

事务和锁上的运算符：

START-TRANS ( <一致性级别> )
END-TRANS
SAVE-TRANS, RETURNS ( <保存id> )
RESTORE-TRANS ( <保存id> )
LOCK-SEGMENT ( <段id>, <模式: SHARE 或 EXCLUSIVE 或 SIX> )
LOCK-RELATION ( <段id>, <关系id>, <模式, 同上> )
RELEASE-TUPLE ( <段id>, <tid> )

元组和扫描上的运算符：

FETCH ( <段id>, <关系id>, <标识符: tid/scanid/imageid>,
        <键值>, <字段列表>, <指向I/O位置的指针> [, HOLD] )

INSERT ( <段id>, <关系id>, <指向I/O位置的指针>
         [, <邻近tid>] ), RETURNS ( <tid> )

DELETE ( <段id>, <关系id>, <标识符, 同上> )

UPDATE ( <段id>, <关系id>, <标识符, 同上>,
         <字段列表>, <指向I/O位置的指针> )

OPEN-SCAN ( <段id>, <路径: relid/imageid/linkid>,
            <起点: 键值/tid/scanid> ), RETURNS ( <scanid> )

NEXT ( <段id>, <scanid>, <字段列表>, <指向I/O位置的指针>
       [, <搜索参数>] [, HOLD] )

CLOSE ( <段id>, <scanid> )

PARENT ( <子段id>, <链接id>, <标识符>,
         <字段列表>, <指向I/O位置的指针> [, HOLD] )

CONNECT ( <子段id>, <链接id>, <标识符>,
          <邻居关系id>, <邻居tid>, <位置: BEFORE/AFTER> )

DISCONNECT ( <子段id>, <链接id>, <标识符> )

数据定义运算符：

CREATE ( <段id>, <对象类型: REL/IMAGE/LINK>, <规格> ),
        RETURNS ( <对象标识符: relid/imageid/linkid> )

DESTROY ( <段id>, <对象标识符, 同上> )

CHANGE ( <段id>, <对象标识符, 同上>, <新规格> )

READSPEC ( <段id>, <对象标识符, 同上>, <指向I/O位置的指针> )

致谢

作者们感谢与关系数据模型创始人 E. F. Codd 以及 IBM 圣何塞研究实验室计算机科学部经理 L. Y. Liu 的许多有益讨论。我们还要感谢 Phyllis Reisner 对 System R 的广泛贡献，她的人因实验（报告于 [24, 25]）使 SEQUEL 语言得到了显著改进。

参考文献