递归SQL语句(Postgresql) -简化版本

Question

这是一个简单的问题，更复杂的张贴在这里：

Recursive SQL statement (PostgreSQL 9.1.4)

简化问题

如果您将上三角矩阵存储在3列(RowIndex、ColumnIndex、MatrixValue)中：

   ColumnIndex       
    1   2   3   4   5
1   2   2   3   3   4
2   4   4   5   6   X
3   3   2   2   X   X
4   2   1   X   X   X
5   1   X   X   X   X

X值将使用以下算法计算：

M[i,j] = (M[i-1,j]+M[i,j-1])/2
(i= rows, j = columns, M=matrix)

Example:
M[3,4] = (M[2,4]+M[3,3])/2
M[3,5] = (m[2,5]+M[3,4])/2

所需的全部结果是：

   ColumnIndex       
    1   2   3    4      5
1   2   2   3    3      4
2   4   4   5    6      5
3   3   2   2    4      4.5
4   2   1   1.5  2.75   3.625
5   1   1   1.25 2.00   2.8125

样本数据：

create table matrix_data (
    RowIndex integer,
    ColumnIndex integer,
    MatrixValue numeric);

    insert into matrix_data values (1,1,2);
    insert into matrix_data values (1,2,2);
    insert into matrix_data values (1,3,3);
    insert into matrix_data values (1,4,3);
    insert into matrix_data values (1,5,4);
    insert into matrix_data values (2,1,4);
    insert into matrix_data values (2,2,4);
    insert into matrix_data values (2,3,5);
    insert into matrix_data values (2,4,6);
    insert into matrix_data values (3,1,3);
    insert into matrix_data values (3,2,2);
    insert into matrix_data values (3,3,2);
    insert into matrix_data values (4,1,2);
    insert into matrix_data values (4,2,1);
    insert into matrix_data values (5,1,1);

这能办到吗？

Answer 1

测试设置：

CREATE TEMP TABLE matrix (
    rowindex integer,
    columnindex integer,
    matrixvalue numeric);

INSERT INTO matrix VALUES
 (1,1,2),(1,2,2),(1,3,3),(1,4,3),(1,5,4)
,(2,1,4),(2,2,4),(2,3,5),(2,4,6)
,(3,1,3),(3,2,2),(3,3,2)
,(4,1,2),(4,2,1)
,(5,1,1);

使用DO在循环中运行插入

DO $$
BEGIN

FOR i IN 2 .. 5 LOOP
   FOR j IN 7-i .. 5 LOOP
      INSERT INTO matrix
      VALUES (i,j, (
         SELECT sum(matrixvalue)/2
         FROM   matrix
         WHERE  (rowindex, columnindex) IN ((i-1, j),(i, j-1))
         ));
   END LOOP;
END LOOP;

END;
$$

见结果：

SELECT * FROM matrix order BY 1,2;

Answer 2

这可以在单个select语句中完成，但这只是因为不需要递归。我会概述解决方案。如果您确实想要SQL代码，请告诉我。

首先，请注意，唯一贡献和项目是沿对角线。现在，如果我们遵循值"4“在(1，5)中的贡献，它贡献4/2到(2,5)和4/4到(3,5)和4/8到(4,5)。每次贡献减半，因为(a+b)/2是(a/2 + b/2)。

当我们扩展它时，我们开始看到一个类似于Pascal三角形的模式。实际上，对于下三角矩阵中的任何给定点(在下面有值)，您可以找到对角元素的贡献值。将一条垂直线延伸到对角线上，一条水平线到达对角线。这些是对角线行的贡献者。

他们贡献了多少？所以我们可以去帕斯卡的三角形。对于我们有值的第一个对角线，贡献为(1,1)/2，对于第二对角线，(1,2,1)/4，对于第三，(1,3,3,1)/8。。。诸若此类。

幸运的是，我们可以使用一个公式(组合学中的“选择”函数)来计算每个值的贡献。2的力量是容易的。而且，确定一个给定的单元格离对角线有多远并不太难。

所有这些都可以组合成一个Postgres SQL语句。不过，@Erwin的解决方案也有效。如果他的解决方案不能满足您的需要，我只想把精力放在调试语句上。

