TSQL-Tasks: Индекс графа. Часть 2. Физическая архитектура.

Я продолжаю цикл работ, посвященных индексу графа и гипердеревьям. В этот раз будет приведена физическая реализация алгоритмов, развитых в моей предыдущей работе ("Индекс графа. Логическая архитектура"). Для понимания результатов этой главы требуется прочесть первую часть.

Скоростной поиск маршрутов. Физическое проектирование.

Теперь приступим к стадии физического проектирования системы. Для начала создадим базу данных для решения наших задач теории графов.

use master

if db_id ( N'Graphs' ) is not null

begin

; throw 50000, N'База данных с именем Graphs уже существует.', 1

end

-- База данных для решения задач теории графов

create database Graphs

-- У нас будет несколько больших вставок, поэтому что не разрастался журнал транзакций,
-- установим простую модель восстановления

alter database Graphs set recovery simple

Понадобится всего 2 таблицы. Во первых, нужна таблица для деревьев всех уровней:

if object_id ( N'dbo.ExtEdges', N'U' ) is not null

begin

; throw 50000, N'Таблица с именем dbo.ExtEdges уже существует.', 1

end

create table dbo.HyperTrees

(

LevelId int not null,

VerId int identity ( 1, 1 ) not null,

VerParId int null,

IsRoot bit not null,

VerRootId int null,

EdgeId int null,

VerStartEdgeId int null,

VerEndEdgeId int null,

constraint PK_HyperTrees_VerId primary key clustered ( VerId asc ) on [PRIMARY],

constraint FK_HyperTrees_VerParId_VerId foreign key ( VerParId ) references dbo.HyperTrees ( VerId )
on update no action on delete no action,

constraint FK_HyperTrees_VerRootId_VerId foreign key ( VerRootId ) references dbo.HyperTrees ( VerId )
on update no action on delete no action,

constraint FK_HyperTrees_EdgeId foreign key ( EdgeId ) references dbo.ExtEdges ( EdgeId )
on update cascade on delete no action,

constraint AK_HyperTrees_IsRoot_VerId unique nonclustered ( IsRoot asc, VerId asc ) on [PRIMARY]

) on [PRIMARY]

Дадим описание полей:

Поле LevelId показывает уровень вершины. То есть для LevelId = 1 мы имеем дело с вершинами графа. Если LevelId = 2, то вершина является деревом, состоящим из вершин графа и т. д. В процедурах это поле, кажется, не нужно, я его оставил для целей отладки. Уровень можно легко посчитать исходя из остальных полей таблицы.
VerId - идентификатор вершины индекса графа.
VerParId - идентификатор родительской вершины для вершины VerId в смысле иерархии дерева. Причем со временем, если произойдет удаление ребра, соединяющего вершины VerId и VerParId, то вершина VerIdId уже не будет связана с VerId, одна поле VerParId будет по прежнему прописано.
IsRoot - признак корневого элемента. Предположим, например, что есть вершина VerId, которая является дочерней для вершины VerParId. Происходит удаление ребра, соединяющего VerId и VerParId. В этом случае привязка VerId к VerParId остается, но для вершины VerId проставляется признак корня (IsRoot становится равным 1). То есть поддерево с корнем в VerId само становится деревом.
VerRootId. Допустим есть вершины VerId, уровень которой больше 1. Тогда данная вершина является деревом, у которого есть свой корень. Этот корень и прописывается в вершине VerRootId.
EdgeId. Вновь предположим, что уровень вершины VerId больше 1. Пусть также вершины VerId является дочерней для некоторой вершины VerParId того же уровня. Значит вершины VerId и VerParId (точнее, деревья, которые им соответствуют) соединяются внешним ребром. Его идентификатор это и есть значение поля EdgeId.
Поля VerStartEdgeId и VerEndEdgeId - также заполняются только на уровнях больше одного. В этом случае считаем что ребро EdgeId выходит из вершины VerParId в вершину VerId. При этом вершины VerPar и VerId являются деревьями и ребро EdgeId инцидентно вершинам этих деревьев. То есть на уровне, на единицу меньшем, чем у вершины VerId ребро EdgeId выходит из вершины VerStartEdgeId в вершину VerEndEdgeId.

Также нужна таблица для хранения ребер, которые не входят в первичное максимальное поддерево. В этой таблице будут храниться ребра, которые не вошли в исходное максимальное поддерево. Как мы видели выше, часть из них может начать использовать в ходе операций удаления и вставки ребер.

use Graphs

if object_id ( N'dbo.ExtEdges', N'U' ) is not null

begin

; throw 50000, N'Таблица с именем dbo.ExtEdges уже существует.', 1

end

create table dbo.ExtEdges

(

EdgeId int identity ( 1, 1 ) not null, -- идентификатор ребра

StartId int not null, -- идентификатор начальной вершины ребра

EndId int not null, -- идентификатор конечной вершины ребра

constraint PK_ExtEdges_EdgeId primary key clustered ( EdgeId asc ) on [PRIMARY],

constraint AK_ExtEdges_StartId_EndId unique nonclustered ( StartId asc, EndId asc ) on [PRIMARY],

constraint AK_ExtEdges_EndId_StartId unique nonclustered ( EndId asc, StartId asc ) on [PRIMARY],

constraint FK_ExtEdges_HyperTrees_StartEdge foreign key ( StartId ) references dbo.HyperTrees ( VerId ) on update cascade on delete no action,

constraint FK_ExtEdges_HyperTrees_EndEdge foreign key ( EndId ) references dbo.HyperTrees ( VerId ) on update cascade on delete no action

) on [PRIMARY]

Для быстрого поиска нам нужны индексы.

Данный индекс поможет быстро путешествовать по родителям вершины, когда, например, требуется найти корень дерева, в котором находится вершина:

create nonclustered index IX_VerParId on dbo.HyperTrees ( VerParId asc ) include ( EdgeId, IsRoot, VerStartEdgeId ) on [PRIMARY]

create nonclustered index IX_VerStartEdgeId on dbo.HyperTrees ( VerStartEdgeId asc )

include ( EdgeId, LevelId )

on [PRIMARY]

Нижеследующий индекс может быть объявлен как уникальный, так как дереве в вершину может входить только одно ребро из родительской вершины. Эти данные имеют смысл только для уровней выше 1, поэтому индекс является диапазонным.

create unique nonclustered index IX_VerEndEdgeId on dbo.HyperTrees ( VerEndEdgeId asc )

include ( LevelId, VerParId, EdgeId )

where ( VerStartEdgeId is not null ) on [PRIMARY]

Опять же индекс на VerRootId имеет смысл для уровней больше 1. Каждая вершина может быть корнем только у одного дерева. Поэтому может объявить такой уникальный, диапазонный индекс:

create unique nonclustered index IX_VerRootId on dbo.HyperTrees ( VerRootId asc ) where ( VerRootId is not null ) on [PRIMARY]

Также в силу нашей архитектуры каждое внешнее ребро может на высших уровнях соединять только одну пару вершин. Поэтому можно создать такой уникальный диапазонный индекс:

create unique nonclustered index IX_EdgeId on dbo.HyperTrees ( EdgeId asc ) where ( EdgeId is not null ) on [PRIMARY]

Ниже идет код одной из важнейших хранимых процедур. Она вычисляет образ вершины на следующем уровне. Перед началом поиска маршрута с помощью этой процедуры потребуется определить образы вершин на высших уровнях индекса графа.

if object_id ( N'dbo.FindNextLevelTree', N'P' ) is null

exec ( N'create proc dbo.FindNextLevelTree as return' )

alter proc dbo.FindNextLevelTree

(

@VerId int,

@VerNextId int out, -- идентификатор вершины, которая строится по дереву. которому принадлежит @VerId

@VerRootId int = null out -- корень дерева, которому принадлежит @VerId

)

begin

set nocount, xact_abort on

;

with ParList

(

-- восхождение вверх по иерархии максимального поддерева

select VerId, VerParId, 0 VerLevel, IsRoot

from dbo.HyperTrees

where VerId = @VerId

union all

select ver.VerId, ver.VerParId, VerLevel + 1, ver.IsRoot

from

ParList

inner join

dbo.HyperTrees ver on ParList.VerParId = ver.VerId

)

-- ищем корень (первый элемент при восхождении наверх, у которого есть признак корня)

select top 1 @VerRootId = ver.VerId

from

ParList

inner join

dbo.HyperTrees ver on ParList.VerId = ver.VerId

where ver.IsRoot = 1

order by VerLevel

option ( maxrecursion 0 )

set @VerNextId = (

select VerId

from dbo.HyperTrees

where VerRootId = @VerRootId and VerRootId is not null

)

end

