3.3.5. Плотный индекс

Пусть по каким-либо причинам невозможно упорядочить основной файл по ключу . Построим дополнительный файл по правилу [17]:

1) записи файла имеют формат , где – поле, принимающее значение ключа записи основного Файла ; – указатель на эту запись;

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

Пример плотного индекса представлен на рис. 3.11. Над плотным индексом можно также построить В-дерево.

Рис. 3.11. Пример плотного индекса

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

В рассмотренных выше способах индексирования данных расчет делался на поиск по значению ключевого поля. Но часто требуется осуществить выборку данных по значениям неключевых полей. В этом случае неключевые поля также должны быть проиндексированы (т.е. для каждого из них строится особый индекс). Индексы, построенные для неключевых полей используются при организации многоаспектного поиска. Широко распространены на практике методы многоаспектного поиска по инвертированным файлам. Пусть имеется основной файл , упорядоченный либо неупорядоченный по значениям вторичного ключа . Строится дополнительный файл по правилу [17]:

1) записи файла имеют формат где - поле, принимающее значение вторичного ключа записи основного файла; – указатели на записи основного файла , имеющие данное значение вторичного ключа ,

2) записи файла , упорядочены по полю .

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

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

Рис. 3.12. Пример инвертированного файла

Поскольку записи инвертированного файла упорядочены по значению ключа , то для поиска записей можно использовать любой из рассмотренных выше методов поиска в упорядоченном файле (например, бинарный поиск или В-дерево). Чтобы выполнить многоаспектный поиск по ключам, необходимо построить инвертированных файлов [17].

Глава 4. Математические основы манипулирования реляционными данными

4.1. Теоретические языки запросов

Для получения информации из отношений необходим язык манипулирования данными, способный выполнять соответствующие операции над отношениями. Наиболее важной частью ЯМД является его раздел для формулировки запросов. Поскольку запросы в общем случае представляют собой произвольные функции над отношениями, необходимо решить вопрос о требуемой выразительности языка запросов. Для исследования этого вопроса были разработаны три типа теоретических языков [2, 17]: