acm-header
登录

ACM通信

实践

面向大型共享数据库的数据协同关系模型


阴阳与电脑鼠标

来源:iStockPhoto.com

回到顶部

noSQL数据库承诺以可伸缩的和程序员友好的方式解决从大数据中提取有价值的信息和业务洞察力的问题,这推动了noSQL数据库成为我们这个领域最近最热门的话题之一。然而,随着大量的开源和商业产品(Membase、CouchDB、Cassandra、MongoDB、Riak、Redis、Dynamo、BigTable、Hadoop、Hive、Pig等等)和周围各种各样的技术术语(Paxos、CAP、Merkle树、gossip、向量时钟、草率的quorum、MapReduce等等)的出现,企业和从业者很难看到树木中的森林。当前的noSQL市场满足垄断竞争市场的三个特征:进入和退出壁垒低;有许多小供应商;这些供应商在技术上生产异质的、高度差异化的产品。12垄断竞争的市场不符合完全竞争的条件。因此,从长远来看,垄断竞争企业将获得零经济利润。

在20世纪70年代早期,数据库世界也处于类似的糟糕状态。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实际上是一个键-值存储,其中键是地址(l-值),值是存储在内存中某个地址(r-值)的数据。c#和Java等语言没有区分r值和l值,这与C或c++不同,它们的区别是显式的。在C语言中,指针解引用操作符*p检索隐式全局存储中存储在地址p处的值。在本文的其余部分中,我们很容易混淆对象(图)和键值存储这两个词。

在c#(或任何其他现代面向对象语言)中,我们可以使用以下类声明对产品进行建模,每个产品都有标题、作者、出版日期和页数的标量属性,并包含两个嵌套集合——一个用于关键字,另一个用于评级:

ins01.gif

给定这个类声明,我们可以使用对象初始化式创建一个产品,并使用集合初始化式将其插入到集合中:

ins02.gif

程序在内存中生成如图所示的对象图图1

的两个嵌套集合关键字而且评级属性都由具有自身标识的实际对象表示。

使用c# 3.0中引入的LINQ(语言集成查询)理解语法,11我们可以通过以下查询找到所有拥有四星评级的产品的标题和关键词:

ins03.gif

LINQ理解语法只是一组标准查询运算符的语法糖,可以在任何现代编程语言中用闭包、lambda表达式(这里写为评级= = >评级 == "****")或内部类,如Objective-C、Ruby、Python、JavaScript、Java或c++。c#编译器将前面的查询转换为下面的去糖目标表达式:

ins04.gif

查询结果中的各种值(特别是Keywords集合)与原始对象图完全共享,结果是一个完全有效的对象图,如图2

现在让我们使用关系模型重做这个示例。首先,我们必须将嵌套的Product类规范化为三个平面表,for产品关键字,评级分别如图所示图3.关系世界中的每个值都需要一个新的主键属性(在这里都称为ID)。此外,关键字而且评级表需要一个额外的外键属性ProductID编码一对多关联产品而且关键字而且评级.稍后,我们将用额外的元数据装饰这些类声明,以反映底层数据库表。

在大多数商业关系数据库系统中,表是通过执行命令式CREATE TABLE DDL(数据定义语言)语句定义的。

与关系世界中的通常情况一样,我们不将每个产品的关键词和评级的单独集合建模为单独的实体,而是直接将多个关键词和评级与特定的产品关联起来。此快捷方式仅适用于一对多关系。多对多关系(多值函数)的标准实践要求交集表只包含外键对来链接相关行。

对于“声明性”语言来说,SQL没有直接表示表或行的表达式,这可能令人惊讶。相反,我们必须使用松散类型的DML语句以命令式样式填充这三个表,我们用c#表示,如图4

这些DML语句创建了三个表,其中填充了如下所示的行图5

将单一类型规范化到单独表的一个重要后果是数据库必须进行维护参照完整性确保:相关表之间的外键/主键关系在表和行之间的突变之间保持同步;每一行的主键在其表中保持唯一;外键总是指向有效的主键。控件中的行,例如,不能删除产品表中的相关行关键字而且评级表。

参考完整性意味着封闭世界假设数据库上的事务通过(概念性地)同步挂起世界,应用所需的更改,并在成功恢复引用完整性时再次恢复世界,回滚任何其他机会来序列化。假设一个封闭的世界,正如我们所说,是关系模型的优点和缺点。一方面,它通过ACID(原子性、一致性、隔离性、持久性)事务简化了开发人员的生活(尽管在实践中,为了提高效率,必须经常处理更弱的隔离级别),并允许进行令人印象深刻的(基于统计的)查询优化。然而,封闭世界的假设与分布和向外扩展直接矛盾。世界越大,越难保持封闭。

回到我们的示例,我们提供naïve查询来查找所有带有四星的产品的标题和关键字,这些标题和关键字直接用关系模型表示。它产生了所有可能组合的叉积产品关键字,评级,并只选择关键词和评分与产品相关且评分为四星的标题和关键词:

ins05.gif

查询的结果是中所示的行集图6.令人失望的是,这个行集本身并没有规范化。

事实上,要返回对象图查询的规范化表示,我们需要对数据库执行两个查询(在单个事务中):一个查询返回标题及其主键,另一个查询选择相关的关键字。

我们在这里观察到的是SQL缺乏组合性在不超出系统范围的情况下,任意地从较简单的值中组合复杂值的能力。通过查看表行的语法定义,我们可以立即发现SQL缺乏组合性;因为没有递归,行只能包含标量值:

ins06.gif

将此定义与匿名类型的定义进行比较,在匿名类型中,一行可以包含任意值,包括其他行(或嵌套集合):

ins07.gif

SQL中充满了非组合的特性。例如,NULL的语义是一个大混乱:为什么把数字13加到NULL值,13 +零,返回NULL,但是两个值相加,零SUM(13日)13,返回?

另外,尽管现代SQL实现中的查询优化器非常强大,但当通过三个嵌套循环(遍历三个表中的每个值)实现时,原始查询可能只需要三次时间。经验丰富的SQL程序员会使用显式连接语法来确保查询和基于对象的查询一样高效:

ins08.gif

根据使用平面结果集的连接结果嵌套的编码,SQL程序员必须在各种类型的内部,外部,离开了,正确的连接。

回到顶部

阻抗失配

1984年,George Copeland和David Maier认识到关系模型和刚刚描述的对象图模型之间的阻抗不匹配,5在此后的25年里,我们看到了O/R(对象-关系)映射器的爆炸式增长,它们试图弥合两个世界之间的差距。

对O/R映射器更持怀疑态度的观点是,它们正在消除将原始对象模型规范化为多个表所造成的损害。对于我们正在运行的示例,这意味着我们必须将信息添加回各个表,以恢复原始模型中存在的关系。在本例中,我们使用LINQ-to-SQL自定义元数据注释;其他O/R映射器使用类似的注释,这通常可以从类型和属性的命名约定中推断出来。

ins09.gif

注意,得到的对象模型必然比我们开始时更复杂,因为我们被迫为原始对象模型中不存在的Rating和Keyword集合引入显式表示。各种外键和主键属性的存在进一步证明了O/R映射抽象是有漏洞的。

除了这些小的差异,所有这些工作的最终结果是,我们现在可以编写查询来查找所有的产品,几乎和我们在规范化之前做的一样简洁:

ins10.gif

由于结果必须作为对象图呈现,O/R映射器将确保创建适当的嵌套结果结构。不幸的是,并不是每个O/R映射器都能有效地做到这一点。9

不仅仅是程序员需要恢复代码的原始结构。数据库实现者还必须通过构建索引来避免我们前面观察到的潜在立方效应,从而使查询高效执行。对于一对多关系,索引不过是由表之间的预计算连接所产生的嵌套集合,以便快速查找外键指向具有特定主键的行的所有行。但是,由于关系模型在组合下不是封闭的,因此必须定义索引的概念该模型。

两个自然指数对应着两者之间的关系产品而且评级而且产品而且关键字,分别。对于Products表中的每个产品,评级索引包含所有相关评级的集合:

ins11.gif

同样的,对于每一个产品产品表,关键字索引包含所有的集合关键字相关产品

ins12.gif

如果我们将索引可视化为Products表上的附加列,那么表之间原始关系的逆转就会变得很明显。Products表中的每一行现在都有一个指向Keywords和Ratings表的外键集合,与原始对象图非常相似,如图7

分层数据规范化的优点之一是能够执行特别查询,即在原始数据模型中没有预想到的条件下连接表。例如,我们可以尝试找到所有的产品对,其中一个产品的标题长度与另一个产品中作者姓名的长度相同,使用以下查询:

ins13.gif

但是,在没有索引的情况下,该查询需要全表扫描,因此在Products表的长度上花费二次元的时间。

创建索引的能力是一个封闭世界的假设。例如,如果我们修改前面的特别查询,以查找其中一个页面具有引用另一个页面的URL的所有Web页面对,那么显然,当您在单个数据库中没有整个Web可用时,为该连接构建索引是相当困难的任务:

ins14.gif

总结到目前为止所学的知识,我们看到,为了使用关系数据库,从自然分层对象模型开始,设计人员需要将数据模型规范化为多个不再反映原始意图的类型;应用程序开发人员必须通过用额外的元数据装饰规范化数据来重新编码原始的层次结构;最后,数据库实现者必须通过构建索引来加快对规范化数据的查询,这些索引实际上也重新创建了数据的原始嵌套结构。

回到顶部

noSQL是coSQL

在这一点上,键值和外键/主键数据模型之间的概念不一致似乎是无法克服的。这将是一种遗憾,因为很明显,两者各有优缺点。如果我们能对关系模型的优点和对象图模型的优点给出一个更数学的解释,那不是很好吗?事实证明,我们可以通过仔细查看为我们在两个模型中运行的示例创建的(内存中的)结构来找到这个问题的答案。

让我们从稍微简化对象图示例开始。为此,我们删除了Ratings和Authors集合的对象标识,以更直接地反映它们在关系世界中的建模方式。我们将Keywords和Ratings项直接内联到父Product中,就像我们有基于值的集合一样。从图片上看,我们从左边的图表移动到右边的图表图8

对于表格表示,我们显示了从外键到主键的关系的显式箭头。再一次,从图片上,我们从左边的图表移动到右边的图9

当我们并排比较最右边的两个图时,我们注意到两个有趣的事实:

  • 在对象图模型中,对象的身份为内涵的也就是说,对象标识不是值本身的一部分,而是由它们在存储中的键决定的。在关系模型中,对象标识为外延也就是说,对象标识是以主键的形式作为值本身的一部分。
  • 就物体同一性的概念而言,这两种表示极为相似;唯一的区别是箭头是反向的!

在这一点上,这两种表示之间似乎有很强的对应关系:它们都由元素的集合(对象或行)和元素之间的箭头的集合组成,唯一的区别是箭头的方向。有什么精确的方法来描述这种情况吗?幸运的是,有一个完整的数学领域是专门为此设计的:范畴论。1

显然,将SQL和noSQL精确形式化为类别超出了本文的讨论范围,但是学习一点类别理论还是很有帮助的。范畴理论起源于对数学结构的研究,并试图通过考虑结构之间的关系来联系结构的类别。因此,范畴论用。来表达数学概念对象,箭头对象之间,和作文以及箭头组成应该满足的一些公理。从计算的角度来看,范畴理论是一种高度程式化、紧凑的函数式语言。虽然它很小,但它足以代表所有的数学。对于计算机科学家来说,范畴理论已经被证明是一个丰富的技术来源,可以很容易地应用于许多现实世界的问题。例如,Haskell对命令式编程建模的方法直接从问题的分类模型中提取出来。

范畴论中第一个强有力的概念是二元性。对偶性的例子在计算机科学中比比皆是。每个程序员都熟悉德摩根定律的两种双重形式:

ins15.gif

计算机科学中其他对偶性的例子包括引用计数和跟踪垃圾收集之间、按值调用和按名称调用之间、基于推和拉的收集之间、事务内存和垃圾收集之间,等等。

形式上,给定一个类别C对于物体和箭头,我们得到了对偶类别有限公司(C)把所有的箭头倒过来C.如果一个声明T是真的在C,那么它的对偶陈述有限公司(T)在双重范畴中是真的吗有限公司(C).在本文的语境中,我们可以将“对偶命题”理解为“opposite statement”。

在SQL类别中,当子节点的外键等于父节点的主键(图10).在noSQL类别中,箭头是反向的。当父节点中的子指针等于存储中的子节点的地址时,父节点指向子节点图11).

换句话说,noSQL类别是SQL类别的对偶,noSQL实际上是coSQL。这种二元性的含义是,coSQL和SQL并不像善与恶那样冲突。相反,它们是和谐共存的两个对立面,可以像阴阳一样相互转化。有趣的是,在中国哲学中,阴象征着开放,因此对应着coSQL的开放世界,而阳象征着封闭,因此对应着SQL的封闭世界。

因为SQL和coSQL在数学上是双重的,我们可以精确地推断出两者之间的权衡,而不是依赖于花言巧语和传闻证据。所附的表给出了一些语句及其对偶,因为它们分别适用于SQL和coSQL。

如果我们真的把对偶性放在心上,我们还可以选择(但不必)调整键值存储的模型,以反映值和计算之间的对偶性,以及同步ACID和异步BASE之间的对偶性(基本可用,软状态,最终一致)。13

在键-值故事中查找给定地址或键的值可能涉及计算,在一个真正开放的世界中,它有潜在的延迟,可能会失败。例如,在c#语言中,getter和setter(称为属性)可以调用任意代码。关于计算驱动的键-值存储具有较长的延迟和较高的失败概率(总是能够处理404)的一个更好的例子可能是Web,其中URI(统一资源标识符)作为键,“资源”作为值,HTTP谓词作为基本查询和数据操作语言。另一方面,在类似c的键值内存模型中,我们通常做一个简化的假设,即在内存中查找键需要恒定的时间并且不会失败。

在关系模型的封闭世界中遍历一个关系需要比较两个关系平等,因为参照的完整性保证了它的成功;反之亦然,参照一致性决定了关系是基于价值的。否则,我们永远无法确定引用一致性是否真的成立。

注意,按值比较键要求SQL类别中的对象是强类型的,至少要足以识别主键和外键;同时,由于我们不需要知道coSQL对象的任何值就可以使用它的键来查找它,所以coSQL世界中的对象可以是松散类型的。

回到顶部

与现实世界的关系

我们的SQL类别抽象模型没有对行结构施加任何限制;我们假设我们只能确定一个主键或外键来关联两行。

在典型的关系模型中,我们将进一步施加这样的约束:行由标量值的平面序列组成(所谓的第一标准形式,或1-NF)。如果我们在1-NF中对偶化关系,那么我们得到一个键-值模型,其中值由标量或键或标量或键的集合组成。令人惊讶的是,这正是Amazon SimpleDB数据模型(参见图12).

如果我们假设外键/主键模型中的行只是blob,键是字符串,那么双键值模型正是HTML5的键值存储模型:

ins16.gif

回到顶部

再讲一点范畴理论

到目前为止,我们已经讨论了SQL和coSQL的基本数据模型,但还没有触及查询。通过应用更多的范畴理论,我们可以展示单个抽象,单子和单子推导,如何被用作SQL和coSQL的统一查询语言。

