SQL 和 SPL 的递归对比

【摘要】
    递归运算是指直接或者间接地调用自身的运算方法。比如我们熟悉的汉诺塔问题,就是典型的递归运算。SQL 和 SPL 是大家比较熟悉的程序语言,本文将探讨对于递归问题,这两种语言的解决方案和基本原理。如何简便快捷的处理递归运算,这里为你全程解析,并提供 SQL 和 SPL 示例代码。SQL 和 SPL 的递归对比

 

一. 递归查找所有引用

 

【例 1】 下面是某公司组织结构表,查询各部门的级别(总部是 1 级,分公司 2 级,依此类推)。

ID

ORG_NAME

PARENT_ID

1

Head Office

0

2

Beijing   Branch Office

1

3

Shanghai   Branch Office

1

4

Chengdu   Branch Office

1

5

Beijing   R&D Center

2

 

SQL的解决方案:

    这个问题需要循环每条记录,递归查找每个机构的所有上级部门。从正常的逻辑来说,我们希望的递归是每条机构记录,都可以通过父机构 ID 找到对应的父记录,以及父记录的父记录,依此类推。但是在 SQL 中,并没有显式的记录、引用这些概念,所以我们只能递归找到有上下级关系的记录,按顺序排列,如下图所示:

..

 

 

在 SQL 中我们可以使用 WITH 语句进行递归查询,语句如下:

 

WITH CTE1 (ID,ORG_NAME,PARENT_ID,O_ID,O_ORG_NAME) AS(

   SELECT

      ID,ORG_NAME,PARENT_ID,ID O_ID,ORG_NAME O_ORG_NAME

   FROM ORGANIZATION

   UNION ALL

   SELECT

      ORG.ID,ORG.ORG_NAME,ORG.PARENT_ID,CTE1.O_ID,CTE1.O_ORG_NAME

   FROM ORGANIZATION ORG

   INNER JOIN CTE1

   ON ORG.ID=CTE1.PARENT_ID

)

SELECT

   O_ID ID,MIN(O_ORG_NAME) ORG_NAME,COUNT(*) "LEVEL"

FROM (

   SELECT

      ID,ORG_NAME,PARENT_ID,O_ID,O_ORG_NAME

   FROM(

      SELECT *

      FROM CTE1

      ORDER BY O_ID,ID

   )

)

GROUP BY O_ID

ORDER BY ID

 

在 ORACLE 中,我们还可以使用 START WITH … CONNECT BY … PRIOR … 进行递归查询,语句如下:

 

SELECT

   MAX(ID) ID, MAX(ORG_NAME) ORG_NAME, COUNT(*) "LEVEL"

FROM (

   SELECT

      ID,ORG_NAME,SUM(ID) OVER (ORDER BY RN) GROUP_ID

   FROM (

      SELECT

         CASE WHEN LAG(PARENT_ID,1) OVER(ORDER BY RN ASC)=0

         OR LAG(PARENT_ID,1) OVER(ORDER BY RN ASC) IS NULL THEN ID

         ELSE NULL END ID,

         CASE WHEN LAG(PARENT_ID,1) OVER(ORDER BY RN ASC)=0

         OR LAG(PARENT_ID,1) OVER(ORDER BY RN ASC) IS NULL THEN ORG_NAME

         ELSE NULL END ORG_NAME,

         RN

      FROM (

         SELECT

            ID,ORG_NAME,PARENT_ID,ROWNUM RN

         FROM ORGANIZATION ORG

         START WITH ORG.PARENT_ID>=0

         CONNECT BY ORG.ID=PRIOR ORG.PARENT_ID

      )

   )

)

GROUP BY GROUP_ID

ORDER BY GROUP_ID

 

我们可以看到,在使用了 START WITH … 语句后,并没有使问题简化。虽然递归查询之后的结果集中,按顺序返回了每个机构的所有上级记录。但是 SQL 中的集合是无序的,我们需要自己加上行号,再通过与相邻行的比较计算出每组的初始位置。另外,SQL 中的 GROUP BY 也只支持等值分组,我们只能再增加分组标记用于分组,如果像 SPL 一样支持条件变化分组(当 PARENT_ID=0 时分组)就能简单许多。

 

对于既不支持 WITH,也没有提供类似 START WITH … 方法的数据库来说,SQL 语句就无法实现递归查询了,只能使用存储过程自己实现递归函数,这里就不做详细说明了。

 

SPL的解决方案:

    在 SPL 中提供了函数 A.prior(F) 用于递归查找引用,默认查找所有引用。


A

1

=T("Organization.txt")

