порядки обхода дерева

      INNER JOIN Поддерево ON Территории.[Код вышестоящей территории] = Поддерево.[Код террито

    FROM Территории

  SELECT Территории.[Код территории], Территории.[Код вышестоящей территории], Территории.Наименование, Уровень + 1

    WHERE [Код вышестоящей территории] = 40288000 — корень поддерева или IS NULL для корня целого дерева

    FROM Территории

  SELECT [Код территории], [Код вышестоящей территории], Наименование, 1

WITH Поддерево ([Код территории], [Код вышестоящей территории], Наименование, Уровень) AS

Выборка поддерева по заданному узлу (здесь и далее по тексту используем синтаксис MS SQL Server 2005):

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

Корневые вершины отличаются от других пар пустой (NULL) ссылкой на предка, в приведенном примере это поле «Код вышестоящей территории».

Матрица смежности может быть также представлена в виде списка (множества) пар с номерами (идентификаторами, кодами) вершин по принципу: есть пара — есть связь, нет пары — нет связи.

Как известно из теории, граф можно представить в виде матрицы, где на пересечении i-й строки и j-го столбца стоит 1, если между узлами (вершинами) графа с номерами i и j есть связь (ребро, дуга), или 0 в противном случае. Такая абстракция называется матрицей смежности.

Это интуитивно понятный способ организации дерева: замыкаем связь таблицы на саму себя (рефлексивная связь), рис. 1.

Список смежности

Углубляться в теорию графов в рамках статьи мы не будем, ограничившись минимальными пояснениями по ходу изложения, и рассмотрим наиболее часто встречающиеся варианты реализации древовидных структур в базах данных. В качестве примера используем Microsoft SQL Server 2005, но, познакомившись с общими принципами, вы сможете без затруднений перенести реализацию на любую другую СУБД, с которой придется работать.

В общем случае все сводится к моделированию многоуровневой связи «главный—подчиненный», «предок—потомок», «общий—конкретный». Говоря более строгим математическим языком, мы моделируем граф без циклов.

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

Иерархические структуры и деревья в SQL

Поиск: Весь сервер Новости Computerworld Мир ПК Открытые системы Windows IT Pro LAN Сети Директор ИС Следите за нами: Авторизоваться с помощью:

Иерархические структуры и деревья в SQL - 03, 2007 | Мир ПК | Издательство «Открытые системы»