PDF大型共享数据库的协同关系数据模型
Erik Meijer 和 Gavin Bierman，微软
与普遍的看法相反，SQL 和 noSQL 实际上只是同一枚硬币的两面。
编者注：本文中的某些字符在某些浏览器中可能无法正确显示。
如果您遇到问题，请尝试使用其他浏览器或下载 PDF 文件。
由于 noSQL 数据库承诺以可扩展且对程序员友好的方式解决从大数据中提取有价值的信息和商业洞察力的问题，因此它们已成为我们领域最近最热门的话题之一。然而，由于开放源代码和商业产品（Membase、CouchDB、Cassandra、MongoDB、Riak、Redis、Dynamo、BigTable、Hadoop、Hive、Pig 等）以及随之而来的技术术语（Paxos、CAP、Merkle 树、gossip、向量时钟、宽松仲裁、MapReduce 等）的嘈杂声，企业和从业人员很难看清问题的本质。
当前的 noSQL 市场满足垄断竞争市场的三个特征：进入和退出的壁垒较低；供应商数量众多且规模较小；这些供应商生产技术上异构、高度差异化的产品。 12 垄断竞争市场与完全竞争的条件不一致。因此，从长远来看，垄断竞争企业将获得零经济利润。
在 1970 年代初期，数据库世界也处于类似的糟糕状态。14 过多的数据库产品暴露了许多底层实现细节，正如数据库人员喜欢说的那样，迫使程序员在物理层而不是逻辑层工作。当 Ted Codd 提出一种新的数据模型和一种基于关系和外键/主键关系的数学概念的结构化查询语言 (SQL) 时，这种局面发生了根本性的变化。4 在关系模型中，数据存储在概念上简单的容器（行表）中，并且对此数据的查询以声明方式表达，而无需了解底层的物理存储组织。
Codd 的关系模型和 SQL 允许来自不同供应商的实现成为（几乎）完美的替代品，因此为完全竞争提供了条件。关系模型和 SQL 的标准化围绕教育工作者、工具供应商、顾问等互补生产者创建了二级网络效应，所有这些都针对相同的底层数学原理。实际关系数据库实现和 SQL 方言之间的差异在很大程度上变得无关紧要。7
今天，关系数据库市场是寡头垄断的经典例子。市场上有少数大型参与者（Oracle、IBM、Microsoft、MySQL），进入壁垒很高，并且所有现有的基于 SQL 的关系数据库产品在很大程度上是无法区分的。寡头垄断可以在长期内保持高利润；今天，数据库行业的价值估计为 320 亿美元，并且仍在以两位数的速度增长。
在本文中，我们为最常见的 noSQL 数据库（即键/值关系）提出了一个数学数据模型，并证明该数据模型是 SQL 的外键/主键关系关系数据模型的数学对偶。按照既定的数学术语，我们将 SQL 的对偶称为 coSQL。我们还展示了关系代数在集合上的单一泛化（即单子和单子推导式）如何构成 SQL 和 noSQL 通用查询语言的基础。尽管普遍的看法认为 SQL 和 coSQL 是水火不容的，但实际上它们通过美丽的数学理论深刻地联系在一起。
正如 Codd 发现关系代数作为 SQL 的形式基础，将数据库行业从垄断竞争市场转变为寡头垄断，从而推动了围绕 SQL 和外键/主键存储的数十亿美元产业一样，我们相信我们的范畴数据模型形式化模型和单子查询语言将允许 coSQL 键值存储实现相同的经济增长。
对象与表
为了设定场景，让我们看一下 Amazon SimpleDB 示例中发现的带有作者和推荐的简单产品示例，并使用对象图和关系表来实现它。
虽然我们通常不这样认为，但用于存储对象图的 RAM 实际上是一个键值存储，其中键是地址（左值），值是存储在内存中某个地址的数据（右值）。与 C 或 C++ 不同，C# 和 Java 等语言不区分右值和左值，在 C 或 C++ 中，这种区别是显式的。在 C 中，指针解引用运算符*p检索存储在地址p在隐式全局存储中的值。在本文的其余部分，我们方便地混淆了对象（图）和键值存储这两个词。
在 C#（或任何其他现代面向对象语言）中，我们可以使用以下类声明对产品进行建模，该声明为每个产品提供标题、作者、出版日期和页数的标量属性，并包含两个嵌套集合——一个用于关键字，另一个用于评分
class Product
{
string Title;
string Author;
int Year;
int Pages;
IEnumerable<string> Keywords;
IEnumerable<string> Ratings;
}
给定此类声明，我们可以使用对象初始值设定项创建产品，并使用集合初始值设定项将其插入到集合中
var _1579124585 = new Product
{
Title = "The Right Stuff"
Author = "Tom Wolfe",
Year = 1979,
Pages = 320,
Keywords = new[]{ "Book", "Hardcover", "American" },
Ratings = new[]{ "****", "4 stars" },
}
var Products = new[]{ _1579124585 };
该程序在内存中生成图 1 所示的对象图。请注意，Keywords和Ratings属性的两个嵌套集合都由具有自身标识的实际对象表示。
使用 C# 3.0 中引入的 LINQ（语言集成查询）推导式语法11，我们可以使用以下查询查找所有具有四星级评分的产品的标题和关键字
var q = from product in Products
where product.Ratings.Any(rating⇒rating == "****")
select new{ product.Title, product.Keywords };
LINQ 推导式语法只是语法糖，用于一组标准查询运算符，这些运算符可以在任何具有闭包、lambda 表达式（此处写为rating⇒rating == "****"）、或内部类（例如 Objective-C、Ruby、Python、JavaScript、Java 或 C++）的现代编程语言中定义。C# 编译器将之前的查询转换为以下解语法糖的目标表达式
var q = Products.Where(product⇒
product.Ratings.Any(rating⇒rating == "****")).Select(product⇒
new{ product.Title, product.Keywords });
查询结果中的各种值，特别是Keywords集合，与原始对象图完全共享，结果是一个完全有效的对象图，如图 2 所示。
现在让我们使用关系模型重做此示例。首先，我们必须将嵌套的Product类规范化为三个平面表，分别用于Products, Keywords、和Ratings，如下所示。关系世界中的每个值都需要一个新的主键属性（此处都称为ID）。此外，Keywords和Ratings表需要一个额外的外键属性ProductID，用于编码Products和Keywords和Ratings之间的一对多关联。稍后我们将使用其他元数据修饰这些类声明，以反映底层的数据库表。
| class Products { int ID; string Title; string Author; int Year; int Pages; } |
class Keywords { int ID; string Keyword; int ProductID; } |
class Ratings { int ID; string Rating; int ProductID; } |
在大多数商业关系数据库系统中，表是通过执行命令式CREATE TABLEDDL 语句定义的。
与关系世界中通常的做法一样，我们不将每个产品的关键字和评分的单个集合建模为单独的实体，而是将多个关键字和评分直接关联到特定产品。此快捷方式仅适用于一对多关系。多对多关系（多值函数）的标准做法是需要包含外键对的交集表来链接相关的行。
对于一种“声明式”语言来说，令人惊讶的是，SQL 没有直接表示表或行的表达式。相反，我们必须使用松散类型的 DML 语句以命令式风格填充这三个表，我们在 C# 中将其表示为如下
| Products.Insert ( 1579124585 , "The Right Stuff" , "Tom Wolfe" , 1979 , 320 ); |
Keywords.Insert ( 4711, "Book" , 1579124585 ); Keywords.Insert ( 1843, "Hardcover" , 1579124585 ); Keywords.Insert ( 2012, "American" , 1579124585 ); |
Ratings.Insert ( 787, "****" , 1579124585 ); Ratings.Insert ( 747, "4 stars" , 1579124585 ); |
这些 DML 语句创建了三个表，其中填充了图 3 所示的行。
将单个类型规范化为单独的表的一个重要后果是，数据库必须维护引用完整性，以确保：跨相关表的外键/主键关系在表和行的突变中保持同步；每行的主键在其表中保持唯一；外键始终指向有效的主键。例如，我们不能删除Products表中的行，而不删除Keywords和Ratings表中的相关行。
引用完整性意味着封闭世界假设，其中数据库上的事务通过（概念上）同步暂停世界、应用所需更改并在成功恢复引用完整性时再次恢复世界来序列化，否则回滚任何更改。我们认为，假设封闭世界既是关系模型的优势，也是它的弱点。一方面，它通过 ACID（原子性、一致性、隔离性、持久性）事务简化了开发人员的生活（尽管在实践中，为了提高效率，人们常常必须处理弱得多的隔离级别），并允许令人印象深刻的（基于统计的）查询优化。然而，封闭世界假设与分布式和横向扩展直接矛盾。世界越大，就越难保持封闭。
回到我们的示例，我们展示了直接根据关系模型表达的查找所有具有四星级评分的产品的标题和关键字的简单查询。它创建了所有可能的Products, Keywords、和Ratings、和的组合的叉积，并仅选择title和和keyword和和，其中rating与product，其中相关，并且
var q = from product in Products
from rating in Ratings
from keyword in Keywords
where product.ID == rating.ProductId
&& product.ID == keyword.ProductID
&& rating == "****"
select new{ product.Title, keyword.Keyword };
此查询的结果是图 4 所示的行集。令人失望的是，此行集本身未规范化。
实际上，要返回对象图查询的规范化表示形式，我们需要对数据库执行两个查询（在单个事务中）：一个查询返回标题及其主键，另一个查询选择相关的关键字。
我们在此处观察到的是 SQL 缺乏组合性——从简单的值中任意组合复杂值而不会超出系统的能力。通过查看表行的语法定义，我们可以立即看到 SQL 缺乏组合性；由于没有递归，因此行只能包含标量值
row ::= new { ..., name = scalar, ... }
将其与匿名类型的定义进行比较，其中行可以包含任意值，包括其他行（或嵌套集合）
value ::= new { ..., name = value, ... } | scalar
SQL 充斥着非组合性功能。例如，NULL 的语义一团糟：为什么将数字 13 添加到 NULL 值13+NULL返回 NULL，但对相同的两个值求和SUM(13, NULL)，却返回 13？
此外，即使现代 SQL 实现中的查询优化器非常强大，但原始查询在通过三个嵌套循环（迭代三个表中的每个值）实现时，也可能会以立方时间运行。经验丰富的 SQL 程序员会改用显式 join 语法来确保查询与我们的基于对象的查询一样高效
var q = from product in Products
join rating in Ratings on product.ID equals rating.ProductId
where rating == "****"
select product into FourStarProducts
from fourstarproduct in FourStarProducts
join keyword in Keywords on product.ID equals keyword.ProductID
select new{ product.Title, keyword.Keyword };
根据使用平面结果集对 join 结果嵌套的编码，SQL 程序员必须在各种INNER, OUTER, LEFT、和RIGHTjoin 风格之间进行选择。
阻抗失配
1984 年，George Copeland 和 David Maier 认识到刚刚描述的关系模型和对象图模型之间的阻抗失配5，并且在四分之一世纪之后，我们看到了 O/R（对象关系）映射器的爆炸式增长，它们试图弥合两个世界之间的差距。
对 O/R 映射器更怀疑的看法是，它们正在消除将原始对象模型规范化为多个表所造成的损害。对于我们的运行示例，这意味着我们必须将信息添加回各个表中，以恢复原始模型中存在的关系。在这种特殊情况下，我们使用 LINQ-to-SQL 自定义元数据注释；其他 O/R 映射器使用类似的注释，这些注释通常可以从类型和属性的命名约定中推断出来。
[Table(name="Products")]
class Product
{
[Column(PrimaryKey=true)]int ID;
[Column]string Title;
[Column]string Author;
[Column]int Year;
[Column]int Pages;
private EntitySet<Rating> _Ratings;
[Association( Storage="_Ratings", ThisKey="ID",OtherKey="ProductID"
, DeleteRule="ONDELETECASCADE")]
ICollection<Rating> Ratings{ ... }
private EntitySet<Keyword> _Keywords;
[Association( Storage="_Keywords", ThisKey="ID"
, OtherKey="ProductID", DeleteRule="ONDELETECASCADE")]
ICollection<Keyword> Keywords{ ... }
}
[Table(name="Keywords")]
class Keyword
{
[Column(PrimaryKey=true)]int ID;
[Column]string Keyword;
[Column(IsForeignKey=true)]int ProductID;
}
[Table(name="Ratings")]
class Rating
{
[Column(PrimaryKey=true)]int ID;
[Column]string Rating;
[Column(IsForeignKey=true)]int ProductID;
}
请注意，最终的对象模型必然比我们开始时的模型更复杂，因为我们被迫为Rating和和Keyword
除了这些小的差异之外，所有这些工作的最终结果是，我们现在可以像规范化之前一样简洁地编写查询以查找所有产品
var q = from product in Products
where product.Ratings.Any(rating⇒rating.Rating == "****")
select new{ product.Title, product.Keywords };
由于结果必须呈现为对象图，因此 O/R 映射器将确保创建正确的嵌套结果结构。不幸的是，并非每个 O/R 映射器都能有效地做到这一点。9
不仅程序员需要恢复代码的原始结构。数据库实现者还必须全力以赴，通过构建索引来有效地执行查询，从而避免我们之前观察到的潜在立方效应。对于一对多关系，索引只不过是嵌套集合，它是通过预先计算表之间的 join 来快速查找外键指向具有特定主键的行的所有行而产生的。然而，由于关系模型在组合下不是封闭的，因此索引的概念必须在模型之外定义。
两个自然索引分别对应于Products和Ratings和Products和Keywords、之间的关系。对于与表中的每个Product，ratings 索引包含所有相关ratings:
from rating in Ratings where rating.ProductID == product.ID
select rating;
类似地，对于每个与表中的每个Product表，keywords 索引包含与该keywords相关的所有与:
from keyword in Keywords where keyword.ProductID == product.ID
select keyword;
如果我们将索引可视化为Products表上的附加列，则表之间原始关系的反转变得明显。现在，Products表中的每一行都有一组外键，指向Keywords和Ratings表，就像原始对象图一样，如图 5 所示。
与分层数据相比，规范化所吹捧的优势之一是执行即席查询的能力——即，在原始数据模型中未设想的条件下 join 表。例如，我们可以尝试查找所有产品对，其中一个产品的标题长度与另一个产品的作者姓名长度相同，使用以下查询
from p1 in Products
from p2 in Products
where p1.Title.Length == p2.Author.Length
select new{ p1, p2 };
然而，如果没有索引，此查询需要全表扫描，因此需要与Products表长度成二次方的时间。
创建索引的能力做出了封闭世界假设。例如，如果我们修改之前的即席查询以查找所有网页对，其中一个页面具有引用另一个页面的 URL，那么很明显，当您没有将整个 Web 放在单个数据库中时，为此 join 构建索引是一项非常困难的任务
from p1 in WWW
from p2 in WWW
where p2.Contains(p1.URL)
select new{ p1, p2 };
总结我们目前所学到的知识，我们看到，为了使用关系数据库，从自然的分层对象模型开始，设计人员需要将数据模型规范化为不再反映原始意图的多种类型；应用程序开发人员必须通过使用额外的元数据修饰规范化数据来重新编码原始的分层结构；最后，数据库实现者必须通过构建索引来加速对规范化数据的查询，这些索引本质上也会重新创建数据的原始嵌套结构。
noSQL 是 coSQL
此时，键值和外键/主键数据模型之间的概念不协调似乎是不可逾越的。那将是令人遗憾的，因为很明显，每个模型都有其优点和缺点。如果我们能够对关系模型在何处闪耀以及对象图模型在何处最有效给出更数学的解释，那不是很好吗？事实证明，我们可以通过更仔细地查看在两种模型中为我们的运行示例创建的（内存中）结构来找到这个问题的答案。
让我们首先稍微简化对象图示例。我们这样做是通过删除Ratings和Authors集合的对象标识，以更直接地反映它们在关系世界中的建模方式。我们将Keywords和Ratings项直接内联到父Product中，就好像我们有基于值的集合一样。如图 6 所示，我们从左侧的图移动到右侧的图。
对于表格表示，我们显示了从外键到主键关系的显式箭头。同样，如图 7 所示，我们从左侧的图移动到右侧的图
当我们对两个最右边的图进行并排比较时，我们注意到两个有趣的事实
• 在对象图模型中，对象的标识是内涵的——即，对象标识不是值本身的一部分，而是由它们在存储中的键确定的。在关系模型中，对象标识是外延的——即，对象标识是值本身的一部分，以主键的形式存在。
• 模对象标识的概念，这两种表示形式非常相似；唯一的区别是箭头的方向相反！
此时，似乎这两种表示形式之间存在很强的对应关系：它们都由元素（对象或行）的集合和元素之间箭头的集合组成，唯一的区别是箭头的方向。是否有某种精确的方法来描述这种情况？幸运的是，有一个完整的数学领域专门为此而设计：范畴论。1
显然，将 SQL 和 noSQL 精确地形式化为范畴超出了本文的范围，但了解一点范畴论仍然具有启发意义。范畴论源于对数学结构的研究以及通过考虑结构之间的关系来关联结构类的尝试。因此，范畴论用对象、对象之间的箭头以及箭头的组合以及箭头组合应满足的一些公理来表达数学概念。范畴论的计算观点是，它是一种高度程式化、紧凑的函数式语言。它虽然很小，但足以表示所有数学。对于计算机科学家来说，范畴论已被证明是技术的丰富来源，这些技术很容易应用于许多实际问题。例如，Haskell 建模命令式编程的方法直接来自问题的范畴模型。
我们将使用的范畴论的第一个强大概念是对偶性。对偶性的例子在计算机科学中比比皆是。每个程序员都熟悉德摩根定律的两种对偶形式
!(a && b) == (!a)||(!b)
!(a||b) == (!a)&&(!b)
计算机科学中对偶性的其他例子包括引用计数和跟踪垃圾回收之间、按值调用和按名称调用之间、基于推送和基于拉取的集合之间以及事务内存和垃圾回收之间，以及许多其他例子。
形式上，给定一个对象和箭头的范畴C，我们通过反转co(C)中的所有箭头来获得对偶范畴C。如果语句T在C中为真，那么它的对偶语句co(T)在对偶范畴co(C)中为真。在本文的上下文中，我们可以将“相反语句”理解为“对偶语句”。
在 SQL 范畴中，当子节点的外键等于父节点的主键时，子节点指向父节点
在 noSQL 范畴中，箭头方向相反。当父节点中的子指针等于子节点在存储中的地址时，父节点指向子节点
换句话说，noSQL 范畴是 SQL 范畴的对偶——noSQL 实际上是 coSQL。这种对偶性的含义是 coSQL 和 SQL 并非像善与恶那样冲突。相反，它们是像阴阳一样和谐共存并可以相互转化的两个对立面。有趣的是，在中国哲学中，阴象征着开放，因此对应于 coSQL 的开放世界，而阳象征着封闭，因此对应于 SQL 的封闭世界。
由于 SQL 和 coSQL 在数学上是对偶的，因此我们可以精确地推断两者之间的权衡，而不是依赖于夸夸其谈和轶事证据。表 1 给出了 SQL 和 coSQL 各自成立的许多语句及其对偶。
表 1. SQL 和 coSQL 之间对偶性的结果
如果我们真的把对偶性放在心上，我们也可以（但不必）微调我们的键值存储模型，以反映值和计算之间的对偶性，以及同步 ACID 和异步 BASE（基本可用、软状态、最终一致）之间的对偶性。13
在键值存储中查找给定其地址或键的值可能涉及计算，这在真正的开放世界中具有潜在的延迟并且可能失败。例如，在 C# 语言中，getter 和 setter（称为属性）可以调用任意代码。也许一个更好的计算驱动的键值存储示例是 Web，它具有长延迟和高失败概率（始终能够处理 404），其中 URI 作为键，“资源”作为值，HTTP 动词作为原始查询和数据操作语言。另一方面，在类似 C 的键值内存模型中，我们通常做出简化的假设，即内存中的键查找需要恒定时间并且不会失败。
在关系模型的封闭世界中，遍历关系涉及比较两个值是否相等，由于引用完整性，这保证会成功；反之亦然，引用一致性规定关系是基于值的。否则，我们永远无法确定引用一致性是否真正成立。
请注意，按值比较键要求 SQL 范畴中的对象是强类型的，至少要足以识别主键和外键；对偶地，由于我们不需要了解 coSQL 对象的值的任何信息即可使用其键找到它，因此 coSQL 世界中的对象可以是松散类型的。
与现实世界的联系
我们 SQL 范畴的抽象模型没有对行的结构施加任何限制；我们仅假设我们可以确定主键或外键来关联两行。
在典型的关系模型中，我们将进一步施加约束，即行由标量值的平面序列组成（所谓的第一个范式，或 1-NF）。如果我们对 1-NF 中的关系进行对偶化，那么我们会得到一个键值模型，其中值由标量或键或标量或键的集合组成。令人惊讶的是，这正是 Amazon SimpleDB 数据模型（图 8）。
如果我们假设外键/主键模型中的行只是 blob，而键是字符串，那么对偶键值模型正是 HTML5 键值存储模型
interface Storage {
readonly attribute unsigned long length;
getter DOMString key(in unsigned long index);
getter any getItem(in DOMString key);
setter creator void setItem(in DOMString key, in any data);
deleter void removeItem(in DOMString key);
void clear();
}
更多范畴论
到目前为止，我们已经讨论了 SQL 和 coSQL 的基本数据模型，但我们尚未触及查询。通过应用更多的范畴论，我们可以展示如何使用单一抽象、单子和单子推导式作为 SQL 和 coSQL 的统一查询语言。
要讨论查询，我们需要更精确地了解我们所说的值的集合是什么意思。纯关系代数基于行集，但实际的关系数据库使用多重集（包）或有序多重集（排列）。为了抽象地建模集合，我们查看行集/包/排列，并应用范畴论格言：“这些各种行集合实现的接口是什么？”以及“我们如何基于此类接口泛化查询？”
首先，让我们坚持使用简单的集合集合。当我们编写 SQL 查询（例如
SELECT F(a,b)
FROM as AS a, bs AS b
WHERE P(a,b)
时，SQL 编译器会将漂亮的语法转换为关系代数表达式，其中涉及选择、投影、join 和笛卡尔积。按照关系世界的惯例，各种运算都使用希腊符号表示
πF(σp(as×bs))
没有理由将关系代数运算符限制为仅对行集（或包或排列）进行运算。相反，我们可以在任何集合M<T>上定义类似的运算符，其中值具有任意类型T.
此类抽象集合的接口M<T>是对集合接口的直接泛化。它允许我们使用常量∅创建空集合；使用函数M<T>给定类型为T的某个值，创建类型为{_} ∈ T→M<T>的单例集合（符号T→M<T>表示函数/闭包/lambda 表达式，它将类型为T的参数值映射到类型为M<T>的结果集合）；并使用二元运算符∪将两个集合组合成更大的集合（根据∪的交换性和幂等性，我们获得各种类型的集合，例如列表、排列、包和集合）
∅ ∈ M<T>
{_} ∈ T → M<T>
∪ ∈ M<T>×M<T> → M<T>
使用这些构造函数，我们可以泛化传统的关系代数运算符（选择σp、投影πF和笛卡尔积×∏）以使用以下签名对广义集合进行运算
σp ∈ M<T>×(T➔bool) → M<T>
πF ∈ M<T>×(T➔S) → M<S>
× ∈ M<T>×M<S> → M<T×S>
实际上，如果我们假设单个运算符用于相关子查询（我们称之为SelectMany，但在 SQL 中通常称为CROSS APPLY）
SelectMany ∈ M<T>×(T➔M<S>) → M<S>
那么我们可以根据这一个运算符定义其他运算符，如下所示
σp(as) = SelectMany(as, aP(a)?{a}:∅)
πF(as) = SelectMany(as, a⇒{F(a)})
as×bs = SelectMany(as, a⇒π(b⇒(a,b),bs))
令人难以置信的是，这种形状的接口在范畴论中是众所周知的。它被称为单子，其中类型构造器M<_>是单子的函子；构造器{_}是单子的单位元；SelectMany是单子的绑定；以及∅和∪分别是中性元素和加法。对于我们其他人来说，它们仅仅是在集合的抽象接口上定义的方法签名。
这不是理论上的好奇。我们可以像 SQL 对关系代数所做的那样，使用相同的语法技巧，但这次是使用单子。这种单子推导式已被函数式程序员和数据库研究人员公认为是一种通用的查询语言。8
LINQ 查询只是单子推导式更熟悉的类 SQL 语法。LINQ 使用人类可读的标识符，而不是希腊符号，例如xs.Where(P)对应于σp(xs)和xs.Select(F)对应于πF(xs)。为了适应各种查询，实际的 LINQ 标准查询运算符包含用于聚合和分组的附加运算符，例如
Aggregate ∈ M<T>x(T×T➔T) → T
GroupBy ∈ M<T>x(T➔K) → M<KxM<T>>
任何实现标准 LINQ 查询运算符的数据源都可以使用推导式语法进行查询，包括 SQL 和 coSQL 数据源，我们将在下一节中展示。
.NET 框架定义了一对标准接口IEnumerable<T>和IQueryable<T>这些接口通常由数据源实现以支持查询，但绝不是必须使用这些特定的接口。其他支持 LINQ 查询运算符的标准接口包括IObservable<T>和IQbservable<T>这些接口使得使用 LINQ 进行复杂事件处理成为可能。10
可扩展性和分布
与大多数 noSQL 的处理方式不同，我们没有将可扩展性作为 coSQL 的定义特征。coSQL 模型的开放性简化了跨大量物理分布式机器的可扩展实现。
当使用 LINQ 查询 SQL 数据库时，通常相似的行存储在实现IQueryable<T>接口的某种具体类型的表中。行之间的关系被提升为跨这些表执行连接的集合上的批量操作；因此，查询接受任意数量的相关表，并从中生成一个新表（如图 9 所示）
IQueryable<S>xIQueryable<T>xIQueryable<U>→IQueryable<R>
由于 SQL 中的关系跨越不同的表，因此将单个封闭世界划分为可以独立处理的“强连接”组件的独立世界并非易事。然而，在封闭世界中，查询优化器可以利用所有关于各种表的可用信息和统计数据。这允许用户编写声明性查询，专注于“做什么”，而让系统负责“如何做”。
在 coSQL 案例中，典型的场景是拥有类型为IQueryable<S>的（指向）自包含的非规范化“文档”的单个集合，类型为S。在这种情况下，查询具有以下类型（如图 10 所示）
IQueryable<S> → R
当没有跨表关系时，作为 coSQL 查询源的集合{x0,x1,...,xn-1} ∈ M<S>可以自然地水平分区或分片为各个子集合{x0}∪{x1}∪...∪{xn-1}，并且每个这样的子集合{xi}可以分布在集群中的各种机器上。
对于 coSQL 查询的很大一部分子集，查询的形状紧密地遵循数据的形状。这种同态查询将集合xs={x0}∪{x1}∪...∪{xn-1}映射到值f(x0)⊕f(x1)⊕...⊕f(xn-1)—也就是说，它们的形式是xs.Select(f).Aggregate(⊕)对于某个函数f ∈ S→R和二元运算符⊕ ∈ RxR→R。事实上，Richard Bird 的第一个同态引理3指出，任何函数h ∈ M<S>→R是关于∪的同态，当且仅当它可以分解为 map 后跟 reduceh(xs) = xs.Select(f).Aggregate(⊕)。数学原理表明，coSQL 查询是使用 MapReduce 执行的。6
MapReduce 的实际实现通常稍微推广 Bird 的引理以使用SelectMany代替Select以便 map 阶段可以返回集合而不是单个值，并插入一个中间的GroupBy作为一种将 map 阶段的值的等价类“写入”键值存储的方式，以便在 reduce 阶段进行后续处理，然后聚合每个子集合
xs.SelectMany(f).GroupBy(s).Select((k,g)→g.Aggregate(⊕k))
例如，DryadLINQ15 使用类型PartitionedTable<S>:IQueryable<S>来表示 LINQ 查询的分区输入集合，然后使用以下函数在分区集合上实现 MapReduce
| MapReduce ∈ IQueryable<S> | // source |
| x(S➔IEnumerable<M>) | // mapper |
| x(M➔K) | // key selector |
| x(KxIEnumerable<M>➔R) | // reducer |
| →IQueryable<R> | |
在集合分布在网络上的开放世界中，查询优化器更难以执行考虑到延迟、错误等的全局优化。因此，大多数 coSQL 数据库依赖于特定模式（例如 MapReduce）的显式编程查询，这些查询可以在目标物理机器配置或集群上可靠地执行。
结论
新兴的 noSQL 市场非常分散，存在许多相互竞争的供应商和技术。编程、部署和管理 noSQL 解决方案需要专业的和底层的知识，这些知识不容易从一个供应商的产品转移到另一个供应商的产品。
noSQL 数据库市场中网络效应起飞的必要条件是，存在一个通用的抽象数学数据模型和相关的 noSQL 查询语言，从而消除逻辑层面的产品差异化，并将竞争转移到物理和操作层面。所有主要的 noSQL 数据库都拥有这样一个共同的数学基础，可以提供足够的临界质量，以说服企业、开发人员、教育机构等投资 noSQL。
在本文中，我们为最常见的 noSQL 形式——即键值存储作为 SQL 的外键/主键存储的数学对偶——开发了一个数学数据模型。由于这种深刻而美妙的联系，我们建议将 noSQL 的名称更改为 coSQL。此外，我们表明单子和单子推导式（即 LINQ）为 SQL 和 coSQL 提供了通用的查询机制，并且 SQL 和 coSQL 的许多优点和缺点自然而然地源于数学原理。
与普遍的看法相反，大数据与小数据的问题与 SQL 与 coSQL 的问题是正交的。虽然 coSQL 模型自然支持极端分片，但它不需要强类型和规范化的事实也使其对“小”数据具有吸引力。另一方面，可以通过仔细的分区来扩展 SQL 数据库。2
这一切意味着 coSQL 和 SQL 并非像善与恶一样相互冲突。相反，它们是和谐共存的两个对立面，可以像阴阳一样相互转化。由于基于单子的通用查询语言，两者都可以使用相同的原理来实现。
问
致谢
非常感谢 Brian Beckman、Jimmy "the aggregator" Nilsson、Bedarra-Dave Thomas、Ralf Lämmel、Torsten Grust、Maarten Fokkinga、Rene Bouw、Alexander Stojanovic 和匿名审稿人，他们的评论极大地改进了本文的呈现，当然还要感谢 Dave Campbell 对 LINQ 所有酷炫工作的支持。
参考文献
1. Awodey, S. 2010. 范畴论（第二版）。牛津大学出版社。
2. Baker, J., Bond, C., Corbett, J., Furman, J., Khorlin, A., Larson, J., et al. 2011. Megastore：为交互式服务提供可扩展、高可用的存储。《创新数据系统研究会议 (CIDR)》。
3. Bird, R. 1987. 列表理论导论。载于《逻辑编程和离散设计演算》，M. Broy 编辑，3-42 页。施普林格出版社。
4. Codd, T. 1970. 大型共享数据库的关系数据模型。《 通讯》，13(6)。
5. Copeland, G., Maier, D. 1984. 使 Smalltalk 成为数据库系统。《 SIGMOD 国际数据管理会议论文集》。
6. Fokkinga, M. 2008. MapReduce—给外行人的两页解释；http://www.cs.utwente.nl/~fokkinga/mmf2008j.pdf。
7. Ghosh, R. A. 2005. 开放标准的经济基础；flosspols.org。
8. Grust, T. 2003. 单子推导式：查询的多功能表示。《数据管理的功能方法》，P. Gray、L. Kerschberg、P. King 和 A. Poulovassilis 编辑，288-311 页。施普林格出版社。
9. Grust, T., Rittinger, J., Schreiber, T. 2010. 雪崩安全的 LINQ 编译。《VLDB Endowment 论文集 3(1-2)》。
10. Meijer, E. 2010. 主题/观察者是对迭代器的对偶。在 FIT：编程语言设计与实现会议上的有趣想法和思考中展示；http://www.cs.stanford.edu/pldi10/fit.html。
11. Meijer, E., Beckman, B., Bierman, G. 2006. LINQ：在 .NET 框架中协调对象、关系和 XML。《 SIGMOD 国际数据管理会议论文集》。
12. Pirayoff, R. 2004. 《微观与宏观经济学》。 Cliffs Notes。
13. Pritchett, D. 2008. BASE：ACID 的替代方案。《》（七月）；https://queue.org.cn/detail.cfm?id=1394128。
14. Stonebraker, M., Hellerstein, J. M. 2005. 循环往复。《数据库系统读本》（第四版），M. Stonebraker 和 J. M. Hellerstein 编辑，2-41 页。麻省理工学院出版社。
15. Yuan Yu, M. I. 2008. DryadLINQ：使用高级语言进行通用分布式数据并行计算的系统。《OSDI（操作系统设计与实现）》。
喜欢还是讨厌？请告诉我们
Gavin Bierman ([[email protected]](https://e.notexist.com)) 是剑桥微软研究院的高级研究员，专注于数据库查询语言、类型系统、语义、编程语言设计与实现、数据模型集成、分离逻辑和动态软件更新。
© 2011 1542-7730/11/0300 $10.00
最初发表于 Queue vol. 9, no. 3—
在 数字图书馆 中评论本文
更多相关文章
Qian Li, Peter Kraft - 事务和无服务器是天生一对
数据库支持的应用程序是无服务器计算令人兴奋的新领域。通过紧密集成应用程序执行和数据管理，事务性无服务器平台实现了许多在现有无服务器平台或基于服务器的部署中不可能实现的新功能。
Pat Helland - 任何其他名称的身份
新兴的系统和协议都在收紧和放松我们对身份的概念，这很好！它们使完成工作更容易。REST、物联网、大数据和机器学习都围绕着有意保持灵活甚至模糊的身份概念。身份概念是我们分布式系统基本机制的基础，包括互换性、幂等性和不变性。
Raymond Blum, Betsy Beyer - 实现数字永恒
当今的信息时代正在为世界所依赖的数据创造新的用途和新的管理方式。世界正在从熟悉的物理人工制品转向更接近信息本质的新型表示方式。我们需要流程来确保知识的完整性和可访问性，以保证历史将被了解和真实。
Graham Cormode - 数据草图
您是否曾经感到被源源不断的信息淹没？ 似乎大量的新电子邮件和短信需要持续关注，还有电话要接听、文章要阅读以及敲门声要回应。 将这些碎片拼凑在一起以跟踪重要内容可能是一个真正的挑战。 为了应对这一挑战，流数据处理模型日益普及。 目标不再是捕获、存储和索引每分钟发生的事件，而是快速处理每个观察结果，以便创建当前状态的摘要。
© 保留所有权利。