Иерархическая структура данных

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Иерархические структуры данных

2. Сравнение моделей данных

3. Упорядочение структур данных

Заключение

Список литературы

Введение

Историю технологии БД принято отсчитывать с начала 1960-х гг., когда появились первые попытки создания специальных программных средств управления базами данных. За прошедшие десятилетия возникали и использовались различные подходы к организации баз данных. Для описания одного из них мы воспользуемся понятием модели данных, предложенным в 1969 г. Эдгаром Коддом. Кодд ввел это понятие для описания конкретного реляционного подхода к организации БД. Понятие модели данных оказалось удобным не только для описания реляционного подхода и сравнения реализаций реляционных СУБД, но и для реализационно-независимого представления и сопоставления других подходов к организации баз данных.

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

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

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

иерархический база данные

1. Иерархические структуры данных

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

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

Пуск > Программы > Стандартные > Калькулятор.

К основным понятиям иерархической структуры относятся: уровень, элемент (узел), связь. Иерархическая модель организует данные в виде древовидной структуры. Дерево представляет собой иерархию элементов называемых узлами. Узел - это совокупность атрибутов данных, описывающих некоторый объект. На схеме иерархического дерева узлы представляются вершинами графа. Каждый узел на более низком уровне связан только с одним узлом, находящимся на более высоком уровне. Иерархическое дерево имеет только одну вершину (корень дерева), не подчиненную никакой другой вершине и находящуюся на самом верхнем (первом) уровне. Зависимые (подчиненные) узлы находятся на втором, третьем и т.д. уровнях. Количество деревьев в базе данных определяется числом корневых записей.

Иерархическая структура БД

К каждой записи базы данных существует только один (иерархический) путь от корневой записи.

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

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

Организация данных в СУБД иерархического типа определяется в терминах: элемент, агрегат, запись (группа), групповое отношение, база данных.

Атрибут (элемент данных) - наименьшая единица структуры данных. Обычно каждому элементу при описании базы данных присваивается уникальное имя. По этому имени к нему обращаются при обработке. Элемент данных также часто называют полем.

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

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

В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи. В нашем примере путь доступа к текстовому процессору Word 2000 выразится следующим двоичным числом: 1010.

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

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

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

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

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

Понятия отношения и веерного отношения в иерархической модели данных не изменяются.

Иерархической базой данных называется множество отношений и веерных отношений, для которых соблюдаются два ограничения:

1. Существует единственное отношение, называемое корневым, которое не является зависимым ни в одном веерном отношении.

2. Все остальные отношения (за исключением корневого) являются зависимыми отношениями только в одном веерном отношении.

Схема иерархической БД по составу компонентов идентична сетевой базе данных. Названные выше ограничения поддерживаются иерархическими СУБД.

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

В графических иллюстрациях структуры приводятся ключи соответствующих отношений.

Иерархическая база данных для вуза. а - исходная структура; б - с добавленными сведениями о группах дипломников

Если понадобится в рамках данной иерархической структуры указать для групп, выполняющих дипломное проектирование, связь с соответствующей выпускающей кафедрой, то установить веерное отношение Р(Кафедра, Группа) невозможно, так как Группа не может быть зависимым отношением дважды (она уже является зависимой для отношения Факультет). Зафиксировать связь студенческих групп с выпускающей кафедрой можно путем выделения соответствующих групп в отдельное отношение с ключом В - группа, что приводит к появлению избыточной информации.

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

Далее эта информация организуется в линейную последовательность значений.

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

Линейное представление значений в иерархической базе данных: а - иерархическая взаимосвязь значений; б - линейное представление данных

От достигнутого уровня происходит подъем на предыдущий уровень, и если возможно применить шаг 1, то процесс повторяется.

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

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

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

2. Сравнение моделей данных

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

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

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

* Теоретическое обоснование. Наличие теоретически обоснованных методов нормализации отношений и проверки ацикличности структуры позволяет получать базы данных с заданными характеристиками.

* Независимость данных. Когда необходимо изменить структуру реляционной БД, это, как правило, приводит к минимальным изменениям в прикладных программах.

* Минимальный расход памяти. Для задач, допускающих реализацию с помощью любой из трех моделей данных, иерархическая модель позволяет получить представление с минимально требуемой памятью.

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

* Низкая скорость при выполнении операции соединения.

* Большой расход памяти для представления реляционной БД. Хотя проектирование в ЗНФ рассчитано на минимальную избыточность (каждый факт представляется в БД один раз), другие модели данных обеспечивают меньший расход памяти для представления тех же фактов. Например, длина адреса связи обычно намного меньше, чем длина значения атрибута.

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

* Допустимость только навигационного принципа доступа к данным.

* Доступ к данным производится только через корневое отношение.

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

3. Упорядочение структур данных

Списочные и табличные структуры являются простыми. Ими легко пользоваться, поскольку адрес каждого элемента задается числом (для списка), двумя числами(для двумерной таблицы) или несколькими числами для многомерной таблицы. Они также легко упорядочиваются. Основным методом упорядочения является сортировка. Данные можно сортировать по любому избранному критерию, например: по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо параметра.

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

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

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

Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который можно использовать при поиске, сортировке и т. п. Ранее рассмотренный принцип дихотомии на самом деле является одним из методов индексации данных в иерархических структурах. После такой индексации данные легко разыскиваются по двоичному коду связанного с ними индекса.

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

Заключение

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

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

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

Список литературы

1. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем. -М.: "Финансы и статистика"2005.

2. Дейт К., "Введение в системы баз данных", Москва, 'Hаука', 2001 г.

3. 3. Дж. Мартин., "Организация баз данных в вычислительных системах" М: Мир 2001г.

4. С.М. Диго "Проектирование и использования баз данных". Москва: Финансы и статистика 2000.

5. Горев А., Ахаян Р., Макашарипов С. "Эффективная работа с СУБД". СПб.: Питер, 2003

Размещено на Allbest.ru