【干货】蒋步星:关系代数的问题及尝试

本文共12000字,建议阅读时间25分钟

本讲座选自北京润乾软件技术有限公司董事长蒋步星。于2015年5月22日在清华大学经管学院上所做的题为《关系代数的问题及尝试》的演讲。

讲座全文:

今天的内容分五个部分,开始先讲一下基本概念和背景;中间三部分都是数据分析的内容,这是今天的重点;最后一块研究得还不够深,但也涉及到关系代数,就放进来一起谈谈。

我们先从编程序谈起。

编程序到现在仍然并不是一件轻松的活。这里我们不去谈那些由于需求不清或变动而导致的困难,那是软件工程的目标。有一些问题,完全没有歧义,你明确知道解法,使用你最熟悉的程序设计语言,但这个程序仍然不好写。

比如 计算一支股票连续上涨了多少天,计算利率变动时房贷还剩余多少本金。想完成这样的运算,都还是要写很多代码才可以。

最近股市不错,今天有不少例子是和股票相关的。

本质上讲,【编写程序的过程就是把解决问题的思路翻译成计算机可识别的精确的形式语言的过程】。

举例来说,就象小学生解应用题,想清楚每分钟进水多少出水多少,鸡多少兔多少等,最后列出四则运算的表达式,也就是精确的形式语言,就可以解决问题。用计算机解决问题的过程是类似的,拿到一个问题,想出解法,然后还要把解法翻译成计算机能理解能执行的动作才能完成。

那么代码为什么难写呢?

其中很大一部分原因是用来记录解法的形式语言和人的自然思维相差很远,它不能直接描述我们的思路。你必须按形式语言规定的思路来完成,这样经常会导致你告诉计算机该怎么做比做本身还要难。

也就是说,【翻译问题解法到形式语言的过程,这个难度经常远远超过解决问题本身】。经常需要受过专业训练的人员,也就是程序员才会做,而我们的精力应当更多地放在解决问题而不是翻译解法上。

进一步,这里面主要的原因,我认为是形式语言采用的代数体系不好。

什么是代数体系呢,通俗一点说,就是定义了一些数据类型,并在这些数据类型上规定一些运算,并且保证这个运算是封闭的,也就是不能算出新类型的数据,逻辑要自洽,也就是不能算出矛盾来。

这里的数据类型有些象面向对象的类,但又不同。面向对象更强调的是类的继承和重载能力,而这里更强调的是运算。

广义地说,我们做数据处理都是在相应的代数体系下做运算。就像我们平时基于数做四则运算。如果我们在这些数上定义的运算不方便,就会造成很多麻烦,比如,如果只有加减法,没有乘法,人们上街买菜都会成问题了。

形式语言中采用的代数体系将非常严重地影响数据处理的效率和能力。我们举两例不够好的代数:罗马数字和汇编语言。用罗马数字做通用的加减法都很困难,只适合做加1减1这类过于简单的运算。

mov ax,3

mov bx,5

mul bx,7

add ax,bs

这是用汇编语言写出来3+5*7这样的运算,你必须把这样一个算式翻译成寄存器的运算,因为汇编语言只有类似字节这样的数据类型及运算。

这显然非常麻烦,如果是浮点数运算则完全不知道该怎么办了。而使用高级语言就方便得多,因为高级语言中直接有了整数、实数这些数据类型及四则运算。从这个意义上讲,FORTRAN是个伟大的发明。

我们用计算机分析数据的目的是找出事物之间的关联,而事物是由其属性决定的,这在技术上表现为结构化数据。数据分析处理的需求绝大多数都是已经或即将被结构化的数据。

非结构化的数据,在存储上可能是大头,但关联运算并不是很多。有一些很专业算法,比如说图象识别,很难把它归到数据分析的类别中。其他日志、地理信息等的分析都是要做结构化之后才能做。

大数据来了,很多人都说结构化数据的时代已经过去了,我不这么认为,结构化数据仍然是数据分析处理的重点。

提到结构化的数据就要说关系代数了,关系代数是专门为结构化数据发明的一种代数体系,是现代关系数据库的理论基础。关系数据库是应用最广的一种数据库。虽然近年来,尤其大数据概念出来后,关系数据库有各种各样的问题,但仍然很强势。

结构化数据是计算机广泛应用之后才大量出现的数据类型,传统数学中很少涉及这种数据类型,关系代数是少有的几项专门为计算机科学发明的数学。计算机应用中有大量的数学,但大多数都是几十年甚至几百年前被数学家发明的。现在热门的数据挖掘,用到的概率论、图论、线性代数基本上都是这种,没有计算机学术界什么事。

关系代数是在结构化数据的集合上定义的一些运算,集合交并差,以及过滤、分组、连接等运算。

关系代数中对关系的定义比较抽象,属性构成的集合称为关系,然后再研究关系的集合上的运算,这个不好懂。我们这里就用通俗地说法,简单地理解成有属性的对象集合,或者用程序员常说的术语,有字段的记录集合。

提到关系代数就要说SQL,SQL是关系代数的形式语言。我们说,这个形式语言没有达到它的设计初衷。

SQL的设计初衷是什么呢?

它希望让普通的业务人员、不需要太懂技术的人员也能用起来。为什么这么说,因为它长得像英语,在它之前的程序设计语言都是形式化较强的,其中的单词只是符号。

而SQL很象英语,甚至有些句子可以作为英语来读,希望懂英语的人就可以使用。但是,这个目的没有达到,稍微复杂一点的查询用SQL都很难写,需要很专业的人才能做出来的。数据库中大量存在着并非由于性能因素导致的难以计算出来的信息。

稍扯远一点,许多SQL教科书都会声称,用SQL写代码,你只要说明要做什么,而不用关心怎么做,说的很高大上,但其实都是胡扯。前两天我看SAS的书也这么说,不过这些胡扯倒不影响这些产品的伟大性。

事实上,任何一种程序设计语言都在某个层面满足这个说法,用汇编语言你也不用关心电子流是怎么流转的,而用SQL你仍然要关心表中的数据是如何组织的。

SQL的不足,我总结是这样几条:

分步这个比较容易理解,一个问题一步做出来总比分几步做出来要难,SQL不是不支持分步,是不提倡。

其它问题会在下面的讨论中涉及。

从这个意义上讲,关系代数还有很大的发展空间。它到现在也就四十年时间,与传统数学领域相比还很年轻,远远不像业界所说的那样,已经把结构化数据搞完了,其实差得很远。

一个类比,现在的关系代数有点像三百年前搞微积分一样,可以搞的东西很多,门槛也不高。三百年前的微积分,现在大学低年级的学生都能够理解,而当前数学前沿的东西,你不读二十年书,根本就没有办法和人对话。计算机科学理论还处于可以有很多事可做的阶段。

下面我们来讲关系代数中的具体的问题,先谈关联运算的描述。

使用SQL对于单表进行查询并不是很难理解和实施,一般也就是选取字段、过滤、排序等,只有分组汇总稍复杂些,也不是多难懂。

但是,有意义的查询经常是多表的,比如查一下从北京到上海打了多少电话,存款超过10万元的人中本科学历及以上的有多少。这些都需要用到多表关联运算。

SQL中用多表关联运算是用JOIN运算实现的,JOIN运算在关系代数中定义非常简单通用,就是两个表做笛卡尔积后再过滤。

简单的好处,就是适用面广,什么都能表达;但也有坏处,它没有把更多的运算特征体现出来。这样,对于关联复杂的情况,无论是理解还是实施都很困难。类比一下,四则运算中如果只有加法没有乘法显然会很头疼。虽然乘法都可以用加法表达,但实在很麻烦。

实施运算也麻烦,我们有九九表算乘法,不需要硬加起来就可以快速运算。要按关系代数的定义来实现JOIN运算也会有类似的困难,当然数据库厂商实施的时候都会做工程上的优化,我没有见过哪个厂商真地用笛卡尔积实现一般的等值JOIN运算,但要严格地实现这个定义,还是会给工程上优化造成很大困难。

事实上,仔细分析后,我们会发现,实际应用中大多数的JOIN都是上面这三种情况,而不需要引入笛卡尔积。

这里说大多数,不是全部,就象不可能把所有的加法都可用乘法来表示。仍然有一些关联运算需要用原始的JOIN来描述,比如用SQL做矩阵乘法,就需要用笛卡尔积。

但日常数据分析中的大多数JOIN都属于这三种情况,我们逐个来解释。

首先是外键属性化,先来看一个例子:

这里有两张表,一个员工表,一个部门表,我们想查一下中国经理的美国员工。员工表里面有一个字段叫部门,这是个外键指向部门表的主键。部分表里又有一个经理字段指回员工表。这是一个很常见的数据结构设计,指来指去的。

我们要算中国经理的美国员工,SQL写出来是这样的:

员工表和部门表JOIN起来,再JOIN回员工表,也就是要同表自叉乘,需要起个别名。在WHERE中先写上JOIN的条件,和最终我们希望的条件,一个国籍是中国,一个国籍是美国。整个句子要看一会才能明白。

这是我的招聘考题,通过率不到一半。许多还都是有两三年工作经验的。不到一半的通过率,可想而知它还是有一定难度的。

那么,为什么不能这样写呢?我还是说员工表,美国员工好理解,但是中国经理这件事我把它写成这样,就是上面红色的部分,这个字段稍复杂一点,有子属性,子属性又有子属性,但那一小段语句并不难理解,也就是部门的经理的国籍是中国。

也就是说,我们要:

SQL不是这样理解外键的,而我们这样去理解外键就容易多了,外键指向的属性可以被直接引用,也可以多层引用,这样就会简单得多,把外键看成一种属性,把JOIN这个运算不再简单地理解成笛卡尔积加过滤。这是第一种情况。

第二种情况是同维表等同,这个比较简单。

这两个1:1的表,主键相同,在数据库设计中经常会有这种情况,许多字段都放在一个表里太宽,还会造成空间冗余浪费,导致性能下降,因此常常会分到多个主键相同的同维表中。

现在我们要做联合查询,这又得做JOIN。

我们希望能把它看成同一个表,直接这么写

还是看红色的部分,同维表的字段可以在任何一个表中随意访问。也就是

这样也会让关联变得简单一些,不必再理解这种JOIN。

第三种情况,按维汇总对齐

这里有合同表和回款表,我们希望按日期统计合同额与回款额,用SQL写出来是这样的:

先把每个表分组汇总后再JOIN起来,如果偷懒不用子查询先JOIN后GROUP,那结果是错误的,统计值会变多。这个问题必须使用子查询。

能不能再简单一些呢?我们可以写成这样

注意红色的部分,我们只要把两个表分别按日期对齐就行,这两个表之间并没有直接关联。我们不必关心表间关联,各自独立计算各自的数据就可以了。

如果这个事情再扯到外键的事就会更复杂,比如

我们希望按地区统计销售员人数和合同额,用SQL写出来是这样:

这个子查询中要套着带JOIN的GROUP,更复杂了。

类似地,按我们刚才的写法结合第一种情况的外键处理方法,这个查询可以写成这样:

红色部分中出现了子属性,但整个句子仍然很简单。

这一条总结起来就是:

三种常用的JOIN以及简化方式说完了,这样理解数据关联有什么用处呢?

一个应用就是用来实现自助报表,或者OLAP。

我是做报表工具出身的,用户经常会向我们提出业务人员自己做报表的需求,自助报表的关键在于让用户把需要的数据取出来,而取数的关键又在于解决多表关联,就如前面所说,有意义的查询大多是多表关联的。把蜘蛛网式的表间关联呈现给业务用户,有时候还需要自关联,要用别名,我想大多数业务人员会晕掉的。

传统的OLAP工具是如何解决多表关联问题呢?

一般都是采用事先建模的方式,要预测用户可能以哪种关联方式查看数据表,事先将关联做成物理宽表或者逻辑视图,这样用户看到就是一个单表了。这是典型的按需建模,也就是有了新的关联需求时就需要再建一个视图或宽表,而建模需要技术人员完成,这个过程的周期就会很长。

有些传统OLAP工具能够根据维的类型自动关联,但解决得不彻底,当同一个表中出现多个同维字段时就会对不上了,比如一个学生有出生地和入学地,都是地区维度,就不知道该怎么自动对应了。对于自关联的处理也很麻烦,需要事先约定指向路径,其实还是按需建模。

如果关系代数对关联的处理是我们上面简化的那样,就不需要这么麻烦了,那三种情况能够描述的关联占了大多数,对自助报表和OLAP业务几乎是全部了,这类关联只要一次性建模就可以了。

也就是说,能达到这样的效果:

我们按照上述模型开发了一个语法翻译引擎,把上面那种简单语法翻译成完整的SQL交由数据库去执行。在这个基础上,配上一个界面就可以方便地实现自助报表。

这是选择数据项的界面,不需要涉及到表的概念,只是数据项稍复杂些,有子数据项,数据项的组织呈树状,不象平常的数据字典是线状的,这个树的层次关系就体现了表的外键关系。

做报表时,我只要把需要的数据项往表里拽就行了。

这和普通单表取数没太大区别,无非就是字段有多层子属性。

这个界面生成上面看到的那些简单语法是很容易的,然后再翻译成SQL执行就可以了。

在做汇总报表时也很简单,把汇总用的维度选定后,仍然是把要统计的数据项往表里拖就可以了。

