持久排列
5.00/5 (8投票s)
2004年5月5日
19分钟阅读
37408
345
一篇关于如何在关系数据库中持久化项目排列的文章。
引言
从关系数据库中获取有序数据集的常用方法是使用 SQL 子句 ORDER BY。这与 SELECT 语句结合使用，根据 ORDER BY 子句指示的列中的值对整个结果数据集进行排序。让我们以以下表（名为 STUDENT）为例：
| 名称 | 系数 |
|---|---|
| John | 10 |
| Michael | 12 |
| George | 8 |
| Steve | 8 |
像“SELECT * FROM STUDENT ORDER BY coefficient DESC”这样的查询将按系数的值降序返回数据。
| Michael | 12 |
| John | 10 |
| George | 8 |
| Steve | 8 |
这种数据排序方法非常简单易用，并且具有作为 SQL 标准一部分的优点，因此几乎所有开箱即用的关系数据库都支持它。然而，它有一个显著的缺点：它只能在用于排序的数据列中的值包含排序过程所需信息时才能有效使用。在现实生活中，我们可能希望以与数据本身无关的顺序获取数据。可能是用户以特定顺序输入数据，并且他/她希望以相同顺序返回，或者任何其他我们可能希望能够以特定顺序获取表中记录的情况，而该顺序无法从数据本身推导（计算）出来。换句话说，在这种情况下，一个简单的 ORDER BY 子句是不够的。让我们举一个例子。
（表 MASTERTABLE）
| ItemGroup (主键) |
|---|
| 48E9405C45EE4BB3A3DCD3918898A815 |
| 40AB772255184B20A4A8EDD89B59536F |
| 0826DE86308148F89CACEBD8A043F4DC |
（表 DETAILTABLE）
| ItemGroup（外键指向 MASTER.ItemGroup） | Item (主键) |
|---|---|
| 48E9405C45EE4BB3A3DCD3918898A815 | 6BF71715E18640419BA9023585E55B55 |
| 48E9405C45EE4BB3A3DCD3918898A815 | C41908F6E896409A95ABD3EC81550B0D |
| 48E9405C45EE4BB3A3DCD3918898A815 | 4D95851F6F7D4CEB8C4AC7ABDAC429D9 |
| 48E9405C45EE4BB3A3DCD3918898A815 | 4D467B250ECD46D3B99857CAE00BC967 |
| 40AB772255184B20A4A8EDD89B59536F | 6F9B9D06515D450E990CD9AEBEE9DCCF |
| 40AB772255184B20A4A8EDD89B59536F | 6BF71715E18640419BA9023585E55B55 |
| 0826DE86308148F89CACEBD8A043F4DC | 63E3F1F9229C41F889C05F66EB0E441 |
| 0826DE86308148F89CACEBD8A043F4DC | 13329EB5387649C6B42DC2FDDE1E5700 |
所有列的类型都是 RAW(16)，您可以在其中看到的值是 GUID（全局唯一标识符）值。它们本身在现实世界中没有任何意义，它们只是盲目的标识符。此数据库有许多类别（在 MASTERTABLE 表中），对于每个类别，我们都可以有零个或多个项目（在 DETAILTABLE 表中）。除了这些标识符，我们没有其他识别信息。我们可以假设这些信息在该数据库之外，或者即使不是，也可能无法或不希望根据它进行排序。让我们假设我们希望维护给定项目组内所有项目的顺序。我们该怎么做？
“SELECT * FROM DETAILTABLE WHERE ItemGroup = <SOME_ITEMGROUP> ORDER BY Item”不会导致任何错误，但也不会做任何有用的事情（它将按字典顺序排序值，这不是我们所追求的）。
我们提出了一些技术，它们将有助于解决此问题以及一些相关问题，如下所述。
方法 #1. 具有分散整数值的附加列
此方法涉及向 DETAILTABLE 表添加一个新列，其中包含有关项目 ID 的元信息。我们将此列称为 Rank。此元信息只是一个正整数，使得“SELECT … WHERE ITEMGROUP = <SOME_ITEMGROUP> ORDER BY Rank”将生成所需的顺序。在插入时，将选择一个 rank 值，以便刚刚插入的项目在该特定项目组的有序项目列表中占据所需位置。在我们的示例中，我们只对项目组内的项目排序感兴趣（并且一个项目作为 PK，只属于一个项目组），因此这些 rank 号在项目组范围内有意义，而不是在 DETAILTABLE 表的范围内有意义。我们为此技术提出的存储过程的技术细节如下所述。对于列 (ItemgGroup, Rank) 应该有一个备用键来强制同一项目组内的 rank 的唯一性。
首先，让 MAXINT 表示您使用的特定数据库支持的最大整数值。出于可移植性考虑，可以为 MAXINT 选择一个保守的值，一个能保证在所有关系数据库上都能工作的值。
假设项目 ITEM1 是为项目组 ITEMGROUPM 插入到 DETAILTABLE 表中的第一个项目。其 rank 应选择为 ROUND (MAXINT / 2) 的值。
现在假设我们已经为项目组 ITEMGROUPM 在 DETAIL 表中输入了一系列 N 个项目，ITEM1、ITEM2... ITEMN，并且它们的 rank 分别是 RANK1、RANK2... RANKN。我们希望将这个新的 ITEM 定位为 ITEMK 的直接后继，0 <= K < N（0 作为特殊情况，当我们希望这个新项目是第一个时，而 RANKN+1 被认为是 MAXINT）。我们将其 rank 值选择为
ROUND ((RANK + (RANKK+1 - RANKK) / 2))，其中 RANK0 定义为 0。如果我们想将新项目作为第一个插入，其 rank 应为 ROUND (RANK1 / 2)，如果想让它成为最后一个，其 rank 应为 ROUND ((MAXINT – RANKN) / 2)。
很容易看出，对于所有 K < P，RANKK < RANKP。
如果在列表中的特定位置插入大量项目（例如，所有项目都一个接一个地作为同一个现有项目的直接后继插入），我们可能会达到某个点，对于某个 K，RANKK+1 - RANKK = 1（ITEMK 是我们前面提到的首选直接前驱）。这实际上意味着不能插入新的 ITEMP 使得 RANKK < RANKP < RANKK+1。我们通过在项目组中的所有项目上重新分配 rank 值来解决这种情况。让我们将以下简单的 rank 重新分配方法称为“全局重新分配”。
ITEMGROUP // user given argument
N //number of items for ITEMGROUP
RANK[] RANKS = “SELECT RANK, ITEM FROM DETAIL
WHERE DETAIL.ITEMGROUP = ITEMGROUP
ORDER BY RANK ASC”
integer index = 1;
integer PREVIOUS = RANKS [1]; //first rank
for each RANK R in RANKS
{
R = ROUND ((MAXINT / (N+1))) * index;
update R to db;
index++;
}
示例
假设我们有 N = 8 个项目，它们的 rank 为：3、5、7、7、7、10、11 和 14。它们将被重新分配为
ROUND (MAXINT / 9), ROUND ((MAXINT / 9)) * 2, ROUND ((MAXINT / 9)) * 3, ROUND ((MAXINT / 9)) * 3, ROUND ((MAXINT / 9)) * 3, ROUND ((MAXINT / 9)) * 6, ROUND ((MAXINT / 9)) * 7, ROUND ((MAXINT / 9)) * 8.
立即可观察到，相等的 rank 重新分配后仍相等，并且如果 rank K 的多重性为 M1，rank P 的多重性为 M2。重新分配后，我们将有
ROUND ((RANKK+1 - RANKK) / (RANKP+1 - RANKP)) = ROUND (M1 / M2); （极限情况是当 K 是最大 rank 时，RANKK+1 为 MAXINT）。
这种重新分配方法的优点是，它保证了 rank 之间合理的“拓宽”，而无需了解或关心 rank 值密度高于平均值的位置。不幸的是，这种简单的重新分配策略没有使用任何可能关于项目预期 rank 分布的信息。
当然，重新分配方法可以在数据库内部或外部实现。作为示例，本文提供了一个 PL/SQL 实现以供将来参考。处理 rank 重新分配的存储过程的主体如下所示。
PROCEDURE
redistranksglobally (itemgroupguid IN RAW)
IS
n NUMBER (38, 0);
f NUMBER (38, 0);
ceils NUMBER (38, 0);
newrank NUMBER (38, 0);
BEGIN
SELECT COUNT (1)
INTO n
FROM detailtable_disp_total
WHERE detailtable_disp_total.itemgroup = itemgroupguid;
IF n > 0
THEN
f := FLOOR (common.maxint / (n + 1));
ceils := common.maxint - f * (n + 1);
newrank := 0;
FOR r IN ranks (itemgroupguid)
LOOP
newrank := newrank + f;
IF ceils > 0
THEN
newrank := newrank + 1;
ceils := ceils - 1;
END IF;
UPDATE detailtable_disp_total
SET detailtable_disp_total.RANK = newrank
WHERE CURRENT OF ranks;
END LOOP;
END IF;
END;
部分有序的等级
如果一个人只想在等级之间进行部分排序，他/她可以选择这样做。列 (ItemgGroup, Rank) 的备用键将必须移除，并且必须设计额外的插入和重新分配语义。本文所附的参考实现中提供了一个如何实现此功能的示例。
这种方法的主要优点是，通过将 [1 ... MAXINT] 作为我们的 rank 值区间，并使 rank 彼此远离，可以在需要任何 rank 重新分配之前发生许多新项目的插入，并且在需要新的重新分配之前会发生更多。这些特性使得这种技术适用于高度可变动的表。
这种方法的主要缺点是引入了排序复杂性，以从给定的项目组中找出第 n 个项目。
下一种技术与此方法在某种程度上互补，因为它使 rank 具有索引意义，但对于绝大多数插入操作，将需要至少部分 rank 重新分配。此外，下一种技术不允许部分排序。
方法 #2. 具有连续整数值的附加列
此方法涉及向 DETAILTABLE 表添加一个新列，其中包含有关项目 ID 的元信息。我们将此列称为 Rank。此元信息只是一个正整数，使得“SELECT … WHERE ITEMGROUP = <SOME_ITEMGROUP> ORDER BY Rank”将生成所需的顺序。在这种情况下，rank 从 1 开始并具有连续的值。由此立即可知，给定项目组的最大 rank 是该项目组的项目计数。
在插入时，将选择一个 rank 值，以便刚刚插入的项目在特定项目组的有序项目列表中占据所需位置。在我们的示例中，我们只对项目组内的项目排序感兴趣（并且一个项目作为 PK，只属于一个项目组），因此这些 rank 号在项目组范围内有意义，但在整个 DETAILTABLE 表的范围内没有意义。需要完全排序，这意味着没有两个不同的项目可以具有相同的 rank。
为某个项目组插入的第一个项目将具有 rank 值 1。
现在假设我们有一个序列 N 个项目属于 DETAIL 表中的项目组 ITEMGROUPM，即 ITEM1, ITEM2... ITEMN，并且它们的排名分别为 RANK1, RANK2... RANKN。我们知道 RANKK = RANKK-1 + 1，除了 RANK1 没有前身。如果我们将新项目插入到列表的末尾，则通过将其排名设置为 N + 1 来完成。如果不是，我们假设新插入项目所需的前身排名为 K，其中 0 <= K < N，0 表示我们希望它在列表的第一位。这通过两个简单步骤实现。首先，我们递增所有严格大于 K 的排名。其次，我们插入排名为 K + 1 的新项目。
我们接着描述一组数据库约束，其作用是确保 rank 具有从 1 开始的正连续整数值。让我们回到前面定义的表 DETAILTABLE。
| ItemGroup（外键指向 MASTER.ItemGroup） | Item (主键) | 秩 | RankMinus1 |
| 48E9405C45EE4BB3A3DCD3918898A815 | 6BF71715E18640419BA9023585E55B55 | 1 | |
| 48E9405C45EE4BB3A3DCD3918898A815 | C41908F6E896409A95ABD3EC81550B0D | 2 | 1 |
| 48E9405C45EE4BB3A3DCD3918898A815 | 4D95851F6F7D4CEB8C4AC7ABDAC429D9 | 3 | 2 |
| 48E9405C45EE4BB3A3DCD3918898A815 | 4D467B250ECD46D3B99857CAE00BC967 | 4 | 3 |
| 40AB772255184B20A4A8EDD89B59536F | 6F9B9D06515D450E990CD9AEBEE9DCCF | 1 | |
| 40AB772255184B20A4A8EDD89B59536F | 6BF71715E18640419BA9023585E55B55 | 2 | 1 |
| 0826DE86308148F89CACEBD8A043F4DC | 63E3F1F9229C41F889C05F66EB0E441 | 1 | |
| 0826DE86308148F89CACEBD8A043F4DC | 13329EB5387649C6B42DC2FDDE1E5700 | 2 |
我们添加了具有整数数据类型的列 Rank 和 RankMinus1。对于每个 rank，RankMinus1 列中的相应值是 rank – 1。我们将在稍后回到为什么会这样。当 rank 为 1 时，RankMinus1 列中的相应条目为 NULL（需要注意的是 RankMinus1 可为空）。
将以以下形式向表 DETAIL 添加一个约束
((RANK =1 AND rankminusone IS NULL)OR RANK>1 AND rankminusone=RANK-1)
该约束将被设置为可推迟且初始推迟，以便在插入新项目时允许对等级进行操作。
将添加一个从 RankMinus1 指向 Rank 的外键，以确保 RankMinus1 列中不会插入错误值。此外，还将引入备用键以确保 (ItemGroup, Rank) 和 (ItemGroup, RankMinus1) 组合的唯一性。
随着这种约束机制的加入，在插入新项目时必须增加新的步骤。具体来说，RankMinus1 列中的值也必须更新。这很容易做到，在此不作详细解释。
这种方法的优点是，排名不仅提供顺序，还提供特定项目的索引信息。可以通过执行“SELECT * FROM DETAIL WHERE Rank = n”来找出“表中的第 n 个元素”。
缺点是，插入一个新的排名为 K 的项目将需要更新 N – K 个排名以及 RankMinus1 列中相应的 N – K 个值。
本文附带的参考实现中提供了如何实现此功能的示例。
隔离主表中的排序信息
我们已经看到，将排序信息保存在详细表中会导致在订单更改时进行大量的更新操作。在以下部分中，我们介绍了一种将该信息存储在主表中的方法。我们还分析了所提出的方法何时可行何时不可行，并讨论了一种效率较低但对项目计数没有那么强限制的实现类似结果的方法。
背景 - 阶乘数系统
定义 1 阶乘
阶乘 n! 定义为 n! = n(n-1)...1，其中 n 是一个自然数。阶乘 n! 是 n 个不同对象可以排列的方式的数量。因为空集只有一个排列，所以认为 0! = 1。
为了说明阶乘数实际上有多大，我们引入一些由斯特林近似产生的限制
命题 1 [Robbins 1955, Feller 1968]
阶乘函数受以下双重不等式限制
|
命题 2 [Gosper]
对于较大的 n，以下情况成立
|
与我们传统的“几何”基数计数系统不同，后者连续“位”的面值形成几何级数，例如 1, 10, 100, ... 或 1, 2, 4, 8, 16, ...，阶乘计数系统的面值是阶乘数 1, 2, 6, 24, 120, ....。因此，阶乘计数系统属于“混合基数表示”系统类别。
以下命题对于阶乘数系统的存在非常重要
命题 3
恒等式 0 * 0! + 1 * 1! + 2 * 2! + 3 * 3! + ... + k * k! = (k + 1)! - 1 对于所有 k ≥ 0 都成立。
命题 4
设 t ≥ 2 为一个自然数。范围 0 ≤ f ≤ t! 中的每个整数都可以唯一地写成以下形式：
|
以另一种形式表示，
|
其中“数字” cj 是满足 0 ≤ cj ≤ j 的整数，对于 1 ≤ j < t。
阶乘数字系统使我们能够将 t 个元素的排序表示为小于 t! 的单个自然数。这在某种意义上是最佳的，因为排列 t 基数集合的元素恰好有 t! 种方式。
方法 #3. 将排列打包为自然数
设 (U1, ..., Ut) 是表示项目的 t 个不同标识键的序列，其中 Ui Î U。这些可以在详细表中构成主键或唯一索引。我们假设数据库对集合 U 施加了全序，我们称之为“自然顺序”，这通常是正确的，无论是 GUID、自动编号字段还是在最广泛使用的关系数据库中可用于标识目的的任何其他内容。
SQL 子句 ORDER BY 始终根据数据库对列数据类型施加的自然顺序对项目进行排序。序列 (U1, ..., Ut) 可以从数据库的自然顺序开始并通过应用一个排列来表示，反之亦然。以下算法将逆排列计算为转置的组合，并将排列表示为一个自然数。有关以下两种算法变体的更多详细信息，请参阅 Donald E. Knuth 的《计算机程序设计艺术，第 2 卷：半数值算法》，第 3.3.2 节
算法 1 [分析一个排列]
我们计算一个双射映射 f : Pt ® [0, t!) Ç Z，其中 Pt 是 (1, ..., t) 的所有可能排列的集合。让 s 表示这样一个排列。
- P1 令
r ¬ t,f ¬ 0。 - P2 找到（唯一的）
s位置，使得ss = r。设置f ¬ r * f + s - 1。 - P3 交换
sr与ss。 - P4 递减
r。如果r > 1，则转到步骤 P2。
注意，当算法停止时，排列 s 变为恒等排列。为了证明该函数确实是双射的，我们反向运行该算法
算法 2 [反向]
对于 r = 2, 3, ..., t
s¬f mod r + 1f = floor([f/r])- 交换
ss与sr。
阶乘数系统与算法 1 之间的关系是恒等式 cr - 1 = s，每次对任何 r 值执行步骤 P2 时都成立。
请注意，这两种算法可以直接在序列 (U1, ..., Ut) 上运行，而不是使用排列 s。在这种情况下，不需要寻找 ss = r，而是需要找出序列 (U1, ..., Ut) 中的最大元素。
如果项目由自动编号列索引，那么简单地将项目添加到序列末尾可以使用
PERMUTATION ¬ t! t + PERMUTATION
在本文附带的源代码中，提供了一个签名为
FUNCTION arrangecategoryitems (initems IN rawtable) RETURN NUMBER
的存储函数，用于计算排列的数字表示。该实现严格遵循上述算法。
items := initems;
i := 0;
s := 1;
t := items.COUNT;
r := t;
f := 0;
LOOP
s := 1;
i := 0;
LOOP
i := i + 1;
EXIT WHEN i > r;
IF items (i) > items (s)
THEN
s := i;
END IF;
END LOOP;
aux := items (s);
items (s) := items (r);
items (r) := aux;
f := r * f + s - 1;
r := r - 1;
EXIT WHEN r <= 1;
NULL;
END LOOP;
RETURN f;
还包含一个从 PERMUTATION 列中提取排序信息的存储函数。
FUNCTION reversearrangecategoryitems (
permutation IN NUMBER,
items IN rawtable
)
RETURN rawtable
该实现严格遵循逆向算法
RESULT := items;
i := 0;
s := 1;
t := items.COUNT;
f := permutation;
r := 1;
LOOP
r := r + 1;
EXIT WHEN r > t;
s := MOD (f, r);
f := FLOOR (f / r);
aux := RESULT (s + 1);
RESULT (s + 1) := RESULT (r);
RESULT (r) := aux;
END LOOP;
LOOP
i := i + 1;
EXIT WHEN i > RESULT.COUNT;
END LOOP;
RETURN RESULT;
这种方法的局限性
如上所述，此方法允许将排列信息存储在主表中而不是详细表中。最多 t 个项目的排序信息存储为小于 t! 的整数。当排序更改时，主表中只有一个字段需要更改，这比本文介绍的其他方法成本低得多。
但是，让我们找出使用（某些）数据库支持的整数数据类型所支持的最大项目数。我们将 PERMUTATION 列添加到主表。在 Oracle 中，我们建议使用 NUMBER(38, 0) 数据类型。在 SQL Server 中，等效的是 DECIMAL(38, 0)。在这两种情况下，MAXINT = 1039 - 1，而使得 t! < MAXINT 的最大数 t 是 t = 34。因此，使用此方法，我们只能在 Oracle 和 SQL Server 上为每个主记录支持 34 个详细项目。
方法 #4. 超越上述限制
除了使用整数，还可以将序列 c1,c2, ..., ct-2, ct-1 打包成字节序列数据类型，即 Oracle 上的 RAW 和 SQL Server 上的 VARBINARY。由于 0 £ cj £ j，可以使用非常简单的字节打包策略将序列表示为字节序列数据类型：每个 cj 将在 PERMUTATION 列中占用 ceil(log2(j+1)) 位。按上述方式打包序列所需的位数是
|
如果我们使用双重不等式 log2(t!) ≤ St ≤ t + log2(t!)，则立即出现此和的一些宽松边界
|
|
使用上限，可以轻松计算 PERMUTATION 列需要分配多少位（而不是字节）。为了计算字节大小，需要将上限除以 8 并计算结果的上限。
但是我们也可以计算存储序列 c1, c2, ..., ct - 2, ct - 1 所需的精确大小。让我们定义
m(t) = the greatest integer m such that 20 + 21 + ... + 2(m - 1) £ t - 1
m(t) 的等效表达式为
m(t) = floor(log2(t))
现在，我们来计算总和。
|
在 Ronald L. Graham, Donald E. Knuth 和 Oren Patashnik 的《具体数学》一书中，求和章节中包含以下求和公式：
|
使用上述公式，我们得到
St = (m(t) - 1) 2m(t) + 1 + (m(t) + 1)(t - 2m(t))
或
St = t (m(t) + 1) + 1 - 2m(t) + 1
粗略地说，St = O(t log(t))。
使用 Oracle RAW(2000) 数据类型，支持的最大项目数为 t = 1640，而使用 SQL Server 与 BINARY(8000) 或 VARBINARY(8000)，支持的最大项目数为 t = 5553。
为了演示目的，我们提供了一个计算后的以字节表示的大小表。
| t | size(PERMUTATION) 以字节计 |
|---|---|
| 10 | 4 |
| 20 | 9 |
| 30 | 15 |
| 40 | 23 |
| 50 | 30 |
| 60 | 38 |
| 70 | 46 |
| 80 | 55 |
| 90 | 63 |
| 100 | 72 |
| 200 | 169 |
| 300 | 274 |
| 400 | 387 |
| 500 | 499 |
| 600 | 623 |
| 700 | 748 |
| 800 | 873 |
| 900 | 998 |
| 1000 | 1123 |
| 2000 | 2495 |
| 3000 | 3989 |
| 4000 | 5489 |
| 5000 | 7102 |
| 6000 | 8727 |
| 7000 | 10352 |
| 8000 | 11977 |
| 9000 | 13703 |
| 10000 | 15453 |
在本文关联的源代码中，包含一个签名为
FUNCTION arrangecategoryitems (initems IN rawtable)
RETURN RAW
的存储函数，用于计算 PERMUTATION 列的值。请注意，该实现使用 UTL_RAW Oracle 包进行字节操作。
RESULT := UTL_RAW.copies ('00', 2000);
bitposition := 0;
bitsize := 1;
samesizecount := 1;
samesizeindex := 1;
items := initems;
t := items.COUNT;
r := t;
LOOP
s := 1;
i := 0;
LOOP
i := i + 1;
EXIT WHEN i > r;
IF items (i) > items (s)
THEN
s := i;
END IF;
END LOOP;
auxitem := items (s);
items (s) := items (r);
items (r) := auxitem;
x := (s - 1) * POWER (2, (24 - bitsize - (bitposition MOD 8)));
xasraw := UTL_RAW.SUBSTR (UTL_RAW.cast_from_binary_integer (x), 2, 3);
curent := FLOOR (bitposition / 8);
IF curent > 0
THEN
aux := UTL_RAW.copies ('00', curent);
ELSE
aux := NULL;
END IF;
aux := UTL_RAW.CONCAT (aux, xasraw);
RESULT := UTL_RAW.bit_or (RESULT, aux);
bitposition := bitposition + bitsize;
samesizeindex := samesizeindex + 1;
IF (samesizeindex > samesizecount)
THEN
BEGIN
samesizeindex := 1;
samesizecount := samesizecount * 2;
bitsize := bitsize + 1;
END;
END IF;
r := r - 1;
EXIT WHEN r <= 1;
NULL;
END LOOP;
还实现了一个从 PERMUTATION 列中提取排序信息的存储函数，其签名为
FUNCTION reversearrangecategoryitems (permutation IN
RAW, items IN rawtable)
RETURN rawtable
再次强调，实现此功能需要进行大量的位操作。
bitposition := 0;
bitsize := 1;
samesizecount := 1;
samesizeindex := 1;
cj := NULL;
RESULT := items;
r := 0;
LOOP
r := r + 1;
EXIT WHEN r > items.COUNT - 1;
curent := FLOOR (bitposition / 8);
xasraw := UTL_RAW.SUBSTR (permutation, curent + 1, 3);
MASK :=
CASE bitposition MOD 8
WHEN 0
THEN 'FFFFFF'
WHEN 1
THEN '7FFFFF'
WHEN 2
THEN '3FFFFF'
WHEN 3
THEN '1FFFFF'
WHEN 4
THEN '0FFFFF'
WHEN 5
THEN '07FFFF'
WHEN 6
THEN '03FFFF'
WHEN 7
THEN '01FFFF'
END;
xasraw := UTL_RAW.bit_and (xasraw, MASK);
x := UTL_RAW.cast_to_binary_integer (xasraw);
s := FLOOR (x / POWER (2, (24 - bitsize - (bitposition MOD 8))));
IF cj IS NULL
THEN
cj := auxvarray (s + 1);
ELSE
cj.EXTEND ();
cj (cj.COUNT) := s + 1;
END IF;
bitposition := bitposition + bitsize;
samesizeindex := samesizeindex + 1;
IF (samesizeindex > samesizecount)
THEN
BEGIN
samesizeindex := 1;
samesizecount := samesizecount * 2;
bitsize := bitsize + 1;
END;
END IF;
END LOOP;
r := cj.COUNT () + 1;
LOOP
r := r - 1;
EXIT WHEN r <= 0;
aux := items (cj (r));
RESULT (cj (r)) := RESULT (RESULT.COUNT - r + 1);
RESULT (RESULT.COUNT - r + 1) := aux;
END LOOP;
请注意，这些算法也可以用所选择的编程语言实现。我们用 PL/SQL 实现它们是为了展示它们可以在过程式语言中实现。
结论
本文试图提出一些能够解决关系数据库中经常出现的项目排序问题的方法。我们期待听到您对这些过程的意见。我们也鼓励任何可能有其他/更好方法的人与我们大家分享。