В данной процедуре есть два выходных параметра. Параметр @VerNextId хранит идентификатор образа вершины на следующем уровне, а @VerRootId - это корень вершины @VerId на текущем уровне. В процедуре с помощью рекурсивного CTE находятся путь от данной вершины к ее родителям. А затем из последних берется первая вершина, у которой имеется признак корня. Затем вершина следующего уровня находится благодаря такому наблюдению. У каждой вершины высшего уровня прописан идентификатор корня дерева на предыдущем уровне, из которого строится данная вершина.

Процедура ниже находит маршрут между вершинами, находящимися на одном уровне:

if object_id ( N'dbo.FindPathInOneTree', N'P' ) is null

exec ( N'create proc dbo.FindPathInOneTree as return' )

alter proc dbo.FindPathInOneTree

(

@VerStartId int,

@VerEndId int

)

begin

set nocount, xact_abort on

declare @MaxVerId int

set @MaxVerId = 2000000000

;

with ParStartList

(

select VerId, VerParId, 0 VerLevel

from dbo.HyperTrees

where VerId = @VerStartId

union all

select ver.VerId, ver.VerParId, ParStartList.VerLevel + 1

from

ParStartList

inner join

dbo.HyperTrees ver on ParStartList.VerParId = ver.VerId

ParEndList

(

select VerId, VerParId, 0 VerLevel

from dbo.HyperTrees

where VerId = @VerEndId

union all

select ver.VerId, ver.VerParId, VerLevel + 1

from

ParEndList

inner join

dbo.HyperTrees ver on ParEndList.VerParId = ver.VerId

ParStartNumList

(

select *, row_number () over ( order by VerLevel desc ) num, 1 tp

from ParStartList

ParEndNumList

(

select *, row_number () over ( order by VerLevel desc ) num, 2 tp

from ParEndList

)

select VerId--, VerParId

from

(

-- часть пути от первой вершины к корню, которая не пересекается с путем к корню второго ребра

select top ( @MaxVerId ) startlist.VerId, startlist.VerParId

from ParStartNumList startlist

where startlist.num > (

select max ( endlist.num )

from

ParEndNumList endlist

inner join

ParStartNumList startnum on startnum.VerId = endlist.VerId

)

order by VerLevel asc

) data

union all

select VerParId--, VerId

from

(

-- часть пути от первой точки (пересечения путей к корню первой и второй вершины) до второй вершины

select top ( @MaxVerId ) endlist.VerParId, endlist.VerId

from ParEndNumList endlist

where endlist.num > (

select max ( startlist.num )

from

ParStartNumList startlist

inner join

ParEndNumList endnum on endnum.VerId = startlist.VerId

)

order by VerLevel desc

) data

union all

select @VerEndId -- надо добавить конечную вершину, так как это VerId из пары вершин в ParEndNumList

end

В этом коде с помощью двух рекурсивных CTE находятся маршруты от заданных вершин до корня дерева. Затем от каждого из этих маршрутов берется часть, которая не пресекается с другим. После чего берется объединение этих двух кусков.

Следующая процедура находит маршрут между двумя вершинами в произвольном графе. Пожалуй, она самая сложна, и отняла у меня много времени. В ходе тестирования ее объем вырос в 2 раза!

if object_id ( N'dbo.FindPath', N'P' ) is null

exec ( N'create proc dbo.FindPath as return' )

alter proc dbo.FindPath

(

@VerStartId int,

@VerEndId int

)

begin

set nocount, xact_abort on

declare

@VerStartTmpId int = @VerStartId, @VerEndTmpId int = @VerEndId,

@VerStartNextId int, @VerEndNextId int,

@LevelId int, @EdgeId int, @LastLevel int,

@VerId int, @VerPrevId int, @VerNextId int,

@CurStartId int, @CurEndId int,

@IniVerEdgeId int,

@TmpRootStartId int, @TmpRootEndId int,

@cnt int, @EdgeStartId int, @EdgeEndId int,

@CurEdgeLevel int,

@CurEdgeStartId int, @CurEdgeEndId int,

@CurNextEdgeStartId int, @CurNextEdgeEndId int,

@LevelPathId int, @IsSuperExtEdge int,

@VerAddId int, @VerAddId_2_From_Diff_SubTr int

if not exists

(

select *

from dbo.HyperTrees

where VerId = @VerStartId

) or

not exists

(

select *

from dbo.HyperTrees

where VerId = @VerEndId

)

begin

; throw 50000, N'Одной из указанных вершин не существует.', 1

return

end

-- для пары ребер ищем их образы в дереве следующего уровня по всем уровням пока не дойдем до самого высокого уровня

if object_id ( N'tempdb..#Vers', N'U' ) is not null

drop table #Vers

create table #Vers

(

LevelId int identity ( 1, 1 ) not null,

VerStartId int not null,

VerEndId int not null,

RootStart int not null,

RootEnd int not null,

--primary key clustered ( VerStartId asc, VerEndId asc ) on [PRIMARY]

primary key clustered ( LevelId asc, RootStart asc ) on [PRIMARY]

) on [PRIMARY]

create unique nonclustered index IX_VerStartId_incl_LevelId_where on #Vers ( VerStartId asc )

include ( LevelId )

where ( VerStartId is not null )

on [PRIMARY]

if object_id ( N'tempdb..#Paths', N'U' ) is not null

drop table #Paths

create table #Paths

(

LevelId int not null,

iRowId int identity ( 1, 1 ) not null,

VerId int not null,

primary key clustered ( LevelId asc, iRowId asc ) on [PRIMARY]

) on [PRIMARY]

create unique nonclustered index IX_LevelId_VerId on #Paths ( LevelId asc, VerId asc ) on [PRIMARY]

if object_id ( N'tempdb..#CurPath', N'U' ) is not null

drop table #CurPath

create table #CurPath

(

iRowId int identity ( 1, 1 ) not null,

VerId int not null,

primary key clustered ( iRowId asc ) on [PRIMARY]

) on [PRIMARY]

if object_id ( N'tempdb..#ExtEdgesData', N'U' ) is not null

drop table #ExtEdgesData

create table #ExtEdgesData

(

LevelPathId int not null,

EdgeStartId int not null,

EdgeEndId int not null,

LevelId int not null,

StartId int not null,

EndId int not null

) on [PRIMARY]

create clustered index IX_Paths on #ExtEdgesData ( LevelPathId asc, LevelId asc, EdgeStartId asc, EdgeEndId asc ) on [PRIMARY]

create /*unique*/ nonclustered index IX_StartId_EndId_incl on #ExtEdgesData ( StartId asc, EndId asc )

include ( LevelPathId, LevelId, EdgeStartId, EdgeEndId )

on [PRIMARY]

set @VerStartNextId = @VerStartId

set @VerEndNextId = @VerEndId

set @VerStartTmpId = @VerStartId

set @VerEndTmpId = @VerEndId

-- Вычисляем последовательные образы вершин в деревьях высших уровней. Когда корни станут равными или когда дойдем до деревьев максимального уровня,

-- то цикл остановится

while isnull ( @VerStartNextId, -1 ) <> isnull ( @VerEndNextId, -1 ) and @VerStartNextId is not null and @VerEndNextId is not null

begin

exec dbo.FindNextLevelTree @VerStartTmpId, @VerStartNextId out, @TmpRootStartId out

exec dbo.FindNextLevelTree @VerEndTmpId, @VerEndNextId out, @TmpRootEndId out

insert into #Vers ( VerStartId, VerEndId, RootStart, RootEnd )

values ( @VerStartTmpId, @VerEndTmpId, @TmpRootStartId, @TmpRootEndId )

set @VerStartTmpId = @VerStartNextId

set @VerEndTmpId = @VerEndNextId

end

-- то есть в таблице #Vers хранятся пары вершин из леса, каждого уровня.

-- Начинаем с первичных вершин, между которыми ищется путь. Далее берутся их образы

-- для леса следущего уровня и так далее.

-- проверяем лежат ли вершины в непересекающихся деревьях

select @TmpRootStartId = RootStart, @TmpRootEndId = RootEnd, @LastLevel = LevelId

from #Vers

where LevelId = (

select max ( LevelId )

from #Vers

where VerStartId is not null

)

if @TmpRootStartId <> @TmpRootEndId

begin

return

end

-- цикл по таблце #Vers (по всем уровням деревьев)

declare curVerLevels cursor local static forward_only for

select LevelId, VerStartId, VerEndId

from #Vers

order by LevelId desc

open curVerLevels

fetch next from curVerLevels into @LevelId, @VerStartTmpId, @VerEndTmpId

while @@fetch_status = 0

begin

--для самого верхнего уровня надо просто найти путь межу вершинами в дереве верхнего уровня

if @LevelId = @LastLevel

begin

truncate table #CurPath

insert into #CurPath ( VerId )

exec dbo.FindPathInOneTree @VerStartTmpId, @VerEndTmpId

insert into #Paths ( LevelId, VerId )

select @LevelId, VerId

from #CurPath

end

else

begin

-- надо пройтись по маршруту в дереве высшего уровня для каждой вершины

-- конца и начала каждой пары соседних ребер надо найти путь между ними в дереве текущего уровня

set @VerPrevId = null

set @VerNextId = null

declare curPrevPath cursor local forward_only for

select

lag ( VerId ) over ( partition by LevelId order by iRowId ) VerPrevId,

VerId,

lead ( VerId ) over ( partition by LevelId order by iRowId ) VerNextId

from #Paths

where LevelId = @LevelId + 1

open curPrevPath

fetch next from curPrevPath into @VerPrevId, @VerId, @VerNextId

while @@fetch_status = 0

begin

-- для первой итерации искать путь между @VerStartTmpId - началом текущего ребра

-- для промежуточных итераций искать путь между концом предыдущего ребра и начлаом текущего ребра

-- для последней итерации искать путь между концом текущего ребра и @VerEndTmpId

-- сбрасываем признак наличия ребра между вершинами, уровень которых больше на 1 больше текущего

set @IsSuperExtEdge = 0

set @VerAddId_2_From_Diff_SubTr = null

-- работаем с первой вершиной маршрута предыдущего уровня

if @VerPrevId is null

begin

-- надо найти начальную вершину маршрута текущего уровня

select @CurStartId = VerStartId

from #Vers

where LevelId = @LevelId

-- надо по первой вершине маршрута высшего уровня найти, какая вершина соответствует ей в дереве низшего уровня (которое и рождает данную первую вершину)

-- VerEdgeId будет прописан для дочерней вершины. Надо определить кто потомок в дереве текущего уровня: VerId или VerNextId

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerNextId

)

begin

select @CurEndId = VerEndEdgeId

from dbo.HyperTrees

where VerId = @VerId

end

else if exists

(

select *

from dbo.HyperTrees

where VerId = @VerNextId and VerParId = @VerId

)

begin

select @CurEndId = VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerNextId

end

else

-- найденное ребро определено для дерева уровень которого более чем на 1 выше чем уровень текущего

begin

exec dbo.GetPrevLevelEdge

@VerId,

@VerNextId,

@CurEndId out,

null

end

else if @VerNextId is null

-- работаем с последней вершиной маршрута предыдущего уровня

begin

select @CurEndId = VerEndId

from #Vers

where LevelId = @LevelId

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerPrevId

)

begin

select @CurStartId = VerEndEdgeId

from dbo.HyperTrees

where VerId = @VerId

end

else if exists

(

select *

from dbo.HyperTrees

where VerId = @VerPrevId and VerParId = @VerId

)

begin

select @CurStartId = VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerPrevId

end

else

begin

set @IsSuperExtEdge = 1

set @LevelPathId = null

set @CurEdgeLevel = null

select top 1 @LevelPathId = LevelPathId, @CurEdgeLevel = LevelId, @EdgeStartId = EdgeStartId, @EdgeEndId = EdgeEndId

from #ExtEdgesData

where StartId = @VerPrevId and EndId = @VerId and LevelId > 1

if @LevelPathId is not null

begin

select top 1 @CurStartId = EndId

from #ExtEdgesData

where

EdgeStartId = @EdgeStartId and EdgeEndId = @EdgeEndId and

LevelPathId = @LevelPathId and LevelId = @CurEdgeLevel - 1

end

else

begin

set @LevelPathId = null

set @CurEdgeLevel = null

select top 1 @LevelPathId = LevelPathId, @CurEdgeLevel = LevelId, @EdgeStartId = EdgeStartId, @EdgeEndId = EdgeEndId

from #ExtEdgesData

where StartId = @VerId and EndId = @VerPrevId and LevelId > 1

select top 1 @CurStartId = StartId

from #ExtEdgesData

where

EdgeStartId = @EdgeStartId and EdgeEndId = @EdgeEndId and

LevelPathId = @LevelPathId and LevelId = @CurEdgeLevel - 1

end

else

-- работаем с ребром посередине пути (не первое и не последнее)

begin

-- надо найти две вершины VerEdgeId

set @CurStartId = null

set @CurEndId = null

-- стурктура дерева: VerPrevId -> VerId -> VerNextId

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerPrevId

) and exists