2

>A1.switch(PARENT_ID,A1:ID)

3

=A1.new(ID,ORG_NAME,~.prior(PARENT_ID).len():LEVEL)

A1:从文件中导入组织机构表。

A2:将父机构 ID 外键对象化,转换为相应的父机构记录,实现自连接。

A3:创建由序号、部门名称和级别构成的新表。其中部门级别,是通过函数 A.prior() 递归查找引用记录的层次数量计算得出。

 

    我们可以看到,实现递归问题的 SPL 脚本非常简洁。这是因为 SPL 的递归更加符合逻辑,函数 A.prior() 会返回当前机构的所有父机构的记录组成的集合,接下来无论是计数还是进行其他复杂运算,都能轻松的解决。

 

SPL同样也支持从数据库中读取数据表,比如A1可以改为:


A

1

=connect("db").query("SELECT   * FROM ORGANIZATION")

 

二. 递归查找引用直到指定值

【例 2】 下面是某公司组织结构表,查询北京分公司的下属机构,并列出其上级机构名称,多层的用逗号分隔。

ID

ORG_NAME

PARENT_ID

1

Head   Office

0

2

Beijing   Branch Office

1

3

Shanghai   Branch Office

1

4

Chengdu   Branch Office

1

5

Beijing   R&D Center

2

 

SQL的解决方案:

    经过前面的分析,我们的直观想法是,每个机构在递归查找上级机构时,如果查找到指定值(例如北京分公司)则停止递归并保留当前机构,查找不到的机构则过滤掉。在 SQL 中,我们很难在一次递归中实现这个目标。我们将问题拆分为两步:首先找到北京分公司的所有下级机构,再按照上一个例题的方法,循环递归查找这些机构的所有父机构,查找到北京分公司时停止。SQL 语句如下:

 

WITH CTE1 (ID,ORG_NAME,PARENT_ID) AS(

   SELECT

      ID,ORG_NAME,PARENT_ID

   FROM ORGANIZATION

   WHERE ORG_NAME='Beijing Branch Office'

   UNION ALL

   SELECT

      ORG.ID,ORG.ORG_NAME,ORG.PARENT_ID

   FROM ORGANIZATION ORG

   INNER JOIN CTE1

   ON ORG.PARENT_ID=CTE1.ID

)

,CTE2 (ID,ORG_NAME,PARENT_ID,O_ID,GROUP_NUM) AS(

   SELECT

      ID,ORG_NAME,PARENT_ID,ID O_ID,1 GROUP_NUM

   FROM CTE1

   UNION ALL

   SELECT ORG.ID,ORG.ORG_NAME,ORG.PARENT_ID,

      CTE2.O_ID,CTE2.GROUP_NUM+1 GROUP_NUM

   FROM ORGANIZATION ORG

   INNER JOIN CTE2

   ON ORG.ID=CTE2.PARENT_ID AND

   CTE2.ORG_NAME<>'Beijing Branch Office'

)

SELECT

   MAX(O_ID) ID, MAX(O_ORG_NAME) ORG_NAME,

   MAX(PARENT_NAME) PARENT_NAME

FROM(

   SELECT

      O_ID, O_ORG_NAME,

      WM_CONCAT(ORG_NAME) OVER

      (PARTITION BY O_ID ORDER BY O_ID,GROUP_NUM) PARENT_NAME

   FROM(

      SELECT

         ID,PARENT_ID,O_ID,GROUP_NUM,

         CASE WHEN GROUP_NUM=1 THEN NULL ELSE ORG_NAME END ORG_NAME,

         CASE WHEN GROUP_NUM=1 THEN ORG_NAME ELSE NULL END O_ORG_NAME

      FROM (

         SELECT

            ID,ORG_NAME,PARENT_ID,O_ID,GROUP_NUM,ROWNUM RN

         FROM CTE2

         ORDER BY O_ID,GROUP_NUM

      )

   )

)

GROUP BY O_ID

ORDER BY O_ID

 

在 ORACLE 中,我们还可以使用 START WITH … CONNECT BY … PRIOR … 进行递归查询,语句如下:

 

WITH CTE1 AS (

   SELECT ID,ORG_NAME,PARENT_ID,ROWNUM RN

   FROM ORGANIZATION ORG

   START WITH ORG.ORG_NAME='Beijing Branch Office'

   CONNECT BY ORG.PARENT_ID=PRIOR ORG.ID

)

