Система учета и контроля работоспособности оборудования на примере городской локальной сети

- опрашивание конечных пользователей, подключенных к этому оборудованию;

- опрашивание самого оборудования.

В первом случае, есть достаточное количество неудобств, связанных с:

- отсутствием электропитания в квартире;

- выключенным персональным компьютером;

- задержкой ответов, связанной с некорректной работой сетевой платы, или ПК в целом;

- установленными защитными средствами, блокирующие запрос-ответ.

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

В виду того, что сеть базируется на оборудовании, подразделяющемся на несколько уровней (в частности управляемые (Layer 2/3 Switch) и неуправляемые (Layer 2 Switch)). Выявление активности и работоспособности оборудования будет вывялятся следующими методами.

Неуправляемые коммутаторы опрашиваются за счет активности подключенных к ним клиентов, если такие в данный момент имеются, а также установленным устройством NetPing B+/PWR-220 от компании LightCom, предназначенное для проверки работоспособности Ethernet сегментов сетей, в которых отсутствуют постоянно включенные устройства, с возможностью автоматической перезагрузки активного сетевого оборудования.

Его особенностями являются следующие параметры как:

Ответ на ICMP запрос (ping запрос) по уникальному IP адресу устройства.

Установку любого IP адреса устройства.

Установку любого MAC адреса устройства.

Сохранение IP и MAC адресов в энергонезависимой памяти после выключения питания устройства.

Изменение IP и MAC адресов удаленно по протоколу UDP при помощи утилиты конфигурирования устройства.

Шифрование пакетов UDP для защиты устройства от несанкционированного изменения параметров.

Защиту от изменения параметров устройства при помощи перемычки на плате устройства.

Сброс параметров к их значению по умолчанию при помощи перемычки на плате устройства.

Поддержка шлюза для отправки пакетов (при ответе) во внешние сети

Ограничение диапазона IP адресов, с которых разрешен доступ к устройству

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

Управляемые коммутаторы опрашиваются через протокол SNMP, а точнее автономный SNMP-траппер, распознающий Cold/Warm Start и Link Up/Down.

Следующим этапом в разработке этой системы является ограничение набора используемых средств.

3. Программная реализация информационной системы

3.1 Средства разработки

Прежде чем приступать к реализации системы следовало определиться со средствами реализации, такими как среда разработки и драйвер базы данных. В качестве среды разработки была выбрана система Unix, с установленным и поддерживающим языком PHP, а для создания базы данных была использована СУБД MySQL.

PHP.

PHP (его полное название: PHP: Hypertext Preprocessor) - это широко используемый язык сценариев общего назначения с открытым исходным кодом. Т.е. PHP это язык программирования, специально разработанный для написания web-приложений (сценариев), исполняющихся на Web-сервере.

Синтаксис языка берет начало из C, Java и Perl. PHP достаточно прост для изучения. Преимуществом PHP является предоставление web-разработчикам возможности быстрого создания динамически генерируемых web-страниц.

Важным преимуществом языка PHP перед такими языками, как языков Perl и C заключается в возможности создания HTML документов с внедренными командами PHP.

Значительным отличием PHP от какого-либо кода, выполняющегося на стороне клиента, например, JavaScript, является то, что PHP-скрипты выполняются на стороне сервера. Можно сконфигурировать свой сервер таким образом, чтобы HTML-файлы обрабатывались процессором PHP, так что клиенты даже не смогут узнать, получают ли они обычный HTML-файл или результат выполнения скрипта.

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

С помощью PHP можно реализовать все те же возможности, что и с помощью CGI-программ. Например: обрабатывать данные из форм, генерировать динамические страницы, получать и посылать куки (cookies).

Кроме этого в PHP включена поддержка многих баз данных (databases), что делает написание Web-приложений с использованием БД до невозможности простым.

Вот неполный перечень поддерживаемых БД:

Adabas D.

InterBase.

Solid.

dBase.

mSQL.

Sybase.

Empress.

MySQL.

Velocis.

FilePro.

Oracle.

Unix dbm.

Informix.

PostgreSQL.

Вдобавок ко всему PHP понимает протоколы IMAP, SNMP, NNTP, POP3 и даже HTTP, а также имеет возможность работать с сокетами (sockets) и общаться по другим протоколам.

JsHttpRequest: AJAX-библиотека.

Библиотека JsHttpRequest -- это мощная утилита для создания AJAX-приложений на PHP. библиотека для создания AJAX-приложений, отличающаяся повышенной кроссбраузерностью, простотой и универсальностью, а также умеющая закачивать файлы на сервер без перезагрузки страницы и работать с формами целиком. Она "прозрачно" поддерживает русскоязычные кодировки (в том числе windows-1251), имеет простотой интерфейс, а также умеет закачивать файлы на сервер без перезагрузки страницы и работать с формами целиком.

Краткий перечень ее ключевых возможностей и отличий от аналогов:

· Кроссбраузерность. Библиотека работает в IE5.0+, Mozilla 1.7+, Firefox 1.0+, Opera 7.20+, Safari (здесь "+" означает "в этой и более новых версиях"). Кроме того, код может работать без поддержки ActiveX и XMLHttpRequest (однако, если эти возможности включены в браузер, они автоматически задействуются). Кроссбраузерность гарантируется автоматическим framework-ом для тестирования библиотеки.

· Поддержка и "прозрачная" работа с любыми кодировками в том числе русскоязычными.

· Закачка файлов (upload) из браузера на сервер без перезагрузки страницы.

· Совместимость с библиотекой prototype. Prototype -- это популярное средство для упрощения работы JavaScript-программиста, включающее поддержку AJAX и другие возможности. Библиотека JsHttpRequest может быть использована в качестве ее серверной PHP-части (после подключение небольшого модуля совместимости JsHttpRequest-prototype.js). При этом все дополнительные возможности, присущие JsHttpRequest (кроссбраузерность, закачка файлов, работа с русскими кодировками и т. д.), остаются в силе.

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

· Передача многомерных структур (аналог JSON) в данных запроса и ответа сервера. При этом используются стандартные средства PHP -- многомерные массивы (данные запроса можно получить из $_REQUEST, данные ответа записываются в $_RESULT), а также стандартные средства JavaScript -- вложенные объекты и свойства. Никакого XML на уровне API: работа происходит "родными" средствами языков.

· Поддержка сессий PHP стандартными средствами.

· Выбор оптимального метода загрузки данных (XMLHttpRequest, Microsoft.XMLHTTP, <SCRIPT>, <IFRAME>) в зависимости от браузера. В частности, возможность загружать данные с других хостов.

· Компонентность библиотеки позволяет отключить ненужные методы загрузки и тем самым сократить объем JavaScript-кода. Например, если вы не планируете закачивать файлы AJAX-ом, вы можете выбрать версию с поддержкой только XML- и SCRIPT-загрузчиков.

· Интерфейс, совместимый с XMLHttpRequest.

Выбор в пользу СУБД MySQL.

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

SQL - это сокращение от Structured Query Language (структурированный язык запросов). SQL создан для работы с реляционными базами данных. Он позволяет пользователям взаимодействовать с базами данных (просматривать, искать, добавлять и управлять данными). MySQL соответствует спецификации ANSI 92 SQL.

Язык SQL достаточно сложен и многогранен. При работе небольшой фирмы, или базы данных в сети internet круг задач ограничен. Поэтому была создана небольшая, но очень быстрая и функциональная реляционная СУБД MySQL. То есть в MySQL задействован не весь язык SQL, а только необходимая его часть. Но этот нюанс нисколько не ограничивает в функциональности данную систему.

Вот перечень основных возможностей пакета MySQL - это многопоточность, поддержка нескольких одновременных запросов, оптимизация связей с присоединением многих данных за один проход, записи фиксированной и переменной длины, ODBC драйвер в комплекте с исходным кодом, гибкая система привилегий и паролей, до 16 ключей в таблице, каждый ключ может иметь до 15 полей. Также есть поддержка ключевых полей и специальных полей в операторе CREATE, поддержка чисел длинной от 1 до 4, строк переменной длины и меток времени, интерфейс с языками C и perl. Основанная на потоках, быстрая система памяти, утилита проверки и ремонта таблицы, все данные хранятся в формате ISO8859_1. Все операции работы со строками не обращают внимания на регистр символов в обрабатываемых строках, псевдонимы применимы как к таблицам, так и к отдельным колонкам в таблице, все поля имеют значение по умолчанию. INSERT можно использовать на любом подмножестве полей. Легкость управления таблицей, включая добавление и удаление ключей и полей.

Можно выполнять команды SQL непосредственно из командной строки системы Unix или из интерактивного режима MySQL. СУБД MySQL имеет библиотеку C API. Ее можно использовать для запросов к базе данных, вставки данных, создания таблиц и т.п.