Answer 3

..。下面是具有多个嵌入式CTE (Tm)的递归CTE：

DROP SCHEMA tmp CASCADE;
CREATE SCHEMA tmp ;
SET search_path=tmp;

CREATE TABLE matrix_data (
    yyy integer,
    xxx integer,
    val numeric);

    insert into matrix_data (yyy,xxx,val) values
      (1,1,2) , (1,2,2) , (1,3,3) , (1,4,3) , (1,5,4)
    , (2,1,4) , (2,2,4) , (2,3,5) , (2,4,6)
    , (3,1,3) , (3,2,2) , (3,3,2)
    , (4,1,2) , (4,2,1)
    , (5,1,1)
        ;

WITH RECURSIVE rr AS (
        WITH xx AS (
                SELECT MIN(xxx) AS x0
                , MAX(xxx) AS x1
                FROM matrix_data
                )
        , mimax AS (
                SELECT generate_series(xx.x0,xx.x1) AS xxx
                FROM xx
                )
        , yy AS (
                SELECT MIN(yyy) AS y0
                , MAX(yyy) AS y1
                FROM matrix_data
                )
        , mimay AS (
                SELECT generate_series(yy.y0,yy.y1) AS yyy
                FROM yy
                )
        , cart AS (
                SELECT * FROM mimax mm
                JOIN mimay my ON (1=1)
                )
        , empty AS (
                SELECT * FROM cart ca
                WHERE NOT EXISTS (
                        SELECT *
                        FROM matrix_data nx
                        WHERE nx.xxx = ca.xxx
                        AND nx.yyy = ca.yyy
                        )
                )
        , hot AS (
                SELECT * FROM empty emp
                WHERE EXISTS (
                        SELECT *
                        FROM matrix_data ex
                        WHERE ex.xxx = emp.xxx -1
                        AND ex.yyy = emp.yyy
                        )
                AND EXISTS (
                        SELECT *
                        FROM matrix_data ex
                        WHERE ex.xxx = emp.xxx
                        AND ex.yyy = emp.yyy -1
                        )
                    )
        -- UPDATE from here:
        SELECT h.xxx,h.yyy, md.val / 2 AS val
        FROM hot h
        JOIN matrix_data md ON
                (md.yyy = h.yyy AND md.xxx = h.xxx-1)
                OR (md.yyy = h.yyy-1 AND md.xxx = h.xxx)
        UNION ALL
        SELECT e.xxx,e.yyy, r.val / 2 AS val
        FROM empty e
        JOIN rr r ON ( e.xxx = r.xxx+1 AND e.yyy = r.yyy)
                OR ( e.xxx = r.xxx AND e.yyy = r.yyy+1 )
        )
INSERT INTO matrix_data(yyy,xxx,val)
SELECT DISTINCT yyy,xxx
        ,SUM(val)
FROM rr
GROUP BY yyy,xxx
        ;

SELECT * FROM matrix_data
        ;

新结果：

NOTICE:  drop cascades to table tmp.matrix_data
DROP SCHEMA
CREATE SCHEMA
SET
CREATE TABLE
INSERT 0 15
INSERT 0 10
 yyy | xxx |          val           
-----+-----+------------------------
   1 |   1 |                      2
   1 |   2 |                      2
   1 |   3 |                      3
   1 |   4 |                      3
   1 |   5 |                      4
   2 |   1 |                      4
   2 |   2 |                      4
   2 |   3 |                      5
   2 |   4 |                      6
   3 |   1 |                      3
   3 |   2 |                      2
   3 |   3 |                      2
   4 |   1 |                      2
   4 |   2 |                      1
   5 |   1 |                      1
   2 |   5 |     5.0000000000000000
   5 |   5 | 2.81250000000000000000
   4 |   3 | 1.50000000000000000000
   3 |   5 | 4.50000000000000000000
   5 |   2 | 1.00000000000000000000
   3 |   4 | 4.00000000000000000000
   5 |   3 | 1.25000000000000000000
   4 |   5 | 3.62500000000000000000
   4 |   4 | 2.75000000000000000000
   5 |   4 | 2.00000000000000000000
(25 rows)