ACM通信
实践
LINQ的世界
构建基于网络和云计算的应用程序的程序员将来自传感器、社交网络、用户界面、电子表格和股票报价等许多不同来源的数据连接在一起。大多数数据不适合传统关系数据库的封闭和干净的世界。它太大了，没有结构，不规范，而且实时流化。一开始，在所有这些不同的数据模型和查询语言之间呈现统一的编程模型似乎是不可能的。但是，通过关注共性而不是差异，大多数数据源将接受某种形式的计算来筛选和转换数据集合。
数学家很久以前就观察到看似不同的数学结构之间的相似之处，并通过范畴理论将这一见解形式化，特别是将单子的概念作为集合的泛化。诸如Haskell, Scala, Python，甚至JavaScript的未来版本都合并了列表和单子推导式来处理集合的副作用和计算。Visual Basic和c#的。net语言采用LINQ(语言集成查询)形式的单子，作为弥合对象和数据世界之间差距的一种方式。本文将单子和LINQ描述为关系代数和SQL的泛化，用于任意类型的任意集合，并解释为什么这使LINQ成为大数据的一个令人信服的基础。
LINQ是在c# 3.0和Visual Basic 9中引入的，作为一组api和相应的语言扩展，它们在编程语言世界和数据库世界之间架起了桥梁。尽管外部开发人员社区对LINQ的热情持续高涨，但这项技术的全部潜力还没有达到。由于LINQ的基本特性，它在对象关系(O/R)之外的映射场景仍然有巨大的潜力，特别是在大数据领域。
大数据的出现使得程序员拥有一个单一的抽象比以往任何时候都更重要，它允许他们至少跨三个不同的维度进行处理、转换、组合、查询、分析和计算:体积或大或小，范围从数十亿项到少数几个结果;各种在模型中，结构化或非结构化，扁平或嵌套;而且速度流或持续，推或拉。因此，我们看到了数量惊人的新数据模型、查询语言和执行结构。LINQ可以在一个抽象后面虚拟化所有这些方面。
以Apache的Hadoop生态系统为例。它至少有八个外部dsl(领域特定语言)或api:一组用于MapReduce计算的低级Java接口;级联，一种“数据处理定义语言，实现为一个简单的Java API”;水槽，“基于流数据流的简单而灵活的架构”;猪一种“表达数据分析程序的高级语言”;HiveQL这是一种“类似sql的语言，用于简单的数据总结、特别查询和大型数据集的分析;”CQL，“在Cassandra中提出的数据管理语言”;Oozie一个基于xml的“协调器引擎，专门基于时间和数据触发器运行工作流”Avro，一种用于数据序列化的模式语言。
要创建端到端应用程序，程序员除了使用Java等通用编程语言外，还需要使用几种外部dsl将所有内容粘在一起。如果数据来自外部RDBMS(关系数据库管理系统)或基于推的源，则甚至需要更多的dsl，如SQL或StreamBase。另一方面，使用LINQ和c#或Visual Basic，程序员可以使用内部dsl可以针对通用OO(面向对象)语言中的任何形状或形式的数据进行编程，该语言自带工具(Visual Studio或Xamarin的跨平台解决方案，如MonoDevelop、iPhone的Mono Touch或Android的Mono)和广泛的标准库集合(。净框架)。
标准查询运算符和LINQ
假设给定一个textsay文件，words.txt您需要计算该文件中不同单词的数量，找出五个最常见的单词，并在饼图中可视化结果。如果您仔细考虑一下，就会清楚这实际上是一个转换集合的练习。这正是LINQ所设计的任务类型。为了简单起见，我们使用LINQ To Objects实现了这个示例来处理内存中的数据;然而，只要进行最小的修改，同样的代码就可以在LINQ到HPC(高性能计算)上运行，在商品集群中存储tb的数据。
标准的文件。ReadAllText方法将文件的内容作为单个大字符串提供。首先，您需要通过分隔符(如空格、逗号、句点等)将该字符串拆分为单个单词。一旦你有了一个单词列表，你需要清理它，删除所有的空单词。最后，将所有单词规范化为小写。
使用LINQ序列操作符，你可以将上一段的描述直接转化为代码:
LINQ没有直接使用序列操作符，而是提供了一种更具“声明性”的查询理解语法。使用推导式，你可以像下面这样重写代码:
将文件转换为单个单词序列后，首先按每个单词对集合进行分组，然后计算每个组(包含该单词的所有出现)中的元素数量，就可以找到每个单词的出现次数:
如果不使用查询理解语法，代码看起来像这样:
要找到最频繁出现的前五个单词，您可以按每个记录排序数看看前五个要素:
现在您已经有了文件中前五个单词的集合，您可以在饼图中可视化它们，如图1．饼图实际上不过是一组片的集合，其中每个片由一个表示整个饼图的比例的数字和一个描述该片所代表内容的图例组成。这意味着通过定义图表API是LINQ友好的，你可以通过在谷歌图像图表API上写一个查询来创建图表:
的等待关键字是用一种非正统的方式使昂贵的强制从Google.Linq.Charts。饼转换到需要显式网络往返的映像中。
这个例子只是触及了LINQ的皮毛。它提供了一个序列操作符库，例如选择,GroupBy,……转换集合，它以查询推导的形式提供语法糖，允许程序员在更高的抽象级别上编写对集合的转换。
为了真正理解LINQ的力量，让我们后退一步，研究它的起源和数学基础。别担心，你只需要高中水平的数学知识。
为了真正理解LINQ的力量，让我们后退一步，研究它的起源和数学基础。别担心，你只需要高中水平的数学知识。
数据集中的解释
关系代数构成了SQL的形式基础，它为值集{}定义了许多常量和构造函数，例如空集Ø
{};注射的值到单例集合{_}{};和联盟把两个集合合并成一个新的集合
x {} {} {};还有许多关系操作符，例如投影，它对集合中的每个元素应用转换x () {} {};选择，它只选择集合中满足给定属性的那些元素
；笛卡尔积，将集合X中的所有元素配对x {} {} {};而且cross-apply，它为第一个集合@中的每个元素生成第二组值({}) x{}{}。
图2描述使用云表示值集的关系代数运算符。SQL编译器翻译用熟悉的方式表示的查询SELECT-FROM-WHERE语法转化为关系代数表达式;为了优化查询，它应用了诸如选择分布的代数定律:
然后将这些逻辑表达式转换为由RDBMS执行的物理查询计划。
例如，SQL查询选择朋友喜欢的名字(朋友，寿司)转换成关系代数表达式(f为了加快查询的执行速度，RDBMS可以使用一个索引来快速查找喜欢的朋友
f.Name, (f喜欢(f,寿司),朋友)。寿司而不是对整个集合进行线性扫描。
交叉应用操作符@特别强大，因为它允许相关的子查询，您可以为第一个集合中的每个值生成第二个集合，并将结果平摊到单个集合@中(f,{…,z}) = f (a)所有其他关系操作符都可以根据交叉应用操作符来定义:.．.f (z)。
作为程序员，您可以很容易地想象编写交叉应用的简单实现:只需遍历输入集中的项，应用给定的函数，并将结果累积到结果集中。然而，这样的实现不需要它的参数为as集{};任何我们可以迭代的东西，如列表、数组或哈希表就足够了。同样，完全没有理由将关系代数操作限制在值{}的集合中。它们也可以基于其他类型的集合实现。
也许令人惊讶的是，也没有任何理由将操作传递到，， @应该仅限于混凝土功能．事实上，您可以使用函数的任何表示形式来确定要执行的计算。例如，在JavaScript这样的语言中，您可以简单地传递一个字符串，然后使用eval将其转换为可执行代码。
你所寻找的是潜在的东西接口关系代数实现的。只要集合M<>的类型构造函数提供满足与{}类似的集类代数属性的操作，以及用于计算的类型构造函数
你可以将关系代数推广到以下操作符集，并且仍然能够通过淡化查询语法在这些集合上编写SQL查询:
对于程序员来说，这只是将接口与实现分离;数学家称其为结构单体，而不是他们所说的查询理解．
像c#这样的OO语言为集合使用规范接口IEnumerable < T >作为抽象集合类型M．通过这样做，可以将关系代数中的运算符识别为LINQ标准查询运算符Linq。可列举的类，如中所示图3．
或者，您也可以使用这个IQueryable < T >表示集合的接口M T > <和表达式树表达< Func <、> >来表示计算．在这种情况下，可以将关系代数运算符识别为LINQ标准查询运算符Linq。可查询类。在c#案例中使用morphismsor将代码视为数据的能力表达式用于代码字面化的类型和lambda表达式是一种基本功能，它允许程序本身在运行时操作、优化和翻译查询。
c#语言定义了表单的类似xquery的推导式，而不是SQL语法from-where-select．前面的SQL查询示例如下:
就像在SQL中一样，推导式被编译器翻译成底层LINQ查询代数:
取决于的过载在哪里而且选择， lambda表达式将被解释为代码或数据。的简化实现这个IQueryable稍后讨论。
如前所述，单子及其在LINQ等实用编程语言中的化身只是关系代数的一般化，通过想象关系代数实现的接口。因此，数据库人员和程序员都应该非常熟悉LINQ背后的概念和思想。
理论付诸实践
与Haskell不同，它以原则性的方式整合了单子和单子推导式，c#类型系统对单子操作符的数学签名没有足够的表达能力。相反，查询推导式的转换是以纯粹基于模式的方式定义的。在第一次传递中，编译器使用一组固定的规则盲目地将推导式糖化到常规的c#方法调用中，然后依靠标准的基于类型的重载解析将查询操作符绑定到它们的实际实现。
例如，方法Foo选择(Bar源，Func，它不涉及任何集合类型，将被绑定作为翻译理解的结果
变成糖化的表达式
该技术在接下来的示例中被广泛使用。
LINQ和它的一元基础之间的另一个区别是查询操作符的类别要大得多，包括分组和聚合，这更像sql。有趣的是，c#中包含的推导式受到Haskell中的单子推导式和列表推导式的启发，递归地启发Haskell在其推导式中添加了对分组和聚合的支持。
自定义查询供应商
雅虎天气服务(http://developer.yahoo.com/weather/)允许查询给定位置的天气预报，使用公制或英制单位表示温度。这个简单的服务是演示LINQ查询操作符的非标准实现的好方法，它完全专门针对这个特定的目标，只允许表单的强类型查询
或者等效地使用查询推导式
操作符的实现从查询中提取城市和温度单位，并使用它们创建REST调用(http://weather.yahooapis.com/forecastrss?w=woeid&u=unit)连接到雅虎服务等待关键字显式地将请求强制转换为响应。
这种风格的自定义LINQ提供程序的技术技巧是将目标查询语言的功能投射到一个类型级别的状态机中，该状态机需要(a)一个城市和(b)一个单位，以“流畅”的方式(并由智能感知支持)引导用户做出可能的选择(图4）.
在状态机的每个转换中，我们收集查询的各个部分(在本例中是特定的城市和温度单位)。原则上，城市并不一定要排在前面，但对于图表来说，允许这两种类型中的任何一种可能都更自然在哪里子句要先指定，但要有两个限制在哪里条款是必需的。我将解除状态机中的这个限制作为读者的练习。
注意，没有任何类型天气,WeatherInCity,或WeatherIn-CityInUnits实现任何标准集合接口。相反，它们表示将提交给Yahoo Web服务的请求的计算阶段，为此不需要定义显式容器类型。让很多人惊讶的是，这两者都不是在哪里方法实际上计算一个布尔谓词。更奇怪的是，range变量的三次出现预测中的查询具有不同的类型。
的天气类定义一个方法，该方法选取查询中指定的城市并将其传递给WeatherInCity，这是基于类型的状态机中的下一个状态:
的“谓词”在哪里方法是一个接受类型值的函数CityPicker，它只有一个返回幻像类的属性城市它的存在只是为了方便智能感知，其相等检查立即返回传递给相等操作符的字符串:
因此，打电话来雅虎。天气()。在哪里(forecast真的只是一种复杂的方式来创造一个新的预测= =“西雅图”)WeatherInCity{城市=“西雅图”}实例使用一个在哪里方法，该方法不接受布尔谓词和返回字符串的相等运算符。
你可以用同样的技巧WeatherInCityInUnits地方(Func < UnitPicker、单位>谓词)所以呼唤在哪里(预测在上一个筛选器的结果上创建一个new实例forecast.Temperature.In.Celsius)WeatherInCityInUnits{城市= "西雅图"，单位=单位。摄氏}．这里使用的技术不仅对定义LINQ操作符的自定义实现很有用，而且还可以用于构建一般的流畅接口。
由于Yahoo服务需要城市作为WOEID(究竟在哪里ID)，因此我们需要在底层进行两个服务调用，以便检索天气预报。第一个服务调用通过检索所请求城市的WOEIDhttp://where.yahooapis.com/v1/places.q(市)? appid = XXXX．如果成功返回，则进行第二次调用以检索该位置的天气预报。对Web服务器的调用是异步执行的，并且都返回一个任务< T >(在Java中你会使用java . util . concurrent。未来的< T >表示异步操作的结果)。因为我们可以考虑任务< T >作为一种包含(最多)一个元素的集合，它也支持LINQ查询操作符，我们有海龟一直向下;的LINQ实现天气的LINQ实现定义任务< T >(见图5）.
虽然这是一个非常小且有限的示例，但它清楚地说明了许多用于创建真实LINQ提供程序的技术，如LINQ to Objects、LINQ to SharePoint、LINQ to Active Directory、LINQ to Twitter、LINQ to Netflix等等。
通用查询供应商
天气服务查询提供程序示例结构为内部DSL。虽然这通过最大限度的静态类型提供了良好的用户体验，但它为重用提供程序的实际实现提供了很少的空间。它是为特定目标从头到尾定制的。在另一端，我们可以创建一个完全通用的查询提供程序，它“按原样”记录一个完整的查询，只需使用一点神奇的元编程。
在c#中，lambda表达式如x可以转换为委托，类型x > 4711Func < int, int >或者转换到类型的表达式树中表达< Func < int, int > >，它将lambda表达式的代码视为数据。在Lisp或Scheme中使用语法引用将代码视为数据。在c#中，lambda表达式结合上下文所期望的类型提供一个基于类型引用机制。
类可查询实现了LINQ标准查询操作符，它接受表达式树作为参数并返回一个表达式他们的自我表现，就像一个宏观记录器图6．
例如，给定一个值xs类型的可查询< int >时,调用xs。选择(x将lambda表达式转换为表达式树(以粗体显示)，然后返回表示调用本身的表达式树x > 4711）xs。选择(x．现在由特定的查询提供者(如LINQ to SQL、实体框架、LINQ to HPC)来翻译结果表达式树并将其编译为目标查询语言。x > 4711）
的这个IQueryable.NET框架附带的基于的实现使用与刚才展示的简化示例代码相同的方案，不同的是它是基于接口的，因此它依赖于第二个接口IQueryProvider提供用于创建实例的工厂这个IQueryable。
通用查询提供程序的优势在于，您可以提供查询优化等通用服务，这些服务实现了诸如xs.Union (y)。(p) = xs.Where (p)。联盟(ys.Where (p))可以在许多LINQ提供程序之间重用。
LINQ-Friendly api
到目前为止，所有的例子都处理了实现特定的LINQ提供程序。LINQ的一个正交方面是利用特定LINQ实现的api，通常是LINQ to Objects。例如，LINQ to XML是一个用于操作XML文档的API，它是专门为LINQ设计的，这样就不需要使用诸如XQuery或XPath之类的DSL来查询和转换XML。
谷歌Chart API是一个Web服务，它允许您使用一个简单的URI(统一资源标识符)方案动态创建具有吸引力的图表。然而，谷歌图表的URI语法不是很序列友好。例如，前面饼图示例的URI是这样的:
问题在于标签的规格(排名= |的| | |)以及数据集的规范12(冠心病= t: 21日,7日,7日,6)该图分两集给出。另一方面，要使用查询生成饼图，您需要一个单独的对集合，为每个片指定值和标签，如从w在top5选择新的切片(w。数){传奇= r.Word}。
换句话说，要使谷歌Chart API序列友好，必须对一组对进行转置M < SxT >变成一对收藏品xM M < S > < T >．函数式程序员立即将其识别为函数的一个实例解压缩可以将包含切片序列的图表转换为谷歌图表API所需的URI格式，方法是使用图表服务规定的分隔符格式化各种集合，如图7．(RS x RT xM< R>)MxM
结论
大数据不仅仅关乎规模。它还涉及数据的多样性，包括数据模型(主键/外键与键/值)和使用模式(拉与推)，以及许多其他维度。本文认为LINQ是一个很有前途的大数据基础。LINQ不仅是关系代数的泛化，而且深深植根于范畴理论，特别是单子。
使用LINQ，用c#、Visual Basic或JavaScript表示的查询可以被捕获为代码或表达式树。这两种表示都可以在运行时进行重写和优化，然后进行编译。我们还展示了如何实现可以在内存中、在SQL和CoSQL数据库上运行的自定义LINQ提供程序，并在Web服务上展示了LINQ友好的api。也可以公开流数据，以便实现LINQ标准查询操作符，从而产生单一抽象，允许开发人员查询大数据的所有三个维度。
致谢
非常感谢云可编程团队成员Savas Parastatidis、Gert drppers、Aaron Lahman、Bart de Smet和Wes Dyer，感谢他们为LINQ和coSQL的各种风格构建基础设施和原型所做的辛勤工作;感谢Rene Bouw、Brian Beckman和Terry Coatta帮助提高本文的可读性;以及戴夫·坎贝尔和萨蒂亚·纳德拉，感谢他们为我撰写这本书提供了必要的推动。
相关文章
在queue.acm.org
实现LINQ提供程序的痛苦
埃尼奥伦
http://queue.acm.org/detail.cfm?id=2001564
与Erik Meijer和José Blakeley的对话
2009年1月2日
http://queue.acm.org/detail.cfm?id=1394137
面向大型共享数据库的数据协同关系模型
埃里克·梅杰，加文·比尔曼
http://queue.acm.org/detail.cfm?id=1961297
相关阅读
- c#查询表达式翻译备忘单;http://bartdesmet.net/blogs/bart/archive/2008/08/30/c-3-0-query-expression-translation-cheat-sheet.aspx
- 带有Order by和Group by的理解;http: / / research.microsoft.com/en-us/um/people/simonpj/papers/list-comp/index.htm
- 表达式;http://www.cs.cmu.edu/Groups/AI/html/r4rs/r4rs_6.html#SEC28
- 谷歌API图表;http://code.google.com/apis/chart/image/
- Hadoop;http://hadoop.apache.org/
- JavaScript;https://developer.mozilla.org/en/JavaScript/Guide/Predefined_Core_Objects#Array_comprehensions
- LINQ;http://msdn.microsoft.com/en-us/netframework/aa904594
- LINQ HPC;http://blogs.technet.com/b/windowshpc/archive/2011/07/07/announcing-linq-to-hpc-beta-2.aspx
- 单体;http://en.wikipedia.org/wiki/Monad_%28functional_programming%29
- .NET并行编程;http://blogs.msdn.com/b/pfxteam/archive/2010/04/04/9990343.aspx
- Python;http://www.python.org/dev/peps/pep-0289/
- Rx(活性扩展);http://msdn.microsoft.com/en-us/data/gg577609
- Scala;http://www.scala-lang.org/node/111
- Xamarin的;http://xamarin.com/
©2011 acm 0001-0782/11/1000 $10.00
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2011 ACM, Inc.
评论
CACM管理员
以下公开信发表在2012年1月出版的《致编辑的信》(//www.eqigeno.com/magazines/2012/1/144814)上。
——CACM管理员
作为一个从事信息系统开发超过15年的开发者，我可以说，Erik Meijer在“根据LINQ的世界”(2011年10月)中所支持的语言集成查询(LINQ)框架组件产生了令人印象深刻的抽象，但这些抽象隐藏了许多真正的问题，严重依赖LINQ的项目有撞上性能墙的风险。单子的数学理论，或者函数式编程中的计算结构，已经很成熟而且很有用，但是今天的信息系统不是数学结构，而是具有真实物理和财政约束的真实物理系统。
虽然处理器速度和内存容量在不断提高，但对于东京和纽约之间的信号往返而言，光速始终意味着至少需要60毫秒。无论数据源位于什么位置，它都不会位于处理器内部，并且需要大量的时间来执行选择、投影和交叉应用。危险的是，使用抽象的程序员很容易用简单的语句创建巨大的计算负载，系统最终会付出性能和操作成本方面的代价。在应用程序编程中，需要更通用的抽象或语言来提取和评估大型、不同的数据源并不是真正的问题。
我不否认数据处理概念的多样性确实是个问题，但我批评LINQ(和Meijer)对语言的关注。许多语言和形式都有能力表达如何获得应用程序所需的信息。我希望它们的数量少一些，这样程序员就可以在许多不同的领域更容易地使用它们，而不必学习和维护这么多。
LINQ不是系统架构师一直在等待的解决方案;它只是隐藏了最具挑战性的问题，把它们移出了视线，但并没有让它们消失。系统仍然必须响应请求，程序员必须向系统提供的关于应用程序需要什么(在哪里找到它，以及要接受的数量和响应时间方面的成本以及应用程序所容忍的资源消耗的指示越少，系统提供的请求发送方所要求的就越少。
在实际的系统中，对请求的响应很少只是信息的集合，而更有可能是时间、成本、大小和质量方面的一组所需行为。
马库斯Kropf
图恩湖,瑞士
--------------------------------------------
作者的回应
抽象意味着隐藏不必要的细节，大多数类库和框架旨在隐藏特定的细节，以简化程序员的生活。然而，如果这些细节实际上与应用程序相关，那么程序员就不应该使用抽象，或者希望抽象是泄漏的(实际上这是一件好事)，这样他们就可以在需要处理较低级别的关注点时潜入底层。
埃里克·梅耶尔
雷蒙德,佤邦