sql - 限制二元组中元素出现的次数

Question

我正试图在 SQL(或 postgresql 9.4)中为以下问题找到一个基于集合的查询解决方案:

我有一组有限的唯一二元组 (x ∈ N, y ∈ N)，它们具有指定的等级。

现在我想删除所有的元组，使剩余的元组满足以下条件:

1. 每个数字在元组的左侧最多出现 n 次，并且
2. 每个数字在右侧最多出现 m 次。

这很容易通过迭代有序元组并计算每个元素出现次数的过程来实现。但是，我想知道是否有单个 (postgre)SQL 查询的解决方案？

为了更具体，请考虑以下 n=2、m=2 的简单示例:

╔═══╦═══╦══════╗
║ x ║ y ║ rank ║
╠═══╬═══╬══════╣
║ 1 ║ 4 ║    1 ║
║ 2 ║ 4 ║    2 ║
║ 3 ║ 4 ║    3 ║
║ 3 ║ 5 ║    4 ║
║ 3 ║ 6 ║    5 ║
║ 3 ║ 7 ║    6 ║
╚═══╩═══╩══════╝

现在我们正在寻找返回以下元组作为结果的查询:(1,4)、(2,4)、(3,5)、(3,6)

表和值的 SQL fiddle :

   create table tab (
     x bigint,
     y bigint,
     rank bigint);

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

我尝试了一种使用 postgres 窗口函数的方法，它解决了上面的例子，但我不确定它是否能找到与其他例子的基于游标的方法一样多的对。

    SELECT x, y FROM (
      SELECT x, y, ROW_NUMBER() OVER (PARTITION BY x ORDER BY rank) AS rx FROM (
        SELECT x, y, rank, ROW_NUMBER() OVER (PARTITION BY y ORDER BY rank) AS ry FROM tab) AS limitY
      WHERE limitY.ry < 3) AS limitX
    WHERE limitX.rx < 3

Answer 1

这是使用单个窗口函数传递的变体(可能更快):

select x, y, rank
from (
  select *, count(*) over (partition by x order by rank) as cx,
            count(*) over (partition by y order by rank) as cy
  from tab
  order by rank
  ) t
where cx < 3 and cy < 3;

还有递归 CTE 方法:

-- use tab directly instead of tabr CTE (and replace all ocurrences of r column with rank)
-- if rank is trusted to be sequential uninterrupted starting with 1
with recursive
  r (r, x, y, rank, cx, cy) as (
    select *, 1 as cx, 1 as cy
    from tabr where r = 1
    union all
    select t.*, case when r.x = t.x then r.cx + 1 else 1 end as cx, case when r.y = t.y then r.cy + 1 else 1 end as cy
    from r, tabr t
    where t.r = r.r + 1
    ),
  tabr as (
    select row_number() over () as r, *
    from tab
    order by rank
    )
select x, y, rank
from r
where cx <= 2 and cy <= 2
order by r;