Кольцевые структуры

Ссылки на подобные и порожденные записи

Множественные ссылки на порожденные записи

Методы физического проектирования для иерархических моделей

Инвертированные файлы

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

Пусть основной файл показан в таблице:

сотрудник

№ п/п	ФИО	ученая степень	научное звание	контактные данные	название (кафедры)	название (должности)
	Иванов И.И.	к.т.н.	доцент		СУиВТ	доцент
	Петров П.П.	к.т.н.	нет		ТАМ	доцент
	Сидоров С.С.	нет	нет		СУиВТ	ассистент
	Яковлев Я.Я.	д.т.н.	профессор		ТАМ	профессор

Соответствующие индексы показаны в таблицах:

ученая степень	ссылки		научное звание	ссылки		название (кафедры)	ссылки		название (должности)	ссылки
д.т.н.			доцент			СУиВТ	1, 3		ассистент
к.т.н.	1, 2		нет	2, 3		ТАМ	2, 4		доцент	1, 2
нет			профессор						профессор

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

Рассмотрим, как выполняется задача поиска нужной записи.

Пусть надо определить список всех сотрудников, работающих в должности доцента, К_доступ=< название (должности) = доцент>. Поиск осуществляется последовательным выполнением шагов:

1) по индексу для ключа название (должности) находится соответствующий элемент: это вторая запись в файле;

2) выбираются ссылки для этой записи: это множество {1, 2};

3) по основному файлу выбираются последовательно записи с номерами 1 и 2 и выводится содержимое поля ФИО для этих записей; получаем список - Иванов И.И. и Петров П.П. Работа алгоритма закончена.

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

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

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

кафедра

название шифр в вузе

сотрудник

сотрудник

сотрудник

кафедра

название шифр в вузе

ФИО ученая научное контактные степень звание данные

Этому абстрактному дереву соответствует следующая структура, показывающая конкретный состав кафедр вуза (верхний уровень описывает кафедры, нижний - сотрудников):

	СУиВТ					ТАМ
Иванов И.И.	к.т.н.	доцент			Петров П.П.	к.т.н.	нет
Сидоров С.С.	нет	нет			Яковлев Я.Я.	д.т.н.	профессор

Поскольку в этом дереве есть два множества подобных элементов (кафедры и сотрудники), сформируем для них таблицы:

сотрудник кафедра

№ п/п	ФИО	ученая степень	научное звание	контактные данные		№ п/п	название	шифр в вузе
	Иванов И.И.	к.т.н.	доцент				СУиВТ
	Петров П.П.	к.т.н.	нет				ТАМ
	Сидоров С.С.	нет	нет
	Яковлев Я.Я.	д.т.н.	профессор

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

название	шифр в вузе	ссылки
СУиВТ		1, 3
ТАМ		2, 4

В таком дереве «хорошо» решаются задачи поиска записей в направлении от корня к терминальным вершинам.

Пусть надо сформировать список сотрудников кафедры СУиВТ (эта задача подобна задаче поиска по вторичному ключу для линейных списков), т.е. К_доступ = < название (кафедры) = СУиВТ >. Задача решается следующим образом:

1) по таблице (файлу) кафедра находят требуемую кафедру (для решения этой задачи применимы методы поиска, рассмотренные ранее для последовательной организации данных) – это строка (запись) с номером 1;

2) выбирают ссылки – это множество {1, 3};

3) по таблице (файлу) сотрудник обращаются к строкам (записям) с номерами 1 и 3. Получают список сотрудников: Иванов И.И., Сидоров С.С. Алгоритм заканчивает работу.

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

Рассмотрим данную организацию хранения элементов для дерева:

	СУиВТ					ТАМ
Иванов И.И.	к.т.н.	доцент			Петров П.П.	к.т.н.	нет
Сидоров С.С.	нет	нет			Яковлев Я.Я.	д.т.н.	профессор

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

сотрудник кафедра

№ п/п	ФИО	ученая степень	научное звание	контактные данные	ссылки		№ п/п	название	шифр в вузе	ссылки
	Иванов И.И.	к.т.н.	доцент					СУиВТ
	Петров П.П.	к.т.н.	нет					ТАМ
	Сидоров С.С.	нет	нет		-
	Яковлев Я.Я.	д.т.н.	профессор		-

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

Пусть надо сформировать список сотрудников кафедры СУиВТ, т.е. К_доступ = < название (кафедры) = СУиВТ >. Задача решается следующим образом:

1) по таблице (файлу) кафедра находят требуемую кафедру – это запись с номером 1;

2) выбирают значение поля ссылки – это 1;

3) по таблице (файлу) сотрудник обращаются к строке (записи) с номером 1 и выводят значение поля ФИО – это Иванов И.И.;

4) анализируют поле ссылки: оно содержит 3: это значит, что под номером 3 в этой таблице (файле) имеются данные о сотруднике, также работающем на данной кафедре;

5) обращаются к строке (записи) с номером 3 и выводят значение поля ФИО – это Сидоров С.С.,

6) поскольку в поле ссылки записи 3 находится символ «-», алгоритм заканчивает работу.

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

Представим данным методом дерево:

	СУиВТ					ТАМ
Иванов И.И.	к.т.н.	доцент			Петров П.П.	к.т.н.	нет
Сидоров С.С.	нет	нет			Яковлев Я.Я.	д.т.н.	профессор

Его описание сведем в таблицы:

сотрудник кафедра

№ п/п	ФИО	ученая степень	научное звание	контактные данные	ссылки на подобные элементы	ссылки на родительские элементы		№ п/п	название	шифр в вузе	ссылки на порожденные элементы
	Иванов И.И.	к.т.н.	доцент						СУиВТ
	Петров П.П.	к.т.н.	нет						ТАМ
	Сидоров С.С.	нет	нет
	Яковлев Я.Я.	д.т.н.	профессор

Как видно, в таблице сотрудников отсутствуют пустые ссылки. Это означает, что конечные записи в цепочках подобных записей ссылаются на первые записи в этих цепочках. Так получаются «горизонтальные» кольца. Наличие таких колец позволяет решать задачи, требующие многократного просмотра записей от начала к концу. Подобная задача, например, имеет место при сортировке файла некоторыми методами. Например, когда требуется отсортировать список сотрудников кафедры СУиВТ по возрастанию значений ключа, а кафедры ТАМ – по убыванию. В то же время совокупность ссылок на порожденные и родительские записи формирует «вертикальные» кольца. Они позволяют переходить от порожденных записей к родительским, чего не было в предыдущих методах.

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

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

Пусть надо определить, на какой кафедре работает сотрудник по фамилии и инициалам Сидоров С.С., т.е. К_доступ=< ФИО=Сидоров С.С. >. Задача решается следующим образом:

1) по таблице (файлу) сотрудник находят требуемого сотрудника – это запись с номером 3;

2) выбирают значение поля ссылки на родительские элементы – это 1;

3) по таблице (файлу) кафедра обращаются к строке (записи) с номером 1 и выводят значение поля название – это СУиВТ. Алгоритм заканчивает работу.

Дата добавления: 2014-01-15