Файлы прямого и последовательного доступа

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

Файлы последовательного доступа организованы на устройствах последовательного доступа.

Файлы последовательного доступа могут быть организованы двумя способами.

1. конец записи отмечается специальным маркером
2. в начале каждой записи записывается ее длина

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

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

NZ=F(k)

NZ – номер записи

k – значение ключа

F - функция

Функция должна быть линейной, чтобы обеспечивать взаимнооднозначное соответствие.

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

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

Существуют разные методы:

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

Инвертированные списки

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

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

Инвертированный список по номеру группы для списка студентов

1-ый уровень 2-ой уровень

Ключ	№ блока
	1
	3

Блок 1

1

Блок 2

Блок 3

№ записи	ФИО	№ группы
	Иванов
	Петров
	Сидоров
	Андреев
	Михайлов
	Николаев
	Борисов

Многозначная зависимость

Многозначная зависимость существует, если при заданных значениях атрибута X существует множество, состоящее из 0 или более взаимосвязанных значений атрибута Y, причем множество значений атрибута Y связано со значением атрибута в отношении U-X-Y, где U – все множество атрибутов отношений.

Обозначение многозначной зависимости X->>Y.

Аксиомы многозначной зависимости

1. дополнение для многозначной зависимости: Если X<U, Y<U, X->>Y, то X->>U-X-Y

2. пополнение для многозначной зависимости: Если X<U, Y<U, V<U, W<U. Причём V<W, X->>Y, то WuX->>VuY

3. транзитивность для многозначной зависимости: Если X<U, Y<U, X->>Y, Y->>Z, то X->>Z-Y

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

1. объединение Если X<U, Y<U, Z<U, X->>Z, X->>Y, то X->>YuZ

2. псевдотранзитивность Если X<U, Y<U, Z<U, W<U, X->>Y, WuY->>Z, то WuX->>Z-(WuY)

3. смешанное правило транзитивности Если X<U, Y<U, Z<U, X->>Y, XuYàZ, то XàZ-Y

4. правило декомпозиции X<U, Y<U, Z<U, X->>Y, X->>Z,то X->>Y^Z, X->>Y-Z, X->>Z-Y