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

■найти запись по заданному признаку;

■перейти от предка к потомку по указанной связи;

■перейти от потомка к предку по некоторой связи;

■создать новую запись или удалить существующую;

■модифицировать заданную запись;

■включить в связь или исключить из связи;

■переставить в другую связь.

2.5Инвертированные базы данных

Ознакомление с различными моделями данных показало, что поиск необходимой информации требует значительных затрат времени даже для иерархических СУБД, особенно при больших объемах баз данных. Однако если удается выделить совокупность признаков, по которым формируется запрос, то можно предложить способ организации баз данных, значительно сокращающий время поиска затребованной информации. В основе такого способа лежит понятие ин-

вертированного списка.

Инвертированный список представляет собой таблицу, в первом столбце которой помещены значения данного признака, а во втором – указатели на соответствующие записи в БД. Допустим, в примере базы данных, приведенной в таблице «Заболевания», в записях о видах заболеваний необходимо выявить заболевания, имеющие одинаковое количество обращений.

ТаблицаЗаболевания

Тогда все записи о видах заболеваний могут быть скомпонованы плотно в памяти друг за другом и иметь порядковые номера, соответствующие их последовательности в таблице «Заболевания». Наряду с этим создается инвертированный список в таком виде:

124

Обозначение УN представляет собой изображение указателя на N–ю запись. Таким образом, инвертированный список как бы заранее хранит ответ на вопрос «Назвать виды заболевания, имеющих определенное количество обращений пациентов». В примере количество обращений выступает в качестве признака в запросе. Конечно, можно выделить и другие признаки: например, на каком участке имеют место обращения по поводу того или иного заболевания. Для каждого признака поиска должен быть построен свой инвертированный список.

Наличие нескольких инвертированных списков позволяет строить запрос в виде некоторой логической функции от совокупности признаков (дизъюнкции, конъюнкции, отрицание).

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

1)выделить в запросе признаки поиска;

2)определить вид логической функции между запрашиваемыми признаками;

3)для каждого признака в нужном инвертированном списке найти множество указателей на записи;

4)в соответствии с видом логической функции произвести операции над множествами указателей.

Соответствие операций над множествами указателей виду логической функции должно быть принято из разделов по реляционной алгебре. Так, логической функции дизъюнкции ставится в соответствие операция объединения множеств, конъюнкции – операция пересечения множеств, отрицанию – операция дополнения и т.д. Для запроса «Какие заболевания имеют количество посещений 16 и имели место на участке№1» в ходе поиска будут выполнены следующие действия:

1)в запросе два признака, количество посещений и № участка;

2)вид логической функции в запросе – конъюнкция;

3)для признака «количество посещений» в инвертированном списке значению 16 будет соответствовать множество указателей {У1, У5, У6}; признаку «№ участка» в соответствующем инвертированном списке для значения «№ участка 1» - множество указателей {У1, У2}.

4)над найденными двумя множествами указателей производится операция перечисления. В итоге получается искомый результат: {У1}. По этому

номеру в файле записей будет найдена запись о заболевании ОРВИ. Если для всех записей, хранящихся в базе данных, созданы инвертирован-

ные списки для возможных вариантов запросов, то такая база данных называется инвертированной. Инвертированные БД широко используются в информа-

125