sql - 最小传输Sql查询

Question

我有两个表，我需要用表 1 sending_qty 的最小移动来满足表 2 Need_qty。

表一

sending_QTY STORE_ID_A
30           30105
16           21168
10           21032
9            30118
6            30011
5            21190
2            21016

表2

Need_QTY    STORE_ID_B
15           21005
10           30019
11           21006
16           30001
11           21015
7            21004

预期输出

STORE_ID_A |STORE_ID_B |TRANSFERRED_QTY_FROM_A |
-----------|-----------|-----------------------|
30105      |21005      |15                     |
30105      |30019      |10                     |
30105      |21006      |5                      |
21168      |21006      |6                      |
21168      |30001      |10                     |
21032      |30001      |6                      |
21032      |21015      |4                      |
30118      |21015      |7                      |
30118      |21004      |2                      |
30011      |21004      |5                      |

还有其他几种组合可以实现这一点，但我需要找到最小可能的转移，以便表 2 need_qty 得到填满 有什么方法可以在不通过程序的情况下实现这一目标？

到目前为止，我已经尝试通过交叉连接来查找组合，但没有太大帮助

Answer 1

这可以通过使用包含整数分区的辅助表使用常规 SQL 来解决。为了这个例子，我们假设这个辅助表有三列:partitions、rank 和 number。对于任何给定的数字，都会有几行可能的分区，每个分区都有其等级。如果数字为 5，则从该表中选择数字为 5 的所有行将显示:

partitions          rank        number
5                   1           5
4, 1                2           5
3, 2                2           5
3, 1, 1             3           5
2, 2, 1             3           5
2, 1, 1, 1          4           5
1, 1, 1, 1, 1       5           5

等级是行中使用的分区数，它对于您提供的问题很重要，因为它允许我们选择最小传输。

对于数字 5，我们有 7 行表示分区。对于更大的数字，返回的行数会更高——数字 12 将有 77 个分区! - 但在我们使用数据库的规模中，这个辅助分区表很容易查询数字 1 到 99，例如提供的示例。更高的数字是可扩展性的问题。

如果您想要创建这样一个表的说明，我很乐意为您提供 - 但由于这是一个漫长的解决方案，我们现在暂时搁置辅助表的生成。

让我们看一下商店 ID A，它有要发送的数量。它们的数量是:

30
16
10
9
6
5
2 

对于每个商店数量，我们可以查询分区辅助表，并获得该数量的各个分区及其排名。然后我们可以创建自己的分区组合。例如，30 将带来许多行，其中之一是:

partitions         rank         number
15,10,5            3            30

10 将带来许多其他的东西:

partitions         rank         number
6,4                2            10

您可以通过结果之间的交叉连接构建所有可能候选者的笛卡尔积，并且对于该产品的每一行，分区按升序排列，等级为分区等级的总和。

另一方面，您的商店 ID B 需要数量。您只需进行完全相同的处理，最后得到另一个相当大的排名有序分区的笛卡尔积。恭喜你取得了这么大的成就。

现在，您只需要查看 Store ID B 分区集合完全包含在 Store ID A 分区集合中的分区行。这会将大型集合大大缩减为几行潜在的传输。商店 ID B 中的其中一行(给出上面的示例)将是:

partitions                     rank
15,10,10,7,6,6,5,5,4,2         10

由于它同时出现在商店 ID A 和商店 ID B 中。在商店 ID A 中，它将是以下内容的组合:

30 = 15,10,5     rank 3
16 = 10,6        rank 2
10 = 6,4         rank 2
9  = 7,2         rank 2
6  = 5,1         rank 2
5  = 5           rank 1
2  = 2           rank 1

给你线路:

partitions                     rank
15,10,10,7,6,6,5,5,5,4,2,2,1   13

最后一步是选择 Store ID B 上排名最低的行。这将是最少的传输次数，您可以像上面那样输出它。

走到这一步的奖励:如果您想看看我们是否可以完全耗尽商店 ID A 的整个库存(而不是满足商店 ID B)，请反转包含关系:确保分区集合 A 完全包含在分区集合中B. 要查看将每个项目从 A 准确移动到 B 以满足 B 并耗尽 A 的最小转移，请在两个集合中查找相同的分区。

和一些实际的 SQL 来模拟算法，至少部分是:

-- this function handles the sorting. It's not necessary but it help make the result look better.
WITH
FUNCTION SORT_PARTITIONS(p_id IN VARCHAR2) RETURN VARCHAR2 IS
result VARCHAR2(100);
BEGIN   
  select rtrim(XMLAGG(XMLELEMENT(E,str||',')).EXTRACT('//text()'),',') into result  
from (
with temp as  (
   select p_id num from dual       
 )
SELECT   trim(regexp_substr(str, '[^,]+', 1, level)) str
FROM (SELECT num str FROM temp) t
CONNECT BY instr(str, ',', 1, level - 1) > 0
order by to_number(str)
);
return result;
END;
-- this function handles containment - when we want to fulfil store ID B, and not necessarily deplete store ID A, or visa-versa.
FUNCTION PARTITION_CONTAINED(seta_partition IN VARCHAR2, setb_partition IN VARCHAR2) RETURN NUMBER IS
result NUMBER;
BEGIN
 with seta as 
(select str, count(str) cnt from (
SELECT trim(regexp_substr(str, '[^,]+', 1, level)) str
FROM (SELECT num str FROM (select SETA_PARTITION num from dual)) t
CONNECT BY instr(str, ',', 1, level - 1) > 0)
group by str),
setb as 
(select str, count(str) cnt from (
SELECT trim(regexp_substr(str, '[^,]+', 1, level)) str
FROM (SELECT num str FROM (select SETB_PARTITION num from dual)) t
CONNECT BY instr(str, ',', 1, level - 1) > 0)
group by str),
lenab as (select count(1) strab from seta, setb where seta.str=setb.str and seta.cnt>=setb.cnt),
lenb as (select count(1) strb from setb)
select strb-strab into result from lenb,lenab;
RETURN result;
END;
-- this store_a simply represents a small Cartesian product of two stores from the stores ID A table - one with quantity 5, the other with quantity 4. I found this was easier to set up. 
store_a as (select SORT_PARTITIONS(n1||','||n2) partitions_sending, rank1+rank2 rank_sending from (select num_partitions n1, rank rank1 from n_partitions where num=5),(select num_partitions n2, rank rank2 from n_partitions where num=4)),

-- this store_b represents the stores ID B's Cartesian product of partitions, again for simplicity. The receiving quantities are 3, 3 and 3.
store_b as (select SORT_PARTITIONS(n1||','||n2||','||n3) partitions_receive, rank1+rank2+rank3 rank_receive from (select num_partitions n1, rank rank1 from n_partitions where num=3),(select num_partitions n2, rank rank2 from n_partitions where num=3),(select num_partitions n3, rank rank3 from n_partitions where num=3))

-- and finally, the filtering that provides all possible transfers - with both "=" (which works for deplete and fulfil) and "partition_contained" which allows for fulfil or deplete. You can choose to leave both or just use partition contained, as it is more flexible.
SELECT * from store_a, store_b where store_a.partitions_sending=store_b.partitions_receive or partition_contained(store_a.partitions_sending,store_b.partitions_receive)=0 order by store_b.rank_receive, store_a.rank_sending asc;