你不必关心这些数据项来自哪些数据表,这些数据表之间有什么关联。

这样看待关联还有个好处,就是数据库的结构更清晰

这是我们平常的ER图,网状结构的,表和表之间都有关系,表多了就很乱,表间耦合度高,加删表时可能牵一发动全身。

而用刚才那种方式理解表间关联,看到的结构是这样一种总线式的

表和表之间没有直接关联,互相没有耦合,表只和中间的维度关联,增加删除表时不影响其它表。

需要说明的是,结构图中连线数量并不因为样式变了而变少,这是数据本身的关联特性决定的,但后一种画法会让结构更清晰了。

这种关联机制在性能方面也有优势。大家知道SQL做分布式计算是很难的,而难就难在JOIN,其它GROUP、WHERE都很容易分布并行计算。但如果把JOIN看成刚才说的那几种情况,分布式计算时就会容易许多。

在这几种JOIN中,同维对齐的表可以按同样规则分段存储,这样了就很容易分布了;外键指向的维表不能同步分段,但一般维表会较小一些,可以在每台机器都存储一份,甚至可以在内存中放下,这样可以用冗余数据换取性能,大的事实表再分段存放,这时JOIN计算几乎不需要发生跨机关联了。

关系代数不区分这些JOIN类型,必须实现笛卡尔积式的JOIN运算,分布式计算就困难的多,一般的办法是将表按键值HASH到不同节点机上再计算,造成大量的网络传输。

不同的JOIN还可以用不同的方法去优化。同维对齐可以事先排序再用归并算法,这个复杂度要比HASH JOIN小得多。外键连接,如果内存可放下则可用指针去做,外存也可以事先转换成序号直接快速定位。

当然实际实现起来事还不少。我们目前只做个内存实验。用JAVA的计算与ORACLE对比,采用数据量比内存小,这样ORACLE会把数据都缓存到内存中。

我们不必看JAVA和ORACLE的对比,技术不一样,一个纯内存,一个有外存。我们只看两者比值的变化,无连接运算的单表,耗时差不多。五个表JOIN时,JAVA用指针连接的方式比ORACLE的HASH JOIN快了一倍多。这种技术放在外存上也会有优势。

下面说序运算和离散化的问题。

人对有序计算是天然关心的。因为人最关心变化的东西,如果一个东西老不变,他不关心。这个东西变了,比昨天怎么样,比去年怎么样,他就会很关心,这个时候序运算就很重要了。

但是关系代数沿用了数学上的无序集合的概念,导致早期SQL没有办法直接做序运算。其实SQL的运算体系是完备的,它可以生成序号再去JOIN来实现序运算。

比如计算一只股票涨了多少钱,用早期SQL写出来是这样的

对于一个用C++或JAVA的程序员会觉得这不可思议,这个运算怎么要写得这么麻烦,但它就是这样。先用一个子查询生成序号,然后再拿这个临时表跟自己JOIN,用序号跟另一个序号加1连接,也就是某天跟昨天连接起来了,然后才能算出比上期。

这个设计,说它反人类都不过分。

2003年ANSI做了一个新SQL标准,增加了窗口函数,比上期运算不再反人类了,写起来就简单多了

窗口函数允许引用相邻记录的信息,这就好多了。但不是所有数据库对窗口函数的支持都够好,ORACLE做得比较好,而业界很流行的开源数据库MySQL就不支持。

SQL无序还表现在它的计算过程无序。过程无序其实有个好处,就是容易并行,计算之间没有依赖性。但有些计算如果可以控制过程会简单许多。

比如我们想计算一支股票最长连续上涨了多少天,思路很简单,先清0,涨一天加一,不涨了再清零,最后取最大的那个数。

但SQL不是这么思维的:

这个句子我想了很久才搞出来,它的原理是把交易日分组,涨了就和前一天是同一组,跌了就换一个组,然后分组汇总计数找出最大的组。对于无序的SQL要凑出这个组就需要几层嵌套再加累积才能搞出来。

这也是我的招聘考题,但是我没有指望应聘者能短时间内做出来,而是写出这个句子问应聘者它想算什么,解释它的原理。

有序运算还和离散性相关,SQL有集合的概念,记录、对象的概念都有,但是关系代数没有设计游离记录的表示方式,也就是缺乏离散性,这又会造成麻烦。

比如我要找年龄最大的人,而不是最大的年龄:

SQL要用一个子查询,先把最大的年龄的找出来,再找谁是这个年龄的,这是SQL的标准写法。

再看一个稍复杂的例子,我要计算股价最高的那三天的平均涨幅:

类似地,SQL要先算出股价最高的那三天,再把每一天的涨幅算出来,再挑出日期在刚才那些日子里的交易,这样绕一下。其实我找到最高的那三天,再找每一天的前一天,只要知道这六天数据就可以了。

缺乏离散性,分组运算就要强制聚合,每次分组完了就要聚合,分组结果就不可复用了。我们有时候分组并不是要聚合结果,而是要分组后的子集。

我们再看例子,有哪些股票连涨了三天,其实这个蛮实用的,我看历史上涨了三天第四天还涨的股票比例有多高,可以指导我买股票。

SQL这个算法又比较绕。

常归思路是先按股票先分组,运算就简化成一支股票的事情了,但SQL的分组不可复用,你必须在一个句子中把分组和序运算一起解决,到处要加上partition,而且算连涨三天,你要跟昨天、前天比,想算连涨第四天时,你就要写四行,连涨N天就不知道怎么做了。

关系代数强调集合性,但缺乏离散性,离散性和有序运算又是结合在一起的。显然集合性也很重要,我们就需要一个既有离散性又有集合性的运算模型,它可以很好地支持批量的有序计算。

其实在数据库发明之前的那些高级语言的离散性都比较好,说白了就是数组,象C++,JAVA都有很好的离散性。

但高级语言的集合性又不好,集合性要求动态语言,因为经常需要针对集合的每个成员做同样的运算,这些运算在编译型的高级语言中要表现为函数指针,用起来很不方便,而在SQL这类解释语言中表现为表达式,很方便。

我们希望把这两点结合起来,在关系代数中引入离散性及有序集合。数据的运算不仅跟数据本身有关,还和它在集合中的位置有关,你设计的这个形式语言要能够让你引用和描述数据以及它的位置,它的前一个、后一个等等。我把这种运算称为离散集合运算。

有了离散集合的运算,刚才那些问题都很好容易解决了。

这是我们做的一个程序设计语言,这里我没有学SQL的风格让它像英语,还是把它形式化,反正是程序人员使用。

在这个体系下,上面那些运算都不困难,而且很直观,其实按照自然思维去写就完了。自己减自己的上一天就是涨幅;连涨了多少天,大了+1,否则就清零。我找到最高的三天的位置,对照位置算涨幅。有序离散性和集合运算结合起来,会让很多运算写起来轻松得多。

不只是写起来轻松,有序化还有很多别的应用。

我们可以提供按位置分组的功能,或者按相邻数据分组,SQL只有等值分组,相等的值被分到一个组,但是我们有时需要按位置分组。比如一段日志文本,每三行一个单位,如果用SQL处理就比较头疼,而要是有按照位置分组,按行号除以三分组就可以得到每个完整的单位去处理。

还有的是不定行的,每一段单位日志会有一个边界标志。这个时候我们需要按照相邻的数据来分组,原始数据本身是有序的,我们走到一个边界标志就新分出一个组,支持有序运算时我能比较方便能定义出这种分组方式。同时有了离散性,我能获得每个组对应的子集,我并不是为了汇总,我是把子集合留着再做复杂运算。

我们经常要做用户行为分析,用户行为是个很复杂的事情。比如我想算一下哪些用户最近三周每周都有连续三天在线,这个运算挺复杂的,不太容易在数据库里面做出来,你要把数据读出来再写一个程序来算。大数据的时候,全读内存又装不下,但是如果没有有序的分组机制,就很难保证每次顺序地读入一个组的数据。用SQL原则上要遍历所有数据,加上索引会好很多,但还是要满表找。

有了有序分组机制后,可以事先把数据按用户排序,然后每次读入一组进行复杂运算,这种机制还容易实现并行计算,每个任务从数据某个点开始分配,计算某一片数据。传统的SQL体系很难高性能地做到这样。

顺便说一句,HADOOP的文件拆分方案也不支持有序分组拆分,处理不定行记录时很难并行。

另外关于连接运算的优化,在前面讲关联性时也说过。有序时可以用归并算法来做连接外键可以用指针或序号的办法优化。做分析时数据仓库的数据是只读的,可以事先把外键准备成序号。

下面说一下交互运算的问题。

说到交互运算,我们先复习一下OLAP这个概念。这个词字面的意思是在线分析,但在线分析实际上是在做什么事呢?

业务用户看到了一些现象,他会猜是什么原因,猜完了以后开始拿着历史数据去看,看我猜的对不对。销售增长,可能是某个销售特别强,我要用数据去验证,销售量降低了,可能哪发灾害了,我要拿数据验证。猜对了,可能得到一个有益的结论,猜错了,我就再换一个猜测。OLAP从字面上看应当是这样的过程。