(

select *

from dbo.HyperTrees

where VerId = @VerNextId and VerParId = @VerId

)

begin

select @CurStartId = VerEndEdgeId

from dbo.HyperTrees

where VerId = @VerId

select @CurEndId = VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerNextId

end

-- стурктура дерева: VerNextId -> VerId -> VerPrevId

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerPrevId and VerParId = @VerId

) and exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerNextId

)

begin

select @CurStartId = VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerPrevId

select @CurEndId = VerEndEdgeId

from dbo.HyperTrees

where VerId = @VerId

end

-- стурктура дерева: VerNextId <- VerId -> VerPrevId

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerPrevId and VerParId = @VerId

) and exists

(

select *

from dbo.HyperTrees

where VerId = @VerNextId and VerParId = @VerId

)

begin

select @CurStartId = VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerPrevId

select @CurEndId = VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerNextId

end

-- стурктура дерева: VerPrevId(другое дерево) <-> VerId

if not exists

(

select *

from dbo.HyperTrees

where VerId = @VerPrevId and VerParId = @VerId

) and

not exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerPrevId

)

begin

--select @VerPrevId '@VerPrevId', @VerId '@VerId', @VerNextId '@VerNextId'

set @IsSuperExtEdge = 1

exec dbo.GetPrevLevelEdge

@VerPrevId,

@VerId,

@CurStartId out,

@CurEndId out

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerNextId and VerParId = @VerId

)

begin

set @VerAddId = (

select VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerNextId

)

end

else if exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerNextId

)

begin

set @VerAddId = (

select VerEndEdgeId

from dbo.HyperTrees

where VerId = @VerId

)

end

else

begin

-- это случай когда как путь (VerPrevId-VerId) так и путь (VerId-VerNextId) пролегают между вершинами предыдущего уровня

-- (из одного дерева в другое)

exec dbo.GetPrevLevelEdge

@VerId,

@VerNextId,

@VerAddId_2_From_Diff_SubTr out,

@VerAddId out

end

--select @VerAddId '@VerAddId'

end

-- стурктура дерева: VerId(другое дерево) <-> VerNextId

if not exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerNextId

) and

not exists

(

select *

from dbo.HyperTrees

where VerId = @VerNextId and VerParId = @VerId

) and @IsSuperExtEdge = 0

begin

set @IsSuperExtEdge = -1

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId = @VerPrevId

)

begin

exec dbo.GetPrevLevelEdge @VerId, @VerNextId, @CurEndId out, null

set @CurStartId = (

select VerEndEdgeId

from dbo.HyperTrees

where VerId = @VerId

)

end

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerPrevId and VerParId = @VerId

)

begin

set @CurStartId = (

select VerStartEdgeId

from dbo.HyperTrees

where VerId = @VerPrevId

)

exec dbo.GetPrevLevelEdge @VerId, @VerNextId, @CurEndId out, null

end

if isnull ( @CurStartId, -1 ) <> isnull ( @CurEndId, -1 )

begin

if @IsSuperExtEdge = 0

begin

truncate table #CurPath

insert into #CurPath ( VerId )

exec dbo.FindPathInOneTree @CurStartId, @CurEndId

insert into #Paths ( LevelId, VerId )

select @LevelId, VerId

from #CurPath

end

else if @IsSuperExtEdge = 1

begin

-- Такие проверки нужны так как могут быть задвоения, связанные с тем, что одно ребро может быть

-- инцидентно несокльким ребрам, соединяющим деревья различных уровней.

truncate table #CurPath

insert into #CurPath ( VerId )

exec dbo.FindPathInOneTree @CurStartId, @CurEndId

if @@rowcount <> 0

begin

insert into #Paths ( LevelId, VerId )

select @LevelId, VerId

from #CurPath cur

where not exists

(

select *

from #Paths paths

where paths.LevelId = @LevelId and cur.VerId = paths.VerId

)

end

else

begin

insert into #Paths ( LevelId, VerId )

select distinct LevelId, VerId

from

(

values

( @LevelId, @CurStartId ),

( @LevelId, @CurEndId )

) cur ( LevelId, VerId )

where not exists

(

select *

from #Paths paths

where paths.LevelId = @LevelId and cur.VerId = paths.VerId

)

end

if @VerAddId is not null and @VerAddId_2_From_Diff_SubTr is null

begin

truncate table #CurPath

insert into #CurPath ( VerId )

exec dbo.FindPathInOneTree @CurEndId, @VerAddId

insert into #Paths ( LevelId, VerId )

select @LevelId, VerId

from #CurPath cur

where not exists

(

select *

from #Paths paths

where paths.LevelId = @LevelId and paths.VerId = cur.VerId

)

--values ( @LevelId, @VerAddId )

end

if @VerAddId is not null and @VerAddId_2_From_Diff_SubTr is not null

