Ознакомление с различными моделями данных показало, что поиск необходимой информации требует значительных затрат времени даже для иерархических СУБД,
особенно при больших объемах баз данных. Однако если удается выделить совокупность признаков, по которым формируется запрос, то можно предложить способ организации баз данных, значительно сокращающий время поиска затребованной информации. В основе такого способа лежит понятие инвертированного списка.
Инвертированный список представляет собой таблицу, в левом столбце которой помещены значения данного признака, а в правом — указатели на соответствующие записи. Допустим, в примере базы данных, приведенной в табл. 2.2... 2.4, в записях об узлах требуется выявить узлы, имеющие одинаковую разрядность. Тогда все записи об узлах могут быть скомпонованы плотно в памяти друг за другом и иметь порядковые номера, соответствующие их последовательности в таблице ОУЗ. Наряду с этим создается инвертированный список в таком виде:
Разрядность... ………… 8 10 16 32
Список указателей…… У7 У2, У4 У1, У6, У8 УЗ, У5
Обозначение YN представляет собой изображение указателя на N-ю запись. Таким образом, инвертированный список как бы заранее хранит ответ на запрос «Назвать характеристики узлов, имеющих заданную разрядность». В примере разрядность выступает в качестве признака в запросе. Конечно, можно выделить и другие признаки, например в каком устройстве применяется узел, каков тип узла. Для каждого признака должен быть построен свой инвертированный список.
Наличие нескольких инвертированных списков позволяет строить запрос в виде некоторой логической функции от совокупности признаков. Наиболее распространен случай построения запроса, когда используются операции дизъюнкции и конъюнкции.
Для поиска необходимой записи должны быть выполнены следующие действия:
1) выделить в запросе признаки поиска;
2) определить вид логической функции между запрашиваемыми признаками;
3) для каждого признака в нужном инвертированном списке найти множество указателей на записи;
4) в соответствии с видом логической функции произвести операции над множествами указателей.
Соответствие операций над множествами указателей виду логической функции должно быть принято из разделов по реляционной модели данных. Так, логической функции дизъюнкции ставится в соответствие операция объединения множеств, коньюнкции — операция пересечения множеств, отрицанию — операция дополнения и т. д. Для запроса «Какие узлы имеют разрядность 16 и используются в устройстве АКЮ?» в ходе поиска будут построены следующие результаты:
1) в запросе два признака: разрядность и объект применения;
2) вид логической функции в запросе — конъюнкция;
3) для признака «разрядность» в инвертированном списке значению 16 будет соответствовать множество указателей {У1, У6, У8}; признаку «применение» в соответствующем инвертированном списке для значения АКЮ — множество указателей {У1, УЗ, У6};
4) над найденными двумя множествами указателей производится операция пересечения. В итоге получается искомый результат: {У1, У6}. По этим номерам в файле записей будут найдены записи об узлах Р1 и СМ5.
Если для всех записей, хранящихся в базе данных, созданы инвертированные списки для возможных вариантов запросов, то такая база данных называется инвертированной. Инвертированные БД широко используются в информационно-поисковых системах (ИПС), предназначенных в основном для хранения текстовых документов. Признаки, по которым отыскивается необходимый документ в ИПС, называются дескрипторами. Для каждого дескриптора в ИПС строится инвертированный список, содержащий все возможные значения дескриптора и соответствующие им множества указателей на документы. Запрос в ИПС имеет вид логического высказывания относительно значений дескрипторов и их взаимосвязи. Так, если в качестве документов выступают ГОСТы по проектированию, то дескрипторами могут быть такие понятия, как год издания, объект проектирования, вид обеспечения, объем печатного материала и др. Запрос мог бы выглядеть, например, так: « Найти ГОСТы, изданные не позднее 1981 г., посвященные проектированию АСУ, для информационного и программного обеспечений ».
■ Примечание. Вид логической функции, соответствующий этому запросу, предоставляем определить самому читателю на основе предыдущих примеров.
Проектная документация, как уже указывалось, слабоструктурирована. Однако любой проектный документ может быть охарактеризован некоторой совокупностью признаков. Так, техническое задание на проектирование, абонентской сети на базе персональных ЭВМ описывается дескрипторами: техзадание, абонентская сеть, проектная документация, персональные ЭВМ. Для хранения текущих проектных документов необходимо заранее заготовить совокупность дескрипторов, которые наряду с содержанием отражали бы и поэтапность составления соответствующих документов. Например, могут быть указаны этапы, стадии, шаги процесса проектирования, а также номера вариантов.
