Ken Henderson's WebLog

TSQL coding challenge

Today’s entry is another T-SQL puzzle. Steve Kass took the prize for the best solution to my last T-SQL puzzle, and several others came up with some pretty original solutions of their own. I especially liked the ones that were T-SQL specific – ones that weren’t translated from other languages.

Today’s challenge is to detect whether a cross-row relationship that exists in a particular table has been corrupted. The scenario is this:

You have a table of employee-to-mentor relationships that looks like this:

CREATE TABLE Employees

(EmpId int PRIMARY KEY,

Mentor int REFERENCES Employees(EmpId)

)

Every employee has exactly one mentor and every mentor has exactly one associated employee. The company's first employee, the CEO, has no mentor, so her mentor column is NULL.  Here's what a simplified version of the table might look like:

INSERT Employees VALUES (0,NULL)

INSERT Employees VALUES (1,0)

INSERT Employees VALUES (2,1)

INSERT Employees VALUES (3,2)

INSERT Employees VALUES (4,3)

INSERT Employees VALUES (5,4)

INSERT Employees VALUES (6,5)

INSERT Employees VALUES (7,6)

INSERT Employees VALUES (8,7)

INSERT Employees VALUES (9,8)

The most recently added employee doesn’t mentor anyone for obvious reasons. His employee number is tracked in a separate table so that it is readily available as a mentor when another employee is added. When a new employee joins, he is assigned the employee that was previously the last employee as his mentor, regardless of his or her title or rank in the company. There is otherwise no relationship between the rows in the table, and, in particular, employee numbers are not necessarily sequential or related in any way.

The company that uses this table has a stored proc that runs on a nightly basis, determines who is mentoring whom, and, using singleton SELECTs, returns the complete list of mentor-employee pairs beginning with the mostly recently added employee (whose ID is cached in a separate table) and working up to the CEO. The Employee table is so huge that it doesn't attempt to store these relationships anywhere; it just returns each one using simple PRINT commands as it determines them. Due to a bug in the app that updates the table when an employee leaves and a lack of RI on the table itself, the relationships between the employees and mentors occasionally become corrupted. Specifically, an employee higher up in the chain erroneously has his mentor set to someone lower in the chain. In other words, his Mentor column is being set to someone being mentored (perhaps indirectly) by him.

The net effect of this is that the stored procedure that returns the mentor-employee pairs gets stuck in an infinite loop. It never reaches the CEO because the relationship chain leading to her is broken. Here's the code for the proc and a function it uses:

CREATE FUNCTION dbo.Mentor(@EmpId int)

RETURNS int

AS BEGIN

      RETURN (SELECT Mentor FROM Employees WHERE EmpId=@EmpId)

END

GO

CREATE PROC ListMentors(@LastEmpIdAdded int) AS

DECLARE @i int

SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)

PRINT 'Employee: '+CAST(@i AS varchar(10))

SELECT @i = dbo.Mentor(@i)

PRINT 'Mentor: '+CAST(@i AS varchar(10))

WHILE (@i IS NOT NULL)

BEGIN

      PRINT 'Employee: '+CAST(@i AS varchar(10))

      SELECT @i = dbo.Mentor(@i)

      PRINT 'Mentor: '+CAST(@i AS varchar(10))

END

And here's some code to simulate the buggy app by intentionally breaking one of the mentor-employee relationships in the sample table:

UPDATE Employees SET Mentor = 7 WHERE EmpId=5

If you run the proc against the sample table after running the above UPDATE, it will get stuck in an infinite loop:

EXEC ListMentors 9 -- 9 is the ID of the last employee added (known in advance)

Your task is to change the proc's singleton SELECT code so that it can detect this type of corruption in the mentor-employee relationships as it traverses the table and return an error message rather than get stuck in an infinite loop. Some rules of the game:

1. Because the company is huge and space on the system is limited, you can’t store values from the Employee table elsewhere (either at the client or on the server, on disk or in memory).

2. For the same reason and because of permissions issues, you can’t modify the table in any way or create any other tables or objects.

3. Your code must run on both SQL Server 2000 and SQL Server 2005.

4. You can't replace the proc's singleton SELECT code with set-oriented code. The company has its reasons for using singleton SELECT logic here, and it's your job to modify the singleton SELECT loop to avoid running infinitely, not rewrite it. This includes changing the logic in the Mentor function.  In fact, you can't change the Mentor function at all.  Your alterations must be limited to the proc.