但是现在OLAP这个词已经被严重狭义化了。一说到OLAP就指转来转去的那个CUBE,旋转、切片这些。严格地说,这个操作谈不上分析,它就没有过程,它只能算是分析结果的灵活呈现。

而分析的过程,我要看上一步的结果才知道下一步的动作,你不可能事先设计一个端到端的路径。你让业务人员自己做,他不会自己建模,需要的运算自己不会做,他就只能找技术人员,很多用户机构大一点的时候,象移动、银行,他找技术人员帮忙的周期是以星期为单位的,这就没法玩了,等算出来这个结论时市场已经不需要了。

除非你能找到既懂业务、又懂技术的牛人,但是这种人很少、也很贵。我们最好还是让业务人员能自己做很多运算。

从这个意义上讲,Excel才是最好的OLAP工具,比Cognos,BO这些都好用得多。Excel像计算器一样的操作,我做一步,得到结果再看下一步怎么做,这才是真正的OLAP工具,Excel的缺点无非就是能支撑的数据量少一点,目前版本的极限是100万行,但灵活分析时用户经常也没那么大数据量。

传统要建模的OLAP体系象笨重的火车模式,跑得快拉得多,但太死板。而用户更需要灵活的汽车模式,我不需要拉那么多跑那么快,我需要想去哪就去哪。

我们来仔细看Excel,我不管它的格式能力,是不是能做一个好看的报表出来,我只关心它对于数据的运算能力。

Excel的运算模型可以理解成关系代数的变种,它有天然的有序性和离散性,关联性弱一些,你要把两个表JOIN起来,要用Lookup函数去写,很麻烦。不过这不是今天的讨论重点,就不展开了。

Excel的基本模型是单层的表,这个模型对分组的运算不封闭。大家用过Excle都有这个体会,你让它做一下分组,它就会变成另外一个东西了,你不能再自由地对分组后各个层次执行单层表的动作。

比如我想对这样的分层组表算一个占比,公式会很难填。

Excel的$符号只能管一层,你用D36除以D4,公式拖到下一个格子就不对了,换到下一组就更没戏了,只能一个个手工硬写,这没法接受了。其它动作,比如针对分组层的再排序再过滤都难办。

Excel背后的代数体系对分组运算没有封闭性。我们需要设计一个对分组运算封闭的代数,这样就可以支持多层表格,分组的结果仍然是这种数据类型,这样就可以连续地操作了。

这是我们基于这种思路开发的一个桌面工具

这个产品在外貌上很象Excel,不同的是它的模型就支持多层表格,从表的左边可以看到每行的有层次信息,这样它可以自动处理分组的层次,各个层次等同处理。

我要想算占比,填入一个格子的公式,其他的同地位的格子都会正确复制,比如这里面要算D35除以D2,这个公式复制到下一组就会自动变成D413除以D325,它会把事情搞对。

我们将这个表格代数和数的运算做一个类比。

我们在整数范围能可以自由地做加减乘,结果还是整数,但是不能做除法,一除就可能出去了,不再是整数了,整数对除法不封闭,除法在整数集合内是不可逆的。

如果我们把数据的范围扩大到有理数,它对除法运算就封闭了,我就可以随意连续运算了。但我要重新定义针对有理数的加减乘除运算规则,这些运算和整数不一样了,比整数的情况要复杂。

类似地,在Excel这种单层模型中,我们可以自由地做过滤、排序、加计算列等运算,但是一做分组就出了范围,不能继续做下去了,它对分组运算不封闭。

凑巧的是,分组运算在关系代数中恰好就被称为除法。

严格来讲关系代数对除法也是封闭的,但它只保留了聚合部分,相当于在整数下定义的除法只保留商的整数部分,这样的运算是不可逆的,你做一下就回不来了,但我们在交互运算中需要可逆的分组。

我们可以设计出对分组运算封闭且可逆的多层表格模型,即分组之后的表格仍然属于这种数据类型,这样各种运算就可以连续执行,复杂一些交互运算也就可行了。

同样地,需要重新定义在多层表格下原来那些单层表格的运算的规则,如排序、过滤、填计算列等。

实际应用中还需要更复杂的多个多层表格连接合并等运算,这些内容太多,就不细说了。

我们来看两个例子,在多层表格模型下如何完成运算。

原始数据

问题和计算思路:

这个问题需要分组后实现组内排序和计算列,然后再对分组汇总层次做排序。

