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

Узлы дерева, которые не имеют поддеревьев, называются листьями. В перечне материалов, это - минимальные части, на которые может быть разобрана деталь. Потомки, или дети, родительского узла - все узлы в поддереве, имееющего родительский узел коренем.

Деревья часто изображаются как диаграммы. (См. рисунок 1) Другой путь представления деревьев состоит в том, чтобы показывать их как вложенные множества (см. рисунок 2); Это основа для используемого мной представления деревьев в 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);

У корня дерева boss - NULL:

        SELECT *

        FROM Personnel

        WHERE boss IS NULL;

Реальные проблемы возникают при попытке вычислить значения вверх и вниз по дереву. Как упражнение, напишите запрос, суммирующий жалованье каждого служащего и его/ее подчиненных; результат:

        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