question

dr.lijenjin avatar image
dr.lijenjin asked

Reducing values in one table until reserves depleted in another - recursion?

Hello everyone,

I have two tables - let's call them dbo.ValuesToReduce and dbo.Reserve The data in the first table (dbo.ValuesToReduce) is:

ValuesToReduceId | PartnerId | Value
-------------------------------------
1                | 1         | 53.15
2                | 2         | 601.98
3                | 1         | 91.05
4                | 2         | 44.56
5                | 3         | 19.11

The second table (dbo.Reserve) looks like this

ReserveId | PartnerId | Value
-------------------------------
1         | 1         | -101.55
2         | 2         | -425.19
3         | 3         | -28.17

What I need to do is: update the Values in ValuesToReduce table using the latter table of Reserves, reducing the numbers until the reserve supply is exhausted. Here's what I should get after running the script:

ValuesToReduceId | PartnerId | Value
-------------------------------------
1                | 1         | 0.00
2                | 2         | 176.79
3                | 1         | 42.65
4                | 2         | 44.56
5                | 3         | 0.00


ReserveId | PartnerId | Value
-------------------------------
1         | 1         | 0.00
2         | 2         | 0.00
3         | 3         | -9.06

So basically, every partner has a "reserve" which he can deplete, and values in the value table should be reduced by partner accordingly if there is still something in the reserves. Reserves should be collocated in the order provided by ValuesToReduceId.

For partner with PartnerId of 1, you can see that he had enough reserve to update his first value to 0 and still had some left to reduce the second value by that amount.

Partner with ID of 2 had a reserve of 425.19, and there were two entries in the values table for that partner, 601.98 and 44.56, in that order (by ValuesToReduceId), so we only updated the first value since the reserve is not big enough for both. The wrong way would have been to update the second value to 0.00 and the first to 221.35.

Partner with ID of 3 has more than enough reserve, so after updating his value to 0, he's left with -9.06

I tried something with recursive cte, but I can't seem to get my head around it. Hope I described the problem clearly enough..

t-sqldynamicrecursion
1 comment
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Peso avatar image Peso commented ·
I think this calls for a standard FIFO algorithm.
0 Likes 0 ·
Matt Whitfield avatar image
Matt Whitfield answered

I don't think this is possible in a truly set based manner - because the fact that you have more than one PartnerID value in the ValuesToReduce table makes it an iterative process. Is there any way that you can re-factor such that PartnerID is unique in the values to reduce table? As that would make the problem much much simpler...

If not, then the way I would attack it is actually with a cursor (because it is an iterative process in it's nature). In fact, I would use two cursors, with logic roughly equivalent to:

Get cursor R for Reserves ordered by PartnerID
Get cursor V for ValuesToReduce ordered by PartnerID and Value descending

while R.ReadRow
begin
  if V.PartnerID <> R.PartnerID
  begin
    Read V until V.PartnerID = R.PartnerID
  end
  while R.Value <> 0 and R.PartnerID = V.PartnerID
    Subtract as much as possible from V, decrement R, update both
    Read V
  end
end

edit -> I really hope someone comes along with a set-based solution, however. I'd learn a lot from that.

10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

jjerome avatar image
jjerome answered

An interesting question, but I don't think you can do it with as a set-based solution. Even if you could, I'm not sure you would want to. Any solution you could come up with will almost certainly look a little crazy to the next guy that's got to support it.

Most old-school db guys would have already passed this off as something you should handle in your application rather than in the database. I don't exactly believe in hard-line rules, but in this case I think you either have to use your application or some cursors/loops to get the functionality you're looking for.

10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Adam Haines avatar image
Adam Haines answered

Here is a set based approach.

DECLARE @ValsToReduce TABLE(
ValsToReduceId INT,
PartnerID INT,
Value NUMERIC(9,2)
);

INSERT INTO @ValsToReduce VALUES (1,1,53.15);
INSERT INTO @ValsToReduce VALUES (2,2,601.98);
INSERT INTO @ValsToReduce VALUES (3,1,91.05);
INSERT INTO @ValsToReduce VALUES (4,2,44.56);
INSERT INTO @ValsToReduce VALUES (5,3,19.11);

DECLARE @Reserves TABLE(
ReserveId INT,
PartnerId INT,
VALUE NUMERIC(9,2)
);

INSERT INTO @Reserves VALUES (1,1,-101.55);
INSERT INTO @Reserves VALUES (2,2,-425.19);
INSERT INTO @Reserves VALUES (3,3,-28.17);

--Hold remainder values to update Reserves
Declare @Results TABLE(
ReserveId INT,
PartnerId INT,
Remainder NUMERIC(9,2)
);

;WITH cte
AS
(
SELECT [vtr].[ValsToReduceId],[vtr].[PartnerID],vtr.[Value] AS ValToReduce,r.[VALUE] AS Reserve
FROM @ValsToReduce vtr
INNER JOIN @Reserves r
ON [vtr].[PartnerID] = [r].[PartnerId]
)
UPDATE v1
SET Value = v2.New_Value
OUTPUT v2.[ValsToReduceId],v2.[PartnerId], v2.[Remainder] INTO @Results
FROM @ValsToReduce v1
INNER JOIN(
    SELECT
    	[t1].[ValsToReduceId],
    	[t1].[PartnerID],
    	[t1].[ValToReduce],
    	[t1].[Reserve],
    	CASE
    		WHEN MAX([t2].[ValsToReduceId]) IS NULL THEN 
    			CASE 
    				WHEN t1.Reserve + t1.[ValToReduce] < 0 
    				THEN 0
    				ELSE t1.Reserve + t1.[ValToReduce]
    			END
    		ELSE
    			CASE 
    				WHEN (t1.Reserve + SUM(t2.ValToReduce)) + t1.[ValToReduce] <= 0
    				THEN 0
    				WHEN (t1.Reserve + SUM(t2.ValToReduce)) > 0
    				THEN t1.[ValToReduce]
    			ELSE (t1.Reserve + SUM(t2.ValToReduce)) + t1.[ValToReduce]
    			END
    	END AS New_Value,
    	CASE	
    		WHEN  MAX([t2].[ValsToReduceId]) IS NULL AND t1.Reserve + t1.[ValToReduce] > 0
    		THEN 0
    		WHEN  MAX([t2].[ValsToReduceId]) IS NULL 
    		THEN t1.Reserve + t1.[ValToReduce]
    		WHEN t1.[Reserve] + SUM(t2.ValToReduce+t1.[ValToReduce]) > 0
    		THEN 0
    	ELSE t1.[Reserve] + SUM(t2.ValToReduce+t1.[ValToReduce]) 
    	END AS Remainder
    FROM cte t1
    LEFT JOIN cte t2
    	ON [t1].[ValsToReduceId] > [t2].[ValsToReduceId]
    		AND [t1].[PartnerID] = [t2].[PartnerID]
    GROUP BY
    	[t1].[ValsToReduceId],
    	[t1].[PartnerID],
    	[t1].[ValToReduce],
    	[t1].[Reserve]
) AS v2
    ON  [v1].[ValsToReduceId] = [v2].[ValsToReduceId]
    	AND [v1].[PartnerID] = [v2].[PartnerID]

UPDATE r
SET [VALUE] = v2.[Remainder]
FROM @Reserves r
INNER JOIN(
    SELECT 
    	[PartnerId],
    	[Remainder],
    	ROW_NUMBER() OVER(PARTITION BY PartnerID ORDER BY ReserveId DESC) AS seq
    from @Results
) AS v2
    ON  [r].[PartnerID] = [v2].[PartnerID]
WHERE v2.[seq] = 1

SELECT *
FROM @ValsToReduce

SELECT *
FROM @Reserves
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

dr.lijenjin avatar image
dr.lijenjin answered

Thanks guys. I ended up writing something similar to Andomar's solution here http://stackoverflow.com/questions/1564917/reducing-values-in-one-table-until-reserves-depleted-in-another-recursion

I'll try to optimize it and fiddle with it some more when I have more time, since it's an interesting problem.

10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Write an Answer

Hint: Notify or tag a user in this post by typing @username.

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.