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!


Comments (65)

  1. umccullough says:

    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

  2. umccullough says:

    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?

  3. MSDNArchive says:

    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

  4. umccullough says:

    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 :)

  5. MSDNArchive says:

    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.

  6. pkr171 says:

    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.

  7. MSDNArchive says:

    pkr171:  See rule #5 — you can’t use COUNT() to determine the number of employees, mentors, or rows in any way :-)

  8. rockmoose says:

    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

  9. Louie says:

    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

  10. Dis4ea says:

    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?

  11. MSDNArchive says:

    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.

  12. Ennor says:

    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.

  13. David says:

    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

  14. Sarus says:

    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

  15. Dis4ea says:

    I think David won :-)

  16. MSDNArchive says:

    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.

  17. MSDNArchive says:

    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.

  18. Brooks says:

    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)

  19. Sjoerd Verweij says:

    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.

  20. Louie says:

    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.

  21. MSDNArchive says:

    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.

  22. Sjoerd Verweij says:

    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…   :-)

  23. MSDNArchive says:

    And I still hold that you’re mistaken :-)

  24. Brooks says:

    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(*).  

  25. Louie says:

    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

  26. MSDNArchive says:

    Louie:  Your sum(Mentor) is another way of counting the number of mentors which violates rule 5.

  27. Dis4ea says:

    Does the SELECT have to return a real error message or is failing instead of looping sufficient?

  28. Sarus says:

    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

  29. Sjoerd Verweij says:

    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

  30. Sjoerd Verweij says:

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

    Select Top 1 @c = EmpID From Employees Order By EmpID Desc

  31. MSDNArchive says:

    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.

  32. Sjoerd Verweij says:

    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.

  33. Louis Nguyen says:

    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

  34. Sjoerd Verweij says:

    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?

  35. MSDNArchive says:

    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.

  36. Sarus says:

    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

  37. Louis Nguyen says:

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

  38. MSDNArchive says:

    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.

  39. Sjoerd Verweij says:

    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…

  40. MSDNArchive says:

    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.  

  41. Sjoerd Verweij says:

    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  :-)

  42. MSDNArchive says:

    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.

  43. Dis4ea says:

    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

  44. Dis4ea says:

    Oh yeah, it’s a solution very specific to this problem so it’s probably not really complete :-(

    Damn you Ken, this hurts :-)

  45. MSDNArchive says:

    Dis4ea:  remember — you can’t modify the Mentor function…

  46. Dis4ea says:

    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

  47. mattes says:

    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

  48. MSDNArchive says:

    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.

  49. Sarus says:

    same as Dis4ea: …  I was reading the List procedure can’t be modified

  50. Brooks says:

    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

  51. Oleg K says:

    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

  52. Oleg K says:

    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

  53. mattes says:

    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)

  54. Sjoerd Verweij says:

    Ken, please put us all out of our misery  :-)

  55. The simplest rule-compliant solution to the employee-mentor challenge I recently posted is to change…

  56. Dis4ea says:

    You are really evil :-)

    But do let us guess some more please :-p

  57. Daryl Blowes says:

    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

    ?

  58. Geedha says:

    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

  59. otto_ says:

    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

  60. Dating says:

    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

  61. Weddings says:

    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