begin

truncate table #CurPath

insert into #CurPath ( VerId )

exec dbo.FindPathInOneTree @CurEndId, @VerAddId_2_From_Diff_SubTr

insert into #Paths ( LevelId, VerId )

select @LevelId, VerId

from #CurPath cur

where not exists

(

select *

from #Paths paths

where paths.LevelId = @LevelId and paths.VerId = cur.VerId

)

insert into #Paths ( LevelId, VerId )

select distinct LevelId, VerId

from

(

values

( @LevelId, @VerAddId ),

( @LevelId, @VerAddId_2_From_Diff_SubTr )

) cur ( LevelId, VerId )

where not exists

(

select *

from #Paths paths

where paths.LevelId = @LevelId and paths.VerId = cur.VerId

)

end

else -- @IsSuperExtEdge = -1

begin

if not exists

(

select *

from #Paths

where LevelId = @LevelId and VerId = @CurStartId

) and @CurEndId is null

begin

insert into #Paths ( LevelId, VerId )

values ( @LevelId, @CurStartId )

end

else

begin

truncate table #CurPath

insert into #CurPath ( VerId )

exec dbo.FindPathInOneTree @CurStartId, @CurEndId

insert into #Paths ( LevelId, VerId )

select @LevelId, VerId

from #CurPath

end

else

begin

if @CurStartId is not null

begin

if not exists

(

select *

from #Paths

where LevelId = @LevelId and VerId = @CurStartId

)

begin

insert into #Paths ( LevelId, VerId )

values ( @LevelId, @CurStartId )

end

-- сбрасываем значения вершин

set @CurStartId = null

set @CurEndId = null

fetch next from curPrevPath into @VerPrevId, @VerId, @VerNextId

end

close curPrevPath

deallocate curPrevPath

end

-- Для уровней выше чем два нужна информация и прообразах вершин-концов ребер составляющих маршрут на текущем уровне.

-- Так как для следующего на 2 вниз уровня неизвестно по каким вершинам идет путь.

if @LevelId > 2

begin

-- Это очередной цикл, но он делается для маршрутов даже не втором, а на более высоких уровнях, поэтому вероятность того, что его длина

-- будет большой, невелика.

declare curFindEdgeData cursor local static forward_only for

select StartId, EndId

from

(

select VerId StartId, lead ( VerId ) over ( order by iRowId ) EndId, iRowId

from #Paths

where LevelId = @LevelId

) data

where EndId is not null

order by iRowId

open curFindEdgeData

fetch next from curFindEdgeData into @EdgeStartId, @EdgeEndId

while @@fetch_status = 0

begin

set @EdgeId = (

select EdgeId

from dbo.HyperTrees

where VerId = @EdgeStartId and VerParId = @EdgeEndId

)

if @EdgeId is null

begin

set @EdgeId = (

select EdgeId

from dbo.HyperTrees

where VerId = @EdgeEndId and VerParId = @EdgeStartId

)

end

if @EdgeId is null

begin

set @EdgeId = (

select EdgeId

from dbo.HyperTrees

where VerStartEdgeId = @EdgeStartId and VerEndEdgeId = @EdgeEndId and VerEndEdgeId is not null

)

end

if @EdgeId is null

begin

set @EdgeId = (

select EdgeId

from dbo.HyperTrees

where VerStartEdgeId = @EdgeEndId and VerEndEdgeId = @EdgeStartId and VerEndEdgeId is not null

)

end

--if @LevelId = 4 select 'data', @EdgeStartId '@EdgeStartId', @EdgeEndId '@EdgeEndId', @EdgeId '@EdgeId'

set @CurEdgeLevel = 1

while @CurEdgeLevel <= @LevelId - 1

begin

if @CurEdgeLevel = 1

begin

select @CurEdgeStartId = StartId, @CurEdgeEndId = EndId

from dbo.ExtEdges

where EdgeId = @EdgeId

insert into #ExtEdgesData

(

LevelPathId,

EdgeStartId,

EdgeEndId,

LevelId,

StartId,

EndId

)

values

(

@LevelId,

@EdgeStartId,

@EdgeEndId,

@CurEdgeLevel,

@CurEdgeStartId,

@CurEdgeEndId

)

end

else

begin

exec dbo.FindNextLevelTree @CurEdgeStartId, @CurNextEdgeStartId out

exec dbo.FindNextLevelTree @CurEdgeEndId, @CurNextEdgeEndId out

--if @LevelId = 4 select @CurEdgeLevel '@CurEdgeLevel', @EdgeStartId '@EdgeStartId', @EdgeEndId '@EdgeEndId',

--@CurEdgeStartId '@CurEdgeStartId', @CurNextEdgeStartId '@CurNextEdgeStartId', @CurEdgeEndId '@CurEdgeEndId', @CurNextEdgeEndId '@CurNextEdgeEndId'

insert into #ExtEdgesData

(

LevelPathId,

EdgeStartId,

EdgeEndId,

LevelId,

StartId,

EndId

)

values

(

@LevelId,

@EdgeStartId,

@EdgeEndId,

@CurEdgeLevel,

@CurNextEdgeStartId,

@CurNextEdgeEndId

)

set @CurEdgeStartId = @CurNextEdgeStartId

set @CurEdgeEndId = @CurNextEdgeEndId

end

set @CurEdgeLevel += 1

end

fetch next from curFindEdgeData into @EdgeStartId, @EdgeEndId

end

close curFindEdgeData

deallocate curFindEdgeData

end

select @LevelId, @VerPrevId, @VerId, @VerNextId, *

from #Paths

where LevelId = @LevelId

order by iRowId

set @LevelId -= 1

fetch next from curVerLevels into @LevelId, @VerStartTmpId, @VerEndTmpId

end

close curVerLevels

deallocate curVerLevels

select *

from #ExtEdgesData

select VerId

from #Paths

where LevelId = 1

order by iRowId

end

Первый значимый этап процедуры заключается в поиске образов вершин до тех пор образы они не окажутся в одном дереве.
Затем начинается цикл по найденным уровням (от последнего к первому).

В цикле происходит реализация алгоритма, который был описан ранее. Для последнего уровня используется процедура FindPathInOneTree для поиска маршрута между образами вершин на последнем уровне. Если уровень не последний, то еще один цикл. Это цикл по вершинам маршрута предыдущего уровня. В нем мы рассматриваем каждые 2 последовательные вершины и ищем маршрут между ними. Эта часть довольно сложна. Здесь надо искать и разбирать несколько случаев при спуске на нижний уровень.

После окончания внутреннего цикла (то есть когда выполнен спуск на еще один уровень) начинается еще один цикл. Его цель состоит в том, чтобы найти прообразы вершин, которые составляют маршрут на данном уровне. Эта задача выполнима, так как на данном уровне вершины соединяются внешними ребрами. По таблице внешних ребер, можно определить концы этих ребер на первом уровне, а затем подняться от первого на текущий уровень, вычисляя образы концов. Эта информация хранится в таблице #ExtEdgesData. Данный цикл принципиально важен, так как позволяет находит прообраз ребра из маршрута на пред предыдущем уровне (то есть на уровне, который на два меньшем текущего).

Далее идет самая простая процедура добавления вершины:

if object_id ( N'dbo.AddVertex', N'P' ) is null

exec ( N'create proc dbo.AddVertex as return' )

alter proc dbo.AddVertex

(

@VerId int = null out

)

begin

set nocount, xact_abort on

insert into dbo.HyperTrees

(

LevelId,

VerParId,

IsRoot,

VerRootId,

EdgeId,

VerStartEdgeId,

VerEndEdgeId

)

values

(

null,

null

)

set @VerId = scope_identity ()

end

Следующая функция проверяет является ли вершина изолированной. Она понадобится далее для добавления ребра.

if object_id ( N'dbo.IsVertextIsolated', N'FN' ) is null

exec ( N'create function dbo.IsVertextIsolated () returns int as begin return 1 end' )

alter function dbo.IsVertextIsolated

(

@VerId int

)

returns bit

begin

if exists

(

select *

from dbo.HyperTrees

where VerId = @VerId and VerParId is not null and IsRoot = 0

) or

exists

(

select *

from dbo.HyperTrees

where VerParId = @VerId and IsRoot = 0

)

begin

return 0

end

return 1

end

Процедура добавления ребер:

if object_id ( N'dbo.AddEdge', N'P' ) is null

exec ( N'create proc dbo.AddEdge as return' )

alter proc dbo.AddEdge

(

@VerStartId int,

@VerEndId int,

@EdgeId int = null out

)

begin

set nocount, xact_abort on

declare @VerStartNextId int, @VerEndNextId int,

@VerStartTmpId int, @VerEndTmpId int,

@VerRootStartId int, @VerRootEndId int,

@LevelId int, @VerParId int

if @VerStartId = @VerEndId

begin

