2011 年 8 月 30 日
第 9 卷，第 8 期

Download PDF version of this article PDF

安全攸关软件的验证

大数据不仅仅关乎规模，而 LINQ 完全能够胜任这项任务。

Erik Meijer

编者注：本文使用了许多数学符号，这些符号可能在您的浏览器中无法正确呈现。如果符号未显示，您可能希望以 PDF 格式阅读本文

构建 Web 和云应用程序的程序员将来自许多不同来源的数据连接在一起，例如传感器、社交网络、用户界面、电子表格和股票行情自动收录器。这些数据中的大多数不适合传统关系数据库的封闭和干净的世界。它太大、非结构化、非规范化且实时流式传输。首先，在所有这些不同的数据模型和查询语言中呈现统一的编程模型似乎是不可能的。然而，通过关注共性而不是差异，大多数数据源将接受某种形式的计算来过滤和转换数据集合。

数学家很久以前就观察到看似不同的数学结构之间的相似之处，并通过范畴论，特别是monads⁹ 的概念（作为集合的泛化）将这种洞察力形式化。Haskell、Scala¹³、Python¹¹，甚至未来版本的 JavaScript⁶ 等语言都已融入列表和 monad 推导式，以处理副作用和集合上的计算。Visual Basic 和 C# 的 .NET 语言采用了 LINQ（语言集成查询）⁷ 形式的 monads，作为弥合对象和数据世界之间差距的一种方式。本文将 monads 和 LINQ 描述为关系代数和 SQL 的泛化，用于处理任意类型的任意集合，并解释了为什么这使 LINQ 成为大数据的引人注目的基础。

LINQ 在 C# 3.0 和 Visual Basic 9 中作为一组 API 和随附的语言扩展引入，弥合了编程语言世界和数据库世界之间的差距。尽管外部开发者社区对 LINQ 的持续兴奋，但该技术的全部潜力尚未被发掘。由于 LINQ 的基础性质，它在 O/R（对象关系）之外的映射场景中仍有巨大的潜力，尤其是在大数据领域。

大数据的出现使程序员比以往任何时候都更需要一个单一的抽象，使他们能够跨至少三个不同的维度进行处理、转换、组合、查询、分析和计算：容量，无论大小，范围从数十亿项到少量结果；多样性，模型中的多样性，结构化或非结构化，平面或嵌套；以及速度，流式传输或持久化，推送或拉取。因此，我们看到了数量惊人的新型数据模型、查询语言和执行框架。LINQ 可以将所有这些方面虚拟化在一个单一的抽象背后。

以 Apache 的 Hadoop⁵ 生态系统为例。它至少附带八种外部 DSL（领域特定语言）或 API：一组用于 MapReduce 计算的低级 Java 接口；Cascading，一种“数据处理定义语言，作为简单的 Java API 实现”；Flume，一种“基于流数据流的简单而灵活的架构”；Pig，一种“用于表达数据分析程序的高级语言”；HiveQL，一种“类似 SQL 的语言，用于轻松进行数据汇总、即席查询和大型数据集的分析”；CQL，一种“用于 Cassandra 中数据管理的提议语言”；Oozie，一种基于 XML 的“协调器引擎，专门用于运行基于时间和数据触发器的工作流”；以及Avro，一种用于数据序列化的模式语言。

为了创建端到端的应用程序，程序员除了需要使用 Java 等通用编程语言将所有内容粘合在一起之外，还需要使用其中的几种外部 DSL。如果数据来自外部 RDBMS（关系数据库管理系统）或基于推送的源，则甚至需要更多 DSL，例如 SQL 或 StreamBase。另一方面，使用 LINQ 和 C# 或 Visual Basic，程序员可以使用内部 DSL 来针对通用 OO（面向对象）语言内部的任何形状或形式的数据进行编程，该语言附带工具（Visual Studio 或来自 Xamarin¹⁴ 的跨平台解决方案，例如 MonoDevelop、Mono Touch for iPhone 或 Mono for Android）和广泛的标准库（.NET Framework）。

标准查询运算符和 LINQ

假设给定一个文本文件——例如，words.txt—您需要计算该文件中不同单词的数量，找到五个最常见的单词，并在饼图中可视化结果。如果您思考一下这个问题，就会清楚地发现这实际上是一个转换集合的练习。这正是 LINQ 设计用于完成的任务类型。为了保持简单，我们使用 LINQ to Objects 实现了这个示例，以处理内存中的数据；然而，只需进行最小的修改，相同的代码就可以在 LINQ to HPC（高性能计算）⁸ 上运行，处理存储在商品集群中的 TB 级数据。

标准File.ReadAllText方法将文件的内容作为单个巨大的字符串提供。您首先需要通过在空格、逗号、句点等分隔符字符处断开字符串，将此字符串分解为单个单词。获得单词列表后，您需要清理它，删除所有空单词。最后，将所有单词规范化为小写。

使用 LINQ 序列运算符，您可以直接将上一段的描述音译为代码

 
var file = System.IO.File.ReadAllText("words.txt"); 
 
var words = file.Split(delimiters) 
           .Where(w⇒!w.IsNullOrWhiteSpace()) 
           .Select(w⇒w.ToLower());

除了直接使用序列运算符外，LINQ 还提供了更“声明式”的查询理解语法。使用理解，您可以将代码重写如下

 
var words = from w in file.Split(delimiters) 
            where !w.IsNullOrWhiteSpace() 
            select w.ToLower();

一旦将文件转换为单个单词序列，您可以通过首先按每个单词对集合进行分组，然后计算每个组中的元素数量（其中包含该单词的所有出现次数）来查找每个单词的出现次数

 
var wordcount = from w in words 
                group by w into group 
                select new{ Word = group.Key, Count = group.Count() };

