Основные задачи

В данной работе для исследования были выбраны 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].

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

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

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >