循环标签系统

有趣片段

循环标签系统

适用于 PostgreSQL

8.4

用以下语言编写

SQL

依赖于

无

此 SQL 查询（需要 PostgreSQL 8.4）构成了一个循环标签系统（wikipedia），足以证明 SQL 是图灵完备的。它完全用符合 SQL:2003 标准的 SQL 编写。

感谢 Andrew (RhodiumToad) Gierth，他提出了这个概念并编写了代码。

这些生成式规则在表 “p” 中以如下方式编码

  "iter" is the production number;
  "rnum" is the index of the bit;
  "tag" is the bit value.

此示例使用以下生成式规则

    110 01 0000

初始状态在非递归联合分支中编码，在本例中仅为 '1'

mod(r.iter, n) 子表达式编码生成式规则的数量，它可以大于表 “p” 的大小，因为空生成式规则未包含在表中。

参数

    the content of "p"
    the content of the non-recursive branch
    the 3 in mod(r.iter, 3)

“p” 编码生成式规则；非递归分支是初始状态，而 3 是规则数量。

每一级结果都以每行 1 位的位串形式编码，其中 rnum 是位数的索引。

在每次迭代中，将移除位 0，并将剩余位向上移一位，并且当且仅当位 0 为 1 时，当前生成式规则的内容将附加到字符串的末尾。

WITH RECURSIVE
p(iter,rnum,tag) AS (
    VALUES (0,0,1),(0,1,1),(0,2,0),
           (1,0,0),(1,1,1),
           (2,0,0),(2,1,0),(2,2,0),(2,3,0)
),
r(iter,rnum,tag) AS (
    VALUES (0,0,1)
UNION ALL
    SELECT r.iter+1,
           CASE
               WHEN r.rnum=0 THEN p.rnum + max(r.rnum) OVER ()
               ELSE r.rnum-1
           END,
           CASE
               WHEN r.rnum=0 THEN p.tag
               ELSE r.tag
           END
    FROM
        r
    LEFT JOIN p
        ON (r.rnum=0 and r.tag=1 and p.iter=mod(r.iter, 3))
    WHERE
        r.rnum>0
    OR p.iter IS NOT NULL
)
SELECT iter, rnum, tag
FROM r
ORDER BY iter, rnum;