1

给定下表：

create table tree
(
    id int,
    parent_id int REFERENCES tree(id),
    operator varchar,
    primary key(id)
);

insert into tree values
(1, null, 'AND'),
(2, 1, 'NOT'),
(3, 1, 'OR'),
(4, 2, 'AND'),
(5, 3, 'Y'),
(6, 3, 'Z'),
(7, 4, 'K'),
(8, 4, 'OR'),
(9, 8, 'X'),
(10, 8, 'A'),
(11, 8, 'B')
;

我如何计算最终的 AST：AND(NOT(AND(K, OR(X, A, B))), OR(Y, Z))

我尝试了使用递归 CTE 的不同方法，但我的问题是 CTE 既不允许在 CTE 的递归部分进行聚合，也不允许在使用 CTE 的子查询中进行聚合。

我尝试的最新方法是：

with RECURSIVE tree1(id, parent_id, operator, n, cc) as (
    select t.*, 0, cc.cc 
    from tree t, lateral(select count(*) as cc from tree tt where tt.parent_id = t.id) cc 
    where t.parent_id is null
    union ALL
    select t.*, n + 1, cc.cc
    FROM tree t INNER JOIN tree1 a on t.parent_id = a.id, lateral(select count(*) as cc from tree tt where tt.parent_id = t.id) cc
), tree2(id, parent_id, operator, n, cc) AS (
    select t.id, t.parent_id, t.operator, t.n, t.cc
    from tree1 t
    where t.n = (select max(n) from tree1)
    union (
        select p.id, p.parent_id, p.operator || '(' || string_agg(c.operator, ', ') || ')' as operator, p.n, p.cc
        from tree1 p, tree2 c
        where p.id = c.parent_id
        group by p.id, p.parent_id, p.operator, p.n, p.cc
        union
        select p.id, p.parent_id, p.operator, p.n, p.cc
        from tree1 p, tree2 c 
        where p.cc = 0 and p.n + 1 = c.n
    )
)
select * from tree2

但由于 CTE 的限制，它不起作用。

文档说 CTE 是图灵完备的，但我找不到计算所需结果的方法。我是否遗漏了什么或者我对图灵完整性的理解是错误的？:)

（我有 Postgres 9.6）

4

0 回答 0