 | 级别： 初级 Srini VenigallaNetsetgo
2003 年 3 月 01 日 IBM DB2 开发者园地文章将递归 SQL 与 SQL 用户定义函数结合起来，以解决涉及多个数据层次结构的复杂问题。
简介
递归是一种极其有效的解析类树关系的技术。在关系数据库中，类树模型用来表示材料单（Bill of Materials (BOM)）、文档层次结构以及组织的层次结构等数据。如果不使用递归，查询这些数据模型就需要在主机应用程序中进行冗长乏味的迭代编程。
DB2® SQL 程序员都熟悉 IBM DB2 Universal Database™ 中可用的递归构造。DB2 SQL 提供了公共表表达式（WITH 子句）来实现递归。DB2 还提供用户定义函数（UDF），您可以使用它将应用程序特定的函数合并到数据库服务器中。从 DB2 版本 7.2 开始，可以用 DB2 SQL 开发 UDF（此前可以用其它高级语言如 C 和 Java™ 来编写它们）。
我将在本文中说明如何将 DB2 中的传统递归 SQL 与基于 SQL 的用户定义函数（SQL UDF）结合起来，以缩短主机程序实现的时间并增强应用程序性能。
为了提供必要的背景知识，我将通过给出一个树结构的示例来开始讨论。接下来，我将给出一个用递归查询来解析树结构的示例。随后，将使用一个内容管理问题来阐明 DB2 递归 SQL 和 SQL UDF 的结合用法。
递归树结构示例
图 1、2 和 3 分别描述了一个树结构的逻辑视图、其表的表示法和递归查询的结果。
图 1. 树结构的逻辑视图
在
图 1中，将内容层次结构描述成包含一组节点的树。该树由根节点 Library 及其子节点 News、Sports 等表示。
上述关系可以存储在如
图 2所示的关系表中。
图 2. 将树节点作为关系表表示
| Parent_id | Item_id | Item_Name | | -1 | 1 | Library | | 1 | 2 | News | | 2 | 3 | World News | | 2 | 4 | Politics | | 2 | 5 | Business | | 2 | 6 | Science | | 2 | 7 | Technology | | 1 | 8 | Sports | | 8 | 9 | Local | | 8 | 10 | Collegiate | | 8 | 11 | Professional | | 9 | 12 | Soccer | | 10 | 13 | Soccer | | 11 | 14 | Soccer | | 9 | 15 | Football | | 10 | 16 | Football | | 11 | 17 | Football |
该表中的 Parent_id 和 Item_id 列可以通过将节点的 Item_id 用作其子节点的 Parent_id 来表示父、子关系。（请注意：根节点 Library 没有真正的父节点；因此将 -1 用作它的父节点。）数据的固有循环本质（任何节点都既可以看作父节点又可以看作子节点的能力表明了这种本质）促进了递归。
给定上面的数据，递归对于开发那些“遍历”树来产生各种结果的查询是有用的，如任何给定节点的所有后代（子节点和子节点的子节点等等）。
例如，查找名为“Sprots”的节点的后代的递归查询产生如
图 3所示的结果集。
图 3. 递归查询的结果
| Parent_id | Item_id | Item_Name | | 8 | 9 | Local | | 8 | 10 | Collegiate | | 8 | 11 | Professional | | 9 | 12 | Soccer | | 9 | 15 | Football | | 10 | 13 | Soccer | | 10 | 16 | Football | | 11 | 14 | Soccer | | 11 | 17 | Football |
DB2 中的递归查询使用 WITH 子句实现，也称为
公共表表达式。从版本 5 开始，就可以在工作站上的 DB2 中使用公共表表达式。
公共表表达式与临时视图非常类似。然而，临时视图仅在定义它的单条 SQL 语句执行期间有效。公共表表达式在 SELECT 语句的开始部分采用 WITH 子句的形式。在使用公共表表达式的查询中可以多次使用它，并且公共表表达式还可以通过取别名连接到它本身，这两个特性使它在实现递归时很有用。
递归查询通常有三个部分：
- 一个公共表表达式形式的虚拟表。
- 一个初始化表。
- 一个与虚拟表进行完全内连接的辅助表。
使用 UNION ALL 合并上述所有表。最后用 SELECT 从递归输出中产生所需的行。
图 4显示了产生
图 3中结果的递归查询。
图 4. 产生图 3 中结果的递归查询。
WITH RPL (Parent_ID, Item_ID, Item_name) AS
(
SELECT ROOT.Parent_ID, ROOT.Item_ID, ROOT.Item_Name
FROM Subject ROOT
WHERE ROOT.Parent_ID = 8
UNION ALL
SELECT CHILD.Parent_ID, CHILD.Item_ID, CHILD.Item_Name
FROM RPL PARENT, Subject CHILD
WHERE PARENT.Item_ID = CHILD.Parent_ID
)
SELECT DISTINCT Parent_ID, Item_ID, Item_Name
FROM RPL
ORDER BY Parent_ID, Item_ID, Item_Name
|
让我们研究这个查询的组件：
- RPL 作为一个具有以下三列的虚拟表：Parent_ID、Item_ID 和 Item_name。
- WITH 子句内的第一个 SELECT 语句是初始化表。它只执行一次。它的结果形成虚拟表的初始内容以作为递归的种子。在上面的示例中，种子是 Parent_ID 为 8 的一行或多行。
- 第二个 SELECT 语句执行多次。将种子作为输入（JOIN 中的辅助表）传递给第二个 SELECT 语句以产生下一个行集合。将 JOIN 的结果添加（UNION ALL）到虚拟表的当前内容中，并放回到其中以形成用于下一次传递的输入。只要有行产生，这个过程就会继续。
- 如果期望，虚拟表上最后的 SELECT 允许我们选择递归查询所产生的所有行或仅部分行。
图 5用图形描述了上述过程。
图 5. 图 4 中递归查询的图形访问计划
以下是如何阅读该图的方法：
- 右边分支是初始化查询，它扫描表 Subject 的主索引文件并使用 Union (6) 将选中的行放置到 Temp (5) 中。
- Temp (5) 是虚拟表。
- 左边分支是查询的递归部分。正如 NLJOIN (7) 所示，它将 Temp (5) 的当前内容连接到 SUBJECT，并将结果放回 TEMP (5) 中。这个过程反复进行，直到没有更多要放到 TEMP (5) 中的行为止。
- 最后的排序和选择操作产生所需的确切结果。
这种技术很好地适用于任何树结构类型 — 发散、收敛、平衡、不平衡以及递归类型。
本文中包含的参考资料 [
Birchall]、[
Chamberlin] 和 [
IBM] 提供了很好的公共表表达式描述。
问题：解决多个层次结构
基于公共表表达式的递归构造提出了一些告诫。最重要的告诫是：您不能以相关方式将一个递归构造的行级结果传递给另一个递归构造。下列语句引自 IBM DB2 Universal Database SQL Reference [
IBM]。
如果在同一语句中定义了多个公共表表达式，不允许公共表表达式之间的循环引用（SQLSTATE 42835）。当创建了两个公共表表达式 dt1 和 dt2 并使 dt1 引用 dt2 且 dt2 引用 dt1 时，就发生循环引用。
如上所述，语句中的多个表表达式不能以相关的方式彼此引用。相关的子查询是对结果集中的每一行执行一次的查询。
让我用示例来阐明这个问题：
考虑 Subjects 层次结构中的一组文档，如
图 1所示。每个主题包含一组文档。Subjects 层次结构中的每个文档都指向一个符合要求的用户组，这个用户组位于组的独立层次结构中。那就意味着有两个树结构 — Subjects 和 User Groups — 都通过文档连接。
图 6说明了该方案。
图 6. 描述多个层次结构 — Subjects 和 User Groups — 的方案
现在，让我们定义一个问题：我们希望为给定用户 Chris（User Group 层次结构的一个叶节点）找出所有符合要求的 Subjects 及其子文档。这样的查询需要立即展开两个层次结构；对于 Subject 层次结构中的每个文档，您需要展开相应的用户层次结构。
查询应该产生结果来显示用户 Chris 有资格查看 Professional Football 下的 Document 2 和 Professional Soccer 下的 Document 3，但不具备查看 Document 1 的资格。
图 7显示了预期结果。
图 7. 所定义问题的预期结果
| PARENT_ID | ITEM_ID | ITEM_NAME | DOCUMENT_ID | NAME | ELIGIBLE | | 11 | 17 | Football | 2 | Document 2 | 1 | | 11 | 14 | Soccer | 3 | Document 3 | 1 | | 11 | 17 | Football | 1 | Document 1 | 0 |
使用表表达式编写一个返回这个结果的查询是不可能的。同时展开两个层次结构要求表表达式的循环引用，而目前 DB2 中还没有直接支持这种循环引用。当 Subjects 层次结构引用 Users 层次结构而 Users 层次结构又引用 Subjects 层次结构时，就会发生循环引用。
[
Birchall] 所描述的可能的解决方案是维护 Groups 的一个经过分解的表。一组 INSERT、UPDATE 和 DELETE 触发器使层次结构表和相关的经过分解的表保持同步。这样，您将只处理一个递归层次结构，而另一个层次结构只是连接到剩余产物。也许，到目前为止，这是唯一的解决方案。
由于可以使用 SQL 用户定义函数（UDF），解决这个问题就轻松得多了，在本文稍后的部分中将对此进行描述。使用 SQL 函数，我们可以使用参数来解决相关性问题。在开始讨论这个解决方案之前，我将简要描述一下 UDF。
SQL 用户定义函数（SQL UDF）概述
用户定义函数，顾名思义，就是您可以添加到数据库中的函数。它们可以是以下几种类型 — 标量函数（类似于 Length() 函数）、行函数、列函数或表函数。根据正交法则 [
Chamberlin]，可以在与 UDF 返回值或值的类型一致的任何 SQL 语句中使用它们。
可以使用高级语言（譬如 C 或 Java）来开发 UDF。从 DB2 UDB 7.2 开始，也可以使用 DB2 SQL 开发 UDF。基于 SQL 的 UDF 的主要优点是：与它们相应的高级语言版本不同，它们可以包含常规 SQL 语句来读取表。而在 DB2 UDB 7.2 中，用高级语言编写的 UDF 不能读取表。
使用 CREATE FUNCTION 语句将 UDF 注册到 DB2。有关 CREATE FUNCTION 语句的详细处理，请参考 DB2 SQL 参考大全手册 [
IBM]。
下列 CREATE FUNCTION 语句创建了一个名为“GETBONUS”的标量 UDF，它获取一个雇员作为输入。由该 UDF 执行的实际操作是作为 SQL 语句嵌入到 CREATE FUNCTION 语句中的。它连接了一组表，在相关列上应用公式并返回一个标量值。
CREATE FUNCTION GETBONUS (EMP CHAR (32))
RETURNS Integer
LANGUAGE SQL
READS SQL DATA
NO EXTERNAL ACTION
DETERMINISTIC
RETURN
Select (....) as "bonus" from TimeSheets JOIN ... where
TimeSheets.Emp_ID=EMP
|
在创建了 UDF 之后，其它 SQL 语句就可以将它作为函数使用了。例如，您可以创建一个查询来获取 EMP 表中所有雇员的奖金权利，如下所示。
Select Emp_name, Emp_Dept, Emp_ID, GETBONUS (EMP_ID) from EMP
|
您可能会争论说：UDF 所能提供的一切，都可以通过使用子查询或通过连接表实现。实际上，UDF 是一种在 SQL 中采用面向对象编程原理的方法。
在上述示例中，GETBONUS UDF 将奖金计算（每年都可能更改）分离成单个函数。通过将该计算分离成单个 UDF，可以高效地实现奖金政策中的更改，而不必在每份报表中或处理奖金数额的查询中进行 SQL 更改。
简单 SQL 函数（只包含一个 RETURN 语句）象宏一样高效运作，并受 DB2 的查询重写规则限制。查询重写是 SQL 编译器中的预处理阶段，在这期间 SQL 语句被转换成可以更容易地进行优化的格式，以改进查询性能。
问题的解决方案：使用 UDF 的多层次结构递归
现在，让我们再回顾一下
图 6中描述的问题。
解决方案如下：
- 展开 Subjects 层次结构。
- 对于 Subjects 层次结构中的每个叶节点（文档），展开 Groups 层次结构。
- 查找用户（输入）是否在指定层次结构（Groups）中。
查询是在两部分中开发的：
第一部分是
标量 UDF，它有两个输入 — Document ID 和 User ID。UDF 展开 Group 层次结构，从与 Document 相连的节点开始，检查该用户是不是该层次结构的一部分，如果是则返回值 1，否则返回值 0。
第二部分是 Subjects 层次结构上的一次常规
递归查询，它利用了第一部分中开发的标量 UDF。
让我们首先创建一个测试环境来实现该解决方案。
创建数据模型和测试数据
下面的图说明了我们将要使用的数据库的逻辑模型。
图 8. 用来实现方案的数据库的逻辑数据模型
要建立表，创建一个数据库并执行
附录中所描述的 SQL 脚本。
创建 SQL UDF
让我们按解决方案中描述的来开发 SQL UDF。
我们命名为 ISELIGIBLE 的 UDF 确定用户是否具有查看文档的资格。它产生一个标量值 0 或 1。
它获取两个输入 — document_id 和用户名 — 并从输入 document_id 所指定的节点开始，递归地解析 Group 层次结构中的节点。
最后，它对包含输入用户名的行计数。如果该用户不属于任何指定的用户层次结构，则计数为零；因此该用户不符合资格。如果计数大于等于 1，则该用户具有查看文档的资格。
使用下列 CREATE FUNCTION 语句来创建 UDF。粗体用来显示 SQL 查询。
CREATE FUNCTION ISELIGIBLE
(Doc Integer, Uname character (64))
RETURNS INTEGER LANGUAGE SQL
READS SQL DATA
NO EXTERNAL ACTION NOT DETERMINISTIC
RETURN
With
Main (grp, subgrp, grpname) AS
(SELECT grp, subgrp, grpname
FROM Group
WHERE (grp, subgrp) IN
(Select grp, subgrp from Group_Document where document_id=Doc)
UNION ALL
SELECT C.grp, C.subgrp, C.grpname
FROM Group C, Main M
WHERE M.subgrp = C.grp
)
Select count(*) from main where Ucase(grpname)=Ucase(Uname)
|
如果您从“命令中心（Command Center）”执行 CREATE FUNCTION 语句时遇到任何问题，请关闭“命令中心”并使用 DB2 命令行处理器（DB2 Command Line Processor）。
创建递归查询
让我们通过完成第二步来完成这个解决方案。在这个步骤中，我们开发了一个递归查询，它解析 Subject 层次结构以及与每个节点相关联的文档。然后，我们利用 ISELIGIBLE 函数来确定用户是否具有访问文档的资格。
下列 SQL 语句实现了我们想做的事情。
WITH RPL (Parent_ID, Item_ID, Item_name) AS
( SELECT ROOT.Parent_ID, ROOT.Item_ID, ROOT.Item_Name
FROM Subject ROOT
WHERE ROOT.Parent_ID =1
UNION ALL
SELECT CHILD.Parent_ID, CHILD.Item_ID, CHILD.Item_Name
FROM RPL PARENT, Subject CHILD
WHERE PARENT.Item_ID = CHILD.Parent_ID
)
SELECT DISTINCT rpl.Parent_ID, rpl.Item_ID, rpl.Item_name,
document.document_id, document.name,
ISELIGIBLE
(document.document_id, char('Chris')) eligible
From (rpl join Subject_Document sd on rpl.parent_id =
sd.parent_id and rpl.item_id=sd.item_id)
Join document on document.document_id = sd.document_id
Order by parent_id, Item_id
|
- 外部的 WITH 展开 Subjects 层次结构并产生 document_id。
- 我们将这些结果与表 Document 连接来获取文档名。
- SQL UDF ISELIGIBLE 运行另一个相关递归查询来查找“Chris”是否属于任何指定给 doc_id 的组中。
图 9说明了通过运行上面的查询所获得的结果。
图 9. 从解决方案获得的结果
| PARENT_ID | ITEM_ID | ITEM_NAME | DOCUMENT_ID | NAME | ELIGIBLE | | 11 | 14 | Soccer | 3 | Document 3 | 1 | | 11 | 17 | Football | 1 | Document 1 | 0 | | 11 | 17 | Football | 2 | Document 2 | 1 |
结果确实和预期的一样。用户“Chris”可以访问分别位于 Professional Football 和 Professional Soccer 下的文档 2 和 3。
当运行递归查询时，正常情况下会有这条 SQL 警告：“SQL0347W The recursive common table expression may contain an infinite loop. SQLSTATE=01605”。
结束语
在任何编程语言中，递归都是一个功能强大的概念。DB2 SQL 中的递归构造提供了一些功能强大的方法来优雅和高效地处理现实层次结构。通过将 SQL UDF 的能力和递归构造结合起来，人们可以将 DB2 SQL 的灵活性和强大功能延伸到新的领域。
通过消除代价极高的迭代应用程序逻辑，这些功能强大的特性还显著提高了客户机程序的性能。
参考资料
[Chamberlin]Don Chamberlin，“A Complete Guide to DB2 Universal Database”，Morgan-Kaufman Publishers. Inc.，可以在书店或这里找到：
http://www1.fatbrain.com/asp/BookInfo/BookInfo.asp?theisbn=1558604820。
[IBM]IBM，IBM DB2 Universal Database SQL Reference V 7.2，位于
http://www.ibm.com/software/data/db2/library/。
[Birchall]Graeme Birchall，“DB2 UDB V7.2 SQL Cookbook”，位于
http://ourworld.compuserve.com/homepages/Graeme_Birchall/HTM_COOK.HTM。
感谢
我真诚地感谢以下朋友的帮助：Steven Hiese（IBM）对本文进行了彻底的技术评审；Serge Rielau（IBM）多次深思熟虑的评论并帮助我在开发的早期阶段中调试 CREATE FUNCTION 环境；Dirk Wollscheid（IBM）、Sailesh Krishnamurthy（UC Berkeley）、NDR Sarma（Texas AMU）、Darrin Nelson（NetSetGo）和 Mike Sieber（NetSetGo）给予我很大的鼓励。
关于作者
|
Srini Venigalla是 NetSetGo, Inc. 的首席工程师。二月，NetSetGo 赢得了最佳 WebSphere® 电子商务解决方案的
IBM Beacon Award。Srini 目前从事内容管理、知识交付和 B-2-B 解决方案等领域的工作，在这些工作中使用 WebSphere、DB2、XML 和 Java 技术。他拥有电子工程学士学位和计算机技术硕士学位。他是 ACM 的成员。可以通过
svenigalla@netsetgo.com 与他联系。
|
附录.创建并实现数据模型
创建数据库
CREATE DATABASE UDFTEST USING CODESET UTF-8
TERRITORY US
|
实现数据模型
CREATE TABLE Subject (
item_id INTEGER NOT NULL,
parent_id INTEGER NOT NULL,
item_name CHAR(127)
);
ALTER TABLE Subject
ADD PRIMARY KEY (item_id, parent_id);
CREATE TABLE Group (
grp INTEGER NOT NULL,
isuser string2 NOT NULL,
subgrp INTEGER NOT NULL,
grpname CHAR(32)
);
ALTER TABLE Group
ADD PRIMARY KEY (grp, subgrp);
CREATE TABLE Document (
document_id INTEGER NOT NULL,
name VARCHAR(20)
);
ALTER TABLE Document
ADD PRIMARY KEY (document_id);
CREATE TABLE Subject_Document (
item_id INTEGER NOT NULL,
parent_id INTEGER NOT NULL,
document_id INTEGER NOT NULL
);
ALTER TABLE Subject_Document
ADD PRIMARY KEY (item_id, parent_id, document_id);
CREATE TABLE Group_Document (
grp INTEGER NOT NULL,
subgrp INTEGER NOT NULL,
document_id INTEGER NOT NULL
);
ALTER TABLE Group_Document
ADD PRIMARY KEY (grp, subgrp, document_id);
ALTER TABLE Subject_Document
ADD FOREIGN KEY (document_id)
REFERENCES Document
ON DELETE RESTRICT
ON UPDATE RESTRICT;
ALTER TABLE Subject_Document
ADD FOREIGN KEY (item_id, parent_id)
REFERENCES Subject
ON DELETE RESTRICT
ON UPDATE RESTRICT;
ALTER TABLE Group_Document
ADD FOREIGN KEY (document_id)
REFERENCES Document
ON DELETE RESTRICT
ON UPDATE RESTRICT;
ALTER TABLE Group_Document
ADD FOREIGN KEY (grp, subgrp)
REFERENCES Group
ON DELETE RESTRICT
ON UPDATE RESTRICT;
|
创建测试数据
在创建表之后，执行下列 SQL 语句来创建数据。
Insert into Subject
(Item_id, Parent_id, Item_Name)
values
(1, -1,'Library'), (2,1,'News'),
(3,2,'WorldNews'), (4,2,'Politics'),
(5,2,'Business'), (6,2,'Science'),
(7,2,'Technology'), (8,1,'Sports'),
(9,8,'Local'), (10,8,'Collegiate'),
(11,8,'Professional'),(12,9,'Soccer'),
(13,10,'Soccer'), (14,11,'Soccer'),
(15,9,'Football'), (16,10,'Football'),
(17,11,'Football')
Insert into Group
(grp, subgrp, grpname, isuser)
values
(-1,1,'Users','N'), (1,2,'Group A','N'),
(1,3,'Group B','N'), (3,31,'Group B1','N'),
(3,32,'Group B2','N'), (31,311,'Chris','Y'),
(2,21,'Pat','Y'), (2,22,'Jane','Y'),
(2,23,'Tom','Y')
Insert into Document (document_id, name)
values
(1,'Document 1'), (2,'Document 2'),
(3,'Document 3')
Insert into Subject_Document
(Item_id, Parent_id, document_id)
values
(17,11,1), (17,11,2), (14,11,3)
Insert into Group_Document (grp, subgrp, document_id)
values (1,2,1), (1,3,2), (3,31,3)
|
关于作者 | | | Srini Venigalla has authored this article |
对本文的评价
| |
