Основные задачи. 
Интеллектуальные системы. 
Теория хранения и поиска информации

В данной работе для исследования были выбраны 7 модельных классов ЗИП:

• 1. ЗИП, в которых вероятность появления в ответе более с записей (с = const) равна нулю, или задачи поиска с коротким ответом;
• 2. поиск идентичных объектов, т. е. случай когда отношение поиска есть отношение равенства, и, значит, в библиотеке надо найти записи равные запросу;
• 3. задачи о близости, которые состоят в поиске во множестве, в котором задан линейный порядок, объекта, ближайшего к объектузапросу;
• 4. ЗИП, когда отношение поиска является отношением частичного порядка, заданное на конечном множестве, в частности включающий поиск (это задача поиска на булевом кубе точек не больших по-компонентно, чем запрос);
• 5. ЗИП, когда отношение поиска является отношением линейного предпорядка;
• 6. задача о доминировании, которая состоит в поиске в конечном подмножестве п-мерного пространства всех тех точек, которые не больше по каждой из компонент, чем запрос, являющейся в данном случае точкой n-мерного пространства;
• 7. задача интервального поиска, которая состоит в поиске в конечном подмножестве n-мерного пространства всех тех точек, которые попадают в n-мерный параллелепипед-запрос.

Выбор модельных классов определяется как повсеместностью использования их в базах данных, так и частотой цитирования в литературе (50, 56, 64, 68, 83, 86, 87, 93, 112, 115, 116, 119, 120, 126, 150, 151, 178, 182].

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

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

На основе информационно-графовой модели можно предложить новую технология проектирования физической организации баз данных (БД). По этой технологии на начальном этапе выделяются классы однотипных вопросов к БД, оформляемые в виде типов ЗИП. При формировании типа надо иметь в виду, что запись — это поисковый образ элемента данных, т. е. поле или множество полей элемента данных, которые представляют интерес в данном типе вопросов. Запрос — это минимальный элемент, содержащий суть вопроса. Запрос совместно с отношением поиска очерчивает тот круг объектов, которые отвечают на данный вопрос. Множество данных БД определяет библиотеку и тем самым задает конкретную ЗИП данного типа. Для каждой ЗИП выделяется множество элементарных операций над запросами, оформляемое в виде базового множества, и решается задача синтеза оптимального ИГ, решающего данную ЗИП. Полученный ИГ описывает оптимальную структуру данных, соответствующую заданным целям оптимизации (среднему времени поиска, времени поиска в худшем случае, объему памяти).

Тем самым один ИГ описывает структурную часть БД, обрабатывающую один класс однотипных вопросов к БД. А сама БД в информационно-графовой модели представляется как совокупность нескольких ИГ, охватывающих весь спектр вопросов к базе данных.

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