; throw 50000, N'Нельзя создавать петли.', 1

return

end

if exists

(

select *

from dbo.ExtEdges

where StartId = @VerStartId and EndId = @VerEndId

) or exists

(

select *

from dbo.ExtEdges

where StartId = @VerEndId and EndId = @VerStartId

) or

exists

(

select *

from dbo.HyperTrees

where VerId = @VerStartId and VerParId = @VerEndId

) or exists

(

select *

from dbo.HyperTrees

where VerId = @VerEndId and VerParId = @VerStartId

)

begin

; throw 50000, N'Ребро между вершинами уже существует.', 1

return

end

-- общий алгоритм такой: для каждой из вершин надо начать процесс поиска их образов на более высоком уровне

-- основиться надо тогда, когда для одной из вершин найденнный уровень является последним

-- если у первой вершины найден поcледний уровень, а у другой вершины этот уровень непоследний,

-- то надо последний образ первой вершины в виде вершины нового уровня присоединить к образу-дереву второй вершины на следующем уровне.

-- если найденный уровень последний для обеих вершин, то надо образовать две вершины следующего уровня и соединить их новым ребром

-- для текущей пары вершин будем искать их образы пока не получатся одинаковые вершины или пока не дойдем до последнего уровня

if object_id ( N'tempdb..#Vers', N'U' ) is not null

drop table #Vers

create table #Vers

(

LevelId int identity ( 1, 1 ) not null,

VerStartId int not null,

VerEndId int not null,

primary key clustered ( VerStartId asc, VerEndId asc ) on [PRIMARY]

) on [PRIMARY]

if object_id ( N'tempdb..#NextLevelVers', N'U' ) is not null

drop table #NextLevelVers

create table #NextLevelVers

(

VerId int not null,

VerRootId int not null,

primary key clustered ( VerId asc ) on [PRIMARY]

) on [PRIMARY]

-- ищем последовательноть образов в деревьях высших уровней

set @VerStartNextId = @VerStartId

set @VerEndNextId = @VerEndId

set @VerStartTmpId = @VerStartId

set @VerEndTmpId = @VerEndId

while @VerStartNextId is not null and @VerEndNextId is not null

begin

insert into #Vers ( VerStartId, VerEndId )

values ( @VerStartNextId, @VerEndNextId )

exec dbo.FindNextLevelTree @VerStartTmpId, @VerStartNextId out

exec dbo.FindNextLevelTree @VerEndTmpId, @VerEndNextId out

set @VerStartTmpId = @VerStartNextId

set @VerEndTmpId = @VerEndNextId

end

set @LevelId = scope_identity ()

-- надо проверить лежат ли две последние вершины в одном дереве

select @VerStartTmpId = VerStartId, @VerEndTmpId = VerEndId, @LevelId = LevelId

from #Vers

where LevelId = @LevelId

-- проверка что у них одинаковый корень

exec dbo.FindNextLevelTree @VerStartTmpId, null, @VerRootStartId out

exec dbo.FindNextLevelTree @VerEndTmpId, null, @VerRootEndId out

-- корни совпадают, то есть новое ребро не дает новых знаний о наличии путей и надо просто сделать вставку в таблтцу внешних ребер и выйти из процедуры

if @VerRootStartId = @VerRootEndId

begin

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerStartId, @VerEndId )

set @EdgeId = scope_identity ()

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerEndId, @VerStartId )

return

end

-- корни отличаются

-- предположим, что уровень вершин одинаков, то есть они являются двумя деревьями одного уровня, которые не входят в деревья более высоких уровней

-- (во всех деревьях всегда больше одной вершины в соответствии с алгоритмами)

-- надо образовать 2 новые вершины более высокого уровня и соединить их новым ребром

-- делать это надо только в том, случае, если вершины не являются изолированными

-- (похоже, что из-за изолированных вершин могту быть изолированные вершины на любом уровне)

if @VerStartNextId is null and @VerEndNextId is null

begin

-- берем 2 вершины последних уровней (в виде корней деревьев последних уровней, которым они принадлежат)

-- в качестве корня нового двухэлементного дерева берем start-вершину

if dbo.IsVertextIsolated ( @VerStartTmpId ) = 0 and dbo.IsVertextIsolated ( @VerEndTmpId ) = 0

begin

-- вставляем корень

insert into dbo.HyperTrees

(

LevelId,

VerParId,

IsRoot,

VerRootId,

EdgeId,

VerStartEdgeId,

VerEndEdgeId

)

values

(

@LevelId + 1,

null,

@VerRootStartId,

null,

null

)

set @VerParId = scope_identity ()

-- вставляем внешнее ребро

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerStartId, @VerEndId )

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerEndId, @VerStartId )

set @EdgeId = scope_identity ()

-- вставляем вторую вершину, которая яляется потомком первой

insert into dbo.HyperTrees

(

LevelId,

VerParId,

IsRoot,

VerRootId,

EdgeId,

VerStartEdgeId,

VerEndEdgeId

)

values

(

@LevelId + 1,

@VerParId,

@VerRootEndId,

@EdgeId,

@VerStartTmpId,

@VerEndTmpId

)

end

else if dbo.IsVertextIsolated ( @VerStartTmpId ) = 1

begin

update dbo.HyperTrees

set IsRoot = 0, VerParId = @VerEndTmpId

where VerId = @VerStartTmpId

end

else

begin

update dbo.HyperTrees

set IsRoot = 0, VerParId = @VerStartTmpId

where VerId = @VerEndTmpId

end

-- предположим что у первой вершины уровень максимальный, а у второй нет. Тогда надо для дерева первой вершины сделать вершину следующего уровня

-- и присоединить ее к дереву следующего уровня для второй вершины

if @VerStartNextId is null and @VerEndNextId is not null

begin

-- надо найти образ для @VerEndNextId на следующем уровне и это будет родитель для новой вершины

--exec dbo.FindNextLevelTree @VerEndNextId, @VerParId out

set @VerParId = @VerEndNextId -- это и так следующих уровень, так как это переменная не null, а @VerStartNextId - null

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerStartId, @VerEndId )

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerEndId, @VerStartId )

set @EdgeId = scope_identity ()

insert into dbo.HyperTrees

(

LevelId,

VerParId,

IsRoot,

VerRootId,

EdgeId,

VerStartEdgeId,

VerEndEdgeId

)

values

(

@LevelId + 1,

@VerParId,

@VerRootStartId,

@EdgeId,

@VerEndTmpId,

@VerStartTmpId

)

end

-- предположим что у второй вершины уровень максимальный, а у первой нет. Тогда надо для дерева второй вершины сделать вершину следующего уровня

-- и присоединить ее к дереву следующего уровня для первой вершины

if @VerStartNextId is not null and @VerEndNextId is null

begin

-- надо найти образ для @VerEndNextId на следующем уровне и это будет родитель для новой вершины

--exec dbo.FindNextLevelTree @VerStartNextId, @VerParId out

set @VerParId = @VerStartNextId -- это и так следующих уровень, так как это переменная не null, а @VerEndNextId

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerStartId, @VerEndId )

insert into dbo.ExtEdges ( StartId, EndId )

values ( @VerEndId, @VerStartId )

set @EdgeId = scope_identity ()

insert into dbo.HyperTrees

(

LevelId,

VerParId,

IsRoot,

VerRootId,

EdgeId,

VerStartEdgeId,

VerEndEdgeId

)

values

(

@LevelId + 1,

@VerParId,

@VerRootEndId,

@EdgeId,

@VerStartTmpId,

@VerEndTmpId

)

end

Код процедуры в точности соответствует алгоритму добавлению ребра, который был описан ранее.

Функция поиска поддерева для вершины:

if object_id ( N'dbo.FindSubTree', N'IF' ) is null

exec ( N'create function dbo.FindSubTree ( @i int ) returns table as return select 1 data' )

alter function dbo.FindSubTree

(

@VerId int

)

returns table

return

with SubTree

(

select VerId

from dbo.HyperTrees

where VerParId = @VerId and IsRoot = 0

union all

select tr.VerId

from

SubTree sub

inner join

dbo.HyperTrees tr on sub.VerId = tr.VerParId

where tr.IsRoot = 0 -- в некласьерный индекс по VerParId добавен включенный столбец IsRoot

)

select VerId

from SubTree

union all

select VerId

from dbo.HyperTrees

where VerId = @VerId

Функция dbo.FindSubHyperTree выполняет поиск поддерева на всех низших уровнях. Данная функция получает в качестве параметра вершину некоторого уровня. Выполняет поиск поддерева с корнем в данной вершине. После этого для каждой вершины найденного поддерева берется корень соответствующего дерева на предыдущем уровне и находится поддерево для каждого такого корня. После этого точно также происходит спуск еще на уровень ниже и так далее пока не дойдем до первого уровня.

if object_id ( N'dbo.FindSubHyperTree', N'IF' ) is null

exec ( N'create function dbo.FindSubHyperTree ( @i int ) returns table as return select 1 as data' )

alter function dbo.FindSubHyperTree ( @VerId int )

returns table

return

with StartHyperTree

(

select VerId

from dbo.FindSubTree ( @VerId )

union all

select intTr.VerId

from

StartHyperTree sub

inner join

dbo.HyperTrees tr on sub.VerId = tr.VerId

cross apply

dbo.FindSubTree ( tr.VerRootId ) intTr

-- По деревьям предыдущего уровня находим корни деревьев нижнего уровня, соответствующих найденным вершинам.

-- Далее через cross apply находим вершины этих деревьев.

)

select VerId

from StartHyperTree

Процедура удаления вершины:

if object_id ( N'dbo.DeleteVertext', N'P' ) is null

exec ( N'create proc dbo.DeleteVertext as return' )

alter proc dbo.DeleteVertext

(

@VerId int

)

begin

set nocount, xact_abort on

declare @VerAddId int

if exists

(

-- вершина входит во внешнее поддерево

select *

from dbo.ExtEdges

where StartId = @VerId

) or exists

(

select *

from dbo.ExtEdges

where EndId = @VerId

)

begin

; throw 50000, N'Вершина не может быть удалена, так как связана ребром с другой вершиной.', 1

return

end

-- надо проверить что у образов нет связи с другими вершинами (потомками или предками)

-- (в результате удаления ребер, на 1-ом уровне могло остаться дерево из одной вершины, поэтому недостаточно проверять только на первом уровне)

-- вершины или ее образ являются для какого-то потомком

;

with IsolatedVertext

(

select VerId

from dbo.HyperTrees

where VerId = @VerId

union all

select ver.VerId

from

dbo.HyperTrees ver

inner join

IsolatedVertext isol on ver.VerRootId = isol.VerId

where ver.VerRootId is not null

)

select top 1 @VerAddId = hier.VerId

from

IsolatedVertext hier

inner join

dbo.HyperTrees ver on hier.VerId = ver.VerParId

where ver.IsRoot = 0

if @VerAddId is not null

begin

; throw 50000, N'Из вершины выходит ребро.', 1

return

end

-- вершина или ее образ являются для какого-то дочерней

;

with IsolatedVertext

(

select VerId, IsRoot

from dbo.HyperTrees

where VerId = @VerId

union all

select ver.VerId, ver.IsRoot

from

dbo.HyperTrees ver

inner join

IsolatedVertext isol on ver.VerRootId = isol.VerId

where ver.VerRootId is not null

)

select top 1 @VerAddId = VerId

from IsolatedVertext

where IsRoot = 0

if @VerAddId is not null

begin

; throw 50000, N'Из вершины выходит ребро.', 1

return

end

-- можно удалить изолированное ребро, но надо также удалить возможные его изолированные образы на высших уровнях

-- также для целостности данных требуется за-null-лить ссылки на удаляемые вершины

;

with IsolatedVertext

(

select VerId

from dbo.HyperTrees

where VerId = @VerId

union all

select ver.VerId

from

dbo.HyperTrees ver

inner join

IsolatedVertext isol on ver.VerRootId = isol.VerId

where ver.VerRootId is not null

)

update tr

set tr.VerParId = null -- вроде бы это ничему не вредит

from

dbo.HyperTrees tr

inner join

IsolatedVertext ver on tr.VerParId = ver.VerId

;

with IsolatedVertext

(

select VerId

from dbo.HyperTrees

where VerId = @VerId

union all

select ver.VerId

from

dbo.HyperTrees ver

inner join

IsolatedVertext isol on ver.VerRootId = isol.VerId

where ver.VerRootId is not null

)

delete ver

from

IsolatedVertext isol

inner join

dbo.HyperTrees ver on isol.VerId = ver.VerId

end

В этой процедуре, конечно, делается проверка на то, является ли вершина изолированной. Однако эта проверка осуществляется не только для самой вершины, но и для всех ее образов на всех уровнях. Ведь в результате операций удаления ребер могут появиться вершины, которые соединяются ребрами с другими вершинами, но в таблице эта связь может быть прописана через более высокие уровни чем 1. И если вершину можно удалить, то надо удалять и все ее уровни.

Мы наконец добрались до процедуры удаления ребра. Много нервов она мне попортила.

if object_id ( N'dbo.DeleteEdge', N'P' ) is null

exec ( N'create proc dbo.DeleteEdge as return' )

-- В ходе написания кода отказался от поля hPath, так как иначе его надо пересчитывать для целого поддерева при вставке новой вершины.

alter proc dbo.DeleteEdge

(

@StartId int,

@EndId int

)

begin

set nocount, xact_abort on

declare

@VerId int, @EdgeId int,

@VerNextId int, @VerRootId int,

@VerStartEdgeId int, @VerEndEdgeId int,

@VerStartNextEdgeId int, @VerEndNextEdgeId int,

@VerParId int, @LevelId int, @MaxLevelId int,

@VerNextEndEdgeId int,

@iter int,

@StartOldId int, @EndOldId int,

@EdgeAddId int,

@LevelAddId int

if @StartId = @EdgeId

begin

; throw 50000, N'Начало и конец не могут совпадать.', 1

return

end

if not exists

(

select *

from dbo.HyperTrees

where LevelId = 1 and VerId = @StartId

) or

not exists

(

select *

from dbo.HyperTrees

where LevelId = 1 and VerId = @EndId

)

begin

; throw 50000, N'Для одного из идентификаторов не существует вершины.', 1

return

end

-- случай неиспользуемого ребра

set @EdgeId = (

select EdgeId

from dbo.ExtEdges

where StartId = @StartId and EndId = @EndId

)

set @EdgeAddId = (

select EdgeId

from dbo.ExtEdges

where StartId = @EndId and EndId = @StartId

)

if @EdgeId is not null and

not exists

(

select *

from dbo.HyperTrees

where EdgeId in ( @EdgeId, @EdgeAddId ) and EdgeId is not null

)

begin

delete dbo.ExtEdges

where StartId = @StartId and EndId = @EndId

delete dbo.ExtEdges

where StartId = @EndId and EndId = @StartId

return

end

-- случай отсутствия ребра

if @EdgeId is null and

not exists

(

select *

from dbo.HyperTrees

where VerId = @StartId and VerParId = @EndId

) and

not exists

(

select *

from dbo.HyperTrees

where VerId = @EndId and VerParId = @StartId

)

begin

; throw 50000, N'Ребра с такими вершинами не существует.', 1

return

end

-- Общий алгоритм удаления состоит в следующем (додумал в поезде): при удалении внутреннего ребра дерево первого уровня, в котором находятся

-- вершины распадается, на 2 поддерева. Это разбиение определяет и разбиение деревьев всех уровней, которые содержат текущее дерево

-- первого уровня. То есть все вершины первого уровня, входящие в гипер-дерево, содержащего наши вершины, разбиваются на 2 части: те, из которых можно дойти

-- до вершины start, и те, из которых можно дойти до вершины end.

-- И надо определить есть ли другое внешнее ребро, которое соединяет вершины из первой и второй частей.

-- Если такого ребра нет, то исходное дерево первого уровня разбивается на 2 части. Это относится и ко всем примыкающим деревьям

-- следующих уровней. Они разбиваются на 2 непересекающиеся части.

-- Если такое ребро есть, то для его концов надо найти дерево X, которое содержит оба образа этих вершин.

-- Тогда для деревьев более выоских уровней ничего не меняется.

-- Все примыкающие деревья меньших уровней разбиваются на 2 непересекающиеся части.

-- А дерево X разбивается на 2 дерева, которые соединяются новым ребром. То есть дерево большего уровня

-- (при необходимости оно создается при помощи нового ребра) получает дополнительную вершину.

-- Все ребра, которые инциденнты вершине-образу-X, естественным образом делятся на 2 части. Одна часть продолжает цепляться к X,

-- вторая - к новому ребру.

-- Если требуется удалить используемое внешнее ребро, то применяются те же рассуждения. Но со сдвигом тот уровень, для которого используется внешнее ребро.

-- Думаю, что для начала требуется выпонлить разделение, описанное выше. В ходе него получатся 2 поддерева. Далее можно будет, идя от корня каждого из

-- деревьев, создать 2 рекурсивных CTE. Их можно будет заджойнить на dbo.ExtEdges.

-- как случай удаления внутреннего ребра (ребра из максимального поддерева) так и случай удаления внешнего ребра идентичны по алгоритму.

-- Разница только в том что в случае внешнего ребра что мы начинаем не с 1-ого а со второго уровня.

-- Данная таблица хранит данные о вновь вставленных вершинах на разных уровнях.

-- Когда вставляется новая вершина X, то для той вершины из которой рождается X требуется сделать переприцелку

