Дескрипторные модели - использовались на ранних стадиях использования документальн. БД. Каждому документу соответствовал дескриптор т.е. описатель. Этот дескриптор имел жесткую стр-ру и описывал документ в соотв. с теми хар-ми, которые требуются для работы с док-ми, разрабатываемыми в БД.
Иерархическая модель данных является наиболее простой среди всех дателогических моделей. Исторически они появились самыми первыми (среди дателогических моделей). Основными информационными единицами иерархической модели данных явл. БД, сегмент и поле. Поле данных определяется как тип, неделимая единица данных доступная пользователю с помощью СУБД. Сегмент - запись, при этом в рамках иерархической модели данных определяется 2 понятия данных: тип сегмента(тип записи), экземпляр сегмента(экземпляр записи). Тип сегмента - это поименованная совокупность типов эл-тов данных. Экземпляр сегмента образуется из конкретных значений полей или элементов данных. Каждый тип сегмента в рамках иерархической модели образует некоторый набор однородной записи. Для возможности различия отдельной записи в данном наборе каждый тип сегмента должен иметь ключ, или набор ключевых атрибутов. Ключом называют набор элементов данных однозначно идентифицирующих экземпляр сегмента. В иерархической модели сегменты объединяются в ориентированный двухуровневый граф. При этом полагают, что направленные ребра графа отражают иерархические связи между сегментами. Каждому экземпляру сегмента, стоящему выше по иерархии и соединенным с данным типом сегмента соответствует несколько экземпляров данного подчиненного типа сегмента. Тип сегмента находящегося на более высоком уровне иерархии называют логически-исходящим по отношениям к типам сегмента соединенными с данными направленными иерархическими ребрами, которые в свою очередь называются логически-подчиненными по отношению к этому типу сегмента. Иногда исходные сегменты называют сегментами-продуктами, а подчиненные сегменты называют сегментами-потомками.
Схема БД: Схема иерархической БД представляет собой совокупность отдельных деревьев, каждое дерево в рамках модели называют физической БД. Каждая физическая БД удовлетворяет следующим иерархическим ограничениям:
1. в каждой физической БД существует один корневой сегмент, т.е. сегмент у которого нет логически-исходного типа сегмента.
2. каждый логически-исходный сегмент может быть связан с производным числом логически-подчиненным сегментом.
3. каждый логически-подчиненный сегмент может быть связан только с одним логически-исходным сегментом.
Сегмент является экземпляром типа сегмент.
Пр. Группа (номер, староста)
сегменты этого типа:
383, иванов
500, петров
и т.д.
Между экземплярами сегмента также существуют иерархические связи.
Экземпляры потомки одного типа, связанные с одним экземпляром сегмента-предка называют близнецами.
Пр. (по рис1.) экземпляры b1,b2,b3 являются близнецами, но b4 подчинен другому экземпляру родительского сегмента и он не является близнецом по отношению к экземпляру b1,b2,b3. Набор всех экземпляров-сегментов подчиненных одному экземпляру корневого сегмента называют физической записью. Количество экземпляров потомков-потомков может быть разным для разных экземпляров родительских сегментов. Поэтому в общих случаях физические записи имеют разную длину. Физические записи в иерархической модели различаются по длине и структуре.
Древовидные структуры:
Опр. Дерево каждый узел которого может быть представлен одним и тем же типом записи называют однородным. (например генеалогическое дерево)
Опр. Дерево в котором задан порядок следования узлов называется упорядоченным. (алгебраическое выражение)
Опр. В неоднородных деревьях каждый узел представлен различными типами.
Опр. Дерево называется сбалансированным если разница деревьев любых двух листьев, т.е. конечных вершин не превышает 1.
Лекция 27.10.
Основные методы работы с древовидными структурами
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.