Деревья в SQL. Часть 1.
Дерево - специальный вид направленного графа. Графы - структуры данных, состоящие из узлов связанных дугами. Кажая дуга показывает однонаправленную связь между двумя узлами. В организационной диаграмме, узлы - сотрудники, а каждая дуга описывает подчинения. В перечне материалов, узлы - модули (в конечном счете, показываемые до индивидуальных частей), и дуги описывают отношение "сделан из". Вершина дерева называется корнем. В организационной диаграмме, это самый большой начальник; в перечне материалов, это собранная деталь. Двоичное дерево - это дерево, в котором узел может иметь не более двух потомков; В общем случае, n-мерное дерево - то, в котором узел может иметь не больше чем n узлов - потомков. Узлы дерева, которые не имеют поддеревьев, называются листьями. В перечне материалов, это - минимальные части, на которые может быть разобрана деталь. Потомки, или дети, родительского узла - все узлы в поддереве, имееющего родительский узел коренем. Деревья часто изображаются как диаграммы. ( ) Другой путь представления деревьев состоит в том, чтобы показывать их как вложенные множества ( ); Это основа для используемого мной представления деревьев в SQL в виде вложенных множеств. В SQL, любые отношения явно явно описываются данными.. Типичный способ представления деревьев состоит в том, чтобы поместить матрицу смежности в таблицу. Т.е. один столбец - родительский узел, и другой столбец в той же самой строке - дочерний узел (пара представляет собой дугу в графе). Например, рассмотрим организационную диаграмму компании с шестью сотрудниками: CREATE TABLE Personnel( emp CHAR(20) PRIMARY KEY, boss CHAR(20) REFERENCES Personnel(emp), salary DECIMAL(6,2) NOT NULL ); Personnel: emp boss salary ========================== 'Jerry' NULL 1000.00 'Bert' 'Jerry' 900.00 'Chuck' 'Jerry' 900.00 'Donna' 'Chuck' 800.00 'Eddie' 'Chuck' 700.00 'Fred' 'Chuck' 600.00 Эта модель имеет преимущества и недостатки. ПЕРВИЧНЫЙ КЛЮЧ - emp, но столбец boss - функционально зависит от него, следовательно мы имеем проблемы с нормализацией. REFERENCES не даст вам возможность указать начальником, того кто не является сотрудником. Однако, что произойдет, когда 'Jerry' изменяет имя на 'Geraldo', чтобы получить телевизионное ток-шоу? Вы также должны сделать каскадные изменения в строках 'Bert' и 'Chuck'. Другой недостаток этой модели - то трудно вывести путь. Чтобы найти имя босса для каждого служащего, используется самообъединяющийся запрос, типа: SELECT B1.emp, 'bosses', E1.emp FROM Personnel AS B1, Personnel AS E1 WHERE B1.emp = E1.boss; Но кое-что здесь отсутствует. Этот запрос дает Вам только непосредственных начальников персонала. Босс Вашего босса также имеет власть по отношению к Вам, и так далее вверх по дереву. Чтобы вывести два уровня в дереве, Вам необходимо написать более сложный запрос самообъединения, типа: SELECT B1.emp, 'bosses', E2.emp FROM Personnel AS B1, Personnel AS E1, Personnel AS E2 WHERE B1.emp = E1.boss AND E1.emp = E2.boss; Чтобы идти более чем на два уровня глубже в дереве, просто расширяют образец: SELECT B1.emp, 'bosses', E3.emp FROM Personnel AS B1, Personnel AS E1, Personnel AS E2, Personnel AS E3 WHERE B1.emp = E1.boss AND E1.emp = E2.boss AND E2.emp = E3.boss; К сожалению, Вы понятия не имеете насколько глубоко дерево, так что Вы должны продолжать расширять этот запрос, пока Вы не получите в результате пустое множество. Листья не имеют потомков. В этой модели, их довольно просто найти: Это сотрудники, не являющиеся боссом кому либо еще в компании: SELECT * FROM Personnel AS E1 WHERE NOT EXISTS( SELECT * FROM Personnel AS E2 WHERE E1.emp = E2.boss); Реальные проблемы возникают при попытке вычислить значения вверх и вниз по дереву. Как упражнение, напишите запрос, суммирующий жалованье каждого служащего и его/ее подчиненных; результат: Total Salaries emp boss salary ========================== 'Jerry' NULL 4900.00 'Bert' 'Jerry' 900.00 'Chuck' 'Jerry' 3000.00 'Donna' 'Chuck' 800.00 'Eddie' 'Chuck' 700.00 'Fred' 'Chuck' 600.00 Другой путь представления деревьев состоит в том, чтобы показать их как вложенные множества. Это более подходящая модель, т.к. SQL - язык, ориентированный на множества. Корень дерева - множество, содержащее все другие множества, и отношения предок-потомок описываются принадлежностью множества потомков множеству предка. Имеются несколько способов преобразования организационной диаграммы во вложенные наборы. Один путь состоит в том, чтобы вообразить, что Вы перемещаете подчиненные "овалы" внутри их родителей, использующих линии края как веревки. Корень - самый большой овал и содержит все другие узлы. Листья - самые внутренние овалы, ничего внутри не содержащие, и вложение соответствует иерархическим отношениям. Это - естественное представление модели "перечень материалов", потому что заключительный блок сделан физически из вложенных составляющих, и разбирается на отдельные части. Другой подход состоит в том, чтобы представить небольшой червь, ползающий по "узлам и дугам" дерева. Червь начинает сверху, с кореня, и делает полную поездку вокруг дерева. Но теперь давайте представим более сильный червь со счетчиком, который начинается с единицы. Когда червь прибывает в узел, он помещает число в ячейку со стороны, которую он посетил и увеличивает счетчик. Каждый узел получит два номера, одино для правой стороны и одино для левой стороны. Это дает предсказуемые результаты, которые Вы можете использовать для формирования запросов. Таблица Personnel имеет следующий вид, с левыми и правыми номерами в виде: CREATE TABLE Personnel( emp CHAR(10) PRIMARY KEY, salary DECIMAL(6,2) NOT NULL, left INTEGER NOT NULL, right INTEGER NOT NULL); Personnel emp salary left right ============================== 'Jerry' 1000.00 1 12 'Bert' 900.00 2 3 'Chuck' 900.00 4 11 'Donna' 800.00 5 6 'Eddie' 700.00 7 8 'Fred' 600.00 9 10 Корень всегда имеет 1 в левом столбце и удвоенное число узлов (2*n) в правом столбце. Это просто понять: червь должен посетить каждый узел дважды, один раз с левой стороны и один раз с правой стороны, так что заключительный количество должено быть удвоенное число узлов во всем дереве. В модели вложенных множеств, разность между левыми и правыми значениями листьев - всегда 1. Представте червя, поворачивающегся вокруг листа, пока он ползет по дереву. Поэтому, Вы можете найти все листья следующим простым запросом: Вы можете использовать такую уловку, для ускорения запросов: постройте уникальный индекс по левому столбцу, затем перепишите запрос, чтобы воспользоваться преимуществом индекса: Причина увеличения производительности в том, что SQL может использовать индекс по левому столбцеу, когда он не испорльзуется в выражении. Не используйте (left - right) = 1, потому что это дает воспользоваться преимуществами индекса. В модели вложенных - имножеств, пути показываются как вложенные множества, которые представлены номерами вложенных множеств и предикатами BETWEEN. Например, чтобы определить всех боссов определенного сотрудника необходимо написать: SELECT :myworker, B1.emp, (right - left) AS height FROM Personnel AS B1, Personnel AS E1 WHERE E1.left BETWEEN B1.left AND B1.right AND E1.right BETWEEN B1.left AND B1.right AND E1.emp = :myworker; Чем больше height, тем дальше по иерархии босс от служащего. Модель вложенных множеств использует факт, что каждое содержащее другие множество является большим в размере (где размер = (right - left)) чем множества, в нем содержащиеся. Очевидно, корень будет всегда иметь самый большой размер. Уровень, число дуг между двумя данными узлами, довольно просто вычислить. Например, чтобы найти уровни между заданным рабочим и менеджером, Вы могли бы использовть: SELECT E1.emp, B1.emp, COUNT(*) - 1 AS levels FROM Personnel AS B1, Personnel AS E1 WHERE E1.left BETWEEN B1.left AND B1.right AND E1.right BETWEEN B1.left AND B1.right AND E1.node = :myworker AND B1.node = :mymanager; (COUNT(*) - 1) используется для того, чтобы удалить двойной индекс узла непосредственно как нахождение на другом уровне, потому что узел - нулевые уровни, удаленные из себя. Вы можете построить другие запросы из этого шаблона. Например, чтобы найти общих боссов двух служащих, объединяют пути и находят узлы который имеют (COUNT(*) > 1). Чтобы найти самых близких общих предков двух узлов, объединяют пути, находят узлы, которые имеют (COUNT(*) > 1), и выбирают с наименьшей глубиной. Translated by Я предполагаю, что Вы имеете перед собой статью за март 1996, так что я не буду повторяться. Множественная модель деревьев имеет некоторые свойства, которые я не упоминал в прошлом месяце. Но сначала, давайте создадим таблицу (см. ) для хранения информации о персонале. Я буду повсюду обращаться к этой таблице в остальной части этой статьи. Дерево на рисунке 1 представлено как A) граф и Б) вложенные множества. Направление показываетя вложением, то есть Вы знаете, что кто-то - подчиненный кого-то еще в иерархии компании, если что левые и правые номера множества этого человека- между таковыми их боссов. Другое свойство, которое я не упоминал в последний раз - то, что потомки- упорядоченны, т.е. Вы можете использовать номера элементов множества, чтобы упорядочить потомков. Это свойство отсутствует в модели матрицы смежности, которая не имеет никакого упорядочения среди потомков. Вы можете использовать этот факт при вставке, обновлении, или удалении узлов в дереве. Одним из свойств дерева является то, что оно является графом без циклов. То есть никакой путь не замыкается, чтобы поймать Вас в бесконечной петле, когда Вы следуете им в дереве. Другое свойство- то, что всегда имеется путь от корня до любого другого узла в дереве. В модели вложенноых множеств, пути показываются как вложенные множества, которые представлены номерами множеств и предикатами BETWEEN. Например, чтобы выяснить всех менеджеров, которым должен отчитываться рабочий, вы можете написать: SELECT 'Mary', P1.emp, (P1.rgt - P1.lft) AS size FROM Personnel AS P1, Personnel AS P2 WHERE P2.emp = 'Mary' AND P2.lft BETWEEN P1.lft AND P1.rgt; Mary emp size ==== === ==== Mary Albert 27 Mary Charles 13 Mary Fred 9 Mary Jim 5 Mary Mary 1 Заметьте, что, когда size = 1, Вы имеете дело С Мэри как с ее собственным боссом. Вы можете исключить этот случай. Модель вложенная множеств использует факт, что каждый вешний набор имеет больший size (size = right - left) чем множества, которые оно содержит. Очевидно, корень будет всегда иметь самый большой size. JOIN и ORDER BY не нужны в модели вложенных множеств, как модели графа смежности. Плюс, результаты не зависят от порядка, в котором отображаются строки. Уровень узла - число дуг между узлом и корнем. Вы можете вычислять уровень узла следующим запросом: SELECT P2.emp, COUNT(*) AS level FROM Personnel AS P1, Personnel AS P2 WHERE P2.lft BETWEEN P1.lft AS P2 GROUP BY P2.emp; Этот запрос находит уровни среди менеджеров, следующим образом: emp level === ===== Albert 1 Bert 2 Charles 2 Diane 2 Edward 3 Fred 3 George 3 Heidi 3 Igor 4 Jim 4 Kathy 4 Larry 4 Mary 5 Ned 5 В некоторых книгах по теории графов, корень имеет нулевой уровнь вместо первого. Если Вам нравится это соглашение, используйте выражение "(COUNT(*)-1)". Самообъединения в комбинации с предикатом BETWEEN- основной шаблон для других запросов. Получение простой суммы зарплаты подчиненных менеджера работает на том же самом принципе. Заметьте, что эта общая сумма будет также включать зарплату босса: SELECT P1.emp, SUM(P2.salary) AS payroll FROM Personnel AS P1, Personnel AS P2 WHERE P2.lft BETWEEN P1.lft AND P1.rgt GROUP BY P1.emp; emp payroll === ======= Albert 7800.0
- Стены из чистого дерева.
- Комнатные растения для дома и души
- Белое дерево " Уроки Photoshop CS2 :: Уроки фотошопа :: Уроки
- Деревянные окна, стеклопакеты, окна из дерева, производство деревянных
- Почему деревья не ходят. Борис Заходер. Стихотворения о животных
- Магические свойства деревьев и трав по Краснову И.П..
- доска, дерево, паркет, фурнитура, дуб, фрезы