5. To keep this interesting, you can't use techniques that rely on counting the number of employees or mentors in advance. For purposes of this exercise, you have no way of knowing how many employees, mentors, or rows are in the table or that meet a particular set of criteria. There may be 10,000 or there may be 10,000,000 -- you have no way of knowing and can't use COUNT() or anything similar to tell you.

6. Because I’ve discussed this with various MS people, if you work for MS (or ever have), you can’t play J

Happy Coding!
Published Friday, February 03, 2006 2:59 PM by khen1234

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

umccullough said:

I must have missed something... Does this do it?

IF EXISTS
(
SELECT
E1.*
FROM
Employees E1
LEFT JOIN Employees E2 ON
E1.Mentor = E2.EmpID
WHERE
E1.Mentor IS NOT NULL AND
E2.EmpID IS NULL
)
BEGIN
RAISERROR('Something Bad Happened',1,1)
END
February 3, 2006 8:08 PM
 

umccullough said:

It would appear that your example table doesn't allow deletion of an employee record where another employee record has a reference to it as a mentor. Did you mean to add the foreign key constraint to the example?
February 3, 2006 8:45 PM
 

khen1234 said:

Yes, I meant to add it as an FK constraint. You simply adjust the mentor reference to another employee (the mentor of the employee about to be deleted) before deleting a mentor. It is, in fact, a bug in the app that handles this that causes the corrupt relationship chain.

Also, your query doesn't detect the condition I'm describing. Here's some sample data that demonstrates the corrupt chain:

INSERT Employees VALUES (0,NULL)

INSERT Employees VALUES (1,0)

INSERT Employees VALUES (2,1)

INSERT Employees VALUES (3,2)

INSERT Employees VALUES (4,3)

INSERT Employees VALUES (5,4)

select * from Employees

update Employees set Mentor = 5 where EmpId=2

select * from Employees

February 3, 2006 11:21 PM
 

umccullough said:

Ok, as I originally suspected, I wasn't understanding.

Too bad also - since I had cooked up 4 additional methods to detect a missing record to find the lowest-cost method.

Yes, this scenario definitely increases the difficulty :)
February 4, 2006 12:16 AM
 

khen1234 said:

I've revised the post to make this a bit more obvious and to provide some examples that are a bit more concrete rather than leaving so much to the imagination.  Hopefully, it makes more sense now.
February 5, 2006 2:57 AM
 

pkr171 said:

My quick solution is to change the function to aviod looping

CREATE FUNCTION dbo.Mentor(@EmpId int)

RETURNS int

AS BEGIN

     RETURN (SELECT Mentor FROM Employees WHERE EmpId=@EmpId and 2 > select count(*) from employee where Mentor=@Empid)

END

GO

This solution will ensure that the proc doesn't loop, but it doesn't issue error message for corrupted link.

Let me think more on this.

February 5, 2006 11:03 AM
 

khen1234 said:

pkr171:  See rule #5 -- you can't use COUNT() to determine the number of employees, mentors, or rows in any way :-)
February 5, 2006 11:07 AM
 

rockmoose said:

Hi,

I don't know if this is invalidated under rule #5 (similar to COUNT())

ALTER PROC ListMentors(@LastEmpIdAdded int) AS

/* Check the validity of the hierarchy */
if( select nullif(checksum_agg(EmpId),checksum_agg(coalesce(Mentor,@LastEmpIdAdded)))
from employees) is not null
begin
raiserror('Bad hierarchy',16,1)
return 50000
end
/* end check */

DECLARE @i int
SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)
PRINT 'Employee: '+CAST(@i AS varchar(10))
SELECT @i = dbo.Mentor(@i)
PRINT 'Mentor: '+CAST(@i AS varchar(10))
WHILE (@i IS NOT NULL)
BEGIN
     PRINT 'Employee: '+CAST(@i AS varchar(10))
     SELECT @i = dbo.Mentor(@i)
     PRINT 'Mentor: '+CAST(@i AS varchar(10))
END

Regards
February 5, 2006 2:28 PM
 

Louie said:

One fact we know is that MentorID(aka EmpID) has to be smaller than EmpID. So the maximum number of times the while loop getting executed should be less than @LastEmpIdAdded


CREATE PROC ListMentors(@LastEmpIdAdded int)
AS

DECLARE @i int

SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)

PRINT 'Employee: ' + CAST(@i AS varchar(10))

SELECT @i = dbo.Mentor(@i)

PRINT 'Mentor: ' + CAST(@i AS varchar(10))

declare @count int
select @count = 0

WHILE (@i IS NOT NULL)
BEGIN
PRINT 'Employee: ' + CAST(@i AS varchar(10))

SELECT @i = dbo.Mentor(@i)

PRINT 'Mentor: ' + CAST(@i AS varchar(10))

select @count = @count + 1
if @count > @LastEmpIdAdded
begin
raiserror('Error.', 1, 1)
return @i
end
END

return @count
go
February 5, 2006 11:55 PM
 

Dis4ea said:

I'm probably looking at it too simple but here it goes :-)

DECLARE @Mentor int

 SELECT @Mentor = Mentor FROM Employees WHERE EmpId=@EmpId

 IF (@Mentor >= @EmpID)
 BEGIN
 SET @Mentor = -1
 END

 RETURN @Mentor

You could then check to see if the returned Mentor is -1 to return an error in the SP.  Or is this not allowed either?
February 6, 2006 3:02 AM
 

khen1234 said:

There's no relationship between the integer values of the mentor IDs and the emp IDs.  The IDs come from outside the system, and it's conceivable that a mentor ID might be a bigger integer than his emp ID.
February 6, 2006 3:10 AM
 

Ennor said:

khen1234 said:
There's no relationship between the integer values of the mentor IDs and the emp IDs.

There must be. At least they must come from one source. Imagine that one of them is an IDENTITY(1,1), and another is IDENTITY(1000000000,1). In such a case original code doesn't need a buggy influention - it will not work by itself.
February 6, 2006 4:22 AM
 

David said:

CREATE FUNCTION dbo.Mentor(@EmpId int)
RETURNS int
AS BEGIN
 RETURN (
   SELECT COALESCE(-x.Mentor,-y.Mentor,e.Mentor) AS [Mentor]
   FROM Employees e
   LEFT OUTER JOIN Employees x ON x.Mentor=e.Mentor AND x.EmpID<>e.EmpID
   LEFT OUTER JOIN Employees y ON y.EmpID=e.EmpID AND y.EmpID=y.Mentor
   WHERE e.EmpId=@EmpId
   )
END
GO

CREATE PROC ListMentors(@LastEmpIdAdded int) AS
DECLARE @i int
SET @i = @LastEmpIdAdded
WHILE (@i IS NOT NULL)
BEGIN
 PRINT 'Employee: '+CAST(@i AS varchar(10))
 SELECT @i = dbo.Mentor(@i)
 IF @i < 0
   BEGIN
   RAISERROR('Mentor Error',16,1)
   BREAK
   END
 PRINT 'Mentor: '+CAST(@i AS varchar(10))
END
GO
February 6, 2006 6:59 AM
 

Sarus said:

What do you think about this?


CREATE FUNCTION dbo.Mentor(@EmpId int) RETURNS int
-- If return value is -1 then there should be an RAISERROR in the calling procedure
AS BEGIN
RETURN (
  select case when count(*) = 1 then Mentor else -1 end
     from Employees
     where Mentor in (select Mentor from Employees where EmpId = @EmpId)
     group by Mentor
     --  having count(*) = 1  -- to stop the looping without any error
  )
END
GO
February 6, 2006 7:09 AM
 

Dis4ea said:

I think David won :-)
February 6, 2006 7:29 AM
 

khen1234 said:

Ennor said:

"khen1234 said:
There's no relationship between the integer values of the mentor IDs and the emp IDs.

There must be. At least they must come from one source. Imagine that one of them is an IDENTITY(1,1), and another is IDENTITY(1000000000,1)."

There isn't.  Imagine a new employee being added whose ID is 8675309.  It gets cached as the last emp id.  Then a new employee is added.  His ID happens to be 15.  His mentor becomes 8675309.  Thus, it's possible for a mentor ID to have a larger integer value than an employee.
February 6, 2006 11:16 AM
 

khen1234 said:

David:  I like this technique, and it would work, but it amounts to changing the singleton select logic of the code to set-oriented logic; it's just that you've located this in the function rather than the proc.  This violates rule #4.  I've enhanced rule 4 to make this more obvious.  There's actually no need to change the Mentor function, anyway.

Sarus:  You're using COUNT() here, which violates rule 5.
February 6, 2006 11:21 AM
 

Brooks said:

This is the case I'm having problems with.  Can this be ruled out?

INSERT Employees VALUES (0,NULL)

INSERT Employees VALUES (1,2)