按股票代码分组后计算每支股票连涨的情况。

计算出每组最长上涨天数后再在分组层次排序。

第二个问题,原始数据:

问题和思路

这里的麻烦在于,在第5步需要打掉分组再变成一个单层表格,即要求运算体系对分组是可逆的。Excel对分组运算不可逆,这个过程就操作不下去。

计算出每科目前十名之后。

打掉科目分组,再按学生重新分组,即可得到结果。

有这样一个多层表格模型,就可以让交互的数据运算更方便地做下去。这就向真正的OLAP迈进了一步。

最后再简单说一下云计算的数据组织问题。

云数据有这样几个特征:

第一,多样性。云计算要解决多租户的问题,显然不同用户的数据结构经常是不一样的,即使同一个用户、同一块业务,数据结构在不同地域、不同时期都会不一样。象我们这样一个小公司的财务系统,数据结构都年年在变,今年没有这种销售提成,明年有了,就要增加一些字段或表来处理。

数据的多样性其实是很本质的需求,世界就是这么复杂。多样性在关系数据库的时代也存在。只不过关系数据库的时代,因为应用范围比较小,一般只在一个机构甚至一个局部,这个矛盾还不是特别严重,能对付过去。但是到了云时代就不容易对付了。你面临的用户五花八门,想在云上给各种用户提供持续的服务,这个事就避不开了。

第二,分离性。不同时段、不同地方的数据是分开的,数据管理也需要联邦制,而不是单一制。比如说北京的数据,下面有海淀、朝阳这些,但是你要换成河北省,中间多了一层石家庄、保定这些地级市,层次不一样了,非要把他们搞成一样的数据结构就会别扭的。但关系代数在理论层面就要求单一性,数据结构就会很别扭。

分离性能带来多样性,但不只是多样性。有时候即使数据不多样也需要分离。比如北京的某种数据特别多,我要给它建索引,到了上海这类数据不多,就不需要建索引。

关系数据理论上没有这种机制,只能在工程上去绕,实际上很多数据库厂家都会想办法做数据分区,但不从概念上支持会导致许多实施层面上的事情很难办。

第三,易计算性。这是最关键的一点。

把数据存起来不是问题,我们还要计算,如果不能计算,这个数据没有意义。

我们需要多样和分离的数据能够合在一起随意计算,这里重要的是要支持批量数据表的高阶集合运算,所谓高阶集合,就是集合的集合,我们面对多样性数据时会大量碰到这种高阶集合的运算。

关系代数所做的运算只涉及有限的几个表,你要明确写出来这个运算是针对哪几个表,如果需要运算的表也构成一个集合,那就在关系代数中就搞不出来了。

你很难想象在一个数据库里面有几万甚至几百万个表,当然我听说北京移动他们就有上万个表,历史积累下来,谁也不敢删这些表。关系数据库肯定不会提倡你在数据库中搞几万个表,但多样性的需求是客观存在的,现实中真地会有这么多种数据结构。如果我们把表也作为一种操作数据,提供高阶集合运算,可以针对这几万个表这样的集合做运算,这个问题就不再是问题。

当前几种主要技术中,SQL的易计算性还是不错的。这几年比较时髦的NoSQL对多样性的支持更好,但严重牺牲了易计算,分离性也一般。SQL的易计算好,但是分离性和多样性比较差。直接操作文件系统,比如Hadoop这种东西,多样性、分离性都好,但是几乎没有什么易计算性。

我们希望设计一个这三个指标都好的东西,这样才能够适合云计算,缺一个都很麻烦。

我的设计想法是模拟日常的纸张文档。

基本的数据单元用于保证多样性,数据结构附在这个数据单元中,不同数据单元可以有不同的数据结构,还可以有子数据结构,比如一个人除了姓名、性别这些外,还可能有家庭成员、工作履历等,可以是一条,也可以多条,都放在一起。这种数据我称为超结构化数据,这种存储试的坏处是运算效率会低一点,不过OITP这种业务一般单个任务涉及数据量并不大,多样性带来的性能损失对现代计算机来讲还是可以容忍的。

采用树形目录的机制存储数据单元来保证分离性,就象平常大文件夹套小文件夹那样保管纸张。关系数据库实际是一种线状结构,所有表排成一条线,即使考虑模式概念,也最多有两层。

然后,这里的关键是,我们要求在树的目录上带有信息,实际上我们日常存放纸文档的时候就是这么做的,我在文件夹上写了财务部,里面的纸张就可以不再写财务部了。这样的好处是可以随意变动层次,或者搬动数据。比如北京数据就是两层,到了河北就变成三层,中间多了一个地级市。

纸张的机制用于存储是没有问题的,但纸张几乎没有任何计算能力。而我们的任务就是要加上这个能力。

这就要用到刚才说的高阶集合运算,要在这些多样的树形分离方式存储的数据单元上定义批量的数据计算,我一次可以算多个目录,包括多个数据单元,每一个数据单元不止一个记录,就像一个小表一样,我都可以计算。

分离性可以使数据之间耦合度降低,我只算北京海淀区的数据时,你把CPU累死,山东人民根本不在乎,完全感觉不到。这两个区域的数据是无关的。既可以统一计算,又是分离的。

这方面的研究我们现在也还比较初级,我们现在基于普通的文件系统并结合前面提到的自己开发的程序设计语言实现了一个数据库的原型,逻辑上多样性、分离性和易计算性都达到了,但计算效率还比较差,尚不能达到实用阶段,下面会进一步做工程上的优化。

今天讲了关系代数的这些问题,并针对每个问题也都大体提出来解决方案的设想及尝试性的产品,但现在的方案还是针对每个问题分别处理的,比如解决关联描述问题的方案中没去管多层表格的交互问题,目前我们还没能设计一个大一统的代数体系把所有问题放在一个框架内解决,这是我希望能在今年几年内能做到的事情。

最后,第一次做这么大范围交流,我想借这个机会诠释一下我们公司的这句口号,让大家更多的了解润乾公司。

我们希望推动的是应用的进步,今天讲的内容看起来很理论,但我们并不是做纯理论研究的,搞理论是为了让它能够应用,必须能够工程化才有意义。

另外,我们推动应用进步是靠技术,而不是靠资金、管理、商业模式等别的东西,那些我们都不擅长;最关键的,这个技术必须是创新的,拥有了核心技术,并且不断推陈出新,否定自我,才能够在市场中不断前进。

今天就报告这些内容,谢谢大家!

编辑:卢苗苗

原文发布于微信公众号 - 数据派THU(DatapiTHU)

原文发表时间:2017-03-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码神联盟

语音识别 | Java 实现 AI 人工智能技术 - 语音识别功能

说到语音识别、语音翻译、图像识别、人脸识别等等,现在已经非常非常非常普及了,看过‘最强大脑’的朋友,也应该对‘小度’这个机器人有所了解,战胜国际顶尖的‘大脑’-...

2.5K60
来自专栏java 成神之路

HashMap实现中文分词器

42470
来自专栏racaljk

当我们谈论计算机科学

下午偶有所悟,特作此文防止青年痴呆。 这学期的学习算是走了一半计算机科学概论。广度的学习通常会被指责为广而不精,但对我而言这是毫无意义的,因为 ...

11440
来自专栏牛客网

美图-北京商业部 - 测试工程师实习生面经

10800
来自专栏数据派THU

独家 | 带你入门比Python更高效的Numpy(附代码)

向量化技巧对于数据科学家来说是相当熟知的,并且常用于编程中,以加速整体数据转换,其中简单的数学变化通过可迭代对象(例如列表)执行。未受到重视的是,把有一定规模的...

12830
来自专栏web前端教室

坚持学一年很难,那坚持一周怎么样?[先行者课程-时间倒数-Data对象]

时间是线性的,所以依附于时间的事情也是线性发展的。例如学js,谁能一下学成高手?谁有js学习秘籍?高手只能跟你装b,却不能带你起飞。 这世界我看只有砖与狗粮是真...

22090
来自专栏人工智能头条

知识图谱系列 | 知识图谱的前世今生与RDF的实践

【人工智能头条导读】本文是我们知识图谱系列的第二篇文章,希望人工智能头条为大家准备的文章对大家的学习有更多的帮助。

75120
来自专栏数据派THU

一文读懂PyTorch张量基础(附代码)

本文介绍了PyTorch Tensor最基础的知识以及如何跟Numpy的ndarray互相转换。

11930
来自专栏牛客网

双非硕士普通的公司的普通面经> 中汇信息 软件开发> 上海银行 IT开发> 上汽技术 Java开发> 荣数信息 Java开发> 平安养老险 Java开发小建议

双非硕士,计算机科班,除了成绩几乎一无是处,没实际工程没实习甚至秋招前没有学过Java基础。 坐标魔都且只考虑金融IT方向,牛客上这方面的公司多数仅出现于off...

64890
来自专栏牛客网

头条测试实习岗面试

19740

扫码关注云+社区

领取腾讯云代金券