离散数据集论文附录
以下是附录
我们在摘要中说，离散数据集的设计目标是为了解决关系代数的各种问题。但前面的文字仅是在定义离散数据集的数据类型及其上的运算，并没有涉及背后的原因。仅仅阅读上面的正文，很难理解为什么要把计算模型设计成这样。
为此，我们在这里增补一些内容来解释离散数据集与关系代数之间的关键差异，从而理解离散数据集的优势。
人们在关系代数基础上发展了程序语言 SQL，我们也基于离散数据集模型开发了程序语言，命名为 SPL（Structured Process Language）。有时我们将用 SQL 和 SPL 的代码示例以体现关系代数和离散数据集的差异。
1. 普遍集合
关系代数中有集合的概念，但只处理由记录（也就是关系，这里我们用偏工程的术语，更易于理解）构成的集合（即表）。
离散数据集的集合概念更为普遍，可以处理任何数据构成的集合，即序列。这些集合，无论是不是由记录构成，都能执行一些共同运算，如聚合、过滤等。
而在关系代数中，单列数值构成的集合要理解成单字段的数据表，显得有些累赘。
特别地，离散数据集还支持由集合构成的集合，这样才能实现真正的分组。
2. 游离记录
离散数据集中的记录是一种基本数据类型，它可以不依赖于数据表而独立存在。数据表是记录构成的集合，而构成某个数据表的记录还可以用于构成其它数据表（排列）。比如过滤运算就是用原数据表中满足条件的记录构成新数据表，这样，无论空间占用还是运算性能都更有优势。
关系代数没有可运算的数据类型来表示记录，单记录实际上是只有一行的数据表，不同数据表中的记录也不能共享。比如，过滤运算时会复制出新记录来构成新数据表，空间和时间成本都变大。
特别地，因为有游离记录，离散数据集允许记录的字段取值是某个记录，这样可以更方便地实现外键连接。
3. 有序性
关系代数是基于无序集合设计的，集合成员没有序号的概念，也没有提供定位计算以及相邻引用的机制。SQL 实践时在工程上做了一些局部完善，使得现代 SQL 能方便地进行一部分有序运算。
离散数据集中的集合是有序的，集合成员都有序号的概念，可以用序号访问成员，并定义了定位运算以返回成员在集合中的序号。离散数据集提供了 [] 符号以在集合运算中实现相邻引用，并支持针对集合中某个序号位置进行计算。
有序运算很常见，却一直是 SQL 的困难问题，即使在有了窗口函数后仍然很繁琐；SPL 则大大改善了这个局面。
例 1：计算股价最高三天的涨幅
SQL：即使有窗口函数，仍然要复杂动作才能实现定位计算
SELECT date, price, seq, rate
FROM (
SELECT date, price, seq,
price/LAG(price,1) OVER (ORDER BY date ASC) rate
FROM (
SELECT date, price,
ROW_NUMBER() OVER (ORDER BY price DESC) seq
FROM stock ) )
WHERE seq<=3
SPL：有序集合支持下的定位计算很简单
T=stock.sort(date)
P=T.ptop(3,price)
T.calc(P,price/price[-1]-1)
例 2：计算一支股票最长连续上涨了多少天？
SQL：没有方便的相邻引用机制，要转换成复杂的分组问题
SELECT MAX(ContinuousDays)
FROM (
SELECT COUNT(*) ContinuousDays
FROM (
SELECT SUM(RisingFlag) OVER (ORDER BY date) NoRisingDays
FROM (
SELECT date,
CASE WHEN price>LAG(price) OVER (ORDER BY date) THEN 0
ELSE 1 END RisingFlag
FROM stock ) )
GROUP BY NoRisingDays )
SPL：有了相邻引用和迭代函数，很容易按自然思维实现
n=0
stock.sort(date).max(if(price>price[-1],n+1,0))
4. 离散性与集合化
关系代数中定义了丰富的集合运算，即能将集合作为整体参加运算，比如聚合、分组等。这是 SQL 比 Java 等高级语言更为方便的地方。
但关系代数的离散性非常差，没有游离记录。而 Java 等高级语言在这方面则没有问题。
离散数据集则相当于将离散性和集合化结合起来了，既有集合数据类型及相关的运算，也有集合成员游离在集合之外单独运算或再组成其它集合。可以说 SPL 集中了 SQL 和 Java 两者的优势。
有序运算是典型的离散性与集合化的结合场景。次序的概念只有在集合中才有意义，单个成员无所谓次序，这里体现了集合化；而有序计算又需要针对某个成员及其相邻成员进行计算，需要离散性。
在离散性的支持下才能获得更彻底的集合化，才能解决诸如有序计算类型的问题。
离散数据集是即有离散性又有集合性的代数体系，关系代数只有集合性。
5. 分组理解
分组运算的本意是将一个大集合按某种规则拆成若干个子集合，关系代数中没有数据类型能够表示集合的集合，于是强迫在分组后做聚合运算。
离散数据集中允许集合的集合，可以表示合理的分组运算结果，分组和分组后的聚合被拆分成相互独立的两步运算，这样可以针对分组子集再进行更复杂的运算。
关系代数中只有一种等值分组，即按分组键值划分集合，等值分组是个完全划分。
离散数据集认为任何拆分大集合的方法都是分组运算，除了常规的等值分组外，还提供了与有序性结合的有序分组，以及可能得到不完全划分结果的对位分组。
基于有序分组运算，上述例 2 的 SQL 实现思路用 SPL 写出来也更为简单：
stock.sort(date).group@i(price>price[-1]).max(~.len())
6. 聚合理解
关系代数中没有显式的集合数据类型，聚合计算的结果都是单值，分组后的聚合运算也是这样，只有 SUM、COUNT、MAX、MIN 等几种。特别地，关系代数无法把 TOPN 运算看成是聚合，针对全集的 TOPN 只能在输出结果集时排序后取前 N 条，而针对分组子集则很难做到 TOPN，需要转变思路拼出序号才能完成。
离散数据集提倡普遍集合，聚合运算的结果不一定是单值，仍然可能是个集合。在离散数据集中，TOPN 运算和 SUM、COUNT 这些是地位等同的，即可以针对全集也可以针对分组子集。
例 3：选出每天价格最高的三支股票
SQL：先要计算出序号再选出
SELECT *
FROM (
SELECT *,
ROW_NUMBER() OVER (ORDER BY price DESC PARTITION BY date) seq
FROM stock )
WHERE seq<=3
SPL：把 TOPN 当作聚合运算直接分组汇总
stock.groups(date;top(3;-price):top3).conj(top3)
SPL 把 TOPN 理解成聚合运算后，在工程实现时还可以避免全量数据的排序，从而获得高性能。而 SQL 的 TOPN 总是伴随 ORDER BY 动作，理论上需要大排序才能实现，需要寄希望于数据库在工程实现时做优化。
7. 连接理解
关系代数中，连接运算被定义为笛卡尔积再过滤，其中没有约定过滤条件的要求，这样，理论上只要运算结果是笛卡尔积的子集，都可以认为是连接运算。
离散数据集将连接运算分成了三种情况：
1) 外键连接
表 A 的某些字段与表 B 的主键关联，B 表称为 A 的外键表，A 表称为事实表。
2) 同维连接
表 A 的主键与表 B 的主键，A 表和 B 表互称为同维表。
3) 主子连接
表 A 的主键与表 B 的主键的部分字段关联，A 表称为 B 的主表，B 表称为 A 的子表。
同维连接和主子连接可以再合并称为主键连接。
可以看出，离散数据集中定义的连接运算有这样的特点：
1) 只有等值连接（连接条件是关联字段相等）
2) 都会和某个表的主键相关
在实际应用过程中，绝大多数连接运算都是等值连接，而且有业务意义的连接也几乎都和主键相关，和主键（指逻辑上的）无关的连接运算，通常会是个错误，因为会导致多对多的关联效果。
离散数据集也设计了笛卡尔积后再过滤的运算，以处理极少数用上述定义不能覆盖的场景，但并不把这种运算看成是常规的连接。
离散数据集对连接运算进行改造后，会获得一些好处。
把外键连接和主键连接区分开，可以更清晰看出数据表之间的关系结构。外键表通常是用于进一步说明某些字段的详细信息，在理解事实表时可以先忽略它。外键连接和主子连接虽然都可能有一对多的情况，但对于理解业务时的地位并不等同。
这样定义的连接剔除了多对多的情况，在处理较多表关联时，不会因漏写某个关联条件而产生多对多的错误逻辑（常常可能把数据库跑死）。
在游离记录的支持下，可以把事实表中的字段直接赋值为外键表的相应记录，这样书写起来要更直观且不易出错。
例 4：取出部门经理是中国人的美国人员工
SQL：关联关系不直观，同表两次连接要起别名
SELECT A.* FROM employee A
JOIN department B ON A.department=B.id
JOIN employee C ON B.manager=C.id
WHERE A.nation='US' AND C.nation='China'
SPL：在建立外键关系之后，关联条件很直观
employee.switch(department,department)
department.switch(manager,employee)
// 上面动作可以在加载数据时做好，实际查询只有下面一句
employee.select(nation=="US" && department.manager.nation="China")
离散数据集的连接定义，还有在性能优化上的巨大优势，我们会在后面再谈到。
关系代数对连接的定义很简单，好处是可以涉及到非常广泛的范围，但同时也会缺失一些关键特征，而无法利用这些特征简化代码书写和实现性能优化。
8. 外存计算
关系代数是个纯数学层面的理论体系，没有考虑内存和外存的区别。
离散数据集则考虑了工程实现的方案，为外存计算做了专门的设计。
离散数据集抽象了游标对象，用于处理只能顺序访问不能随机访问的数据，这符合不特定存储设备上的外部数据的特征。提出并利用导出游标的框架，将大多数游标运算的与对应的序表运算设计得非常相似，尽量提高外存计算的透明性。基于游标运算编写的计算逻辑，可以很轻松地应用到这些外部存储的数据上。
离散数据集中还设计了提供有限随机访问能力的组表用于外部存储，这是根据硬盘这种最常见存储设备的特征设计的。同样地，基于组表运算编写的计算逻辑，也很容易在硬盘上高速实现。
附表机制允许一个组表同时存储多个关联的数据表。主键连接的关系通常在数据结构设计时就已经确定，不会在计算过程中临时指定表与关联字段。将主键连接的若干表事先存储在一起，相当于预先关联，可以减少存储量及关联计算量，获得更优性能。这也是利用了离散数据集对连接运算的理解，外键连接情况就不可以事先关联。
9. 有序下的高性能
离散数据集特别强调有序集合，利用有序的特征可以实施很多高性能算法。这是基于无序集合的关系代数无能为力的，只能寄希望于工程上的优化。
这里简要罗列一些利用有序特征后可以实施的低复杂度运算。
1)
组表对键有序，相当于天然有一个索引。对键字段的过滤经常可以快速定位，以减少外存遍历量。随机按键值取数时也可以用二分法定位，在同时针对多个键值取数时还能重复利用索引信息。
2)
通常的分组运算是用 HASH 算法实现的，如果我们确定地知道数据对分组键值有序，则可以只做相邻对比，避免计算 HASH 值，也不会有 HASH 冲突的问题，而且非常容易并行。
3)
组表对键有序，两个大组表之间主健连接可以执行更高性能的归并算法，只要对数据遍历一次，不必缓存，对内存占用很小；而传统的 HASH 分堆方法不仅比较复杂度高，需要较大内存并做外部缓存，还可能因 HASH 函数不当而造成二次 HASH 再缓存。
键有序的组表，还可以利用分位点拆分成多段，实现并行计算。HASH 算法要实现并行时需要占用较大内存，难以将并行度提高。
若参与连接的某一个组表被过滤后变小，则可以利用键有序的特征，快速定位另一个组表中对应的数据，避免全表遍历。
4)
大组表作为外键表的连接。事实表小时，可以利用外键表有序，快速从中取出关联键值对应的数据实现连接，不需要做 HASH 分堆动作。事实表也很大时，可以将外键表用分位点分成多个逻辑段，再将事实表按逻辑段进行分堆，这样只需要对一个表做分堆，而且分堆过程中不会出现 HASH 分堆时的可能出现的二次分堆，计算复杂度能大幅下降。
其中 3 和 4 利用了离散数据集对连接运算的改造，如果仍然延用关系代数的定义（可能产生多对多），则很难实现这种低复杂的算法。
结语
以上是离散数据集和关系代数的重点差异。在工程实现方面，离散数据集还有一些优势，比如更易于并行、大内存预关联提高外键连接性能等，以及一些在应用时的注意事项，比如怎样保证在数据在物理上有序、如何存储数据以支持随意分段并行等。限于篇幅，我们舍去了这些理论色彩相对较弱的内容，对已写内容也没有做深入的展开解释，不过已经可以从中窥探出这两种代数体系的不同。
我们已经完成了 SPL 的工程实现，在乾学院上还有更多 SPL 的相关资料，包括技术原理以及实践案例，以及与关系数据库上 SQL 在敏捷计算和性能提升方面的差异对比，感兴趣的读者可以前去参考。
本文仅涉及 OLAP 业务，也就是只关注数据计算，对于 OLTP 业务没有提及。可以说当前的离散数据集更适合用于数据仓库的理论基础。事实上，关系代数作为 OLTP 业务的理论基础也有诸多问题，比如无法支持数据结构的多样性、实现事务一致性的成本太高等。我们正在研究，在未来将发布进一步的想法，以解决关系代数处理 OLTP 业务时的困难。
关系代数发布于 50 年前，当时的应用需求、计算机硬件环境和当前相比，都有了巨大的变化。当时非常适应的模型体系现在不适应也是很正常的，从这个意义上讲，离散数据集可以认为是关系代数的一个进化版，但并不是完全向上兼容版。
