МОДЕЛИРОВАНИЕ ИЕРАРХИЙ СРЕДСТВАМИ РЕЛЯЦИОННОЙ СУБД AB C D FG E HI J NO K L RS M T U PQ. - презентация

1 МОДЕЛИРОВАНИЕ ИЕРАРХИЙ СРЕДСТВАМИ РЕЛЯЦИОННОЙ СУБД AB C D FG E HI J NO K L RS M T U PQ

2 НЕКОТОРЫЕ ВАЖНЫЕ ЗАДАЧИ, ХАРАКТЕРНЫЕ ТОЛЬКО ДЛЯ ИЕРАРХИЙ НЕКОТОРЫЕ ВАЖНЫЕ ЗАДАЧИ, ХАРАКТЕРНЫЕ ТОЛЬКО ДЛЯ ИЕРАРХИЙ определить, находится ли узел А в поддереве, вершиной которого является узел Б;определить, находится ли узел А в поддереве, вершиной которого является узел Б; выбрать непосредственного родителя узла А;выбрать непосредственного родителя узла А; выбрать всех родителей узла А в порядке их уровня в дереве;выбрать всех родителей узла А в порядке их уровня в дереве; выбрать все узлы, находящиеся в поддереве, вершиной которого является узел А;выбрать все узлы, находящиеся в поддереве, вершиной которого является узел А; выбрать все узлы, непосредственным родителем которых является узел А;выбрать все узлы, непосредственным родителем которых является узел А; определить наиболее близкого общего родителя для узлов А и B.определить наиболее близкого общего родителя для узлов А и B.

3 РЕКУРСИЯ A B C D FG E HI J NO K L RS M T U УЗЕЛ H G F E D I C B A J K L M N O P Q R S T U ПРЕДОК E D D C B E A A - F G H I J J K K L L M M PQ

4 CREATE TABLE T (Id INT NOT NULL IDENTITY PRIMARY KEY, Parent INT NOT NULL REFERENCES T(Id), Parent INT NOT NULL REFERENCES T(Id), Data VARCHAR); Data VARCHAR); CREATE TABLE T (Id INT NOT NULL IDENTITY PRIMARY KEY, Parent INT NOT NULL REFERENCES T(Id), Parent INT NOT NULL REFERENCES T(Id), Data VARCHAR); Data VARCHAR); Уникальный идентификатор узла Указатель на непосредственного предка узла Содержательна я частьA A или NULL A BAB CAC DBD EBE FCF GCG HCH IDI JEJ KEK LEL OFO MGM NGN PHP

5 получить все корневые элементы SELECT * FROM T WHERE Parent=Id; наличие неопределённого значения использовано как признак корня дерева SELECT * FROM T WHERE Parent=NULL; Идентификаторы узлов можно получить следующим предложением SQL SELECT Id FROM T; Если в таблице хранится несколько независимых иерархий, все корневые элементы можно определить таким образом: SELECT * FROM T WHERE Parent NOT IN (SELECT Id FROM T); выбрать все узлы (без повторов), имеющие потомков SELECT DISTINCT Parent FROM T; список узлов, не имеющих потомков SELECT DISTINCT Id, Data FROM T WHERE Id NOT IN (SELECT DISTINCT Parent FROM T); SELECT * FROM T AS E1 WHERE NOT EXISTS (SELECT * FROM T AS E2 WHERE E1.Id=E2.Parent);

6 Получить всех потомков, например узла E Получаем идентификатор узла E SELECT Id FROM T WHERE Data='E'; Идентификатор узла E = 5. Выбираем все узлы, для которых идентификатор непосредственного предка равен идентификатору узла E. SELECT * FROM T WHERE Parent=5; Окончательно SELECT * FROM T WHERE Parent=(SELECT Id FROM T WHERE Data='E'); Аналогично определяется непосредственный предок заданного узла SELECT * FROM T WHERE Id=(SELECT Parent FROM T WHERE Data='E');

7 вывести два уровня в дереве SELECT T1.Data, T2.Data FROM T AS T1, T AS T2, T AS T3 WHERE T1.Id=T2.Parent AND T3.Id=T2.Parent; выбрать значения более чем на два уровня глубже SELECT DISTINCT T1.Data, T2.Data, T3.Data FROM T AS T1, T AS T2, T AS T3, T AS T4 WHERE T1.Id=T2.Parent AND T2.Id=T3.Parent AND T2.Id=T3.Parent AND T3.Id=T4.Parent; T3.Id=T4.Parent;

8 ПРЕИМУЩЕСТВА И НЕДОСТАТКИ РЕКУРСИВНОГО МЕТОДА

9 ОБРАЗОВАНИЕ ПЕТЕЛЬ УЗЕЛ H G F E D I C B A J K L M N O P ПРЕДОК C C C B B D A A - E E E G G F H K

10 ВЛОЖЕННЫЕ МНОЖЕСТВА ИЛИ МЕТОД ПРАВОГО И ЛЕВОГО КОЭФФИЦИЕНТОВ

11 A BC D FG E HI J K LM

12 ПРЕИМУЩЕСТВА И НЕДОСТАТКИ МЕТОДА ПОЛНОГО ОБХОДА ДЕРЕВА

13 A BC E HI LM Разрыв в нумерации коэффициентов РАЗРЫВ НУМЕРАЦИИ ПРИ УДАЛЕНИИ ВЕТВЕЙ ДЕРЕВА

14 A BC E HI LM ПЕРЕСЧЕТ КОЭФФИЦИЕНТОВ

15 A BC D FG E HI J K LM ВАРИАНТ МЕТОДА ПРАВОГО И ЛЕВОГО КОЭФФИЦИЕНТОВ

16 A BC D FG E HI J K LM Удаляемый узел УДАЛЕНИЕ УЗЛА

17 A BC FG E HI J K LM D ДОБАВЛЕНИЕ УЗЛА

18 A BC FG E HI J K LM D

19 … ВСПОМАГАТЕЛЬНАЯ ТАБЛИЦА A B C D FG E HI J NO K L RS M T U УЗЕЛ F E E D D F C B A F G G G O O O O O ПРЕДОК D A C A B B A A - A D B A J F D B A PQ УДАЛЁННОСТЬ …

20 ПРЕИМУЩЕСТВА И НЕДОСТАТКИ МЕТОДА ВСПОМОГАТЕЛЬНАЯ ТАБЛИЦА

21 ПРЕИМУЩЕСТВА И НЕДОСТАТКИ МЕТОДА Microsoft SQL Server 2008

22 СРАВНЕНИЕ МЕТОДОВ ПРЕИМУЩЕСТВА И НЕДОСТАТКИ