x

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..

more ▼

asked Oct 14, 2009 at 05:08 AM in Default

dr.lijenjin gravatar image

dr.lijenjin
37 1 1 2

I think this calls for a standard FIFO algorithm.
Oct 15, 2009 at 04:57 PM Peso
(comments are locked)
10|1200 characters needed characters left

4 answers: sort voted first

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
more ▼

answered Oct 15, 2009 at 04:23 PM

Adam Haines gravatar image

Adam Haines
91 1

Nice! Vote up...
Oct 15, 2009 at 04:41 PM Matt Whitfield ♦♦
Just what I was looking for. Thanks!
Oct 21, 2009 at 05:51 AM dr.lijenjin
(comments are locked)
10|1200 characters needed characters left

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.

more ▼

answered Oct 14, 2009 at 10:05 AM

Matt Whitfield gravatar image

Matt Whitfield ♦♦
29.4k 61 65 87

Interesting.. I was thinking something along that line. The premise of the problem can actually be altered much if we say that Reserves table doesn't have to be updated as long as you can guarantee that the values in the Values table will be correctly reduced (minding the reserve for that partner which doesn't have to be permanantly altered). But anyway, I don't have any more time for this at the moment so I'll have to use the solution at hand, and then play with it when I get more time. Thanks
Oct 15, 2009 at 03:56 AM dr.lijenjin
Matt: I am almost certain that a pure, set-based solution can be devised, it just won't perform well because the optimizer will implement it as an O(n^2) or worse.
Oct 18, 2009 at 02:56 PM RBarryYoung
oops. Yes, like Adam's
Oct 18, 2009 at 02:56 PM RBarryYoung
Oh, and it's certainly easy enough to do with a quirky update, but I don't count that as "pure set-based", only "semi set-based".
Oct 18, 2009 at 03:01 PM RBarryYoung
Barry - I look forward to the day that I can approach a problem like this with your level of knowledge!
Oct 18, 2009 at 04:49 PM Matt Whitfield ♦♦
(comments are locked)
10|1200 characters needed characters left

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.

more ▼

answered Oct 14, 2009 at 03:52 PM

jjerome gravatar image

jjerome
191

This particular problem had to be solved in pure SQL due to constraints my DBA's have set. I can't use CLR, and this code is a part of a much much larger and complex stored procedure. I used a while loop in the end. Thanks
Oct 15, 2009 at 04:01 AM dr.lijenjin
(comments are locked)
10|1200 characters needed characters left

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.

more ▼

answered Oct 15, 2009 at 03:50 AM

dr.lijenjin gravatar image

dr.lijenjin
37 1 1 2

(comments are locked)
10|1200 characters needed characters left
Your answer
toggle preview:

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

New code box

There's a new way to format code on the site - the red speech bubble logo will automatically format T-SQL for you. The original code box is still there for XML, etc. More details here.

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

SQL Server Central

Need long-form SQL discussion? SQLserverCentral.com is the place.

Topics:

x986
x51
x21

asked: Oct 14, 2009 at 05:08 AM

Seen: 1668 times

Last Updated: Oct 15, 2009 at 05:40 AM