递归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 v alues是使用以下算法计算：

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); 

运行的INSERT在一个循环中与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

这可以在一个SQL SELECT语句来完成，但只是因为递归没有必要。我将概述解决方案。如果你真的想要SQL代码，请告诉我。

首先，请注意，唯一对总和有贡献的项目是沿着对角线的。现在，如果我们遵循（1，5）中的值“4”的贡献，它对（2,5）和4/4对（3,5）和4/8对（4,5）贡献4/2 ）。因为（a + b）/ 2是（a/2 + b/2），所以每次贡献被减半。

当我们扩展这个时，我们开始看到一个类似于帕斯卡三角形的模式。实际上，对于下三角矩阵中的任何给定点（下面有值的地方），您可以找到对该值有贡献的对角元素。向上延伸一条垂直线以击中对角线和水平线以击中对角线。那些是对角线的贡献者。

他们贡献多少？那么，为此我们可以去帕斯卡的三角形。对于我们有价值的第一个对角线，贡献是（1,1）/ 2。对于第二个对角线，（1,2,1）/ 4。第三，（1,3,3,1）/ 8。 。 。等等。

幸运的是，我们可以使用公式计算每个值的贡献（combinatorics中的“选择”函数）。 2的力量很容易。而且，确定一个给定的细胞距对角线的距离并不算太大。

所有这些都可以合并成一个Postgres SQL语句。然而，@ Erwin的解决方案也可行。如果他的解决方案不能满足您的需求，我只想将这些努力投入到调试声明中。

Answer 3

...这里谈到的递归CTE为带多个嵌入式的CTE（TM）：

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) 

Answer 4

while (select max(ColumnIndex+RowIndex) from matrix_data)<10 
begin 
     insert matrix_data 
     select c1.RowIndex, c1.ColumnIndex+1, (c1.MatrixValue+c2.MatrixValue)/2 
     from matrix_data c1 
      inner join 
      matrix_data c2 
      on c1.ColumnIndex+1=c2.ColumnIndex and c1.RowIndex-1 = c2.RowIndex 
     where c1.RowIndex+c1.ColumnIndex=(select max(RowIndex+ColumnIndex) from matrix_data) 
     and c1.ColumnIndex<5 
end