Кроме технических подробностей можно добавить, что MySQL работает как на Unix, так и на платформе Windows 95/98, он очень прост и удобен в работе.

Иерархические структуры данных в реляционных БД.

Сегодня большинство хранилищ данных, как простых так и сложных, построены на основе реляционных баз данных. В них используются либо файл-серверные системы (dBase, Paradox, Clipper, FoxPro, Access), либо SQL-серверы (Oracle, Informix, Sybase, Borland InterBase, MS SQL и т.д.). Реляционные базы данных в большинстве случаев удовлетворяют требования какой-либо предметной области данных, но часты и случаи когда требуется представление и хранение данных в иерархическом виде.

Архитектура реляционных баз данных ориентирована на хранение внутри таблиц БД информации о сущностях информационной системы и связях между ними. Каждая из записей таблицы содержит информацию об одном экземпляре. Организация хранения информации о независимых друг от друга экземплярах сущностей (т.е. так называемых «плоских» данных) не вызывает никаких затруднений. Однако, наряду с «плоскими» данными, при построении даже простых информационных систем, приходится хранить в БД и информацию о «вложенных» друг в друга сущностях, т.е иерархические данные.

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

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

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

Обработка данных. Данные можно обрабатывать самыми различными способами. Можно выбирать любые поля, фильтровать и сортировать данные. Можно объединять данные со связанной с ними информацией и вычислять итоговые значения. Вы также можете отобрать некоторые данные и затем изменить, удалить, скопировать их в другую таблицу или создать для них новую таблицу.

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

Все эти функциональные возможности в полной мере реализованы в MySQL, как и в любой другой СУБД.

Обзор существующих программных средств и протоколов проверки соединений в сетях.

Выбор способов и объектов мониторинга сети зависит от множества факторов. На самом общем уровне можно говорить о таких элементах как:

1. проверка физической доступности оборудования;

2. детальная проверка не критичных, но важных параметров функционирования сети: производительности, загрузки и т.п.;

3. проверка параметров, специфичных для сервисов и служб данного конкретного окружения (наличие некоторых значений в таблицах БД, содержимое лог-файлов).

Начальный уровень любой проверки - тестирование физической доступности оборудования (которая может быть нарушена в результате отключения самого оборудования либо отказе каналов связи). Как минимум, это означает проверку доступности по Internet Control Message Protocol (ICMP) (ping), причем желательно проверять не только факт наличия ответа, но и время прохождения сигнала, и количество потерянных запросов: аномальные значения этих величин, как правило, сигнализируют о серьезных проблемах в конфигурации сети.

Internet Control Message Protocol (ICMP).

Одним из основных элементов прослушивания сети, вне зависимости от установленного оборудования, является утилита ping.

Ping -- это служебная компьютерная программа, предназначенная для проверки соединений в сетях на основе TCP/IP.

Она отправляет запросы Echo-Request протокола ICMP указанному узлу сети и фиксирует поступающие ответы (ICMP Echo-Reply). Время между отправкой запроса и получением ответа (RTT, от англ. Round Trip Time) позволяет определять двусторонние задержки (RTT) по маршруту и частоту потери пакетов, то есть косвенно определять загруженности каналов передачи данных и промежуточных устройств.

Также пингом называется время, затраченное на передачу пакета информации в компьютерных сетях от клиента к серверу и обратно от сервера к клиенту, оно измеряется в миллисекундах. Время пинга связано со скоростью соединения и загруженностью каналов на всём протяжении от клиента к серверу.

Полное отсутствие ICMP-ответов может также означать, что удалённый узел (или какой-либо из промежуточных маршрутизаторов) блокирует ICMP Echo-Reply или игнорирует ICMP Echo-Request.

Программа ping является одним из основных диагностических средств в сетях TCP/IP и входит в поставку всех современных сетевых операционных систем. Функциональность ping также реализована в некоторых встроенных ОС маршрутизаторов, доступ к результатам выполнения ping для таких устройств по протоколу SNMP определяется RFC 2925 (Definitions of Managed Objects for Remote Ping, Traceroute, and Lookup Operations).

В системах Unix одним из самых надежных и проверенных методов прослушивания является использование утилиты fping.

Fping - это программа, которая позволяет пользователям с помощью запросов echo request протокола ICMP определить отвечает ли удаленный компьютер. fping отличается от ping тем, что в командной строке можно указать любое количество целей, или указать файл, который содержит список целей, которые необходимо опросить. Вместо того чтобы посылать пакеты одной цели до тех пор пока она не ответит или не истечет таймаут, fping посылает пакет ping и переходит к следующей цели в циклической последовательности.

По умолчанию, если цель отвечает, то она удаляется из списка проверки; если цель не отвечает в течении определенного временного лимита и/или лимита повторений, то она считается недоступной. fping также может посылать определенное количество пакетов или может зацикливаться бесконечно (как в ping). В отличие от ping, fping задумывался для использования в скриптах, так что его вывод планировался так, чтобы его было просто обработать.

У описанных выше утилит есть существенный недостаток по сравнению с утилитами протокола ARP:

- ограничение одной подсетью;

- медленным временем реакции на запрос-ответ;

- возможность блокирования ICMP Echo-Reply и игнор ICMP Echo-Request;

- отсутствие метода проверки соотношения на Ethernet-адрес / IP-адрес.

Address Resolution Protocol (ARP)

ARP (англ. Address Resolution Protocol -- протокол разрешения адресов) -- сетевой протокол, предназначенный для преобразования IP-адресов (адресов сетевого уровня) в MAC-адреса (адреса канального уровня) в сетях TCP/IP. Он определён в RFC 826.

Каждый узел сети имеет два адреса, физический адрес и логический адрес. В сети Ethernet для идентификации источника и получателя информации используются оба адреса. Информация пересылаемая от одного компьютера другому по сети содержит в себе физический адрес отправителя, IP-адрес отправителя, физический адрес получателя и IP-адрес получателя. ARP-протокол обеспечивает связь между этими двумя адресами. Существует четыре типа ARP-сообщений: ARP-запрос (ARP request), ARP-ответ (ARP reply), RARP-запрос (RARP-request) и RARP-ответ (RARP-reply). Локальный хост при помощи ARP-запроса запрашивает физический адрес хоста-получателя. Ответ (физический адрес хоста-получателя) приходит в виде ARP-ответа. Хост-получатель, вместе с ответом, шлет также RARP-запрос, адресованный отправителю, для того, чтобы проверить его IP адрес. После проверки IP адреса отправителя, начинается передача пакетов данных.

Перед тем, как создать подключение к какому-либо устройству в сети, IP-протокол проверяет свой ARP-кеш, чтобы выяснить, не зарегистрирована ли в нём уже нужная для подключения информация о хосте-получателе. Если такой записи в ARP-кеше нет, то выполняется широковещательный ARP-запрос. Этот запрос для устройств в сети имеет следующий смысл: "Кто-нибудь знает физический адрес устройства, обладающего следующим IP-адресом?" Когда получатель примет этот пакет, то должен будет ответить: "Да, это мой IP-адрес. Мой физический адрес следующий: ..." После этого отправитель обновит свой ARP-кеш, и будет способен передать информацию получателю.

Arping - ARP level ping utility - программа позволяет выполнить эхо-запрос указав MAC адрес, сопоставить MAC и IP адрес минуя ARP кэш. Например, при появлении в сети злоумышленника наполняющего сеть не IP пакетами, можно вычислить его IP адерс.

Принцип ее действия простой - создается ICMP-пакет типа Ping Request, где в IP-заголовке прописан широковещательный адрес назначения 255.255.255.255, а в Ethernet-заголовке - MAC-адрес, который нужно пингануть. Если ответ на широковещательный пинг от узла с заданным MAC есть, то в ответе будет фигурировать его IP адрес. Но пинговаться машины будут только если они:

1) отвечают на запросы ICMP Ping (сетевой экран не фильтрует данный тип входящих ICMP-пакетов)

2) отвечают на широковещательные ICMP (а это по умолчанию практически везде запрещено, net.ipv4.icmp_echo_ignore_broadcasts=1, дабы машины нельзя было тривиально использовать для проведения Reflection DDoS).

Более надежный способ опроса сети, с учетом обхода сетевых экранов, на соответствие IP адреса, соответсвующего заданному MAC- это ARP-сканирование по диапазону IP-адресов утилитой Arpdig.

Arpdig - средство сканирования целого сегмента адресов IP или списка, через whohas запросы ARP, собирающее ARP - ответы и показывающее результаты.

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

Simple Network Management Protocol (SNMP).

SNMP (англ. Simple Network Management Protocol -- простой протокол управления сетью) -- это протокол управления сетями связи на основе архитектуры TCP/IP.

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

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

Управляющая система может получить информацию через операции протокола GET, GETNEXT и GETBULK. Агент может самостоятельно без запроса отправить данные, используя операцию протокола TRAP или INFORM. Управляющие системы могут также отправлять конфигурационные обновления или контролирующие запросы, используя операцию SET для непосредственного управления системой. Операции конфигурирования и управления используются только тогда, когда нужны изменения в сетевой инфраструктуре. Операции мониторинга обычно выполняются на регулярной основе.

Переменные доступные через SNMP организованы в иерархии. Эти иерархии и другие метаданные (такие как тип и описание переменной) описываются Базами Управляющей Информации (англ. Management Information Bases (MIBs)).

Сам по себе SNMP не определяет, какая информация (какие переменные) управляемая система должна предоставлять. Зачастую SNMP использует расширяемую модель, где доступная информация определяется Базами Управляющей Информации (MIB). Базы Управляющей Информации описывают структуру управляющей информации устройств. Они используют иерархическое пространство имен содержащее уникальный идентификатор объекта (англ. object identifier (OID)). Грубо говоря, каждый уникальный идентификатор объекта идентифицирует переменную, которая может быть прочитана или установлена через SNMP. MIBы используют нотацию, определенную в ASN.

Иерархия MIB может быть изображена как дерево с безымянным корнем, уровни которого присвоены разными организациями. На самом высоком уровне MIB OIDы принадлежат разным организациям, пока на более низком уровне OIDы выделяются ассоциированным организациям. Эта модель реализует управление через все слои сетевой модели OSI так как MIBы могут быть определены для всех подобных ситуаций и информации.

Управляемый объект - это одна из любого числа характеристик специфических для управляемого устройства. Управляемый объект включает в себя один или более экземпляров объекта (идентифицируемых по OID), которые на самом деле переменные.

Существует два типа управляемых объектов:

Скалярные объекты определяют единственный экземпляр объекта.

Табличные объекты определяют множественные, связанные экземпляры объектов которые группируются в таблицах MIB.

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

Идентификатор объекта (OID) уникально идентифицирует управляемый объект в иерархии MIB.

3.2 Программная реализация проекта

Вся структура системы реализована через PHP скрипты, работающими с данными хранящимися в базе данных MySQL и выводящейся всей необходимой информацией на web приложение, которое наглядно помогает ориентироваться и работать со всеми необходимыми компонентами. Web- интерфейс в свою очередь реализован через средства HTML, PHP и JSHttpRequest под управлением Web-сервера Apache, с дополнительно установленными такими средствами как: JpGraph, GD. Вся система находится под управлением системы FreeBSD v.7.0, в связи с ее стабильностью работы, великолепно себя зарекомендовавшей в качестве операционной системы под сервера, не высокими системными требованиями к аппаратной конфигурации и поддержкой необходимых программного обеспечения для реализации системы.

Система функционирует на сервере с конфигурацией:

Тип ЦП: Pentium 233 МГц.

Системная плата: Gigabyte GA-6VTX (1 ISA, 5 PCI, 1 AGP, 1 AMR, 3 DIMM, Audio).

Чипсет системной платы: VIA VT82C694T Apollo Pro133T.

Объем оперативной памяти: 128 Мб (SDRAM).

Видеоадаптер: NVIDIA Vanta/Vanta LT (Microsoft Corporation) (8 Мб).

Дисковый накопитель: ST310212A (10Гб, Ultra-ATA/133).

Сетевой адаптер: Realtek RTL8139 Family PCI Fast Ethernet NIC.

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

Если обращение происходит к блоку редактирования или занесения информации о каком-то оборудовании, модуль AJAX состоящий из двух компонентов, строит web- страницу выбирая запросами из БД требуемых нами данных. При внесении изменений все отредактированные данные отсылаются и записываются в базу данных.

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

Механизм работы с БД.

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

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

Добавление узла в дерево осуществляется с помощью простой команды вставки записи, например:

INSERT INTO test1 (id, parent)

VALUES (<идентификатор узла>, <идентификатор родителя>);

Для перемещения узла к другому родителю следует выполнить команду UPDATE:

UPDATE test1

SET parent = <идентификатор нового родителя>

WHERE id = <идентификатор перемещаемого узла>;

Удаление узла и всего поддерева осуществляется с помощью команды DELETE: