Introduction
Sometimes, we need to store our map in a database and save some data related to the map. I've tried to do this, and I've found the path between the streets.
The benefit of my way is set base manipulation, as SQL Server optimizer has multi-thread processing for set base manipulation. and search in set base processing can have binary search efficient.
As you can see, I have 20 or more streets and alleys in the map, for storing them to database, I design this table:
The logic of my Table is that each node(street) can have multiple parents
and for each parent, it has one record, and each node(street) can have
multiple child(street):
Using the Code
First Step
At first, I needed to store my map to table, I got a screen shot of Google map and inserted it into my table using a procedure.
Take a look at my table design:
CREATE TABLE [dbo].[WayTree](
[ID] [int] IDENTITY(1,1) NOT NULL,
[WayName] [nvarchar](300) NULL,
[WayHierarchyID] [hierarchyid] NULL,
[WayLevel] AS ([WayHierarchyID].[GetLevel]()) PERSISTED,
[WayAncestor] AS ([WayHierarchyID].[GetAncestor]((1))) PERSISTED,
[Cost] [decimal](18, 0) NULL,
PRIMARY KEY CLUSTERED
(
[ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, _
IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
Cost is the distance of child from his parent!
And procedure is:
create proc [dbo].[InsertChild] (@ParrentID int, @ChildName nvarchar(100), @cost Decimal)
as
begin
Declare @ParrentHierarchyID HierarchyID
if ((select count(*) from WayTree where id = @ParrentID)=0)
begin
insert into WayTree (WayName, WayHierarchyID, Cost) values(@ChildName,N'/', 0 )
end
else
begin
insert into WayTree(WayName, WayHierarchyID, Cost)
select @ChildName,
WayHierarchyID.GetDescendant((select max(WayHierarchyID.ToString())
from WayTree w
where WayHierarchyID.IsDescendantOf_
((select w2.WayHierarchyID from WayTree w2 where w2.ID = @ParrentID)) = 1
and w.WayHierarchyID.GetLevel()=w3.WayHierarchyID.GetLevel()+1), null).ToString(),
@cost from WayTree w3 where ID = @ParrentID
end
end
As you can see for inserting WayHierarchyID, I add some code, the reason is that we need to find last direct child of parent(@ParentID), you can find the direct child with function GetLevel(), because always this term [child.GetLevel() = Parent.GetLevel()+1] is true, for example the input of procedure is:
@ParentID = 11
and the hierarchyid of record with id = 11 is N'/1/2'
and it has three direct children : N'/1/2/1', N'/1/2/2', N'/1/2/3'
so next child has this hierarchyid : N'/1/2/4'
which we find this hierarchyid with function .GetDescendant()
Please note the logical errors in procedure are not completely handled as it depends on each business logic.
The last thing I need to do for inserting a map is calling my procedure, in fact I don't insert all the node , just some of them, you can find ChildName from map, if you ask why I use the ID of parent instead of its name in my procedure, I want you to go to the table design and check its logic, each street can have multiple records as it can have multiple parents, so its name is not useful, we need its ID, but you can solve this problem in UI:
exec InsertChild 1 , N'EmamKHomeini', 0
exec InsertChild 1 , N'Basti', 2
exec InsertChild 2 , N'Aftab', 2
exec InsertChild 2 , N'Laleh1', 2
exec InsertChild 2 , N'Laleh2', 4
exec InsertChild 2 , N'Mahtab', 5
exec InsertChild 2 , N'Laleh3', 6
exec InsertChild 2 , N'Laleh4', 8
exec InsertChild 2 , N'Laleh5', 10
exec InsertChild 1 , N'Soheil', 5
exec InsertChild 1 , N'Mokhaberat', 8
exec InsertChild 11 , N'M_Alley1', 3
exec InsertChild 11 , N'M_Alley2', 5
exec InsertChild 11 , N'Laleh4', 7
exec InsertChild 11 , N'MokhaberatAlley3', 8
exec InsertChild 1 , N'Isargaran', 10
exec InsertChild 16 , N'I_Alley1', 3
exec InsertChild 16 , N'I_Alley2', 5
exec InsertChild 16 , N'I_Alley3', 8
exec InsertChild 1 , N'Farhangian', 13
exec InsertChild 20 , N'I_Alley1', 3
exec InsertChild 20 , N'I_Alley2', 5
exec InsertChild 20 , N'I_Alley3', 8
exec InsertChild 20 , N'Farhang1', 3
exec InsertChild 20 , N'Farhang2', 5
exec InsertChild 20 , N'Farhang3', 8
Second Step
Writing the query to find path, and shortest path between two locations:
The major logic of my query is retrieving all the parent/child of beginning street in a recursive way, and parent/child of result node to last, so I have all the nodes which have relation with beginning node, then I create path between nodes by adding direct parents and children together.
At last, I found the path which includes beginning and destination.
declare @Beginning nvarchar(100) = N'Laleh4'
declare @Destination nvarchar(100) = N'Farhang3'
declare @MaxRecursion int = 4
;with cte as (
select 1 as RowNumber,Begining.WayName BeginingName, _
Begining.WayHierarchyID as BeginingHierarchyID, _
Begining.WayHierarchyID.ToString() as BeginingHierarchyIDString,
Begining.Cost BeginingCost,
RelatedWay.WayName RelatedWayName,
RelatedWay.WayHierarchyID.ToString() as RelatedHierarchyIDString,
RelatedWay.WayHierarchyID as RelatedHierarchyID,
RelatedWay.Cost RelatedWayCost
from WayTree Begining
inner join WayTree RelatedWay on (RelatedWay.WayHierarchyID.IsDescendantOf_
( Begining.WayHierarchyID) = 1 and Begining.WayHierarchyID != RelatedWay.WayHierarchyID
and RelatedWay.WayLevel = Begining.WayLevel + 1) or
(Begining.WayHierarchyID.IsDescendantOf_
(RelatedWay.WayHierarchyID) = 1 and _
Begining.WayHierarchyID != RelatedWay.WayHierarchyID
and Begining.WayLevel = RelatedWay.WayLevel + 1)
where Begining.WayName= @Beginning
union all
select c.RowNumber + 1 as RowNumber, Begining.WayName BeginingName, _
Begining.WayHierarchyID as BeginingHierarchyID,
Begining.WayHierarchyID.ToString() as BeginingHierarchyIDString,
Begining.Cost BeginingCost,
RelatedWay.WayName RelatedWayName,
RelatedWay.WayHierarchyID.ToString() as RelatedHierarchyIDString,
RelatedWay.WayHierarchyID as RelatedHierarchyID,
RelatedWay.Cost RelatedWayCost
from cte c
inner join WayTree as Begining on c.RelatedWayName = Begining.WayName
inner join WayTree RelatedWay on ((RelatedWay.WayHierarchyID.IsDescendantOf_
(Begining.WayHierarchyID) = 1 and Begining.WayHierarchyID != RelatedWay.WayHierarchyID
and RelatedWay.WayLevel = Begining.WayLevel + 1) or
(Begining.WayHierarchyID.IsDescendantOf_
( RelatedWay.WayHierarchyID) = 1 and _
Begining.WayHierarchyID != RelatedWay.WayHierarchyID
and Begining.WayLevel = RelatedWay.WayLevel + 1))
where c.RowNumber<@MaxRecursion
and RelatedWay.WayHierarchyID != c.BeginingHierarchyID
and RelatedWay.WayHierarchyID != Begining.WayHierarchyID
), cte2 as (
select distinct cte.BeginingName, _
cte.BeginingHierarchyIDString,cte.BeginingHierarchyID, cte.BeginingCost,
cte.RelatedWayName, cte.RelatedHierarchyIDString, _
cte.RelatedHierarchyID, cte.RelatedWayCost
from cte
)
,cte4 as(
select 1 AS RowNumber, BeginingHierarchyID, BeginingHierarchyIDString,BeginingName , _
CAST(cte2.BeginingName AS nvarchar(MAX)) as waypath, cast(BeginingCost as decimal) _
as cost ,cast(0 as decimal)pathcost
from cte2
union all
select 1 as RowNumber, RelatedHierarchyID, RelatedHierarchyIDString, RelatedWayName, _
CAST(cte2.RelatedWayName AS nvarchar(MAX)) as waypath, cast(RelatedWayCost as decimal) _
as cost,cast(0 as decimal) as pathcost
from cte2
union all
select C.RowNumber + 1, c2.BeginingHierarchyID,C2.BeginingHierarchyIDString,C2.BeginingName,
cast((c.waypath+'.'+C2.BeginingName) as nvarchar(MAX)) as waypath,
cast(case when c.BeginingHierarchyID.IsDescendantOf_
(c2.BeginingHierarchyID)=1 then c2.BeginingCost
when c2.BeginingHierarchyID.IsDescendantOf_
(c.BeginingHierarchyID )=1 then c2.BeginingCost end as decimal),
cast(c.pathcost + cast(case when c.BeginingHierarchyID.IsDescendantOf_
(c2.BeginingHierarchyID)=1 then c.Cost
when c2.BeginingHierarchyID.IsDescendantOf_
(c.BeginingHierarchyID )=1 then c2.BeginingCost end as decimal)
as decimal)
from cte4 c
inner join cte2 c2 on (c.BeginingHierarchyID.IsDescendantOf_
(c2.BeginingHierarchyID)=1 and c.BeginingHierarchyID.GetLevel() = _
c2.BeginingHierarchyID.GetLevel()+1 and c.waypath not like N'%'+c2.BeginingName+N'%')
or (c2.BeginingHierarchyID.IsDescendantOf_
(c.BeginingHierarchyID )=1 and c.BeginingHierarchyID.GetLevel() _
+1 = c2.BeginingHierarchyID.GetLevel() and c.waypath not like N'%'+c2.BeginingName+N'%')
WHERE C.RowNumber<10
)
select * into #temp from cte4
OPTION (MAXRECURSION 10);
select distinct * from #Temp
where waypath like N'%'+@Destination+'%'
and waypath like N'%'+@Beginning+'%'
Remember in the worst case, the max recursion is the sum of location with two or more parents + the length of longest WayLevel.
Points of Interest
I think if we want to show shortest path to users, the best way could be saving them after process, and when user wants the result, just showing the result, without process.
