implementing recursive common table expressions (cte)Posted: 22/03/2012
Last time i needed a table structure for groups and subgroups so i decided to create two tables and when i needed to query the groups from the database a i reminded myself about commont table expressions (cte) and the possibility to use them to query recursive data. So i looked at the msdn and found a good example. Nonetheless this is a good example i decided to post my own example too.
First of all i will describe the two included tables. In the group table the name of the groups gets saved. The data in the table are parent and sub groups. Human is the parentgroup of child, juvenile and adult. Child is the parentgroup of baby and tottler.
create table Groups (PK_Groups int IDENTITY primary key, Name nvarchar(256))
To reflect the hirachie of the groups i created the GroupsToGroups table. In this table the parent child relationship between groups is definied. Child is the child of human so FK_Groups reflects the parent key and FK_SubGroups reflects the child key.
create table GroupsToGroups (PK_GroupsToGroups int IDENTITY primary key, FK_Groups int, FK_SubGroups int)
So i need a function that returns a group with all the subgroups to check if a person is member of a specific group or subgroup. To reach this goal i am using a recursive common table expression. The GroupsFunc takes on parameter PK_Group and returns a list of the overtaken group plus all subgroups.
CREATE function dbo.GroupsFunc(@PK_Group int) returns table as return ( with GroupsCte (PK_Groups, Name, FK_SubGroups, [Level]) as ( select PK_Groups, Name, null FK_SubGroups, 1 [Level] from dbo.Groups g where g.PK_Groups = @PK_Group union all select gzg.FK_SubGroups, g.Name, gzg.FK_Groups, [Level] + 1 from GroupsCte gcte inner join dbo.GroupsToGroups gzg on gzg.FK_Groups = gcte.PK_Groups inner join dbo.Groups g on gzg.FK_SubGroups = g.PK_Groups ) select PK_Groups, Name, FK_SubGroups, [Level] from GroupsCte )
The cte consists of two parts. The first part is the entry part, the second part is the recursive part. As you see in the second part the GroupsCte is used to join on the GroupsToGroups table. The recusion gets executed until the second query does not bring an result. If the query returns the result is feeded to the cte and so the next recursion step is executed. Here is the result of the executed GroupsFunc.
select * from GroupsFunc(1)
select * from GroupsFunc(2)
select * from GroupsFunc(5)
After i finished the function with the common table expression i thought about a way to do this without a cte. Here is the result. It gives the same result as the GroupsFunc but i needet two functions and the outer apply keyword to realise this, and the resulting functions are much more complicated than the cte solution. The most imported point in the implementation is the recursive call of the function in the outer apply part. For every group in one hirachie the GroupFuncWithoutCte is called again and returns the child groups. If a group has no childs then the recusion ends.
CREATE function dbo.GroupsFuncWithoutCte(@PK_Group int, @recLevel int) returns @tempGroups table ( PK_Groups int, Name nvarchar(256), FK_SubGroups int, [Level] int ) as begin declare @count int select @count = count(gzg.FK_Groups) from dbo.GroupsToGroups gzg inner join dbo.Groups g on gzg.FK_SubGroups = g.PK_Groups where gzg.FK_Groups = @PK_Group if(@count > 0) begin insert @tempGroups select g.PK_Groups, g.Name, gzg.FK_Groups, @recLevel + 1 from dbo.GroupsToGroups gzg inner join dbo.Groups g on gzg.FK_SubGroups = g.PK_Groups where gzg.FK_Groups = @PK_Group insert @tempGroups select gf.PK_Groups, gf.Name, gf.FK_SubGroups, gf.Level from @tempGroups tg cross apply dbo.GroupsFuncWithoutCte(tg.PK_Groups, @recLevel + 1) gf end return end
--Entry point CREATE function dbo.GroupsFuncWithoutCteMain(@PK_Group int) returns @tempGroups table ( PK_Groups int, Name nvarchar(256), FK_SubGroups int, [Level] int ) as begin insert @tempGroups select g.PK_Groups, g.Name, null FK_SubGroups, 0 [Level] from dbo.Groups g where g.PK_Groups = @PK_Group insert @tempGroups select gf.PK_Groups, gf.Name, gf.FK_SubGroups, gf.[Level] from @tempGroups tg cross apply dbo.GroupsFuncWithoutCte(tg.PK_Groups, 1) gf return end
The starting point is the GroupsFuncWithoutCteMain function that queries the Group table and the calls the GroupsFuncWithoutCte function.
select * from dbo.GroupsFuncWithoutCteMain(1)