如果不使用查询理解语法，代码将如下所示

 
var wordcount = words.GroupBy(w⇒w).Select(group⇒ 
                   new{ Word = group.Key, Count = group.Count() };

要查找五个最常用的单词，您可以按Count对每个记录进行排序，并取前五个元素

 var top5 = wc.OrderByDescending(p⇒p.Count).Take(5);

现在您已经拥有了文件中前五个单词的集合，您可以将它们在饼图中可视化，如图 1 所示。饼图实际上只不过是一个切片集合，其中每个切片包含一个数字，该数字表示整个饼图的比例，以及一个描述切片代表内容的图例。这意味着通过将图表 API 定义为 LINQ 友好的，您可以通过编写对 Google 图像图表 API⁴ 的查询来创建图表

 
var chart = new Pie(from w in top5 
                    select new Slice(w.Count){ Legend = r.Word }) 
            { Title = "Top 5 words" }; 
var image = await chart;

Theawait关键字以非正统的方式使用，以使从Google.Linq.Charts.Pie到需要网络往返的图像的昂贵的强制转换变得显式。

此示例仅触及了 LINQ 的表面。它提供了一个序列运算符库，例如Select, Where, GroupBy,...用于转换集合，并以查询理解的形式提供语法糖，使程序员能够在更高的抽象级别编写集合上的转换。

然而，要真正理解 LINQ 的强大功能，让我们退后一步，研究它的起源和数学基础。别担心，您只需要高中水平的数学知识即可。

数据中心解释

关系代数是 SQL 的形式基础，它定义了许多值集 {Σ} 的常量和构造函数，例如空集 ∅∈{Σ}；将值注入到单例集合 {_}∈Σ→{Σ} 中；以及将两个集合联合成新的组合集合 ∪∈{Σ}×{Σ}→{Σ}；。还有许多关系运算符，例如投影，它将转换应用于集合中的每个元素 π∈(Σ→∧)×{Σ}→{∧}；选择，它仅选择集合中满足给定属性 σ∈(Σ→𝔹)×{Σ}→{Σ} 的那些元素；笛卡尔积，它将一对集合 X∈{Σ}×{∧}→{Σ×∧} 的所有元素配对；以及交叉应用，它为第一个集合 @∈(Σ→{∧})×{Σ}→{∧} 中的每个元素生成辅助值集。

图 2 使用云来表示值集，描绘了关系代数运算符。

SQL 编译器将以熟悉的SELECT-FROM-WHERE语法表示的查询转换为关系代数表达式；为了优化查询，它应用代数定律，例如选择的分布：σ(p,σ(q,×s)) = σ(×→p(×)∧q(×),×s)；然后将这些逻辑表达式转换为由 RDBMS 执行的物理查询计划。

例如，SQL 查询SELECT Name FROM Friend WHERE Likes(Friend, Sushi)被转换为关系代数表达式 π(f↠f.Name, (σ(f↠Likes(f,Sushi), Friend)。为了加快查询的执行速度，RDBMS 可以使用索引来快速查找喜欢Sushi的朋友，而不是对整个集合进行线性扫描。

交叉应用运算符@特别强大，因为它允许相关的子查询，您可以在其中为第一个集合中的每个值生成第二个集合，并将结果展平为单个集合@(f,{a,...,z})=f(a) ∪...∪f(z)。所有其他关系运算符都可以根据交叉应用运算符定义

 
   xs X ys = @(x ⇒ π(y ⇒(x,y),ys),xs) 
   π(f,xs) = @(x ⇒{f(x)},xs) 
   σ(p,xs) = @(x ⇒p(x)?{x}: ∅,xs)

作为程序员，您可以轻松想象编写交叉应用的简单实现：您只需迭代输入集中的项目，应用给定的函数，并将结果累积到结果集中。然而，这样的实现不需要其参数是集合{Σ}；任何我们可以迭代的东西（例如列表、数组或哈希表）就足够了。同样，关系代数运算完全没有理由仅限于值集{Σ}。它们也可以基于其他类型的集合来实现。

也许令人惊讶的是，传入π, σ和@的操作也没有理由仅限于具体的函数Σ→∧。实际上，您可以使用函数的任何表示形式来确定要执行的计算。例如，在 JavaScript 等语言中，您可以简单地传递一个字符串，然后使用eval将其转换为可执行代码。

您正在寻找的是关系代数实现的底层接口。只要集合存在类型构造函数M<Σ>，它提供的操作满足与{Σ}类似的类集合代数性质，以及计算的类型构造函数Σ↠∧，它满足与Σ→∧类似的类函数性质，您就可以将关系代数推广到以下运算符集，并且仍然可以通过反糖化查询语法来编写针对这些集合的 SQL 查询

 
   ∅ ∈ M<Σ> 
   {_} ∈ Σ→M<Σ> 
   ∪ ∈ M<Σ>xM<Σ>→M<Σ> 
   @ ∈ (Σ↠M<∧>)xM<Σ>→M<∧>

对于程序员来说，这只是将接口与实现分离；数学家称由此产生的结构为 monads，并且他们谈论的是推导式而不是查询。

C# 等 OO 语言使用集合的规范接口IEnumerable<T>作为抽象集合类型M<T>的特定实例，并使用委托Func<Σ,∧>来表示计算Σ↠∧。通过这样做，您将关系代数中的运算符识别为 LINQ 标准查询运算符，如Linq.Enumerable类中所定义。

 
   //projection π 
   IEnumerable<T> Select<S,T>(IEnumerable<S> source, Func<S,T> selector) 
   //CROSS-APPLY @ 
   IEnumerable<T> SelectMany<S,T>(IEnumerable<S> source, Func<S,IEnumerable<T>> selector) 
   //selection σ 
   IEnumerable<T> Where<T>(IEnumerable<T> source, Func<T,bool> predicate)

或者，您可以使用IQueryable<T>接口来表示集合M<T>和表达式树Expression<Func<Σ,∧>>来表示计算Σ↠∧。在这种情况下，您将关系代数运算符识别为 LINQ 标准查询运算符，如Linq.Queryable类中所定义。使用态射（或在 C# 的情况下使用Expression类型和用于代码字面量的 lambda 表达式）将代码视为数据的能力是一项基本能力，它允许程序本身在运行时操作、优化和转换查询。

C# 语言没有使用 SQL 语法，而是定义了类似 XQuery 的 formfrom-where-select.之前的 SQL 查询示例看起来像这样

fromfriendinfriendswherefriend.Likes(Sushi)selectfriend.Name

就像在 SQL 中一样，推导式由编译器转换为底层的 LINQ 查询代数

friends.Where(friend ⇒friend.Likes(Sushi)).Select(friend ⇒friend.Name)

根据Where和Select的重载，lambda 表达式将被解释为代码或数据。本文稍后将介绍IQueryable的简化实现。

正如已经表明的那样，monads 及其在 LINQ 等实用编程语言中的化身仅仅是通过想象关系代数实现的接口来泛化关系代数。因此，LINQ 背后的概念和思想对于数据库人员和程序员来说都应该非常熟悉。

理论付诸实践

与以原则性方式融入 monads 和 monad 推导式的 Haskell 不同，C# 类型系统对于 monad 运算符的数学签名来说不够富有表现力。相反，查询推导式的转换是以纯粹基于模式的方式定义的。在第一遍中，编译器盲目地反糖化推导式，使用一组固定的规则¹，将其转换为常规的 C# 方法调用，然后依赖于基于标准类型的重载解析将查询运算符绑定到它们的实际实现。

例如，方法Foo Select(Bar source, Func<Baz, Qux> selector)（不涉及任何集合类型）将被绑定为转换推导式的结果

var foo = from baz in bar select qux

到反糖化表达式

var foo = bar.Select(baz ⇒qux)

这项技术在下一节介绍的示例中得到了广泛应用。

LINQ 与其 monad 基础之间的另一个区别是更大一类的查询运算符，包括分组和聚合，这更像 SQL。有趣的是，C# 中推导式的包含（其灵感来自 Haskell 中的 monad 和列表推导式）反过来又启发了 Haskell 为其推导式² 添加分组和聚合的支持。

自定义查询提供程序

Yahoo 天气服务 (http://developer.yahoo.com/weather/) 允许使用公制或英制单位查询给定位置的天气预报。这项简单的服务很好地说明了 LINQ 查询运算符的非标准实现，该实现完全专门针对此特定目标，并且仅允许以下形式的强类型查询

 
  var request = Yahoo.WeatherService(). 
                Where(forecast⇒forecast.City == city). 
                Where(forecast⇒forecast.Temperature.In.units); 
  var response = await request;

或等效地使用查询推导式

 
  var request = from forecast in Yahoo.WeatherService() 
                where forecast.City == city 
                where forecastTemperature.In.units 
                select forecast; 
  var response = await request;

运算符的实现从查询中提取城市和温度单位，并使用它们创建一个 REST 调用 (http://weather.yahooapis.com/forecastrss?w=woeid&u=unit) 到 Yahoo 服务，这是使用await关键字显式强制将请求转换为响应的结果。

这种自定义 LINQ 提供程序风格的技术诀窍是将目标查询语言（在本例中为需要 (a) 城市和 (b) 单位的 Yahoo 天气服务）的功能投影到类型级状态机中，该状态机以“流畅”的风格（并由 IntelliSense 支持）引导用户完成他们可以做出的可能选择（图 3）。

在状态机中的每次转换中，我们收集查询的各个感兴趣部分——在本例中，是特定的城市和温度单位。原则上，城市真的不需要排在第一位，但对于图形来说，允许首先指定任一类型的where子句可能更自然，但限制是需要where子句。我将状态机中此限制的解除作为读者的练习。

请注意，类型Weather, WeatherInCity,或WeatherInCityInUnits均未实现任何标准集合接口。相反，它们代表了将提交给 Yahoo Web 服务的请求的计算阶段，为此您不需要定义显式容器类型。许多人感到惊讶的是，这两个Where方法实际上都没有计算布尔谓词。更奇怪的是，查询中范围变量forecast的三次出现中的每一次都具有不同的类型。

TheWeather类定义了一个单一的方法，该方法选择查询中指定的城市并将其传递给WeatherInCity，这是基于类型的状态机中的下一个状态

 
   WeatherInCity Where(Weather source, Func<CityPicker,string> city) 
   { 
     return new WeatherInCity{ City = city(new CityPicker()) }; 
   }

方法的“谓词”是一个函数，它接受WhereCityPicker类型的值，该类型具有一个返回虚类City的单一属性，该虚类仅用于方便 IntelliSense，并且其相等性检查立即返回传递给相等运算符的字符串。因此，调用

 
   class CityPicker { City City; } 
   class City 
   { 
       static string operator == (City c, string s) { return s; } 
   }

Yahoo.Weather().Where(forecast⇒forecast=="Seattle")实际上只是创建new WeatherInCity{ City = "Seattle" }实例的复杂方式，使用方法，该方法不接受布尔谓词和返回字符串的相等运算符。Where您可以在

WeatherInCityInUnits Where(Func<UnitPicker,Unit> predicate)中使用相同的技巧，以便调用Where(forecast ⇒forecast.Temperature.In.Celsius)在前一个过滤器的结果上创建一个new WeatherInCityInUnits{ City = "Seattle", Unit = Unit.Celsius }实例。此处使用的技术不仅对于定义 LINQ 运算符的自定义实现很有用，而且还可以用于构建通用的流畅接口。由于 Yahoo 服务需要将城市作为 WOEID（地球上哪里 ID），因此我们需要在后台进行两次服务调用才能检索天气预报。第一次服务调用通过 http://where.yahooapis.com/v1/places.q(city)?appid=XXXX 检索请求城市的 WOEID。如果成功返回，则进行第二次调用以检索该位置的天气预报。对 Web 服务器的调用是异步执行的，并且都返回一个

Task<T>（在 Java 中，您将使用java.util.concurrent.Future<T>来表示异步操作的结果）。由于我们可以将视为一种包含（最多）一个元素的集合，因此它也支持 LINQ 查询运算符¹⁰，并且我们拥有一直向下的海龟；（在 Java 中，您将使用的 LINQ 实现是使用WeatherTask<T>的 LINQ 实现定义的。

 
   class YahooWeatherInCityInUnits 
   { 
     string City; string Units; string AppID; 
 
     TaskAwaiter<ForeCast> GetAwaiter() 
     { 
       var www = new WebClient(); 
       var response = 
         from xml in www.DownloadStringTaskAsync(...City, AppID...) 
         let woeid = ...fish WOEID from result... 
         from rss in www.DownloadStringTaskAsync(...woeid...) 
         let forecast = ...deserialize forecast from rss... 
         select forecast; 
       return response.GetAwaiter(); 
     } 
   }

尽管这是一个非常小且有限的示例，但它清楚地说明了用于创建真实世界 LINQ 提供程序的许多技术，例如 LINQ to Objects、LINQ to SharePoint、LINQ to Active Directory、LINQ to Twitter、LINQ to Netflix 以及更多。

通用查询提供程序

天气服务查询提供程序示例被构造为内部 DSL。虽然这提供了出色的用户体验和最大的静态类型，但它几乎没有为重用提供程序的实际实现留下空间。它是为特定目标从上到下定制构建的。在频谱的另一端，我们可以创建一个完全通用的查询提供程序，它使用一点元编程魔法“按原样”记录完整的查询。

在 C# 中，lambda 表达式（例如x⇒x>4711）可以转换为委托——例如，类型为Func<int,int>——或转换为类型为Expression<Func<int,int>>的表达式树，它将 lambda 表达式的代码视为数据。在 Lisp 或 Scheme 中，人们会使用语法引用³ 将代码视为数据。在 C# 中，lambda 表达式与上下文期望的类型相结合，提供了一种基于类型的引用机制。

类Queryable实现了 LINQ 标准查询运算符，这些运算符将表达式树作为参数，并返回一个Expression自身的表示形式，非常像宏记录器

 
   class Queryable<T> 
   { 
     Expression This { get; set; } 
 
     Queryable(){ This = Expression.Constant(this); } 
 
     Queryable<S> Select<S>(Expression<Func<T,S>> f) 
     { 
       return new Q<S> 
       { 
         This = Expression.Call(This,"Select",new[]{typeof(S)}, f) 
       }; 
     } 
   }

例如，给定类型为xs的值Queryable<int>，调用xs.Select(x⇒x>4711)会导致 lambda 表达式被转换为表达式树（以粗体显示），然后返回表示调用自身的表达式树xs.Select(x⇒x>4711)。现在，由特定的查询提供程序（例如 LINQ to SQL、Entity Framework、LINQ to HPC）来转换生成的表达式树并将其编译为目标查询语言。

TheIQueryable-基于实现的，该实现在 .NET Framework 中附带，它使用与刚刚显示的简化示例代码相同的方案，不同之处在于它是基于接口的，因此它依赖于第二个接口IQueryProvider来提供用于创建IQueryable.

实例的工厂。通用查询提供程序的优势在于您可以提供通用服务，例如查询优化，这些服务实现重写规则，例如xs.Union(ys).Where(p) = xs.Where(p).Union(ys.Where(p))，这些规则可以在许多 LINQ 提供程序中重用。

LINQ 友好的 API

到目前为止，所有示例都处理了实现特定的 LINQ 提供程序。LINQ 的一个正交方面是利用特定 LINQ 实现（通常是 LINQ to Objects）的 API。例如，LINQ to XML 是一个用于操作 XML 文档的 API，它专门为 LINQ 而设计，这消除了对 DSL（例如 XQuery 或 XPath）查询和转换 XML 的需求。

Google Chart API⁴ 是一种 Web 服务，可让您使用简单的 URI（统一资源标识符）方案动态创建外观精美的图表。但是，Google 图表的 URI 语法对序列不太友好。例如，早期示例饼图的 URI 如下所示

 
   http://chart.apis.google.com/chart 
     ?cht=p3&chtt=Top+5+words&chs=500x200 
     &chd=t:21,12,7,7,6 
     &chl=the|of|a|that|is

问题在于标签的规范 (chl=the|of|a|that|is) 和图表数据集的规范 (chd=t:21,12,7,7,6) 在两个单独的集合中给出。另一方面，要使用查询生成饼图，您需要一个指定每个切片的value和 label 的对的单个集合，如from w in top5 select new Slice(w.Count){ Legend = r.Word }.

换句话说，要使 Google Chart API 对序列友好，您必须转置对的集合M<SxT>到一对集合M<S>xM<T>。函数式程序员立即将其识别为函数Unzip ∈(R →S x R →T x M<R>) →M<S>xM<T>. 的实例Unzip

 
   string CompileToUri() 
   { 
     var tt = Title.UrlEncode(); 
     var p = Slices.Unzip( 
         slices ⇒slices.Select(slice ⇒slice.Legend).SeparatedBy("|"), 
         slices ⇒slices.Select(slice ⇒slice.Value).SeparatedBy(",")); 
 
     return string.Format(@"http://chart.apis.google.com/chart 
         ?cht=p3&chtt={0}&chl=t:{1}&chd={2}", tt, p.First, p.Second); 
   }

可以通过使用图表服务规定的分隔符格式化各种集合，将包含切片序列的图表转换为 Google Chart API 所需的 URI 格式以下是类型和PieSlice的一些便捷构造函数，以及GetAwaiter以下是类型方法，该方法在

 
   class Pie 
   { 
     IEnumerable<Slice> Slices; string Title; 
     Chart(IEnumerable<Slice> slices){ Slices = slices; } 
     TaskAwaiter<Image> GetAwaiter(){ ...CompileToUri()... } 
   } 
   
   class Slice 
   { 
     int Value; string Legend; 
     Slice(int Value){ Value = value;} 
   }

上触发将序列编译为 URI，并向 Google 发出 Web 请求现在，您可以通过编写 LINQ 查询以自然的方式生成数据集来创建饼图（以及所有其他 Google 图表类型），然后等待图表图像从对:

 
   var slices = from w in top5 
             select new Slice(w.Count){ Legend = r.Word }; 
   var image = await new Pie(slices){ Title = "Top 5 words" };

http://chart.apis.google.com/chart

的调用返回

结论

大数据不仅仅关乎规模。它还关乎数据的多样性，包括数据模型（主键/外键与键/值）以及消费模式（拉取与推送）等许多维度。本文认为 LINQ 是大数据的一个有希望的基础。LINQ 既是关系代数的泛化，又在范畴论（特别是 monads）中具有深厚的根基。

借助 LINQ，以 C#、Visual Basic 或 JavaScript 表示的查询可以捕获为代码或表达式树。然后可以重写和优化任一表示形式，并在运行时随后编译。我们还展示了如何实现可以在内存中以及在 SQL 和 CoSQL 数据库上运行的自定义 LINQ 提供程序，并且我们介绍了 Web 服务上的 LINQ 友好 API。也可以公开流式数据¹²，以便实现 LINQ 标准查询运算符，从而形成一个单一的抽象，使开发人员能够查询大数据的所有三个维度。

致谢

非常感谢云可编程团队成员 Savas Parastatidis、Gert Drapers、Aaron Lahman、Bart de Smet 和 Wes Dyer 在构建 LINQ 和 coSQL 的所有风格的基础设施和原型方面所做的辛勤工作；感谢 Rene Bouw、Brian Beckman 和 Terry Coatta 帮助提高本文的可读性；以及感谢 Dave Campbell 和 Satya Nadella 为实际撰写本文提供了必要的推动力。