Дерево – это нелинейная структура данных, используемая для представления иерархических связей, имеющих отношение «один ко многим».

Дерево с базовым типом Т определяется рекурсивно либо как пустая структура (пустое дерево), либо как узел типа Т с конечным числом древовидных структур этого же типа, называемых поддеревьями.

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

Самый верхний узел дерева называется корнем. Верхний узел для нижнего узла называется предком, а нижний узел для верхнего – потомком. Вершины (узлы), не имеющие потомков, называются терминальными вершинами или листьями. Нетерминальные вершины называются внутренними. Две вершины дерева соединяются ветвью. Дерево без ветвей с одной вершиной – это пустое или нулевое дерево.

Корень дерева лежит на нулевом уровне. Максимальный уровень какой-либо вершины дерева называется ее глубиной (от корня до узла) или высотой (от узла до максимально удаленного листа). Отсюда максимальный уровень корня равен нулю. Максимальный уровень всех вершин называется глубиной дерева.

Число непосредственных потомков у вершины (узла) дерева называется степенью вершины (узла).

Максимальная степень всех вершин является степенью дерева. Число ветвей от корня к вершине есть длина пути к этой вершине.

Каждому узлу дерева можно сопоставить имя узла и значение узла, то есть собственно данные, хранящиеся в этом узле. Причем, если значением являются разнородные данные (записи или объединения), то значением узла можно считать значение одного из полей этих данных, называемого ключом.

25. Определение СУБД. История развития. Языковые и программные средства СУБД. История развития СУБД насчитывает более 35 лет. В 1968 году была введена в эксплуатацию первая промышленная СУБД система IMS фирмы IBM. Первый этап развития СУБД связан с организацией баз данных на больших машинах типа IBM 3601370, EC – IBM и мини-ЭВМ типа PDP11. Базы данных хранились во внешней памяти центральной ЭВМ, пользователями этих баз данных были задачи, запускаемые в основном в пакетном режиме. Интерактивный режим доступа обеспечивался с помощью консольных терминалов, которые не обладали собственными вычислительными ресурсами (процессором, внешней памятью) и служили только устройствами ввода – вывода для центральной ЭВМ. Программы доступа к БД писались на различных языках и запускались как обычные числовые программы. СУБД – это совокупность программных и языковых средств, предназначенных для создания, ведения и совместного использования БД многими пользователями. Язык описания данных (ЯОД) – это язык высокого уровня, который предназначается для описания схемы баз и данных или ее частей. Описание структуры данных на формализованном языке называется схемой данных. С помощью ЯОД выполняется описание типов данных, подлежащих хранению или выборке из базы, их структур и связей между собой. ЯОД – это не процедурный язык. Исходные тексты (описание данных) после трансляции отображаются в управляющие таблицы адресов памяти. В соответствии с полученным описанием СУБД находит в базе требуемые данные, преобразует их и передает в прикладную программу, которой они необходимы, либо определяет место в памяти системы, куда требуется разместить и в каком виде, а также с какими данными установить связь. Для конкретной СУБД возможны различные способы обработки исходных текстов описаний данных, составленных на ЯОД. В одних случаях вначале трансляция описаний с целью выявления синтаксических ошибок, если ошибок нет, выполняется дальнейшая обработка запроса. В других случаях после трансляции и отладки (в случае выявления ошибок), готовые отлаженные описания с помощью ОС помещают в специальную библиотеку описаний, откуда СУБД выбирает их по соответствующему идентификатору при обработке запросов, (идентификатор соответствующего запроса поступает в запрос). СУБД значительно различаются по своим характеристикам и функциям. Первые продукты такого рода были разработаны для больших ЭВМ в конце 1960-х годов и были весьма примитивны. С тех пор СУБД постоянно совершенствовались, а функции их расширялись. Усовершенствования касались не только обработки баз данных: СУБД также снабжались функциями, упрощающими создание приложений баз данных. Характеристики и функции СУБД можно разделить на три подсистемы: подсистему средств проектирования, подсистему средств обработки и ядро СУБД.Подсистема средств проектирования (design tools subsystem) представляет собой набор инструментов, упрощающих проектирование и реализацию баз данных и их приложений. Как правило, этот набор включает в себя средства для создания таблиц, форм, запросов и отчетов. В СУБД также имеются языки программирования и интерфейсы для них. Подсистема обработки (run-time subsystem) занимается обработкой приложений, созданных с помощью средств проектирования. Ядро СУБД (DBMS) выполняет функцию посредника между подсистемой средств проектирования и обработки и данными. Ядро СУБД получает запросы, выраженные в терминах таблиц, строк и столбцов и преобразует эти запросы в команды операционной системы, выполняющие запись и чтение данных с физического носителя. Кроме того, ядро участвует в управлении транзакциями, блокировке, резервном копировании и восстановлении.