,CTE2 AS (

   SELECT

      ID,ORG_NAME,PARENT_ID,RN,

      CASE WHEN LAG(ORG_NAME,1) OVER(ORDER BY RN ASC)= 'Beijing Branch Office' OR

      LAG(ORG_NAME,1) OVER(ORDER BY RN ASC) IS NULL THEN 1 ELSE 0 END FLAG

   FROM(

      SELECT ID,ORG_NAME,PARENT_ID,ROWNUM RN

      FROM CTE1

      START WITH 1=1

      CONNECT BY CTE1.ID=PRIOR CTE1.PARENT_ID

   )

)

SELECT

   MAX(ID) ID, MAX(O_ORG_NAME) ORG_NAME,

   MAX(PARENT_NAME) PARENT_NAME

FROM(

   SELECT

      ID,O_ORG_NAME,GROUP_ID,

      WM_CONCAT(ORG_NAME) OVER

      (PARTITION BY GROUP_ID ORDER BY RN) PARENT_NAME

   FROM(

      SELECT

         ID, ORG_NAME, O_ORG_NAME,RN,

         SUM(ID) OVER (ORDER BY RN) GROUP_ID

      FROM(

         SELECT

            PARENT_ID,RN,

            CASE WHEN FLAG=1 THEN NULL ELSE ORG_NAME END ORG_NAME,

            CASE WHEN FLAG=1 THEN ID ELSE NULL END ID,

            CASE WHEN FLAG=1 THEN ORG_NAME ELSE NULL END O_ORG_NAME

         FROM CTE2

      )

   )

)

GROUP BY GROUP_ID

ORDER BY GROUP_ID

 

SPL的解决方案:

    在 SPL 中提供了函数 A.prior(F,r) 用于递归查找引用直到指定值:


A

1

=T("Organization.txt")

2

>A1.switch(PARENT_ID,A1:ID)

3

=A1.select@1(ORG_NAME=="Beijing Branch Office")

4

=A1.new(ID,ORG_NAME,~.prior(PARENT_ID,A3) :PARENT_NAME)

5

=A4.select(PARENT_NAME!=null)

6

=A5.run(PARENT_NAME=PARENT_NAME.(PARENT_ID.ORG_NAME).concat@c())

A1:导入组织机构表

A2:将父机构 ID 外键对象化,转换为相应的父机构记录,实现外键对象化。

A3:选出北京分公司的记录。

A4:创建由序号、部门名称和所有上级部门的记录集合组成的表。

A5:选出父机构不为空的记录,即北京分公司的记录。

A6:循环将父机构名称拼成由逗号分隔的字符串。

 

    SPL的解决方案依然非常简洁,使用北京分公司的记录作为参数,用于在递归时查找引用直到北京分公司记录为止。与 SQL 相比,SPL 的逻辑看起来非常清晰。

 

三. 递归查找叶子记录

 

【例 3】 在中国行政区划表中,查询河北省下属区县。部分数据如下:

ID

NAME

PARENT_ID

1

China

0

11

Beijing

1

12

Tianjin

1

13

Hebei

1

1301

Shijiazhuang

13

1302

Tangshan

13

 

SQL的解决方案:

 

    首先我们查找所有从属于河北省的记录,然后在这些记录中查找那些不是其他区域的父区域的记录。SQL 语句如下:

 

WITH CTE1 (ID,NAME,PARENT_ID,PARENT_NAME) AS(

   SELECT

      ID,NAME,PARENT_ID,NULL PARENT_NAME

   FROM CHINA_REGION

   WHERE NAME='Hebei'

   UNION ALL

   SELECT

      T.ID,T.NAME,T.PARENT_ID,CTE1.NAME PARENT_NAME

   FROM CHINA_REGION T

   INNER JOIN CTE1

   ON T.PARENT_ID=CTE1.ID

)

SELECT ID,NAME,PARENT_NAME

FROM CTE1 T1

WHERE NOT EXISTS(

   SELECT 1

   FROM CTE1 T2

   WHERE T1.ID=T2.PARENT_ID

)

ORDER BY ID

 

SPL的解决方案:

    在 SPL 中提供了函数 P.nodes@d(F,r) 用于递归查找所有叶子:


A

1

=T("ChinaRegion.csv")

2

>A1.switch(PARENT_ID,A1:ID)

3

=A1.select@1(NAME=="Hebei")

4

=A1.nodes@d(PARENT_ID,A3)

5

=A4.new(ID,NAME,PARENT_ID.NAME:PARENT_NAME)

A1:导入中国行政区划表

A2:将父行政区 ID 外键对象化,转换为相应的父行政区记录,实现外键对象化。

A3:选出河北省的记录。

A4:使用函数 P.nodes() 进行递归查找,其中选项 @d 时递归查找所有叶子。

A5:生成由序号、行政区名称和上级行政区名称组成的表。

 

四. 遍历目录下所有文件

 

【例 4】 某小学在线教学终端调查表的汇总整理,统计各终端占比。文件目录结构如下:

..

目录中的调查文件是 EXCEL 格式,部分数据如下:

ID

STUDENT_NAME

TERMINAL

1

Rebecca   Moore

Phone

2

Ashley   Wilson

Phone,PC,Pad

3

Rachel   Johnson

Phone,PC,Pad

4

Emily   Smith

PC,Pad

5

Ashley   Smith

PC

6

Matthew   Johnson

Phone

7

Alexis   Smith

Phone,PC

8

Megan   Wilson

Phone,PC,Pad

 

    由于 SQL 语句不能用于目录和文件的读取,这里就不给出 SQL 的解决方案了,我们看一下 SPL 是如何解决目录和文件的递归遍历问题的。

 

SPL的解决方案:

    在 SPL 中提供了函数directory@s()用于递归查找所有所有子目录下的文件名:


A

1

=directory@ps("C:/Primary School")

2

>A1.run(t=T(~),@+=t.len(),~=t.conj(TERMINAL.split@c()))

3

=A1.conj().groups(~:TERMINAL;count(~)/A2:PERCENTAGE)

A1:使用函数directory()导入文件目录,其中选项 @s 用于递归查找所有子目录下的文件名

A2:循环读取文件,将终端按逗号拆分并求合集。

A3:将所有的终端分组汇总每种终端的百分比。

 

五. JSON文件递归合并字段值

 

【例 5】 下面是某时刻,新冠状病毒世界各地确诊人数的 JSON 数据,要统计世界确诊人数。文件部分数据如下:

 

[

   {Region:"USA",Confirmed:[

      {Region:"California",Confirmed:3671902},

      {Region:"New York",Confirmed:1139740},

      {Region:"Virginia",Confirmed:620801},

      {Region:"Florida",Confirmed:2064525},

      …

   ]},

   {Region:"Brazil",Confirmed:[…]},

   {Region:"India",Confirmed: […]},

   {Region:"France",Confirmed: […]}

   …

]

 

    由于 SQL 语句不能用于 JSON 文件的读取,这里就不给出 SQL 的解决方案了,我们看一下 SPL 是如何解决 JSON 数据文件内容的递归遍历问题的。

 

SPL的解决方案:

    在 SPL 中提供了函数 A.field@r()用于递归获取字段值,函数 A.conj@r() 用于递归合并序列成员。SPL 脚本如下:


A

1

=json(file("COVID-19.json").read())

2

=A1.field@r("Confirmed")

3

=A2.conj@r().sum()

A1:导入 JSON 数据文件。

A2:递归获取所有确诊字段值。

A3:递归合并所有确诊人数并求和。

 

总结

经过上面的讨论,我们可以看到,SQL 虽然提供了实现递归问题的方法,但是使用起来却不简单。这是因为 SQL 中没有显式的记录、引用这些概念,返回的递归结果只是靠行号来标识上下级关系。而 SQL 中的集合又是无序的,这使得递归后续的运算非常麻烦。

SPL支持异构的数据结构,并且有显示的记录概念。更重要的是,SPL 处理递归问题的思路非常清晰,自连接后使用递归函数,再进行集合运算即可。SPL 所提供的递归功能要更加灵活,适应性也更加广泛,可以用于很常见的递归目录、文件内容递归等应用场景。

    另外,当查询比较复杂时,SQL 语句的复杂程度会成倍增加。比如经常要用到临时表、嵌套查询等等,使得 SQL 语句的编写和维护难度提升。而 SPL 只要按自然思维去组织计算逻辑,逐行书写出简洁的代码。

esProc 是专业的数据计算引擎,基于有序集合设计,同时提供了完善的集合运算,相当于 Java 和 SQL 优势的结合。在 SPL 的支持下,递归运算会非常容易。


以下是广告时间

对润乾产品感兴趣的小伙伴,一定要知道软件还能这样卖哟性价比还不过瘾? 欢迎加入好多乾计划。
这里可以低价购买软件产品,让已经亲民的价格更加便宜!
这里可以销售产品获取佣金,赚满钱包成为土豪不再是梦!
这里还可以推荐分享抢红包,每次都是好几块钱的巨款哟!
来吧,现在就加入,拿起手机扫码,开始乾包之旅



嗯,还不太了解好多乾?
猛戳这里
玩转好多乾