4.3 声明式编程

除了流之外，数据值通常存储在称为数据库的大型存储库中。 数据库由一个包含数据值的数据存储以及一个用于检索和转换这些值的接口组成。存储在数据库中的每个值称为一个记录。 具有类似结构的记录被分组到表中。使用查询(查询是查询语言中的语句)检索和转换记录。 到目前为止，目前使用的最普遍的查询语言称为结构化查询语言或SQL(发音为“sequel”)。

SQL是声明性编程语言的一个例子。 语句不直接描述计算，而是描述某些计算的预期结果。 数据库系统的查询解释器的角色是设计并执行一个计算过程来产生这样的结果。

这种交互与Python或Scheme的过程编程范式有本质区别。 在Python中，计算过程由程序员直接描述。 声明性语言抽象出过程细节，而专注于结果的形式。

4.3.1 表

SQL语言是标准化的，但是大多数数据库系统实现了该语言的一些自定义变体，这些变体被赋予了专有的特性。 在本文中，我们将描述在Sqlite中实现的SQL的一个小子集。 您可以通过下载Sqlite或使用这个在线SQL解释器来跟随本文。

表(也称为关系)有固定数量的命名列和类型化列。 表的每一行代表一个数据记录，每一列有一个值。 例如，一个城市表可能有包含数值的列latitude longitude，以及包含字符串的列名。 每一行通过其纬度和经度值表示城市位置位置。

在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!

排序子句。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;

通过将多个表合并成一个表来组合数据，这是数据库系统中的基本操作。 有许多连接的方法，都是密切相关的，但我们将集中在这篇文章的一种方法。 当表被连接时，结果表为输入表中的每个行组合包含一个新行。 如果两个表被连接，左边的表有m行，右边的表有n行，那么连接的表将有m*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允许我们使用关键字as在from子句中为表提供别名，并使用点表达式引用特定表中的列。下面的select语句计算不相等城市对之间的温差。where子句中的字母排序约束确保每个pair在结果中只出现一次。

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函数创建的，该函数返回tuple的新子类，为tuple中的每个元素命名。

考虑下一节中列出的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语句的结果。考虑上一节的距离表，下面重复。

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语句的子句构造的类select的实例

>>> class Select:
        """select [columns] from [tables] where [condition] order by [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):
            """Join, filter, sort, and map rows from tables to columns."""
            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函数是通过调用create_make_row在Select构造函数中创建的，create_make_row是一个高阶函数，它为结果表创建一个新类，并定义如何将输入行投影到输出行。(这个函数的一个版本在sql中有更多的错误处理和特殊情况。)

>>> def create_make_row(description):
        """Return a function from an input environment (dict) to an output row.
        description -- a comma-separated list of [expression] as [column name]
        """
        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):
        """Return an iterator over dictionaries from names to values in a row.
        tables -- a comma-separate sequences of table names
        env    -- a dictionary from global names to tables
        """
        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):
        """Create an environment of names bound to values."""
        env = dict(zip(names, rows))
        for row in rows:
            for name in row._fields:
                env[name] = getattr(row, name)
        return env

以上，行。_fields的计算结果是包含行的表的列名。_fields属性之所以存在，是因为行的类型是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)

The example above is equivalent to the following SQL statement.

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的执行方法。 到目前为止，解释器可以正确地执行文本中包含的所有SQL语句。 虽然这个简单的解释器只实现了完整结构化查询语言的一小部分，但它的结构演示了序列处理操作和查询语言之间的关系。

查询计划。 声明性语言描述结果的形式，但不显式地描述应该如何计算该结果。 这个解释器总是连接、筛选、排序，然后投影输入行，以计算结果行。 然而，可能存在更有效的方法来计算相同的结果，并且查询解释器可以自由地选择其中之一。选择高效的程序来计算查询结果是数据库系统的核心特征。

例如，考虑上面的最后一个select语句。 与计算城市和距离的连接然后过滤结果不同，可以通过以下方法计算相同的结果：首先按名称列对两个表进行排序，然后在经过排序的表的线性过程中只连接具有相同名称的行。当表很大时，从查询计划选择中获得的效率收益非常可观。

4.3.5 递归Select语句

Select语句还可以包含一个with子句，用于生成和命名用于计算最终结果的附加表。不包括联合语句，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关键字确保聚合中不包含列中的重复值。在动物表中只有两种不同的腿值。特殊的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语句应该至少包含一个聚合列，并且只有在内容可从聚合中预测的情况下才包括非聚合列。