INSERT Employees VALUES (2,1)

INSERT Employees VALUES (3,0)
February 6, 2006 3:32 PM
 

Sjoerd Verweij said:

Hmm. Doing this requires some type of state or pre-knowledge, which you have expressly forbidden. You have also expressly forbidden any implicit state from the IDs.

I'll be very interested to see your solution. I'm willing to bet that it violates your own rules in spirit if not the letter.
February 6, 2006 6:06 PM
 

Louie said:

According to your table definition, I cannot insert a Mentor ID which is larger than the EmpID.

insert employees values (101, 102)

INSERT statement conflicted with COLUMN FOREIGN KEY SAME TABLE constraint 'FK__Employees__Mento__288BBB3A'.

if I do this:

insert employees values (101, null)
insert employees values (102, null)
update employees set mentor = 102 where empid = 101

then I will have two employees (0, 102) with no mentors.

February 6, 2006 6:08 PM
 

khen1234 said:

Louie: the FK constraint just ensures that the mentor ID exists as an employee.  There's no relationship between the numbers.  I could add 8675309 as an employee (whose mentor is empid 9, then add empid 10, whose mentor is 8675309.)

Sjoerd:  You're mistaken.  Keep trying.
February 6, 2006 6:54 PM
 

Sjoerd Verweij said:

I still hold that this cannot be fixed in the loop, not without changing the order of the results or some domain knowledge you are withholding.

I have a large bowl of crow here should I be proven wrong. We'll see...   :-)
February 6, 2006 7:09 PM
 

khen1234 said:

And I still hold that you're mistaken :-)
February 6, 2006 7:12 PM
 

Brooks said:

This version of the code will populate the data correctly, which is allowed with the existing constraints.   David's solution doesn't work for this set of data as it walks the relationships, which can't be done if the relationship chain is broken.  

INSERT Employees VALUES (0,NULL)
INSERT Employees VALUES (1,1)
INSERT Employees VALUES (2,1)
INSERT Employees VALUES (3,0)

update employees set mentor = 2 where empid = 1

I can think of ways of solving this, but they involve writing procedural versions of count(*).  

February 6, 2006 7:31 PM
 

Louie said:

alter PROC ListMentors(@LastEmpIdAdded int)
AS

DECLARE @i int
SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)

PRINT 'Employee: ' + CAST(@i AS varchar(10))

SELECT @i = dbo.Mentor(@i)

PRINT 'Mentor: ' + CAST(@i AS varchar(10))

declare @MentorID int

WHILE (@i IS NOT NULL)
BEGIN
   PRINT 'Employee: ' + CAST(@i AS varchar(10))

   SELECT @i = dbo.Mentor(@i)

   PRINT 'Mentor: ' + CAST(@i AS varchar(10))

   select @MentorID = sum(mentor) from employees where mentor = @i
   if @MentorID > @i
   begin
       raiserror('Error', 1, 1)
       return @i
   end
END
go
February 6, 2006 10:21 PM
 

khen1234 said:

Louie:  Your sum(Mentor) is another way of counting the number of mentors which violates rule 5.
February 6, 2006 10:36 PM
 

Dis4ea said:

Does the SELECT have to return a real error message or is failing instead of looping sufficient?
February 7, 2006 2:19 AM
 

Sarus said:

Hi, if it's only the count(*) then you can do it like this ;-)

CREATE FUNCTION dbo.Mentor(@EmpId int) RETURNS int
-- If return value is -1 then there should be an RAISERROR in the calling procedure
AS BEGIN
RETURN (
 select min(case when a.EmpId <> @EmpId then -1 else a.Mentor end)
    from Employees a
    where a.Mentor in (select Mentor from Employees where EmpId = @EmpId)
    group by a.Mentor
 )
END
GO
February 7, 2006 5:04 AM
 

Sjoerd Verweij said:

Oh, I can do a CHEESY version:


CREATE PROC ListMentors(@LastEmpIdAdded int) AS

DECLARE @i int, @c int

SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)
Select @c = max(empid) from employees   -- See? No count  :-p

PRINT 'Employee: '+CAST(@i AS varchar(10))

SELECT @i = dbo.Mentor(@i)

PRINT 'Mentor: '+CAST(@i AS varchar(10))

WHILE (@i IS NOT NULL)

BEGIN

     PRINT 'Employee: '+CAST(@i AS varchar(10))

     SELECT @i = dbo.Mentor(@i)
     Set @c = @c - 1
     If (@c < 0)  RaisError('I have detected with my mighty cheese that the chain is broken!', 16, 1) With Log

     PRINT 'Mentor: '+CAST(@i AS varchar(10))

END

February 7, 2006 11:00 AM
 

Sjoerd Verweij said:

Oh, and if Max() is too much like counting, I can always do

Select Top 1 @c = EmpID From Employees Order By EmpID Desc
February 7, 2006 11:01 AM
 

khen1234 said:

Sjoerd:  It's not "only COUNT(*)" -- you "can't use COUNT() or anything similar."  Your last solutions also assume a numeric relationship between the emp IDs.  There isn't one.  What if they aren't sequential (i.e., what if there are gaps between them)?  What if the max emp ID is 10000, but the others are all under 10?  Neither max or top 1 is useful in those situations.
February 7, 2006 11:24 AM
 

Sjoerd Verweij said:

Umm, I don't assume anything about the IDs. All I am doing is capping the number of iterations. The max EmpID is at the very least equal to the number of employees, and is therefore always a correct number of iterations to cap at. I never said efficient -- in your example, I would still do 10000 iterations, even if there are only 11 employees --, but it WILL exit the loop rather than churn away indefinitely. So there.

As for Top 1 Desc or Max being similar to Count... that's a spirit vs. letter of the law kind of thing. Hence my snarky comment in the code  :-)

My bowl of crow is still waiting. And getting a bit smelly, too.
February 7, 2006 11:39 AM
 

Louis Nguyen said:

Hi,

This is my solution attempt.  Every 1000 iterations, it checks the average "vector".  If the vector is exactly the same as the last check, we're in a loop.  @c counter @v vector @w lastVector.

Thanks,
Louis

CREATE PROC ListMentors(@LastEmpIdAdded int) AS
DECLARE @i int, @c int, @v int, @w int
SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)
PRINT 'Employee: '+CAST(@i AS varchar(10))
SELECT @i = dbo.Mentor(@i)
SELECT @v = 0, @c =0
PRINT 'Mentor: '+CAST(@i AS varchar(10))
WHILE (@i IS NOT NULL)
BEGIN
     PRINT 'Employee: '+CAST(@i AS varchar(10))
     SELECT @i = dbo.Mentor(@i)
     SELECT @v = @v +@i, @c=@c+1
     PRINT 'Mentor: '+CAST(@i AS varchar(10))

     -- Infinite loop check
     If (@c % 1000)=0 Begin
           If @v/1000 = @w/1000 Begin
               Print 'Inifinite Loop - Possible table corruption detected'
               Break
           End
           Else Begin
               Select @w=@v
               Select @v=0, @c=0
           End
     End
END
February 7, 2006 11:43 AM
 

Sjoerd Verweij said:

As a random aside, why on Earth does the proc have the first Print/Select/Print outside of the loop to begin with? Isn't that a bit redundant?

February 7, 2006 11:48 AM
 

khen1234 said:

Sjoerd:  oh, I see what you're doing.  That's clever, but it won't work correctly if the max(empid) is a negative number.  It's also terribly inefficient, as you've mentioned.  Try to come up with a solution that makes no assumptions about the IDs themselves.  They might as well be char-based emp IDs as far as this puzzle is concerned.
February 7, 2006 2:44 PM
 

Sarus said:

Hi,
so here is my latest try. No counting and no assumptions for the EmpID.
While working with integers, the funktion will raise a converting error when a loop is detected.

If you work with strings, then there must be only one tack witch isn't a legal EmpID (substitute this tack with the string '*Error*' in the function code). If the function returns this tack raise an error in the calling procedure.

CREATE FUNCTION dbo.Mentor(@EmpId int) RETURNS int
-- funktion will raise a converting error when a loop is detected.
-- if the EmpID are Strings then you have to use a string-tag which isn't possible
AS BEGIN
RETURN (
select case when max(case when a.EmpId = @EmpId then 0 else 1 end) = 0 then a.Mentor
            else '*Error*' end
   from Employees a
   where a.Mentor in (select Mentor from Employees where EmpId = @EmpId)
   group by a.Mentor
)
END
February 8, 2006 7:24 AM
 

Louis Nguyen said:

Hi,

Here is a refinement on my previous submission.  The previous proc arbitrarily set the infinite loop check frequency at 1000 iterations.  This won't work if the Employees table is large.  e.g. we traverse to the end of 1M+ rows and we loop back.  The revised proc dynamically bumps up the check frequency.

