MS SQL

Depth Travesal

Please support our MS SQL advertiser: Intel Parallel Studio Home

•

Join Date: Mar 2008

Posts: 2

Reputation: snow00 is an unknown quantity at this point

Solved Threads: 0

snow00

Offline

Newbie Poster

Depth Travesal

Mar 17th, 2008

Hi, I am a newbie for MSSQL. Previously, I was given a question regarding MSSQL. Although the interview had over, but I am curious to find out on how to solve the question below:

There are 2 tables, NAMES (ID INT IDENTITY(1,1), NAME SYSNAME) and
RELATIONSHIPS (NAMEID INT, PARENT_NAMEID INT) linked via NAMES.ID=
RELANTIONSHIP.NAMEID and where top-most name has a PARENT_NAMEID=0.
Show a nested list of names including LEVEL, NAMEID and NAME, where
LEVEL indicates the nest level (or depth) from top. You may use functions,
stored procedures,views and any other Transact SQL commands compliant
with Microsoft SQL 2000.

Sample Data:
NAMES table content
ID NAME
1 Frank
2 Jo
3 Mary
4 Peter
5 Amy

RELATIONSHIPS table content

NAMEID PARENT_NAMEID
1 0
2 1
3 2
4 1
5 2

Expected Output

LEVEL ID NAME
0 1 Frank
1 2 Jo
2 5 Amy
2 3 Mary
1 4 Peter

Thanks in advanced

•

Join Date: Feb 2008

Posts: 42

Reputation: huangzhi is an unknown quantity at this point

Solved Threads: 13

huangzhi

Offline

Light Poster

Re: Depth Travesal

Mar 20th, 2008

Try this code in Query Analyser. It enough for small data. If you want to use for big data, modify the code.

 Help with Code Tags 
 MSSQL Syntax (Toggle Plain Text) 
SET nocount ON
CREATE TABLE #tmpName (ID int, [Name] varchar(255))
CREATE TABLE #tmpRelation (ID int, ID_Parent int)
 
INSERT #tmpName (ID, [Name]) select 1, 'Frank'
INSERT #tmpName (ID, [Name]) select 2, 'Jo'
INSERT #tmpName (ID, [Name]) select 3, 'Mary'
INSERT #tmpName (ID, [Name]) select 4, 'Peter'
INSERT #tmpName (ID, [Name]) select 5, 'Amy'
 
INSERT #tmpRelation (ID, ID_Parent) select 1, 0
INSERT #tmpRelation (ID, ID_Parent) select 2, 1
INSERT #tmpRelation (ID, ID_Parent) select 3, 2
INSERT #tmpRelation (ID, ID_Parent) select 4, 1
INSERT #tmpRelation (ID, ID_Parent) select 5, 2
 
CREATE TABLE #tmpResult (ID int, ID_Parent int, [Level] int, [Name] varchar(255))
 
INSERT #tmpResult (ID, ID_Parent, [Level], [Name])
  SELECT N.ID, R.ID_Parent, 0, N.[Name]
    FROM #tmpName N inner join #tmpRelation R on
	N.ID = R.ID
    WHERE ID_Parent = 0
 
while EXISTS (SELECT 1 FROM #tmpName N left join #tmpResult R on N.ID = R.ID where R.ID is null)
begin
  INSERT #tmpResult (ID, ID_Parent, [Level], [Name])
    SELECT N.ID, R.ID_Parent, C.[Level] + 1, N.[Name]
      FROM #tmpName N inner join #tmpRelation R on
	N.ID = R.ID INNER JOIN (
			SELECT	P.ID, P.[Level]
			  FROM	#tmpResult P left join #tmpResult C on
				P.ID = C.ID_Parent
			  WHERE C.ID IS NULL
				) C ON
	R.ID_Parent = C.ID
end
 
SELECT ID, [Level], Name FROM #tmpResult
 
DROP TABLE #tmpResult
DROP TABLE #tmpName
DROP TABLE #tmpRelation
set nocount on
create table #tmpName (ID int, [Name] varchar(255))
create table #tmpRelation (ID int, ID_Parent int)

insert #tmpName (ID, [Name]) select 1, 'Frank'
insert #tmpName (ID, [Name]) select 2, 'Jo'
insert #tmpName (ID, [Name]) select 3, 'Mary'
insert #tmpName (ID, [Name]) select 4, 'Peter'
insert #tmpName (ID, [Name]) select 5, 'Amy'

insert #tmpRelation (ID, ID_Parent) select 1, 0
insert #tmpRelation (ID, ID_Parent) select 2, 1
insert #tmpRelation (ID, ID_Parent) select 3, 2
insert #tmpRelation (ID, ID_Parent) select 4, 1
insert #tmpRelation (ID, ID_Parent) select 5, 2

create table #tmpResult (ID int, ID_Parent int, [Level] int, [Name] varchar(255))

insert #tmpResult (ID, ID_Parent, [Level], [Name])
  select N.ID, R.ID_Parent, 0, N.[Name]
    from #tmpName N inner join #tmpRelation R on
	N.ID = R.ID
    where ID_Parent = 0

while exists (select 1 from #tmpName N left join #tmpResult R on N.ID = R.ID where R.ID is null)
begin
  insert #tmpResult (ID, ID_Parent, [Level], [Name])
    select N.ID, R.ID_Parent, C.[Level] + 1, N.[Name]
      from #tmpName N inner join #tmpRelation R on
	N.ID = R.ID inner join (
			select	P.ID, P.[Level]
			  from	#tmpResult P left join #tmpResult C on
				P.ID = C.ID_Parent
			  where C.ID is null
				) C on
	R.ID_Parent = C.ID
end

select ID, [Level], Name from #tmpResult

drop table #tmpResult
drop table #tmpName
drop table #tmpRelation