4.3 声明式编程

INFO

来源：4.3 Declarative Programming

除了流之外，数据值通常存放在称为数据库（database）的大型存储库中。数据库包含一个数据存储区，其中存放数据值，还提供检索和转换这些值的接口。存储在数据库中的每个值称为记录（record）。结构相似的记录归入同一张表（table）。记录通过查询（query）来检索和转换，查询是查询语言中的语句。时至今日，使用最广泛的查询语言是结构化查询语言（Structured Query Language），简称 SQL（读作「sequel」）。

SQL 是声明式编程语言的一个例子。SQL 语句不直接描述计算过程，而是描述某个计算期望得到的结果。设计并执行计算过程、产生这一结果，是数据库系统查询解释器（query interpreter）的职责。

这种交互方式与 Python 或 Scheme 的过程式编程范式大不相同。在 Python 中，计算过程由程序员直接描述。声明式语言把过程细节抽象掉，转而关注结果的形式。

4.3.1 表

SQL 语言是标准化的，但大多数数据库系统都实现了一些自定义变体，各自带有专有功能。本书描述的是 Sqlite 实现的一个 SQL 小子集。你可以 下载 Sqlite 或使用 在线 SQL 解释器 跟着一起操作。

一张表也称为关系（relation），它有固定数量的列，每列都有名称和类型。表的每一行代表一条数据记录，每列各有一个值。例如，一张城市表可能有两列存放数字值：经度和纬度，另有一列 name 存放字符串。每一行都用经度和纬度值表示一个城市的位置。

Latitude	Longitude	Name
38	122	Berkeley
42	71	Cambridge
45	93	Minneapolis

在 SQL 中，可以用 select 语句创建一张单行表，行值之间用逗号分隔，列名跟在关键字 「as」 后面。所有 SQL 语句都以分号结尾。

sqlite> select 38 as latitude, 122 as longitude, "Berkeley" as name;
38|122|Berkeley

第二行是输出结果，每行对应表的一行，各列之间用竖线分隔。

用 union 可以把两张表的行合并起来，构造出多行表。新表沿用左表的列名。一行内多余的空格不影响结果。

sqlite> select 38 as latitude, 122 as longitude, "Berkeley" as name union
   ...> select 42,             71,               "Cambridge"        union
   ...> select 45,             93,               "Minneapolis";
38|122|Berkeley
42|71|Cambridge
45|93|Minneapolis

用 create table 语句可以给表命名。这个语句也能用来创建空表，但我们重点关注它给已有表命名的形式，这个已有表由 select 语句定义。

sqlite> create table cities as
   ...>    select 38 as latitude, 122 as longitude, "Berkeley" as name union
   ...>    select 42,             71,               "Cambridge"        union
   ...>    select 45,             93,               "Minneapolis";

表一旦有了名字，就可以在 select 语句的 from 子句中使用这个名字。用特殊的 select * 形式可以显示表的所有列。

sqlite> select * from cities;
38|122|Berkeley
42|71|Cambridge
45|93|Minneapolis

4.3.2 Select 语句

select 语句可以定义一张新表：要么列出单行中的值，要么（更常见）用 from 子句对现有表做投影：

select [column description] from [existing table name]

结果表的各列由一串逗号分隔的表达式描述，每个表达式都会对现有输入表的每一行求值一次。

例如，我们可以创建一张两列的表，用每个城市相对伯克利偏北或偏南的距离来描述它。每一度纬度相当于向北 60 海里。

sqlite> select name, 60*abs(latitude-38) from cities;
Berkeley|0
Cambridge|240
Minneapolis|420

列描述是某个语言中的表达式，它与 Python 有很多共同点：中缀运算符，如 + 和 %；内置函数，如 abs 和 round；以及描述求值顺序的括号。这些表达式中的名称，比如上面的 latitude，求值为被投影那一行的列值。

每个表达式后面都可以选择性地跟关键字 as 和一个列名。当整张表要被命名时，通常最好给每列起个名字，这样将来就能在 select 语句中引用它。由简单名称描述的列会自动命名。

sqlite> create table distances as
   ...>   select name, 60*abs(latitude-38) as distance from cities;
sqlite> select distance/5, name from distances;
0|Berkeley
48|Cambridge
84|Minneapolis

Where 子句。 select 语句还可以包含一个带过滤表达式的 where 子句。这个表达式会过滤要投影的行。只有过滤表达式的求值结果为真值的行，才会用来在结果表中生成一行。

sqlite> create table cold as
   ...>   select name from cities where latitude > 43;
sqlite> select name, "is cold!" from cold;
Minneapolis|is cold!

Order 子句。 select 语句还可以对结果表排序。order 子句包含一个排序表达式，会对每个未被过滤掉的行求值。该表达式的求值结果用作结果表的排序依据。

sqlite> select distance, name from distances order by -distance;
84|Minneapolis
48|Cambridge
0|Berkeley

把这些特性组合起来，select 语句就能把输入表投影成各种各样的相关输出表。

4.3.3 连接

数据库通常包含多张表，查询可能需要用到不同表中的信息才能算出想要的结果。比如，我们可能有另一张表，描述不同城市的日平均最高气温。

sqlite> create table temps as
   ...>   select "Berkeley" as city, 68 as temp union
   ...>   select "Chicago"         , 59         union
   ...>   select "Minneapolis"     , 55;

把多张表连接（join）成一张表来组合数据，这是数据库系统的基本操作。连接的方法有很多，彼此密切相关，但本书只关注其中一种。连接表时，结果表中会为输入表各行的每一种组合生成一个新行。如果连接两张表，左表有 $m$ 行，右表有 $n$ 行，那么连接后的表就有 $m\cdot n$。在 SQL 中，连接用 select 语句的 from 子句中以逗号分隔的表名来表示。

sqlite> select * from cities, temps;
38|122|Berkeley|Berkeley|68
38|122|Berkeley|Chicago|59
38|122|Berkeley|Minneapolis|55
42|71|Cambridge|Berkeley|68
42|71|Cambridge|Chicago|59
42|71|Cambridge|Minneapolis|55
45|93|Minneapolis|Berkeley|68
45|93|Minneapolis|Chicago|59
45|93|Minneapolis|Minneapolis|55

连接通常还会搭配一个 where 子句，用来表达两张表之间的关系。例如，如果我们想把数据收集到一张表里，以便把纬度和气温关联起来，就要从连接结果中选出两张表都提到同一个城市的那些行。在 cities 表中，城市名存放在名为 name 的列中；在 temps 表中，城市名存放在名为 city 的列中。where 子句可以选出连接表中这两个值相等的行。在 SQL 中，数值相等用单个 = 符号来测试。

sqlite> select name, latitude, temp from cities, temps where name = city;
Berkeley|38|68
Minneapolis|45|55

表可能有重名的列，因此我们需要一种按表名区分列的办法。表也可能和自身连接，因此我们还需要一种区分表的办法。为此，SQL 允许在 from 子句里用关键字 as 给表起别名，并用点表达式引用某张表中的列。下面的 select 语句计算不同城市两两之间的温差。where 子句中的字母顺序约束保证每一对城市在结果中只出现一次。

sqlite> select a.city, b.city, a.temp - b.temp
   ...>        from temps as a, temps as b where a.city < b.city;
Berkeley|Chicago|10
Berkeley|Minneapolis|15
Chicago|Minneapolis|5

SQL 中组合表的两种方式，join 和 union，让这门语言具有很强的表达能力。

4.3.4 解释 SQL

要为目前介绍的这部分 SQL 创建一个解释器，我们需要：一个表示表的结构、一个把文本语句解析成可执行代码的解析器，以及一个执行解析后语句的求值器。sql 解释器示例包含了所有这些组件，演示了一个简单但功能完整的声明式语言解释器。

在这个实现中，每张表都有自己的类，表中的每一行都用它所属表这个类的一个实例来表示。一行中，表的每一列都对应一个属性；而表就是一个行的序列。

表的类是用 Python 标准库 collections 包中的 namedtuple 函数创建的，该函数返回一个新的元组子类，为元组中的每个元素命名。

考虑上一节的 cities 表，下面重复一遍：

sqlite> create table cities as
   ...>    select 38 as latitude, 122 as longitude, "Berkeley" as name union
   ...>    select 42,             71,               "Cambridge"        union
   ...>    select 45,             93,               "Minneapolis";

下面的 Python 语句为这张表构造了一个表示：

>>> from collections import namedtuple
>>> CitiesRow = namedtuple("Row", ["latitude", "longitude", "name"])
>>> cities = [CitiesRow(38, 122, "Berkeley"),
              CitiesRow(42,  71, "Cambridge"),
              CitiesRow(43,  93, "Minneapolis")]

用序列操作可以解释 select 语句的结果。考虑上一节的 distances 表，下面重复一遍：

sqlite> create table distances as
   ...>   select name, 60*abs(latitude-38) as distance from cities;
sqlite> select distance/5, name from distances;
0|Berkeley
48|Cambridge
84|Minneapolis

这张表由 cities 表的 name 列和 latitude 列生成。把函数映射到输入表的各行上，就能生成这张结果表：这个函数对每个 CitiesRow 返回一个 DistancesRow。

>>> DistancesRow = namedtuple("Row", ["name", "distance"])
>>> def select(cities_row):
        latitude, longitude, name = cities_row
        return DistancesRow(name, 60*abs(latitude-38))
>>> distances = list(map(select, cities))
>>> for row in distances:
        print(row)
Row(name='Berkeley', distance=0)
Row(name='Cambridge', distance=240)
Row(name='Minneapolis', distance=300)

我们的 SQL 解释器把这种做法推广开来：一个 select 语句表示为 Select 类的一个实例，由该语句的各个子句构造而成。

>>> class Select:
        """从 [tables] 中选择 [columns]，满足 [condition]，按 [order] 排序。"""
        def __init__(self, columns, tables, condition, order):
            self.columns = columns
            self.tables = tables
            self.condition = condition
            self.order = order
            self.make_row = create_make_row(self.columns)
        def execute(self, env):
            """把来自各表的行连接、过滤、排序，再映射到列上。"""
            from_rows = join(self.tables, env)
            filtered_rows = filter(self.filter, from_rows)
            ordered_rows = self.sort(filtered_rows)
            return map(self.make_row, ordered_rows)
        def filter(self, row):
            if self.condition:
                return eval(self.condition, row)
            else:
                return True
        def sort(self, rows):
            if self.order:
                return sorted(rows, key=lambda r: eval(self.order, r))
            else:
                return rows

execute 方法先连接输入表，再过滤和排序得到的行，然后把一个叫 make_row 的函数映射到这些行上。make_row 函数是在 Select 构造函数中调用 create_make_row 创建的，它是一个高阶函数，负责为结果表创建新类，并定义如何把输入行投影成输出行。（带更多错误处理和特殊情况处理的版本见 sql。）

>>> def create_make_row(description):
        """返回一个从输入环境（dict）到一行输出的函数。
        description -- 由 [表达式] as [列名] 组成的逗号分隔列表
        """
        columns = description.split(", ")
        expressions, names = [], []
        for column in columns:
            if " as " in column:
                expression, name = column.split(" as ")
            else:
                expression, name = column, column
            expressions.append(expression)
            names.append(name)
        row = namedtuple("Row", names)
        return lambda env: row(*[eval(e, env) for e in expressions])

最后，我们需要定义 join 函数来创建输入行。给定一个 env 字典，其中以表名为键存放现有表（即行的列表），join 函数用 itertools 包中的 product 函数把输入表中所有行的组合起来。然后它把一个叫 make_env 的函数映射到连接后的行上，这个函数把每一种行组合转换成一个字典，以便用来求值表达式。（带更多错误处理和特殊情况处理的版本见 sql。）

>>> from itertools import product
>>> def join(tables, env):
        """返回一个迭代器，遍历一行中从名称到值的字典。
        tables -- 逗号分隔的表名序列
        env    -- 从全局名称到表的字典
        """
        names = tables.split(", ")
        joined_rows = product(*[env[name] for name in names])
        return map(lambda rows: make_env(rows, names), joined_rows)
>>> def make_env(rows, names):
        """创建一个把名称绑定到值的环境。"""
        env = dict(zip(names, rows))
        for row in rows:
            for name in row._fields:
                env[name] = getattr(row, name)
        return env

上面的代码中，row._fields 求值为包含该行的表的列名。之所以存在 _fields 属性，是因为 row 的类型是一个 namedtuple 类。

我们的解释器已经足够完整，可以执行 select 语句了。例如，我们可以计算从伯克利到其他所有城市的纬度距离，并按经度排序。

>>> env = {"cities": cities}
>>> select = Select("name, 60*abs(latitude-38) as distance",
                    "cities", "name != 'Berkeley'", "-longitude")
>>> for row in select.execute(env):
        print(row)
Row(name='Minneapolis', distance=300)
Row(name='Cambridge', distance=240)

上面的例子等价于下面这条 SQL 语句：

sqlite> select name, 60*abs(latitude-38) as distance
   ...>        from cities where name != "Berkeley" order by -longitude;
Minneapolis|420
Cambridge|240

我们还可以把这张结果表存进环境，再和 cities 表连接起来，取出每个城市的经度。

>>> env["distances"] = list(select.execute(env))
>>> joined = Select("cities.name as name, distance, longitude", "cities, distances",
                    "cities.name == distances.name", None)
>>> for row in joined.execute(env):
        print(row)
Row(name='Cambridge', distance=240, longitude=71)
Row(name='Minneapolis', distance=300, longitude=93)

上面的例子等价于下面这条 SQL 语句：

sqlite> select cities.name as name, distance, longitude
   ...>        from cities, distances where cities.name = distances.name;
Cambridge|240|71
Minneapolis|420|93

完整的 sql 示例程序还包含一个简单的 select 语句解析器，以及 create table 和 union 的 execute 方法。这个解释器能正确执行前面出现的所有 SQL 语句。虽然这个简单的解释器只实现了完整结构化查询语言的一小部分，但它的结构展示了序列处理操作和查询语言之间的关系。

查询计划。 声明式语言描述结果的形式，但不明确描述结果该怎么算出来。这个解释器总是先连接、过滤、排序，再投影输入行，以此算出结果行。不过，算出同一结果可能有更高效的办法，查询解释器可以从中挑选。为查询结果挑选高效的计算过程，是数据库系统的核心特性。

例如，考虑上面的最后一条 select 语句。与其先计算 cities 和 distances 的连接再过滤结果，不如先按 name 列对两张表排序，再对排好序的表做一次线性遍历，只连接名称相同的行。当表很大时，查询计划选择带来的效率提升可能相当可观。

4.3.5 递归 Select 语句

select 语句可以选择性地包含一个 with 子句，用来生成并命名计算最终结果所需的附加表。不含 union 的 select 语句的完整语法如下：

with [tables] select [columns] from [names] where [condition] order by [order]

我们已经演示了 [columns] 和 [names] 的允许取值。[condition] 和 [order] 是可以对输入行求值的表达式。[tables] 部分是一个逗号分隔的列表，其中每个元素都是下面这种形式的表描述：

[table name]([column names]) as ([select statement])

任何 select 语句都可以用来描述 [tables] 中的一张表。

例如，下面的 with 子句声明了一张表 states，包含城市及其所在的州。select 语句计算出同一州内的城市对。

sqlite> with
   ...>   states(city, state) as (
   ...>     select "Berkeley",  "California"    union
   ...>     select "Boston",    "Massachusetts" union
   ...>     select "Cambridge", "Massachusetts" union
   ...>     select "Chicago",   "Illinois"      union
   ...>     select "Pasadena",  "California"
   ...>   )
   ...> select a.city, b.city, a.state from states as a, states as b
   ...>        where a.state = b.state and a.city < b.city;
Berkeley|Pasadena|California
Boston|Cambridge|Massachusetts

在 with 子句中定义的表可以有一个递归情况，用其他输出行来定义输出行。例如，下面的 with 子句定义了一张从 5 到 15 的整数表，从中选出奇数值并求平方。

sqlite> with
   ...>   ints(n) as (
   ...>     select 5 union
   ...>     select n+1 from ints where n < 15
   ...>   )
   ...> select n, n*n from ints where n % 2 = 1;
5|25
7|49
9|81
11|121
13|169
15|225

在 with 子句中可以定义多张表，用逗号分隔。下面的示例从一张整数表、它们的平方以及成对平方之和中，算出所有毕达哥拉斯三元组。毕达哥拉斯三元组由整数 a、b、c 组成，满足 $a^2+b^2=c^2$ 。

sqlite> with
   ...>   ints(n) as (
   ...>     select 1 union select n+1 from ints where n < 20
   ...>   ),
   ...>   squares(x, xx) as (
   ...>     select n, n*n from ints
   ...>   ),
   ...>   sum_of_squares(a, b, sum) as (
   ...>     select a.x, b.x, a.xx + b.xx
   ...>            from squares as a, squares as b where a.x < b.x
   ...>   )
   ...> select a, b, x from squares, sum_of_squares where sum = xx;
3|4|5
6|8|10
5|12|13
9|12|15
8|15|17
12|16|20

设计递归查询，要保证每个输入行中都有足够的信息来算出结果行。例如，要计算斐波那契数列，输入行不仅需要当前元素，还需要前一个元素，才能算出下一个元素。

sqlite> with
   ...>   fib(previous, current) as (
   ...>     select 0, 1 union
   ...>     select current, previous+current from fib
   ...>     where current <= 100
   ...>   )
   ...> select previous from fib;
0
1
1
2
3
5
8
13
21
34
55
89

这些示例说明，即使在声明式语言中，递归也是一种强大的组合手段。

构建字符串。 在 SQL 中，可以用 || 运算符把两个字符串拼接成一个更长的字符串。

sqlite> with wall(n) as (
  ....>   select 99 union select 98 union select 97
  ....> )
  ....> select n || " bottles" from wall;
99 bottles
98 bottles
97 bottles

这个特性可以用来拼接短语、构造句子。例如，构造英语句子的一种方式，是把主语名词短语、动词和宾语名词短语拼接起来。

sqlite> create table nouns as
  ....>   select "the dog" as phrase union
  ....>   select "the cat"           union
  ....>   select "the bird";
sqlite> select subject.phrase || " chased " || object.phrase
  ....>        from nouns as subject, nouns as object
  ....>        where subject.phrase != object.phrase;
the bird chased the cat
the bird chased the dog
the cat chased the bird
the cat chased the dog
the dog chased the bird
the dog chased the cat

作为练习，用递归的本地表生成诸如「the dog that chased the cat that chased the bird also chased the bird.」这样的句子。

4.3.6 聚合和分组

到目前为止介绍的 select 语句可以连接、投影和操作单个行。此外，select 语句还能对多行做聚合操作。聚合函数 max、min、count 和 sum 分别返回某列中值的最大值、最小值、个数和总和。通过定义多个列，可以把多个聚合函数应用到同一组行上。只有 where 子句包含的列才会纳入聚合。

sqlite> create table animals as
  ....>   select "dog" as name, 4 as legs, 20 as weight union
  ....>   select "cat"        , 4        , 10           union
  ....>   select "ferret"     , 4        , 10           union
  ....>   select "t-rex"      , 2        , 12000        union
  ....>   select "penguin"    , 2        , 10           union
  ....>   select "bird"       , 2        , 6;
sqlite> select max(legs) from animals;
4
sqlite> select sum(weight) from animals;
12056
sqlite> select min(legs), max(weight) from animals where name <> "t-rex";
2|20

关键字 distinct 保证聚合时不重复计入相同元素。比如 animals 表中 legs 列只有两个不同的值（2 和 4）。特殊的 count(*) 语法统计行的数量。

sqlite> select count(legs) from animals;
6
sqlite> select count(*) from animals;
6
sqlite> select count(distinct legs) from animals;
2

上面每个 select 语句都生成了一张只有一行的表。select 语句中的 group by 和 having 子句用来把行划分成组，并只选出其中一部分组。having 子句或列描述中的任何聚合函数都会独立作用于每个组，而不是表中整个行集。

例如，要从这张表算出四足动物和二足动物的最大体重，下面第一条语句把狗和猫归为一组，把鸟归为另一组。结果表明，二足动物的最大体重是 3（即鸟），四足动物的最大体重是 20（即狗）。第二个查询列出 legs 列中至少有两个不同名称的那些值。

sqlite> select legs, max(weight) from animals group by legs;
2|12000
4|20
sqlite> select weight from animals group by weight having count(*)>1;
10

group by 子句中可以出现多个列和完整表达式，并为每一种唯一的取值组合形成一组。通常，用于分组的表达式也会出现在列描述中，这样一眼就能看出哪些结果行来自哪个组。

sqlite> select max(name) from animals group by legs, weight order by name;
bird
dog
ferret
penguin
t-rex
sqlite> select max(name), legs, weight from animals group by legs, weight
  ....>   having max(weight) < 100;
bird|2|6
penguin|2|10
ferret|4|10
dog|4|20
sqlite> select count(*), weight/legs from animals group by weight/legs;
2|2
1|3
2|5
1|6000

having 子句可以包含与 where 子句相同的过滤条件，但也可以包含聚合函数的调用。为了获得最快的执行速度和最清晰的语言用法，应按内容过滤单个行的条件应放在 where 子句中，只有条件中需要聚合时才用 having 子句（比如指定一组的最小计数）。

使用 group by 子句时，列描述中可以包含不聚合的表达式。有时，SQL 解释器会从另一个带聚合的列所对应的那一行中取值。例如，下面的语句给出体重最大的动物的名称。

sqlite> select name, max(weight) from animals;
t-rex|12000
sqlite> select name, legs, max(weight) from animals group by legs;
t-rex|2|12000
dog|4|20

然而，一旦无法确定聚合对应哪一行（比如用 count 而不是 max 聚合），所选的值就可能是任意的。为了最清晰、最可预测地使用这门语言，带 group by 子句的 select 语句应至少包含一个聚合列；只有当非聚合列的内容可以从聚合推断出来时，才包含它们。