为了讨论查询,我们需要更精确地描述我们的意思集合的值。纯关系代数基于行集,但实际的关系数据库使用多集(包)或有序多集(排列)。为了抽象地对集合建模,我们观察行的集合/包/排列,并应用范畴理论的格言:“这些不同的行集合实现的接口是什么?”和“我们如何基于这样的接口概括查询?”

首先,让我们坚持使用简单集合。当我们编写SQL查询时,例如

ins17.gif

SQL编译器会根据选择、投影、连接和笛卡尔积将这些漂亮的语法转换为关系代数表达式。按照关系世界的习惯,各种操作都用希腊符号表示:

ins18.gif

没有理由将关系代数运算符限制为只处理行集(或包或排列)。相反,可以在上定义类似的运算符任何集合M T > <任意类型的值T

这种抽象集合的接口M T > <是集合的一般化。它允许我们使用常量创建一个空集合Ø;创建类型的单例集合M T > <给定一个T类型的值使用函数{_} M T > <(符号T M T > <表示映射类型的实参值的函数/闭包/lambda表达式T类型的结果集合M T > <);并使用二元运算符将两个集合合并为一个更大的集合cup.gif的交换性和幂等性cup.gif,我们得到各种各样的集合,如列表、排列、包和集合):

ins19.gif

使用这些构造函数,我们可以推广传统的关系代数运算符(选择P、投影F,和笛卡尔积×),使用以下签名对广义集合进行运算:

ins20.gif

事实上,如果我们假设相关子查询有一个操作符,我们称之为SelectMany,但常被称为交叉应用在SQL

ins21.gif

然后我们可以根据这个单独的操作符定义其他的操作符,如下所示:

ins22.gif

令人难以置信的是,这种形状的界面在范畴理论中是众所周知的。它被称为单孢体,其中类型构造函数M < _ >是一个函子单孢体;构造函数{_}是单子的单位;SelectMany是单子的束缚;而且Ø而且cup.gif分别是中性元素和加法。对于我们其他人来说,它们只是定义在集合抽象接口上的方法的签名。

这不是理论上的好奇。我们可以使用与SQL使用关系代数相同的语法技巧,但使用单子代替。这样的单子理解已经被函数式程序员和数据库研究人员公认为一种通用的查询语言。8

LINQ查询只是单单子推导式更熟悉的类似sql的语法。LINQ使用人类可读的标识符,而不是希腊符号xs.Where (P)P(x)而且xs.Select (F)F(x).为了适应广泛的查询,实际的LINQ标准查询运算符包含用于聚合和分组的附加运算符,例如

ins23.gif

任何实现标准LINQ查询操作符的数据源都可以使用理解语法进行查询,包括SQL和coSQL数据源,我们将在下一节中介绍。

.NET框架定义了一对标准接口IEnumerable < T >而且这个IQueryable < T >它们通常由数据源实现,以支持查询,但并不一定需要使用这些特定的接口。支持LINQ查询操作符的其他标准接口包括IObservable < T >而且IQbservable < T >接口,使使用LINQ进行复杂事件处理成为可能。10

回到顶部

可伸缩性和分布

与大多数对noSQL的处理不同,我们没有提到可伸缩性是coSQL的一个定义特性。coSQL模型的开放性简化了跨大量物理分布式机器的可伸缩实现。

在使用LINQ查询SQL数据库时,通常类似的行存储在实现这个IQueryable < T >接口。行之间的关系被提升为集合上的批量操作,集合在这些表之间执行连接;因此,查询使用任意数量的相关表,并从这些表生成一个新表。图中显示了三个表图13

因为SQL中的关系跨越不同的表,所以将单一的封闭世界划分为可以独立处理的“强连接”组件的独立世界并非易事。然而,在一个封闭的世界中,查询优化器可以利用关于各种表的所有可用信息和统计信息。这允许用户编写关注“是什么”的声明性查询,而让系统处理“如何”。

在coSQL情况下,典型的场景是只有一个类型集合这个IQueryable <年代>类型s的自包含的非规范化“文档”的指针。在这种情况下,查询具有类型这个IQueryable <年代> R(见图14).

当没有跨表关系时,集合{x0, x1x、…n1M < S >coSQL查询的源可以自然地水平分区,或分片,到单个子集合{x0cup.gif{x}cup.gif...cup.gif{xn - 1}和每个这样的子集合{x .}}可以分布在集群上的不同机器上。

对于大量的coSQL查询,查询的形状与数据的形状密切相关。这样的同态查询映射一个集合xs={x0cup.gif{x1cup.gif...cup.gif{xn - 1}到f(x0oplus.giff (x1oplus.gif...oplus.giff (xn - 1)也就是说,它们的形式是一样的xs.Select (f) .Aggregate (oplus.gif对于一些功能fisin.gifS R和二进制运算符oplus.gifisin.gifRxRR.理查德·伯德的第一个同态引理3.说明任何函数hisin.gifM < S > R是关于的同态cup.gif当且仅当它可以被分解成一个map,然后是一个reduce:h (x) = xs.Select (f) .Aggregate (oplus.gif.数学表明,coSQL查询是使用MapReduce执行的。6

MapReduce的实际实现通常稍微概括了Bird的引理SelectMany而不是选择因此,映射阶段可以返回一个集合而不是单个值,并插入中间项GroupBy作为一种将map阶段的值等价类“写入”到key-value存储中,以便在reduce阶段进行后续处理的方法,然后在每个子集合上聚合:

ins24.gif

例如,DryadLINQ15使用类型PartitionedTable < S >:神游yable <年代>表示用于LINQ查询的分区输入集合,然后使用中所示的函数在分区集合上实现MapReduce图15

在集合跨网络分布的开放环境中,考虑到延迟、错误等因素,查询优化器很难执行全局优化。因此,大多数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“聚合者”Nilsson, Bedarra-Dave Thomas, Ralf Lämmel, Torsten Grust, Maarten Fokkinga, Rene Bouw, Alexander Stojanovic和匿名的主审,他们的评论极大地改进了本文的呈现,当然也要感谢Dave Campbell对LINQ所有酷东西的支持。

ACM队列的q戳相关文章
queue.acm.org

与Erik Meijer和Jose Blakeley的对话
http://queue.acm.org/detail.cfm?id=1394137

碱:一种酸的替代品
丹普里切特
http://queue.acm.org/detail.cfm?id=1394128

弥合对象-关系的鸿沟
克雷格·罗素
http://queue.acm.org/detail.cfm?id=1394139

回到顶部

参考文献

1.Awodey, S。范畴论(第二版)。牛津大学出版社,2010。

2.贝克,J.,邦德,C.等。超大商店:为交互服务提供可伸缩、高可用的存储。创新数据系统研究会议。(2011)。

3.列表理论导论。在离散设计的逻辑规划与微积分。M.布罗伊主编。斯普林格-弗拉格(1987),342。

4.用于大型共享数据库的数据关系模型。Commun。ACM 13(1970年6月)。

5.Copeland, G.和Maier, D.使Smalltalk成为一个数据库系统。在ACM SIGMOD数据管理国际会议论文集。1984.

6.Fokkinga, M. mapreduce为外行人提供两页的解释;http://www.cs.utwente.nl/~fokkinga/mmf2008j.pdf

7.开放标准的经济基础(2005);flosspols.org

8.Grust, t . 2003。单子推导式:查询的通用表示。在数据管理的功能方法。P.格雷,L.克施伯格,P.金,A.波洛瓦西里斯,Eds。施普林格Verlag, 2003, 288311。

9.Grust, T., Rittinger, J., Schreiber, T.雪崩安全LINQ编译。VLDB基金会议录(12), 2010年。

10.主题/观察者是迭代器的二元。在FIT:编程语言设计和实现会议上的有趣想法和想法(2010);http://www.cs.stanford.edu/pldi10/fit.html

11.Meijer, E. Beckman, B. Bierman, G. LINQ:协调。net框架中的对象、关系和XML。ACM SIGMOD数据管理国际会议论文集。ACM,纽约,2006年。

12.Pirayoff, R。微观与宏观经济学。悬崖笔记,2004。

13.普里契特博士:碱:酸的替代品。ACM队列(2008年7月)。

14.斯通布雷克,赫勒斯坦,J.M.善有善报。在数据库系统中的阅读(第四版)。斯通布雷克和赫勒斯坦主编。麻省理工学院出版社,剑桥,马萨诸塞州,2005,241。

15.袁宇,M.I. DryadLINQ:一个使用高级语言的通用分布式数据并行计算系统。操作系统设计与实现“,”2008.

回到顶部

作者

埃里克·梅耶尔emeijer@microsoft.com)在过去的15年里一直致力于“云的民主化”。他最为人所知的可能是他在Haskell语言方面的工作,以及他对LINQ和响应式框架(Rx)的贡献。

加文·比尔曼gmb@microsoft.com)是微软剑桥研究院的高级研究员,专注于数据库查询语言、类型系统、语义、编程语言设计与实现、数据模型集成、分离逻辑和动态软件更新。

回到顶部

脚注

DOI:http://doi.acm.org/10.1145/1924421.1924436

回到顶部

数据

F1图1。产品集合的对象图。

F2图2。对象图结果的书与四星评级。

F3图3。产品数据库的数据声明。

F4图4。在Product数据库中插入值。

F5图5。产品数据库的关系表。

F6图6。表格结果的书与四星评级。

F7图7。产品表的关键字和评级索引。

F8图8。内联关键字和评级的产品集合的对象图。

F9图9。具有显式关系的Products数据库的关系表。

F10图10。从子到父的SQL箭头。

季图11。从父到子的coSQL箭头。

F12图12。产品集合的Amazon simpleDB表示。

F13图13。三个关系表之间的外键关系。

F14图14。coSQL文档的集合。

F15图15。DryadLINQ中MapReduce的签名。

回到顶部

UT1表格SQL和coSQL之间的二元性的后果。

回到顶部


©2011 acm 0001-0782/11/0400 $10.00

允许为个人或课堂使用部分或全部作品制作数字或硬拷贝,但不得为盈利或商业利益而复制或分发,且副本在首页上附有本通知和完整的引用。除ACM外,本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表,都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。

数字图书馆是由计算机协会出版的。版权所有©2011 ACM, Inc.


评论


匿名

我喜欢这个想法,但是否需要手动合并结果集,如SQL和XML上的LINQ'ing,或对两者使用相同的查询?
让coSQL接受一个IQueryable并返回一个IObservable,或者最好是IObservable的Task,这将是很方便的。因为大多数gui只需要在序列中初始显示的前x个引用项。ie。下拉,滚动之前的列表等。如果不需要,让控件取消请求,那么在准备好时返回其余的请求将非常方便。“JIT数据访问”。
——N2Cheval


Anil Shafeeque

有趣的主题。但我总觉得对象模型上的查询不能像关系模型那样执行。还是假设性能可以通过Map reduce等分布式计算框架来实现?

+阿尼尔


CACM管理员

以下这封信发表在2011年7月出版的《致编辑的信》(//www.eqigeno.com/magazines/2011/7/109897)上。
——CACM管理员

Erik Meijer和Gavin Bierman的文章《大型共享数据库的数据协同关系模型》(2011年4月)过火了,他们声称关系模型和NoSQL的“键-值对”是等价的,而没有考虑到30多年前E.F. Codd对数据模型的定义。Meijer和Bierman发现NoSQL系统与关系模型的某些部分有相似之处,错误地认为两者是等价的。

Codd在1980年“数据抽象、数据库和概念建模研讨会”(http://portal.acm.org/citation.cfm?id=806891)的论文《数据库管理中的数据模型》中,将数据模型定义为由三个部分组成:用一阶逻辑表示格式良好表达式的数据结构;运算符在这些结构上关闭,允许推理;以及完整性约束来强制内部一致性。

NoSQL系统没有这样定义的数据模型。其他的都是评论。

Meijer和Bierman忽略了逻辑和推理,没有解释键-值系统如何识别完整性约束,更不用说执行完整性约束了。他们引用参考完整性(一种完整性约束形式)作为关系数据库承担的外生成本来纠正缺陷。事实其实恰恰相反;一致性是任何数据库管理系统的核心义务。键-值系统中缺乏约束检查,这给应用程序带来了约束检查的负担,关系模型就是专门为纠正这种情况而发明的。

Codd在他的时代也遇到了类似的缺乏理解的问题。在同一篇论文中,他写道:“在比较数据模型时,人们常常完全忽略运算符和完整性规则。当这种情况发生时,由此产生的比较就有可能变得毫无意义。”

Codd的里程碑式文章《大型共享数据库的数据关系模型》(Communications, 1970年6月)讨论了Meijer和Bierman提出的其他观点,包括路径独立性。一个有兴趣的读者会在一晚上读那篇文章学到很多东西。

对象关系映射库和NoSQL系统试图(通过技术手段)解决一个非技术问题:有才华的人不愿意掌握关系模型,从而受益于它的数据一致性和逻辑推理能力。他们不是利用它,要求DBMS供应商提供更多的关系功能,而是试图避免并取代它,无意中提倡回到20世纪60年代脆弱、不可靠、不合逻辑的系统,去掉绿条风扇折叠纸。

詹姆斯·k·洛登
纽约

----------------------------------------------------

作者的回应:

洛登的评论有许多错误。事实上,我们的文章明确地批评了NoSQL缺乏一致认可的数据模型。我们并没有忽略“推理”,而是提出了一种基于单单子推导的查询语言,有趣的是,这与我们更喜欢的关系模型查询语言相同。我们没有断言关系模型和键-值模型是等价的,而是对偶的。减弱一致性检查的问题涉及到NoSQL系统的核心问题,超出了本文的范围。

埃里克·梅耶尔
雷蒙德,佤邦
加文·比尔曼
剑桥大学,英国


CACM管理员

以下这封信发表在2011年6月出版的《致编辑的信》(//www.eqigeno.com/magazines/2011/6/108669)上。
——CACM管理员

我想澄清一下Erik Meijer和Gavin Bierman在他们的文章《用于大型共享数据库的数据的协同关系模型》(2011年4月)中关于SQL起源的陈述,文中说:“当Ted Codd提出一种基于关系和外键/主键关系的数学概念的新数据模型和结构化查询语言(SQL)时,情况发生了根本性的变化。”实际上,从Codd在1970年发表的有影响力的通讯文章《大型共享数据库的数据关系模型》(由Meijer和Bierman引用)到SQL语言需要额外的步骤和人员。在本文以及后续的文章和论文中,Codd讨论了基于关系演算和关系代数的查询语言。但是,是Raymond Boyce和Donald Chamberlin在研究了Codd的工作后,定义了SEQUEL语言,后来改名为SQL, Chamberlin和Boyce首先记录了这一语言。(1)关于Codd的思想如何影响Boyce和Chamberlin以及System R团队的其他成员,请参阅Chamberlin。

保罗McJones
加州山景城

参考文献

(1)张伯林和博伊斯:一种结构化的英语查询语言。在1974年ACM SIGFIDET(现为Sigmod)数据描述、访问和控制研讨会(Ann Arbor, MI, 5月13日)的会议记录中。ACM出版社,纽约,1974,249264。

(2)张伯林,D.口述史,保罗·麦克琼斯,采访者。计算机历史博物馆,山景城,加州,2009年7月21日;http://www.computerhistory.org/collections/accession/102702111


显示所有4评论

Baidu
map