IBM 圣何塞研究实验室，加利福尼亚州圣何塞
Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control,
Ann Arbor, Michigan, May 1974
摘要：本文提出了一种结构化英语查询语言（SEQUEL）的数据操纵功能，可用于访问集成关系数据库中的数据。SEQUEL 无需引入约束变量和量词的概念，在表格结构上定义了一组简单操作，这些操作被证明与一阶谓词演算具有同等的表达能力。SEQUEL 用户面对的是一套一致的英语关键词模板，这些模板反映了人们如何使用表格获取信息的方式。此外，SEQUEL 用户可以以结构化的方式组合这些基本模板，从而形成更复杂的查询。SEQUEL 旨在作为一种数据库子语言，同时服务于专业程序员和偶尔使用的数据库用户。
CR 分类：3.5, 3.7, 4.2 | 关键词：查询语言，数据库管理系统，信息检索，数据操纵语言
随着计算机系统的进步，我们目睹了从过程式问题描述到声明式问题描述的逐步演进。有两个主要原因推动了这一演进。首先，必须找到降低专业程序员软件成本的方法。程序的创建、维护和修改成本一直在快速上升。结构化编程的概念(1, 2)被引入以简化编程并降低软件成本。其次，越来越需要让非专业用户能够与格式化数据库进行有效通信。计算机行业的大部分成功取决于培养出一类不同于训练有素的计算机专家的用户群体。
本文所展示的结构化英语查询语言（SEQUEL）的工作，与声明式问题描述这一趋势是一致的。它试图识别数据库用户所需的基本功能，并开发出一套简单且一致的规则，将这些功能应用于数据。这些规则旨在简化专业人员的编程工作，同时使数据库交互能够惠及一类新的用户群体。
这里有必要简要讨论一下这类新用户群体。有些用户与计算机的交互过于稀少或非结构化，以至于他们不愿意学习一种查询语言。对于这些用户，自然语言或菜单选择(3, 4)似乎是最可行的替代方案。然而，还存在一个庞大的用户群体：他们虽然并非计算机专家，但愿意学习一种合理的高层级、非过程式查询语言来与计算机交互。会计师、工程师、建筑师和城市规划师就是这类用户的例子。SEQUEL 正是为这类用户群体设计的。出于这个原因，SEQUEL 强调简单的数据结构和操作。
在一系列论文中，E. F. Codd(5–9)引入了数据的关系模型，这似乎是最简单的通用数据结构，并且提供了最大程度的数据独立性。在本文中，我们仅讨论规范化关系，它可以被视为具有 n 列和可变行数的表格，如图 1 所示。
| EMP | NAME | SAL | MGR | DEPT |
|---|---|---|---|---|
| SMITH | 10000 | JONES | TOY | |
| JONES | 12000 | ANDERSON | FURNITURE | |
| LEE | 10000 | THOMAS | APPLIANCES |
图 1. 描述雇员的关系。
除了引入关系数据结构之外，Codd 还定义了一种允许以关系格式访问或引用数据的语言(9)。这种语言以及类似的 COLARD(10)、RIL(11) 都基于一阶谓词演算。这些语言中的查询通常要求：
I. 用户定义额外的变量，其值为关系的行或部分行；以及
II. 用户使用布尔表达式及全称和存在量词来陈述查询。
Knuth(12) 已经表明，FORTRAN 中的大多数语句都相当简单。我们认为这对于数据库查询也是如此。我们之前已提出了一种名为 SQUARE 的数据子语言(13, 14)，它提供了一种简单直观的机制来引用表中的数据。SQUARE 使得用户能够以面向集合的表格查找方式来描述数据选择，而不是逐行进行的方式。这使得可以消除量词以及用于关联多个表中信息的显式链接项。因此，SQUARE 用户不需要具备谓词演算的数学素养即可对表格做出相对简单的引用。然而，已有证明表明 SQUARE 语言是完备的，即任何可以在谓词演算中表达的查询都可以在 SQUARE 中表达(14)。
本文尝试总结 SQUARE 工作的要点，并报告后续为未受过训练的用户开发一种比 SQUARE 简洁数学符号更熟悉的记法的工作。在开发这种新语法的过程中，我们努力牢记自顶向下结构化编程的概念、线性记法的需求以及易维护、易修改的可读程序的需求。最终产生的语法可以最恰当地描述为一种块结构化的英语关键字语法。
在本节中，我们将通过一系列示例来回顾 SQUARE 查询语言的主要特性。对这些特性更精确的定义可以在文献(13)中找到。在后续章节中，SEQUEL 的查询功能将被引入并应用于同一组示例以及其他示例。
本节及后续章节中的所有示例均取自一个描述百货商店运营的数据库，该数据库包含五张表：
| EMP (NAME, DEPT, MGR, SAL, COMM) |
| SALES (DEPT, ITEM, VOL) |
| SUPPLY (SUPPLIER, ITEM, VOL) |
| LOC (DEPT, FLOOR) |
| CLASS (ITEM, TYPE) |
EMP 表为每位商店员工设置一行，记录其姓名、部门、经理、薪水和去年的佣金。SALES 表给出各年每个部门销售每种商品的销售量。SUPPLY 表给出各年每家供应商向商店供应各种商品的数量。LOC 表给出每个部门所在的楼层，CLASS 关系将销售的商品分类为不同类型。
SQUARE 中最简单的表达式称为映射（mapping），如下面的查询 Q1 所示。
Q1. 查找玩具部门员工的姓名。
EMP ('TOY')
NAME DEPT
一个映射由表名（EMP）、域（DEPT）、范围（NAME）和参数（'TOY'）组成。映射的值是命名表中范围列的值集合，这些值在域列中对应的值与参数匹配。映射模拟了人们使用表格的方式。在这个例子中，查找玩具部门员工的姓名，人们会沿着 EMP 表的 DEPT 列向下查找，找到 'TOY' 条目，然后列出对应的 NAME 条目。
映射的域或范围可以涉及多个列，如下面的 Q2 所示。Q2 的结果是一个 (姓名, 薪水) 对列表。
Q2. 查找在玩具部门工作且经理为 Anderson 的员工的姓名和薪水。
EMP ('TOY', 'ANDERSON')
NAME, SAL DEPT, MGR
映射可以通过将一个映射应用于另一个映射的结果来进行组合，如下面的 Q3 所示。
Q3. 查找二楼各部门销售的商品。
SALES ∘ LOC ('2')
DEPT DEPT FLOOR
从过程化角度看，LOC 映射产生一个部门集合，该集合作为 SALES 映射的参数；结果是该集合中任何部门销售的商品集合。从描述性角度看，查询以自顶向下、从左到右的方式书写，非常类似英文表达。用户希望从 SALES 中获取 ITEM，当 DEPT 满足某些条件时；这些条件被表示为 LOC 中的 DEPT，其中 FLOOR 的值为 '2'。
一般来说，映射的结果是一个值或元组的集合。值集合可以进一步通过应用数学函数如 SUM、COUNT、AVG、MAX 或 MIN 来处理：
Q4. 查找鞋部门员工的平均薪水。
AVG ( EMP' ('SHOE'))
SAL DEPT
EMP 上的撇号表示在应用 AVG 函数之前不会从集合中消除重复的薪水。
映射产生的集合也可以使用标准的集合运算符（并、交、差）进行处理，如下面的 Q5 所示：
Q5. 查找由 Levi 供应且在男装部门销售的商品。
SUPPLY ('LEVI') ∩ SALES ('MEN')
ITEM SUPPLIER ITEM DEPT
示例 Q6 展示了 SQUARE 的基本特性如何嵌套以形成复杂查询：
Q6. 查找二楼各部门销售的 A 类商品的总量。
SUM ( SALES CLASS ('A'), LOC ('2'))
VOL ITEM,DEPT ITEM TYPE DEPT FLOOR
SEQUEL 语言在表达能力上与 SQUARE 等价，但其目标受众是那些更习惯于英语关键字格式而非 SQUARE 简洁数学记法的用户。我们将通过回顾前一节的示例查询并引入一些新的示例来介绍 SEQUEL 的特性。
与 SQUARE 一样，最简单的 SEQUEL 表达式是一个映射，它指定一个表、一个域、一个范围和一个参数，如下面的 Q1 所示。
Q1. 查找玩具部门员工的姓名。
SELECT NAME
FROM EMP
WHERE DEPT = 'TOY'
该映射返回符合 DEPT = 'TOY' 测试条件的所有姓名的完整集合。
SEQUEL 为用户提供了一个一致的模板来表达简单查询。用户需要指定他希望 SELECT 的列、查询列所在的表（FROM）以及返回行需要满足的条件（WHERE）。SELECT-FROM-WHERE 块是该语言的基本构成部分。在交互式系统中，这个模板可能会呈现给用户，用户只需填空即可。对于简单的映射，SELECT-FROM-WHERE 块类似于 GIS(15) 和 IQF(16) 所采用的方法。
如果映射中的 WHERE 子句被省略，该映射将返回一个投影，即从整个表中选取的选定列的唯一值列表：
Q1.1. 列出 EMP 表中的所有部门。
SELECT DEPT
FROM EMP
类似地，如果省略 SELECT 子句和 FROM 关键字，映射将完整地返回所有满足 WHERE 子句条件的行，如下面的 Q1.2 所示：
Q1.2. 列出描述薪水大于 8000 的员工的行。
EMP WHERE SAL > '8000'
与 SQUARE 一样，域或范围可以涉及多个列，如下面的 Q2 所示：
Q2. 查找在玩具部门工作且经理为 Anderson 的员工的姓名和薪水。
SELECT NAME, SAL
FROM EMP
WHERE DEPT = 'TOY'
AND MGR = 'ANDERSON'
SEQUEL 高度显式的语法使我们能够在 WHERE 子句中构建逻辑测试。例如，值比较可以使用列名表达式，以及使用除等于以外的其他条件。以下示例 Q2.1 说明了这些要点。
Q2.1. 查找在 'ADMIN' 部门工作，或者薪水与佣金之和超过 10000 的员工的姓名。
SELECT NAME
FROM EMP
WHERE DEPT = 'ADMIN'
OR SAL + COMM > '10000'
与 SQUARE 一样，一个映射可以应用于另一个内部映射的结果，如下面的 Q3 所示。
Q3. 查找二楼各部门销售的商品。
SELECT ITEM
FROM SALES
WHERE DEPT =
SELECT DEPT
FROM LOC
WHERE FLOOR = '2'
再次需要注意到这个示例中自顶向下结构化编程的影响。在编写基本的 SELECT-FROM-WHERE 块时，用户写到了想要为 SALES 的 DEPT 字段指定匹配条件的位置。他既可以指定一个简单的值匹配，如 DEPT = 'TOY'，也可以像 Q3 中那样指定一个内部映射。如果他需要指定另一个映射，只需填写另一个 SELECT-FROM-WHERE 块即可。交互式系统同样可以辅助这个过程。因此，该语言被简化为几个基本构建块和一组用于组合这些块的简单规则。
在 SEQUEL 中，组合查询中外部映射和内部映射之间的匹配条件被显式地陈述（在 Q3 中为 '='）。我们利用这种显式性，允许将任何关系运算符（=, ≠, >, ≥, <, ≤）作为匹配条件。一般来说，内部映射生成一个值集合。外部映射返回命名表（Q3 中为 'SALES'）的行，其域值（Q3 中为 'DEPT'）与内部映射生成的某个值通过匹配条件进行比较。因此 Q3 返回由二楼任何部门销售的商品。
通过在匹配条件后面使用关键字 ALL，我们可以使外部映射返回其域值与内部映射生成的所有值进行比较的行。因此，在 Q3 中将 'DEPT =' 改为 'DEPT = ALL' 将返回由二楼所有部门销售的商品。这说明了 SQUARE 中所谓的"连接映射"(13)。Q3.1 是进一步的说明。
Q3.1. 查找薪水高于鞋部门任何员工的员工。
SELECT NAME
FROM EMP
WHERE SAL > ALL
SELECT SAL
FROM EMP
WHERE DEPT = 'SHOE'
一般情况下，任何比较运算符（>, < 等）都可以在任一侧或两侧用关键字 'ALL' 修饰，以便进行集合间的比较。当集合用于比较而不带 'ALL' 时，默认含义为"某个"（some）。
与 SQUARE 一样，我们可以通过将函数放在 SELECT 子句中，将数学函数应用于映射的结果，如下面的 Q4 所示。
Q4. 查找鞋部门员工的平均薪水。
SELECT AVG (SAL)
FROM EMP
WHERE DEPT = 'SHOE'
在 SEQUEL 中，重复值的问题通过以下默认规则解决：如果数学函数应用于映射的结果，映射将保留重复值；否则，消除重复值。这些默认设置可以被显式地覆盖。
Q4 是 SEQUEL 中一条通用规则的示例：SELECT 子句可以包含任何来自所使用表的列名的算术表达式。如果表达式中出现数学函数，其参数取自符合条件的表行集合。例如：
Q4.1. 列出鞋部门的每位员工及其与部门平均薪水的偏差。
SELECT NAME, SAL - AVG (SAL)
FROM EMP
WHERE DEPT = 'SHOE'
SEQUEL 中的并和交运算符的使用方式与 SQUARE 完全相同，如下面的 Q5 所示。
Q5. 查找由 Levi 供应且在男装部门销售的商品。
SELECT ITEM
FROM SUPPLY
WHERE SUPPLIER = 'LEVI'
∩
SELECT ITEM
FROM SALES
WHERE DEPT = 'MEN'
区分在一个映射内部使用 AND/OR 与在映射之间使用并/交的效果非常重要。第一种情况，由 AND/OR 分隔的子句作用于表的同一行；第二种情况，映射独立应用，然后将并/交运算应用于其结果。为了说明这一点，假设 EMP 表包含以下条目：
| NAME | DEPT | MGR |
|---|---|---|
| JOHN | SHOE | BOB |
| FRED | SHOE | FRANK |
| FRED | TOY | BOB |
| BILL | TOY | FRANK |
以下是两个示例查询的结果：
Q5.1. 映射内部使用 AND —— 结果：JOHN
SELECT NAME
FROM EMP
WHERE DEPT = 'SHOE'
AND MGR = 'BOB'
Q5.2. 映射之间使用 ∩ —— 结果：JOHN, FRED
SELECT NAME
FROM EMP
WHERE DEPT = 'SHOE'
∩
SELECT NAME
FROM EMP
WHERE MGR = 'BOB'
下面重复示例 Q6，展示 SEQUEL 特性如何嵌套以形成复杂查询：
Q6. 查找二楼各部门销售的 A 类商品的总量。
SELECT SUM (VOL)
FROM SALES
WHERE ITEM =
SELECT ITEM
FROM CLASS
WHERE TYPE = 'A'
AND DEPT =
SELECT DEPT
FROM LOC
WHERE FLOOR = '2'
请注意，在此查询中使用缩进来分隔各个映射并展示查询的结构。在实践中，将缩进设为可选并以分号终止每个映射可能更方便。那么在上述查询中，TYPE = 'A' 后面会有一个分号，FLOOR = '2' 后面会有两个分号。
SQUARE 查询语言的主要动机是开发一种访问关系数据库的简便方法。我们认为，基于应用谓词演算的语言及其变量和量词概念，对普通用户来说需要过多的数学素养。SQUARE 成功避免了约束变量和量词的概念，但当需要将表中特定行的值与另一行或多行的值相关联时，仍然需要一个自由变量。在 SQUARE 中，这类查询通常采用以下形式：
自由变量 : 测试条件
自由变量代表表的一行。查询结果是从使测试条件为真的行中取得的一组值。示例 Q7 说明了这一概念。
Q7 (SQUARE). 查找管理超过十名员工的经理姓名。
x EMP : COUNT ( EMP (x ) ) > 10
NAME NAME MGR NAME
请注意，在 Q7 中，自由变量 x 用于将经理的姓名与代表其员工的一组行相关联，以便对该组进行计数。经验表明，这种"分组"在查询中出现得非常频繁。因此，SEQUEL 提供了一种方式，按照一列或多列的值将表的行划分为组，这类似于信息代数中的 "glump" 概念(17)。任何 SEQUEL 中的 FROM 子句都可以附加一个可选的 GROUP BY 子句，其效果是表的行被视为按匹配的列值分组。
例如，如果一个查询包含子句 FROM EMP GROUP BY MGR，则 EMP 表的行将被按匹配的 MGR 值分组。在此子句的作用域内，对列引用的使用有一定的限制。分组列（上例中的 MGR）可以被引用，因为它每个分组只有一个值。可以对列值使用数学函数，其隐含规则是它们将一组列值作为参数，并为该组返回一个值。例如，在 FROM EMP GROUP BY MGR 的作用域内，函数 AVG(SAL) 将为每位经理返回其员工的平均薪水。其他函数如 SUM、COUNT 和 MAX 以类似的方式运行。非分组条件的列名除了作为返回每个分组单值的函数参数外，不能被引用。
示例 Q7 现在用 SEQUEL 重新编写，以说明 GROUP BY 特性：
Q7 (SEQUEL). 查找管理超过十名员工的经理姓名。
SELECT MGR
FROM EMP GROUP BY MGR
WHERE COUNT (NAME) > 10
分组概念由示例 Q8 进一步说明：
Q8. 列出各部门及各部门员工薪水的总和。
SELECT DEPT, SUM (SAL)
FROM EMP GROUP BY DEPT
如果需要，用户可以从常量构造一个字面值元组甚至整张表，以供查询使用。下面的 Q9 说明了这一点，同时也说明了特殊函数 SET，该函数返回由 GROUP BY 子句分组在一起的值集合。
Q9. 查找拥有名为 SMITH、JOHNSON 和 HUGHES 的员工、且他们的经理均为 JONES 的部门。
SELECT DEPT
FROM EMP
WHERE SET (NAME, MGR) =
{ <'SMITH', 'JONES'>,
<'JOHNSON', 'JONES'>,
<'HUGHES', 'JONES'> }
SQUARE 中仍有少数查询需要自由变量，以消除列引用中的歧义。在大多数情况下，可以通过在 SEQUEL 中用表名限定列名来解决歧义。下面的 Q10 说明了这一点，它实现了 Codd(7) 所说的 SALES 表和 SUPPLY 表在 ITEM 列上的"连接"：
Q10. 列出 SALES 和 SUPPLY 中 ITEM 值匹配时连接在一起的行。
SALES, SUPPLY
WHERE SALES.ITEM = SUPPLY.ITEM
在表名不足以解决歧义的情况下（因为同一个表名在查询中出现多次），SEQUEL 允许将任意选择的块标签附加到映射上，并用于限定列引用。下面的 Q11 说明了这一点。
Q11. 查找薪水高于其经理的员工的姓名。
B1: SELECT NAME
FROM EMP
WHERE SAL >
SELECT SAL
FROM EMP
WHERE NAME = B1.MGR
在此查询中，标记为 B1 的外部映射返回满足以下测试条件的所有行的 NAME 值：B1 行的 SAL 值必须大于其 NAME 与 B1 行的 MGR 相同的行的 SAL 值。
本节我们说明基于一阶谓词演算的语言(9–11)所表达查询与 SEQUEL 所表达查询在感知上的差异。基于演算的语言允许描述以对相关关系中各行进行测试的方式来进行。
考虑查询 Q6 在演算中的表达：
SUM { x[VOL] ∈ SALES :
(∃y ∈ CLASS) ((y[ITEM] = x[ITEM]) ∧ (y[TYPE] = 'A'))
∧ (∃z ∈ LOC) ((z[DEPT] = x[DEPT]) ∧ (z[FLOOR] = '2')) }
演算程序员必须关注：
y[ITEM] = x[ITEM] 和 z[DEPT] = x[DEPT]然而，我们之前已经展示过，这个查询在 SEQUEL 中可以通过简单地组合三个映射块来表达。当然，我们并不是说真正复杂的查询在 SEQUEL 中表达起来很简单；我们要强调的是 SEQUEL 和更传统方法之间的区别。这种感知上的差异在文献(13)中得到了更充分的讨论。
本文展示了基于数据关系模型的数据子语言的数据操纵功能（DMF）。该子语言也被用作数据定义功能（DDF）的基础(18)。DDF 和 DMF 共同构成了一种面向非计算机专家用户的查询功能。简单的块结构化英语关键字语法和简单的表格操作使得用户能够以较少的培训和数学素养与 SEQUEL 系统进行交互，而这在基于演算的系统或传统过程式编程语言中是无法做到的。
SEQUEL 用户通过集合表达式而非逐行迭代的方式来描述要访问的相关数据。由此产生的查询往往简洁、表达清晰，且易于编写、维护和修改。SEQUEL 查询的形式语法见附录。
作者感谢 M. M. Astrahan、E. D. Carlson、E. F. Codd、P. L. Fehder、W. F. King、P. Reisner 和 R. Williams 在 SEQUEL 开发过程中的交流互动。
(1) E. W. Dijkstra, "Structured Programming," Software Engineering Techniques, NATO Science Committee (ed. J. N. Buxton and B. Randell), 1969, pp. 88–93.
(2) F. T. Baker, "System Quality Through Structured Programming," Proc. AFIPS 1972 FJCC, vol. 41, 1972, pp. 339–343.
(3) F. B. Thompson, P. Lockemann, B. H. Dostert, R. Deverill, "REL: A Rapidly Extensible Language System," Proc. 24th ACM National Conference, New York, N.Y., August 1969, pp. 399–417.
(4) E. F. Codd, "Seven Steps to Rendezvous with the Casual User," IBM Research Report RJ 1333, IBM Research Laboratory, San Jose, Calif., January 1974.
(5) E. F. Codd, "A Relational Model of Data for Large Shared Data Banks," Comm. ACM, vol. 13, no. 6 (June 1970), pp. 377–387.
(6) E. F. Codd, "Further Normalization of the Data Base Relational Model," Courant Computer Science Symposia, vol. 6, Data Base Systems, Prentice-Hall, New York, May 1971.
(7) E. F. Codd, "Relational Completeness of Data Base Sublanguages," Courant Computer Science Symposia, vol. 6, Data Base Systems, Prentice-Hall, New York, May 1971.
(8) E. F. Codd, "Normalized Data Base Structure — A Brief Tutorial," Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control, San Diego, Calif., November 1971.
(9) E. F. Codd, "A Data Base Sublanguage Founded on the Relational Calculus," Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control, San Diego, Calif., November 1971.
(10) G. Bracchi, A. Fedeli, and P. Paolini, "A Language for a Relational Data Base Management System," Proc. of the Sixth Annual Princeton Conf. on Info. Sci. and Systems, March 1972, pp. 84–92.
(11) P. L. Fehder, "The Representation-Independent Language," IBM Technical Report RJ 1121, IBM Research Laboratory, San Jose, Calif., November 1972.
(12) D. E. Knuth, "An Empirical Study of FORTRAN Programs," Software — Practice and Experience, Vol. 1, No. 2 (April 1971), pp. 105–133.
(13) R. F. Boyce, D. D. Chamberlin, W. F. King III, and M. M. Hammer, "Specifying Queries as Relational Expressions," Proceedings of ACM SIGPLAN/SIGFIDET Interface Meeting on Programming Languages and Information Retrieval, Gaithersburg, Md., November 1973.
(14) R. F. Boyce, D. D. Chamberlin, W. F. King III, and M. M. Hammer, "Specifying Queries as Relational Expressions: SQUARE," IBM Technical Report RJ 1291, IBM Research Laboratory, San Jose, Calif., October 1973.
(15) J. H. Bryant and P. Semple, Jr., "GIS and File Management," Proceedings of ACM National Conference, 1966, pp. 97–107.
(16) "Interactive Query Facility (IQF) for IMS/360," Publication No. GH20-1074, IBM Corp., White Plains, N.Y., 1971.
(17) CODASYL, "An Information Algebra," Comm. ACM, 5, 4 (April 1962), pp. 190–204.
(18) R. F. Boyce and D. D. Chamberlin, "Using a Structured English Query Language as a Data Definition Facility," IBM Technical Report RJ 1318, IBM Research Laboratory, San Jose, Calif., December 1973.
注：[ ] 表示可选项，| 表示替代形式。