[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Базы Данных / Язык запросов SQL /

Древовидные структуры в SQL

sql.ru

По материалам статьи Joe Celko на intelligententerprise.com " Trees in SQL"

Обзор некоторых общих вопросов, касающихся древовидных структур и иерархии в SQL


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


CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
boss CHAR(10) DEFAULT NULL REFERENCES Personnel(emp),
salary DECIMAL(6,2) NOT NULL DEFAULT 100.00);

Personnel
emp
bosssalary
'Albert''NULL'1,000.00
'Bert''Albert'900.00
'Chuck''Albert'900.00
'Donna''Chuck'800.00
'Eddie''Chuck'700.00
'Fred''Chuck'600.00

Таблица 1. Список смежных вершин графа

Другим способом представления древовидной структуры являются вложенные множества. Поскольку SQL является языком, предназначеным для работы со множествами, то эта модель является более предпочтительной, чем стандартный пример списка смежных вершин графа, который более часто встречается в литературе. Давайте создадим тестовую таблицу Personnel, не обращая пока внимания на поля lft и rgt:


CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
CONSTRAINT order_okay CHECK (lft < rgt) );

Эта проблема часто описывается в учебниках с помощью поля для Сотрудника (Personnel emp) и одного из его Начальников (Boss). Следующая таблица (Таблица 2) - за исключением полей lft и rgt - в теории графов называется список смежных вершин графа или пары вершин графа, смежные друг другу.

Personnel
emp
iftrgt
'Albert'112
'Bert'23
'Chuck'411
'Donna'56
'Eddie'78
'Fred'910

Таблица 2. Вложенные множества

Структура организации может быть представлена в виде направленного графа, как показано на рис.1

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

Еще одной проблемой, связанной с моделью "Список смежных вершин графа" является то, что поля Начальник (Boss) и Сотрудник (Personnel emp) содержат данные одинакового вида (имя сотрудника) и поэтому эти данные должны располагаться в одном и том же поле нормализованной таблицы. Для подтверждения того, что эти данные не нормализованы, предположим, что "Chuck" изменил свое имя на "Charles"; вы должны изменить его имя в обеих полях и в нескольких местах. По определению, в нормализованной таблице одна сущность должна встречаться лишь однажды и только в одном месте.

Последней проблемой является то, что "Список смежных вершин графа" не является подчиненной (субординационной) моделью. Полномочия передаются сверху вниз в иерархическом порядке, но если я уберу сотрудника по имени "Chuck", я разорву всю его подчиненность от сотрудника по имени "Albert". В некоторых случаях (например, для трубопроводов) это справедливо, но в нашем случае мы не предполагаем такой ситуации.

Чтобы изобразить древовидную структуру в виде вложенных множеств, заменим вершины графа овалами, где подчиненные овалы вложены один в другой. Основание дерева будет представлено самым большим овалом, который содержит все остальные овалы. Концевые вершины будут представлены самыми внутренними овалами, не содержащими внутри никаких других овалов, а вложенность будет показана иерархическими взаимоотношениями. Поля rgt и lft (я не использую зарезервированные слова RIGHT и LEFT) - это именно то, что показывает вложенность.

Если эта образная модель не работает, то представьте себе маленького червя, ползущего вдоль дерева против часовой стрелки. Каждый раз, когда он достигает правую или левую сторону вершины, он нумерует ее. Червь останавливается после того, когда он обойдет вокруг всего дерева и вернется назад к основанию.

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

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

Для преобразования графа в модель вложенных множеств вспомните о маленьком червячке, ползущем вдоль дерева. Червь начинает двигаться сверху - от основания - и обползает вокруг всего дерева. Когда он приходит к вершине, он присваивает значение стороне, которую он посещает и увеличивает значение счетчика на единицу. Каждая вершина получает два значения - одно для правой стороны и одно для левой. (Специалисты называют это модифицированным алгоритмом обхода вершин графа в прямом порядке.) И в заключение, удалим за ненадобностью поле "Personnel.Boss", которое представляло ребро графа.

Это дает нам некоторые предсказуемые результаты, которые мы можем использовать при построении запросов. Основание всегда можно представить в виде:
(left = 1, right = 2 * (SELECT COUNT(*) FROM TreeTable));
для вершин всегда справедливо (left + 1 = right); условие BETWEEN определяет поддерево и т.д. Ниже представлены некоторые базовые запросы, которые могут быть вам полезны:

1. Найти сотрудника и всех его начальников, независимо от глубины вложения.


 SELECT P2.*
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P1.emp = :myemployee;

2. Найти сотрудника и всех его подчиненных. (Этот запрос симметричен первому.)


 SELECT P1.*	-- (В оригинале опечатка: SELECT P2.*)
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P2.emp = :myemployee;
 

3. Добавьте GROUP BY и обобщенные функции к этим базовым запросам и вы получите иерархические отчеты. Например, суммарный лимит заработной платы, которой распоряжается каждый сотрудник:


SELECT P2.emp, SUM(S1.salary)
   FROM Personnel AS P1, Personnel AS P2,
        Salaries AS S1
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P1.emp = S1.emp
  GROUP BY P2.emp;
 

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


SELECT COUNT(P2.emp) AS indentation, P1.emp
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
  GROUP BY P1.emp
ORDER BY P1.emp;   -- (В оригинале опечатка: ORDER BY P1.lft)
 

5. Модель вложенных множеств содержит неявный порядок смежных вершин, которого нет в модели "Список смежных вершин графа". Добавление новой вершины как смежной крайней правой:


BEGIN
DECLARE right_most_sibling INTEGER;

SET right_most_sibling
    = (SELECT rgt
         FROM Personnel
        WHERE emp = :your_boss);

UPDATE Personnel
   SET lft = CASE WHEN lft > right_most_sibling
                  THEN lft + 2
                  ELSE lft END,
       rgt = CASE WHEN rgt >= right_most_sibling
                  THEN rgt + 2
                  ELSE rgt END
 WHERE rgt >= right_most_sibling;

INSERT INTO Personnel (emp, lft, rgt)
VALUES ('New Guy', right_most_sibling,
                  (right_most_sibling + 1))
END;
 

6. Для преобразования модели "Список смежных вершин графа" в модель вложенных множеств можно использовать a push down stack алгоритм. Предположим, что мы имеем следующую таблицу:

Несмотря на то, что эта процедура работает, вы можете переписать ее на языке, позволяющем работать с массивами, вместо того, чтобы придерживаться чистого SQL.




Комментарии

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Базы Данных / Язык запросов SQL /

Введение в SQLite
29-03-2009   

SQLite – это библиотека, написанная на языке C, реализующая SQL механизм работы с данными, другими словами, движок баз данных... подробнее

Кол. просмотров: общее - 4399 сегодня - 1

Работа с SQLite
29-03-2009   

SQLite – это реляционная база данных, запросы к которой можно осуществлять при помощи языка запросов SQL. База данных не поддерживает все особенности SQL и уступает в функциональности другим развитым СУБД, но вполне подходит для хранения и извлечения информации... подробнее

Кол. просмотров: общее - 4915 сегодня - 1

Подробно о типах данных
29-03-2009   

В следующих выпусках рубрики T-SQL для начинающих будет рассказано о применении синтаксиса T-SQL для построения таблиц. Но прежде чем начинать строить таблицы, необходимо поговорить о типах данных... подробнее

Кол. просмотров: общее - 4527 сегодня - 1

Естественные ключи против искусственных ключей
29-03-2009   

Данная статья излагает взгляд автора на проблему, регулярно обсуждающуюся в группах новостей, посвящённых разработке приложений с использованием РСУБД... подробнее

Кол. просмотров: общее - 4450 сегодня - 0

Использование команды UNION
29-03-2009   

Итак команда union используется для обьединения вывода двух или более запросов select. Особенности команды которые придется учитывать... подробнее

Кол. просмотров: общее - 4641 сегодня - 0



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects