25. Типология простых (фактографических) запросов и организация поисковых массивов для различных типов запросов.

Любое состояние объекта характеризуется набором атрибутов, имеющих значения в этот момент времени. Записываются они в виде записи – совокупности формализованных элементов данных. В контексте задач поиска можно сказать, что значение атрибута идентифицирует объект (можно использовать значение атрибута в качестве поискового признака). Фактографические данные можно непосредственно интерпретировать (без дополнительных комментариев).

При этом способ идентификации данных через атрибуты плохо подходит для слабо структурированной информации (=связанной с объектами, имеющими умозрительную природу: категориями, понятиями, знаковыми системами). В этом случае объекты определяются опосредованно, через другие объекты, используя естественные или искусственные языки (пример – язык математики).

Ключ, идентифицирующий запись единственным образом – первичный. Ключ, идентифицирующий группу записей – вторичный.

Сцепленный ключ – состоящий из нескольких элементов данных. Ключ может храниться и составе записи или отдельно.

Физическая реализация ключа – индекс. Он обеспечивает доступ к записям, соответствующим отдельным значениям ключа.

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

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

В задачах поиска существуют два способа организации данных. Первый – прямая организация массива (сначала первичные ключи, потом вторичные), второй – инвертированный список.

Первый способ удобен для поиска по условию «каковы свойства указанного объекта?», а второй – «какие объекты обладают этим свойством?».

В[какой то книге какого то мартина] приводится такая типология простых (атомарных) запросов:

1). А(Е) = ? Каково значение атрибута А для объекта Е?

2). А(?) = V Какие объекты имеют значение атрибута равное V? 3). ?(Е) = V Какие атрибуты объекта Е имеют значение равное V? 4). ?(Е) = ? Какие значения атрибутов имеет объект Е?

5). А(?) = ? Какие значения имеет атрибут А в наборе?

6). ?(?) = V Какие атрибуты объектов набора имеют значение равное V?

Взапросах типов 2, 3, 6 вместо = могут быть использованы другие операторы сравнения (>,<, не равно или другие).

Запросы типа 1 выполняются поиском по «прямому» массиву: доступ к записи производится по первичному ключу. Запросы типа 2 выполняются поиском по инвертированному списку: доступ к записи(ям) производится по указателю, выбираемому из списка по значению вторичного ключа. Ответом в этих случаях будет значение атрибута или идентификатора. Запросы типа 3 имеют ответом имя атрибута.

Запросы типа 2, 5, 6 относятся к нескольким атрибутам, и в этом случае могут быть построены несколько индексов, облегчающих поиск по этим ключам. Для обработки запросов 2-го типа есть три типа архитектур доступа: Системы с вторичными индексами – записи расположены в соответствии с последовательностью значений первичного ключа.

Системы частично инвертированных файлов – произвольная последовательность. Первичный индекс отсутствует.

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