Модель инвертированных файлов и информационно-поисковые системы

Модель инвертированных файлов можно рассматривать как частный случай сетевой двухуровневой модели данных.

Основными информационными конструкциями в модели инвертированных файлов являются основной файл, который соответствует понятию "отношения", "ин­вертированный файл" и "список связи".

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

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

Определенная таким образом последовательность значений атрибута А и номеров записей основного файла является инвер­тированным файлом.

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

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

Пример.База данных содержит основные файлы Сотрудники и Зарпла­та. Естественно, что списки связи установ­лены по атрибуту Фамилия, а инвертированных списков в нашем примере максимально может быть пять (по числу атрибутов в ос­новных файлах).

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

Рисунок 2.17. Инвертированный список Должность (Сотрудники)

инженер — 01, 04

технолог — 02, 03

Список связи (Сотрудники, Зарплата)

01 —08, 10

02 — 05, 07, 11

03—06

04—09

Список связи (Зарплата, Сотрудники)

05—02

06—03

07—02

08—01

09—04

10—01

11—02

Вопросы для самоконтроля к главе 2

1.Какими параметрами различают модели данных?

2Чем характеризуется реляционная модель данных?

3.Что такое «отношение»?Как вы понимаете отношение с двухуровневой структурой?

4.Что такое кортеж?

5.Перечислите процедурные операции с реляционной базой данных.

6.Чем отличаются операции выборки и проекции?

7.Приведите примеры функциональных зависимостей между атрибутами.

8.Что такое ключ отношения?

9.Что такое первичный ключ отношения?

10.Какие требования к базам данным удовлетворяются процедурой нормализации отношения?

11.Чем отличается процедура нормализации базы данных от нормализации СЕИ?

12.Что такое неполная функциональная зависимость для 2НФ?

13. Что такое транзитивная функциональная зависимость для 3НФ?

14.Какие требования к базам данным удовлетворяются процедурой проверки на ацикличност?

15.Каким способом восстанавливаются свойства ацикличности?

16.Чем характеризуется сетевая модель данных?

17.Что такое веерное отношение?

18.В чем принципиальное отличие операций в сетевой и реляционной базах данных?

19. Чем характеризуется иерархическая модель данных?

20.Опишите правило концевого прохождения значений данных в иерархической модели.

21.В чем преимущества реляционной базы данных?

22.Что такое инвертированный файл и список связи?

23.Когда примеряются инвертированные файлы?

Глава 3. Методы организации данных

3.1 Методы организации данных в памяти ЭВМ

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

Организация данных может быть линейной и нелинейной.

Среди линейных методов выделяются последовательная и цепная организации данных.

К нелинейным относятся древовидная, в том числе бинарное дерево.

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

а) время формирования данных, или упорядочение данных по ключевому атрибуту;

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

в) время корректировки данных, т.е. включение или исклю­чение одной записи;

г) объем дополнительной памяти. Например, для адресов связи.