CREATE PROC ListMentors(@LastEmpIdAdded int) AS
DECLARE @i int, @c int, @v int, @w int, @iter int, @freq int
SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)
PRINT 'Employee: '+CAST(@i AS varchar(10))
SELECT @i = dbo.Mentor(@i)
SELECT @v = 0, @c =0, @iter=0, @freq=10
PRINT 'Mentor: '+CAST(@i AS varchar(10))
WHILE (@i IS NOT NULL)
BEGIN
     PRINT 'Employee: '+CAST(@i AS varchar(10))
     SELECT @i = dbo.Mentor(@i)
     SELECT @v = @v +@i, @c=@c+1, @iter=@iter+1
     PRINT 'Mentor: '+CAST(@i AS varchar(10))

     -- Infinite loop check
     If (@c % @freq)=0 Begin
           If @v/@freq = @w/@freq Begin
               Print 'Inifinite Loop - Possible table corruption detected'
               Break
           End
           Else Begin
               Select @w=@v
               Select @v=0, @c=0
           End

           -- If the number of total iterations is large, bump up the check freq by power of 10
           If @freq*10<@iter Begin
               Select @freq=@freq*10
           End
     End
END
PRINT 'Total iterations: '+CAST(@iter as varchar(50))
February 8, 2006 1:49 PM
 

khen1234 said:

Louis:  these are some creative solutions, but, like I said in the rules, you can't modify the Mentor function.  Trust me:  it isn't necessary.
February 8, 2006 1:56 PM
 

Sjoerd Verweij said:

I think you've got Louis and Sarus confused  :-)

I am starting to get the icky feeling the solution to this puzzle might be delayed until April 1st...

February 8, 2006 2:04 PM
 

khen1234 said:

Sjoerd:  Ah, my bad.  Yes -- I meant Sarus.

April 1st?  Are you thinking there is no solution?  At least one that doesn't violate at least the spirit of the rules I laid out?

Trust me: there's a solution, a really simple one, and it doesn't violate the rules in any way.  I'm refraining from posting it until everyone has had their shot at figuring it out on their own.  

February 8, 2006 2:29 PM
 

Sjoerd Verweij said:

I'm saying that I do not see a solution only fixing the singleton Select, detecting both skips and loops (note that most attempts are limited to loops only). I see two possible outcomes:

- You post a simple solution within the rules. Much screaming and denting walls with my forehead will ensue.

- You post a simple solution that does not fit in the rules and/or does not work properly. Much screaming will ensue as well, albeit of a different kind  :-)
February 8, 2006 2:38 PM
 

khen1234 said:

Sjoerd said: I'm saying that I do not see a solution only fixing the singleton Select, detecting both skips and loops

I've never said anything about detecting skips.  The original challenge was to detect and avoid the infinite loop.

I assure you there's a solution -- a really simple one (once you know about it, I guess :-) ) that compiles with the rules in spirit as well as in actuality.  It's also reasonably efficient (keep in mind that the entire proc is inefficient to start with) and requires no arcane coding constructs or anything more than a few minor changes to the proc.
February 8, 2006 3:48 PM
 

Dis4ea said:

Ok, very sloppy could be optimized.

CREATE FUNCTION dbo.Mentor(@EmpId int)

RETURNS int

AS BEGIN
 
     DECLARE @Mentor int
     DECLARE @nextMentor int
     DECLARE @nextMentorsMentor int
     
 
     SELECT @Mentor = Mentor FROM Employees WHERE EmpId=@EmpId
     SELECT @nextMentor = Mentor FROM Employees WHERE EmpId = @Mentor
     SELECT @nextMentorsMentor = Mentor FROM Employees WHERE EmpId = @nextMentor

     IF @EmpId = @nextMentorsMentor
SET @Mentor = -1

     RETURN (@Mentor)

END

GO
February 9, 2006 3:00 AM
 

Dis4ea said:

Oh yeah, it's a solution very specific to this problem so it's probably not really complete :-(
Damn you Ken, this hurts :-)
February 9, 2006 3:42 AM
 

khen1234 said:

Dis4ea:  remember -- you can't modify the Mentor function...
February 9, 2006 8:45 AM
 

Dis4ea said:

Damn, all the time inside my head I was reading the List procedure can't be modified :-s
I don't know why I was reading it like that.

/me slaps hisself
February 9, 2006 9:08 AM
 

mattes said:

this works, if you accept type conversion as an error message and the loops stop already at 8

SELECT @i = case when exists(select * from employees where empid = @i and not exists(select * from employees where empid != @i and mentor = dbo.mentor(@i))) then dbo.Mentor(@i) else 'corruption in the mentor-employee relationships detected' end
February 9, 2006 10:21 AM
 

khen1234 said:

Mattes:  that's a nifty idea, but rule 4 prohibits replacing the singleton approach in the code with set-oriented logic, which is what your change amounts to.  I realize a set-oriented approach would be much more efficient, but there's a particular concept I'm trying to demonstrate here.  Trust me:  you can fix the code without having to make any radical changes to it.
February 9, 2006 10:28 AM
 

Sarus said:

same as Dis4ea: ...  I was reading the List procedure can't be modified
February 9, 2006 10:50 AM
 

Brooks said:

Using the above test case this works, although it won't be fast.  There are a few more comments in the code.  

CREATE PROC dbo.ListMentors(@LastEmpIdAdded int) AS

DECLARE @i int
DECLARE @previousi int
DECLARE @currentinner int
DECLARE @previousinner int

SET @i = @LastEmpIdAdded -- ID of last employee added (known in advance)
PRINT 'Employee: '+CAST(@i AS varchar(10))

SET @previousi = @i
SET @i = dbo.Mentor(@i)

PRINT 'Mentor: '+CAST(@i AS varchar(10))

WHILE (@i IS NOT NULL)
BEGIN
     PRINT 'Employee: '+CAST(@i AS varchar(10))

     SET @currentinner = @LastEmpIdAdded
     SET @previousinner = @currentinner

     WHILE (@currentinner IS NOT NULL)
     BEGIN
         PRINT 'Prev Employee: '+CAST(@previousinner AS varchar(10))  
         SET @currentinner = dbo.Mentor(@currentinner)
         PRINT 'Curr Employee: '+CAST(@currentinner AS varchar(10))
         IF (@i = @currentinner AND @previousi =  @previousinner)
         BEGIN
            SET @currentinner = NULL  -- exit the inner loop as this are now at the outer loop
         END
         IF (@i = @currentinner AND @previousi <>  @previousinner) -- we got here again but from from a different employee
         BEGIN
                RAISERROR('Mentor Loop Error',16,1)
                SET @currentinner = NULL
                SET @i = NULL
         END
         SET @previousinner = @currentinner
     END

     SET @previousi = @i
     SET @i = dbo.Mentor(@i)
     PRINT 'Mentor: '+CAST(@i AS varchar(10))

END
February 9, 2006 6:48 PM
 

Oleg K said:

Ken,

I've only seen your blog today for the first time.
Good stuff!

This puzzle is not a trivial one... here's my solution (tested - works):

CREATE PROC ListMentors(@LastEmpIdAdded int) AS

DECLARE @i int

SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)

PRINT 'Employee: '+CAST(@i AS varchar(10))

SELECT @i = dbo.Mentor(@i)

PRINT 'Mentor: '+CAST(@i AS varchar(10))

DECLARE @j int

SELECT @j = dbo.Mentor(@i)

WHILE (@i IS NOT NULL)

BEGIN

     PRINT 'Employee: '+CAST(@i AS varchar(10))

     SELECT @i = dbo.Mentor(@i)

     PRINT 'Mentor: '+CAST(@i AS varchar(10))

     SELECT @j = dbo.Mentor(dbo.Mentor(@j))
     IF (@j = @i)
     BEGIN
            RAISERROR('Loop Error',16,1)
            SET @i = NULL
     END

END
February 10, 2006 4:59 AM
 

Oleg K said:

Could you guys explain me the winning solution for the previous puzzle?
I can see that there's some play with addresses, but I don't know SQL Server that well.
A brief explanation would be very much appreciated :o)
Thanks
February 10, 2006 5:07 AM
 

mattes said:

what about that

     SELECT @i = dbo.Mentor(case when not exists(select * from employees where empid != @i and mentor = dbo.mentor(@i)) then @i else 'corruption in the mentor-employee relationships detected' end)
February 10, 2006 7:42 AM
 

Sjoerd Verweij said:

Ken, please put us all out of our misery  :-)
February 10, 2006 1:52 PM
 

Ken Henderson's WebLog said:

The simplest rule-compliant solution to the employee-mentor challenge I recently posted is to change...
February 11, 2006 2:11 PM
 

Dis4ea said:

You are really evil :-)
But do let us guess some more please :-p
February 12, 2006 5:42 AM
 

Daryl Blowes said:

I could be wrong but it seems like none of these solutions really work when you have a circular loop involving more than one or two relations.  Shouldn't it be invalid when:

JOHN mentored TOM who mentored JERRY who mentored ALEX who mentored JOHN

?

November 11, 2006 10:29 AM
 

Geedha said:

I guess there will be small syntax problems here and there cos I wasn't able to try it out in the system. But please confirm if this logic will work..........

CREATE PROC ListMentors(@LastEmpIdAdded int) AS

DECLARE @empId int, @mentorID int, @CheckForReptitiveMentor int, @bitFirstTimeLoop bit

SET @CheckForReptitiveMentor = 0

SELECT @empId  = @LastEmpIdAdded -- ID of last employee added (known in advance)

PRINT 'Employee: '+CAST(@empId AS varchar(10))

SELECT @mentorID = dbo.Mentor(@empId )

PRINT 'Mentor: '+CAST(@mentorID  AS varchar(10))

WHILE (@mentorID  IS NOT NULL)

BEGIN

     SELECT @empId = @mentorID

     PRINT 'Employee: '+CAST(@empId  AS varchar(10))

     SELECT @mentorID   = dbo.Mentor(@empId)

     If    @MentorId= @CheckForReptitiveMentor

       BEGIN

             print "Corrupt data"

             @mentorID = null

       END

     PRINT 'Mentor: '+CAST(@mentorID  AS varchar(10))

     if @bitFirstTimeLoop =  0

       BEGIN

             set @bitFirstTimeLoop = 1

            SELECT @CheckForReptitiveMentor = @MentorId

       END

 END

February 3, 2007 6:24 PM
 

otto_ said:

Hi - I am too late replying but can this be a possible solution ( i havent looked at the answer)

CREATE PROC ListMentors(@LastEmpIdAdded int) AS

DECLARE @i int , @x int , @y int , @a int , @b int

SELECT @i = @LastEmpIdAdded -- ID of last employee added (known in advance)

PRINT 'Employee: '+CAST(@i AS varchar(10))

SELECT @i = dbo.Mentor(@i)

PRINT 'Mentor: '+CAST(@i AS varchar(10))

WHILE (@i IS NOT NULL)

BEGIN

     PRINT 'Employee: '+CAST(@i AS varchar(10))

    select @x = empid , @y = mentor from employees where empid = @i

     SELECT @i = dbo.Mentor(@i)

   select @a = empid , @b = mentor from employees where empid = @i

if exists (select 1 from employees where empid < @y and mentor= @y) OR ( @x = @b and @y = @a ) OR (@x=@y) -- cyclic error detected

begin

select 'Cyclic error detected , aborting proc'

return

end

     PRINT 'Mentor: '+CAST(@i AS varchar(10))

END

June 27, 2007 3:30 PM
 

Dating said:

Today’s entry is another T-SQL puzzle. Steve Kass took the prize for the best solution to my last T-SQL puzzle , and several others came up with some pretty original solutions of their own. I especially liked the ones that were T-SQL specific – ones tha

May 30, 2008 11:42 PM
 

Weddings said:

Today’s entry is another T-SQL puzzle. Steve Kass took the prize for the best solution to my last T-SQL puzzle , and several others came up with some pretty original solutions of their own. I especially liked the ones that were T-SQL specific – ones tha

June 5, 2008 6:31 AM
 

Ken Henderson s WebLog TSQL coding challenge | fire pit said:

PingBack from http://firepitidea.info/story.php?id=916

June 13, 2009 11:20 PM
 

Ken Henderson s WebLog TSQL coding challenge | work from home said:

PingBack from http://workfromhomecareer.info/story.php?id=10700

June 16, 2009 8:42 AM
 

Ken Henderson s WebLog TSQL coding challenge | alternative dating said:

PingBack from http://topalternativedating.info/story.php?id=1246

June 17, 2009 3:51 AM
 

Ken Henderson s WebLog TSQL coding challenge | debt settlement program said:

PingBack from http://edebtsettlementprogram.info/story.php?id=24816

June 19, 2009 9:43 AM

Leave a Comment

(required) 
(optional)
(required) 

  
Enter Code Here: Required
Submit

This Blog

Syndication

© 2009 Microsoft Corporation. All rights reserved. Terms of Use  |  Trademarks  |  Privacy Statement
Microsoft
Page view tracker