[MSSQL] Grei liten graf som datastruktur

[Kul drittunge]

Laget en liten graf med materialisert sti.

 

Dette kan man da visualisere som et sykkelhjul, hvor det "stråler ut" spiler og det langs spilene er noder som kan peke til hverandre.

 

Er helt sikkert mye her som ikke er helt riktig, deriblandt håndtering av syklisitet, men det er en helt ok begynnelse for dem som vil utforske det videre.

 

I korthet kan da en node ha flere parents.

Med denne datastrukturen kan man enkelt finne alt av interesse under en parent, man kan finne korteste vei, og en del annet knask.

 

 

drop table Graphs
go
create table Graphs
(
id int identity (1, 1) primary key
, parent_id int 
	CONSTRAINT FK_Graphs_parent_id
	references Graphs (id)
, path varchar (900) 
	CONSTRAINT DF_Graphs_path
	DEFAULT (newid ())
, lvl tinyint
	CONSTRAINT DF_Graphs_lvl
	DEFAULT (0)
)
go
create trigger  [trg_ai_Graphs] on [dbo].[Graphs] after insert
as
declare @n_rows int
set @n_rows = @@rowcount

if @n_rows = 0 return
else
begin try  
-- on insert, get shortest path from parent		
update Graphs
set path = sub.this_path
	, lvl = sub.this_lvl
from	 
	(
		select inserted.id
			, coalesce (shortest_parent_paths.path, '') + cast (inserted.id as varchar (max)) + ',' as this_path
			, coalesce (shortest_parent_paths.lvl, 0) + 1 as this_lvl	
		from inserted
			left outer join 
			(
				select *
				from 
					( 
						select id, parent_id
						from inserted	
					) as sub	
					outer apply
					(
						select top 1 g.path, g.lvl
						from Graphs g
						where 0 = 0 
							and g.id = sub.parent_id
						order by g.lvl asc
					) as dub
			) as shortest_parent_paths on shortest_parent_paths.id = inserted.id
	) as sub
where 0 = 0
	and Graphs.id = sub.id

end try
begin catch
return
end catch
go
create trigger [trg_u_Graphs] on [dbo].[Graphs] for update
as
declare @n_rows int
set @n_rows = @@rowcount

if @n_rows = 0 return
else
begin try  
-- on update (one parent_id has changed), get shortest path from parent
-- on update, also update paths for all children if updated path is shorter
select parents.* 
into #parents
from 
	(
		select inserted.id
			, shortest_parent_paths.old_path
			, coalesce (shortest_parent_paths.path, '') + cast (inserted.id as varchar (max)) + ',' as this_path
			, shortest_parent_paths.old_lvl
			, coalesce (shortest_parent_paths.lvl, 0) + 1 as this_lvl	
		from inserted
			inner join 
			(
				select *
				from 
					( 
						select inserted.id
							, inserted.parent_id
							, deleted.parent_id as old_parent_id
							, deleted.path as old_path
							, deleted.lvl as old_lvl
						from inserted	
							inner join deleted on deleted.id = inserted.id
						where 0 = 0
							and deleted.parent_id <> inserted.parent_id
					) as sub	
					outer apply
					(
						select top 1 g.path
							, g.lvl
						from Graphs g
						where 0 = 0 
							and g.id = sub.old_parent_id
						order by g.lvl asc
					) as dub
			) as shortest_parent_paths on shortest_parent_paths.id = inserted.id
	) as parents 

select children.*
into #children
from #parents as parents
	inner join Graphs children on children.path like parents.old_path + '%'

update Graphs
set path = sub.new_path 
	, lvl = sub.new_lvl
from
	(
		select c.id
			, stuff (c.path, 1, len (p.old_path), p.this_path) as new_path
			, (c.lvl - p.old_lvl) + p.this_lvl as new_lvl
		from #parents p
			inner join #children c on c.path like p.old_path + '%'	 
	) as sub
where 0 = 0
	and Graphs.id = sub.id
end try
begin catch
return
end catch
go

insert into Graphs
(
parent_id
)
select null

insert into Graphs
(
parent_id
)	
select 1

insert into Graphs
(
parent_id
)	
select 2
union all
select 2
insert into Graphs
(
parent_id
)	
select 3
union all 
select 3

insert into Graphs
(
parent_id
)	
select 4

go


select * from Graphs

update Graphs
set parent_id = 
	case 
		when parent_id = 2 then 1
		else 2
	end
where 0 = 0
and id in (4,5)

select * from Graphs

 

En kjekk ting å bruke for å stykke opp den materialiserte stien, er en funksjon fra Erland Sommarskog.

/****** Object:  UserDefinedFunction [dbo].[util_list2tbl]	Script Date: 04/23/2008 19:08:43 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
/* 
AUTHOR: Erlend Sommarskog
URL: http://www.sommarskog.se/arrays-in-sql.html#iter-list-of-integers
*/	
create function [dbo].[util_list2tbl] (@list ntext)
  RETURNS @tbl TABLE (listpos int IDENTITY(1, 1) NOT NULL,
					  number  int NOT NULL) AS
  BEGIN
  DECLARE @pos	  int,
		  @textpos  int,
		  @chunklen smallint,
		  @str	  nvarchar(4000),
		  @tmpstr   nvarchar(4000),
		  @leftover nvarchar(4000)


  SET @textpos = 1
  SET @leftover = ''
  WHILE @textpos <= datalength(@list) / 2
  BEGIN
	 SET @chunklen = 4000 - datalength(@leftover) / 2
	 SET @tmpstr = ltrim(@leftover + substring(@list, @textpos, @chunklen))
	 SET @textpos = @textpos + @chunklen

	 SET @pos = charindex(',', @tmpstr)
	 WHILE @pos > 0
	 BEGIN
		SET @str = substring(@tmpstr, 1, @pos - 1)
		INSERT @tbl (number) VALUES(convert(int, @str))						
		SET @tmpstr = ltrim(substring(@tmpstr, @pos + 1, len(@tmpstr)))
		SET @pos = charindex(',', @tmpstr)
	 END

	 SET @leftover = @tmpstr
  END

  IF ltrim(rtrim(@leftover)) <> ''
	INSERT @tbl (number) VALUES(convert (int, @leftover))

RETURN
END