-- ребер, которые идут в X. Тут недостаточно оперировать полями VerEnd/StartEdgeId, так как ребра могут входить

-- в X с больших уровней.

if object_id ( N'tempdb..#NewVer', N'U' ) is not null

drop table #NewVer

create table #NewVer

(

LevelId int not null,

VerId int not null,

VerNextId int null

) on [PRIMARY]

-- сделаем удобный порядок

if exists

(

select *

from dbo.HyperTrees

where VerId = @StartId and VerParId = @EndId

)

begin

set @VerId = @StartId

set @StartId = @EndId

set @EndId = @VerId

end

if exists

(

select *

from dbo.HyperTrees

where EdgeId = @EdgeAddId

)

begin

set @EdgeId = @EdgeAddId

end

-- вычислим стартовый уровень

if exists

(

select *

from dbo.HyperTrees

where VerId = @EndId and VerParId = @StartId

)

begin

set @LevelId = 1

end

else

begin

-- для случая высшего уровня надо перенацелить начало и конец на вершины второго уровня

set @StartOldId = @StartId

set @EndOldId = @EndId

select @LevelId = LevelId, @StartId = VerParId, @EndId = VerId

from dbo.HyperTrees

where EdgeId = @EdgeId

end

set @LevelAddId = @LevelId

/*select @MaxLevelId = max ( LevelId )

from dbo.HyperTrees*/

-- вычисление максимального уровня символично, так как в любом случае произойдет выход из цикла когда процедура FindNextLevelTree вернет null

set @MaxLevelId = 2000000000

insert into #NewVer ( LevelId, VerId, VerNextId )

values ( @LevelId, @EndId, null )

-- Выполним разбиение. Надо идти в цикле по уровням.

while @LevelId <= @MaxLevelId

begin

-- на первом уровне для нового корня используется сама же вершина @EndId. Поэтому можно просто обновить признак корня.

update dbo.HyperTrees

set IsRoot = 1

where VerId = @EndId

-- найдем соответствующую вершину следующего уровня

exec dbo.FindNextLevelTree @StartId, @VerNextId out, @VerRootId out

if @VerNextId is null

begin

-- первый уровень является и последним поэтому за счет обновления IsRoot у нас просто будет 2 дерева на наивысшем уровне

break

end

else

begin

-- вершина текущего уровня, в которую входит ребро, которое соединяет @VerNextId с ее родителем на следующем уровне

select @VerNextEndEdgeId = VerEndEdgeId

from dbo.HyperTrees

where VerId = @VerNextId

if @VerNextEndEdgeId is null -- вершина @VerNextId сама является корневой

begin

select top 1 @VerNextEndEdgeId = VerStartEdgeId

from dbo.HyperTrees

where VerParId = @VerNextId

end

-- в общем, условия выше это признак того, что на уровне @LevelId какое-то ребро выходит или выходит из поддерева, образованного вершиной @EndId

if @VerNextEndEdgeId in

(

select VerId

from dbo.FindSubTree ( @EndId )

)

begin

-- ребро следующего уровня входит в новое поддерево, значит новую вершину следующего уровня строим по оставшему поддереву

-- а текущее должно иметь новый корень - @EndId

update dbo.HyperTrees

set VerRootId = @EndId

where VerId = @VerNextId

insert into dbo.HyperTrees

(

LevelId,

VerParId,

IsRoot,

VerRootId,

EdgeId,

VerStartEdgeId,

VerEndEdgeId

)

values

(

@LevelId + 1,

@VerNextId,

@VerRootId,

null, -- здесь пустые значения, так как мы вставляем корень (а эти данные прописываются только для дочерних вершин)

null,

null

)

set @VerId = scope_identity ()

insert into #NewVer ( LevelId, VerId, VerNextId )

values ( @LevelId + 1, @VerId, @VerNextId )

-- для все вершин следующего уровня, которые входят в вершины старого но не нового деревьев текущего уровня надо сделать переприцелку на другого родителя

update dbo.HyperTrees

set VerParId = @VerId

where VerEndEdgeId in

(

select VerId

from dbo.FindSubTree ( @VerRootId )

) and

VerEndEdgeId not in

(

select VerId

from dbo.FindSubTree ( @EndId )

)

update dbo.HyperTrees

set VerParId = @VerId

where VerStartEdgeId in

(

select VerId

from dbo.FindSubTree ( @VerRootId )

) and

VerStartEdgeId not in

(

select VerId

from dbo.FindSubTree ( @EndId )

)

end

else

begin

-- ребро из родителя входит в старое поддерево, значит новую вершину следующего уровня строим по новому поддереву

insert into dbo.HyperTrees

(

LevelId,

VerParId,

IsRoot,

VerRootId,

EdgeId,

VerStartEdgeId,

VerEndEdgeId

)

values

(

@LevelId + 1,

@VerNextId,

@EndId,

null,

null

)

set @VerId = scope_identity ()

insert into #NewVer ( LevelId, VerId, VerNextId )

values ( @LevelId + 1, @VerId, @VerNextId )

-- для всех ребер следующего уровня, которые выходят из вершин нового поддерева надо выполнить переприцелку их на нового родителя

update dbo.HyperTrees

set VerParId = @VerId

where VerEndEdgeId in

(

select VerId

from dbo.FindSubTree ( @EndId )

)

update dbo.HyperTrees

set VerParId = @VerId

where VerStartEdgeId in

(

select VerId

from dbo.FindSubTree ( @EndId )

)

end

-- делаем присваивание для работы на следующем уровне

set @StartId = @VerNextId

set @EndId = @VerId

set @LevelId += 1

end

select @VerId = VerId

from #NewVer

where LevelId = ( select max ( LevelId ) from #NewVer )

-- Поиск вершин, которые соединены ребрами с вершинами, которые находятся в новых деревьях

-- и их последующая переприцелка на новые деревья

---------------------------------------------------------------------------------------------------

;

with NewVerData

(

select LevelId, VerId, VerNextId,

lead ( VerId ) over ( order by LevelId asc ) VerNextLevelId

from #NewVer

)

update tr

set tr.VerStartEdgeId = ver.VerId,

tr.VerParId = ver.VerNextLevelId

from

NewVerData ver -- #NewVer ver

inner join

dbo.HyperTrees tr on ver.VerNextId = tr.VerStartEdgeId

inner join

dbo.ExtEdges edge on tr.EdgeId = edge.EdgeId

inner join

dbo.FindSubHyperTree ( @VerId ) hyptr on edge.StartId = hyptr.VerId

where tr.LevelId > @LevelAddId

select @@rowcount qq

;

with NewVerData

(

select LevelId, VerId, VerNextId,

lead ( VerId ) over ( order by LevelId asc ) VerNextLevelId

from #NewVer

)

update tr

set tr.VerStartEdgeId = ver.VerId,

tr.VerParId = ver.VerNextLevelId

from

NewVerData ver -- #NewVer ver

inner join

dbo.HyperTrees tr on ver.VerNextId = tr.VerStartEdgeId

inner join

dbo.ExtEdges edge on tr.EdgeId = edge.EdgeId

inner join

dbo.FindSubHyperTree ( @VerId ) hyptr on edge.EndId = hyptr.VerId

where tr.LevelId > @LevelAddId

select @@rowcount qq1

---------------------------------------------------------------------------------------------------

if @EdgeId is not null

begin

update dbo.HyperTrees

set EdgeId = null, VerStartEdgeId = null, VerEndEdgeId = null

where EdgeId = @EdgeId

delete ext

from dbo.ExtEdges ext

where exists

(

select *

from dbo.ExtEdges addedge

where

addedge.EdgeId = @EdgeId and

addedge.StartId = ext.EndId and

addedge.EndId = ext.StartId

)

delete dbo.ExtEdges

where EdgeId = @EdgeId

end

-- выполнено разделение деревьев всех уровней, теперь надо проверить есть ли ребро, соединяющее обе стороны

set @EdgeId = null

exec dbo.FindNextLevelTree @VerNextId, null, @VerRootId out

set @StartId = @VerRootId -- поиск надо начинать с корня на текущем уровне

select *

from dbo.HyperTrees

where VerId in ( @StartId, @EndId )

return

select top 1 @EdgeId = EdgeId

from

dbo.ExtEdges edges

inner join

dbo.FindSubHyperTree ( @StartId ) st on edges.StartId = st.VerId

inner join

dbo.FindSubHyperTree ( @EndId ) en on edges.EndId = en.VerId

option ( maxrecursion 0 )

-- Тут порядок вершин не важен, так как для каждой пары вершин делаем 2 ребра (это сделано, чтобы не делать по 2 проверки).

-- То есть за счет удвоения объема экономим на времени проверок.

if @EdgeId is null

begin

-- нет вершины, которая бы способствовала построению пути из start в end, значит разделения достаточно,

-- мы получили 2 непересекающихся подграфа

return

end

else

begin

-- Тут надо соединить вершины.

-- Соединяться будут вершины самого последнего уровня (то есть сперва надо найти образы концов найденного ребра,

-- образовать новую вершину уровня выше максимального)

-- Можно было бы искать возможность соединения и деревьев меньшего уровня. Но для этого надо искать поддерево

-- меньшего уровня, что может замедлить поиск, да и алгоритм не выработан.

-- Вершины @StartId и @EndId это 2 вершины, на которые было разбито дерево последнего уровня.

-- Теперь надо соединить их ребром. Пусть start-вершина будет корнем нового дерева.

-- Также для поиска значений VerStartEdgeId, VerEndEdgeId надо найти образы концов @EdgeId на предпоследнем уровне

select @VerStartEdgeId = StartId, @VerEndEdgeId = EndId

from dbo.ExtEdges

where EdgeId = @EdgeId

set @iter = 1

while @iter < @LevelId

begin

exec dbo.FindNextLevelTree @VerStartEdgeId, @VerStartNextEdgeId out

exec dbo.FindNextLevelTree @VerEndEdgeId, @VerEndNextEdgeId out

set @iter += 1

if @iter >= @LevelId

begin

break

end

set @VerStartEdgeId = @VerStartNextEdgeId

set @VerEndEdgeId = @VerEndNextEdgeId

end

update dbo.HyperTrees

set IsRoot = 1

where VerId = @StartId

update dbo.HyperTrees

set IsRoot = 0, VerParId = @VerStartNextEdgeId/*@StartId*/,

EdgeId = @EdgeId, VerStartEdgeId = @VerStartEdgeId, VerEndEdgeId = @VerEndEdgeId

where VerId = @EndId

end

Следующая хранимая процедура вычисляет прообраз концов ребра на предыдущем уровне. Эта процедура очень важна, она используется в процедуре поиска маршрутов при переходе между уровней.

if object_id ( N'dbo.GetPrevLevelEdge', N'P' ) is null

exec ( N'create proc dbo.GetPrevLevelEdge as return' )

alter proc dbo.GetPrevLevelEdge

(

@VerFirstId int,

@VerSecondId int,

@VerCurFirstId int = null out,

@VerCurSecondId int = null out

)

begin

set nocount, xact_abort on

declare @EdgeStartId int, @EdgeEndId int, @CurEdgeLevel int, @LevelPathId int

select top 1 @LevelPathId = LevelPathId, @CurEdgeLevel = LevelId, @EdgeStartId = EdgeStartId, @EdgeEndId = EdgeEndId

from #ExtEdgesData

where StartId = @VerFirstId and EndId = @VerSecondId and LevelId > 1

if @LevelPathId is not null

begin

select top 1 @VerCurFirstId = StartId, @VerCurSecondId = EndId

from #ExtEdgesData

where

EdgeStartId = @EdgeStartId and EdgeEndId = @EdgeEndId and

LevelPathId = @LevelPathId and LevelId = @CurEdgeLevel - 1

end

else

begin

set @LevelPathId = null

set @CurEdgeLevel = null

select top 1 @LevelPathId = LevelPathId, @CurEdgeLevel = LevelId, @EdgeStartId = EdgeStartId, @EdgeEndId = EdgeEndId

from #ExtEdgesData

where StartId = @VerSecondId and EndId = @VerFirstId and LevelId > 1

select top 1 @VerCurFirstId = EndId, @VerCurSecondId = StartId

from #ExtEdgesData

where

EdgeStartId = @EdgeStartId and EdgeEndId = @EdgeEndId and

LevelPathId = @LevelPathId and LevelId = @CurEdgeLevel - 1

end

go

Напомню, что изначально граф хранится в таблице dbo.Edges, которая введена в первой части и в которой хранятся только ребра графа. При работе процедур добавления и удаления вершин и ребер удобно синхронно вести таблицу dbo.Edges и таблицы dbo.HyperTrees, dbo.ExtEdges. Это полезно, так как, например, если с таблицей dbo.HyperTrees что-то случится, то ее данные можно будет воссоздать по таблице dbo.Edges. Поэтому нам нужна еще одна таблица, в которой будет храниться соответствие между идентификаторами вершин из таблицы dbo.Edges и идентификаторами вершин из dbo.HyperTrees.

use Graphs

if object_id ( N'dbo.EdgesRel', N'U' ) is not null

begin

; throw 50000, N'Таблица dbo.EdgesRel уже существует.', 1

return

end

create table dbo.EdgesRel

(

VerIniId int not null,

VerId int not null,

constraint PK_EdgesRel_VerId primary key clustered ( VerId asc ),

constraint AK_EdgesRel_VerIniId unique nonclustered ( VerIniId asc )

) on [PRIMARY]

go

Теперь для для процедур добавления и удаления ребер надо написать обертки, в которых будет синхронизация между нашими таблицами вместе с dbo.Edges. Кроме того все будет внутри транзакции. Ниже идет обертка для процедуры добавления ребра:

if object_id ( N'dbo.AddEdgeWrapper', N'P' ) is null

exec ( N'create proc dbo.AddEdgeWrapper as return' )

alter proc dbo.AddEdgeWrapper

(

@StartId int,

@EndId int,

@EdgeId int out

)

begin

set nocount, xact_abort on

declare @VerId int, @VerStartId int, @VerEndId int, @ErrMsg varchar ( max )

if @StartId > @EndId

begin

set @VerId = @StartId

set @StartId = @EndId

set @EndId = @VerId

end

begin try

begin tran

if not exists

(

select *

from dbo.EdgesRel

where VerIniId = @StartId

)

begin

exec dbo.AddVertex @VerStartId out

insert into dbo.EdgesRel ( VerIniId, VerId )

values ( @StartId, @VerStartId )

end

else

begin

set @VerStartId = (

select VerId

from dbo.EdgesRel

where VerIniId = @StartId

)

end

if not exists

(

select *

from dbo.EdgesRel

where VerIniId = @EndId

)

begin

exec dbo.AddVertex @VerEndId out

insert into dbo.EdgesRel ( VerIniId, VerId )

values ( @EndId, @VerEndId )

end

else

begin

set @VerEndId = (

select VerId

from dbo.EdgesRel

where VerIniId = @EndId

)

end

insert into dbo.Edges ( StartId, EndId )

values ( @StartId, @EndId )

exec dbo.AddEdge @VerStartId, @VerEndId, @EdgeId out

commit tran

end try

begin catch

if xact_state () <> 0

begin

rollback tran

end

set @ErrMsg = 'Ошибка. Процедуры: ' + isnull ( error_procedure (), 'неизвестно' ) + '. Номер: ' + isnull ( cast ( error_number () as varchar ( 100 ) ), 'неизвестно' ) +

'. Строка: ' + isnull ( cast ( error_line () as varchar ( 100 ) ), 'неизвестно' ) +

'. Описание: ' + isnull ( error_message (), 'неизвестно' )

end catch

if isnull ( @ErrMsg, '' ) <> ''

begin

; throw 50000, @ErrMsg, 1

end

go

Теперь напишем процедуру-обертку для удаления ребра:

if object_id ( N'dbo.DeleteEdgeWrapper', N'P' ) is null

exec ( N'create proc dbo.DeleteEdgeWrapper as return' )

alter proc dbo.DeleteEdgeWrapper

(

@StartId int,

@EndId int

)

begin

set nocount, xact_abort on

declare @VerId int, @VerStartId int, @VerEndId int, @ErrMsg varchar ( max )

if @StartId > @EndId

begin

set @VerId = @StartId

set @StartId = @EndId

set @EndId = @VerId

end

begin try

begin tran

set @VerStartId = (

select VerId

from dbo.EdgesRel

where VerIniId = @StartId

)

set @VerEndId = (

select VerId

from dbo.EdgesRel

where VerIniId = @EndId

)

delete from dbo.Edges

where StartId = @StartId and EndId = @EndId

exec dbo.DeleteEdge @VerStartId, @VerEndId

commit tran

end try

begin catch

if xact_state () <> 0

begin

rollback tran

end

'. Строка: ' + isnull ( cast ( error_line () as varchar ( 100 ) ), 'неизвестно' ) +

'. Описание: ' + isnull ( error_message (), 'неизвестно' )

end catch

if isnull ( @ErrMsg, '' ) <> ''

begin

; throw 50000, @ErrMsg, 1

end

go

Все процедуры и функции готовы. В следующей части будет проведена проверка работы алгоритмов на больших объемах. Также будет представлена процедура дефрагментации гипердерева.

TSQL-Tasks

Страницы

Страницы

вторник, 27 января 2015 г.

Индекс графа. Часть 2. Физическая архитектура.

Комментариев нет:

Отправить комментарий

Страницы

Страницы

вторник, 27 января 2015 г.

Индекс графа. Часть 2. Физическая архитектура.

Комментариев нет:

Отправить комментарий

вторник, 27 января 2015 г.