Оптимальное решение базовых задач хранения и поиска в информационно-графовой модели данных

• Автор: Гасанов, Эльяр Эльдарович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 368 с. : ил

Оглавление
Введение
1 Информационный граф (ИГ) как управляющая система, моделирующая алгоритмы хранения и поиска информации
1.1 Задачи хранения и поиска в базах данных
1.2 Понятие информационного графа
1.3 Критерий допустимости ИГ
1.4 Полнота для информационных графов
1.5 Сложность информационных графов
1.6 Мощностная нижняя оценка
1.7 Случай оптимальности перебора
2 Задачи информационного поиска с коротким ответом
2.1 Задачи поиска с коротким ответом
2.1.1 Существование древовидного оптимального ИГ для задач поиска с коротким ответом
2.1.2 Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей
2.1.3 Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом
2.1.4 Леммы о сведении
2.2 Поиск идентичных объектов
2.2.1 Бинарный поиск
2.2.2 Константный в среднем алгоритм поиска
2.2.3 Константный в худшем случае алгоритм поискаШ
2.2.4 Оценки памяти константного в худшем случае алгоритма поиска
2.3 Задачи о близости

ОГЛАВЛЕНИЕ

2.3.1 Бинарный поиск
2.3.2 Константный в среднем алгоритм поиска
2.3.3 Константный в худшем случае алгоритм поиска
3 Задачи поиска на частично-упорядоченных множествах данных
3.1 Задачи поиска на конечных частично-упорядоченных множествах данных
3.2 Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных
3.2.1 Включающий поиск
3.2.2 О недревовидности оптимальных ИГ включающего поиска
3.2.3 О древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей
3.2.4 Нижняя оценка сложности включающего поиска
3.2.5 Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесповторных или древовидных ИГ
3.2.6 Оценки сложности одного метода решения задачи включающего поиска
3.2.7 Оценки В-сложности включающего поиска
3.3 Задачи поиска на линейно-упорядоченных множествах данных
3.3.1 Последовательные алгоритмы решения задачи поиска с отношением поиска вида линейного предпорядка
3.3.2 Моделирование поиска в системах с несколькими вычислителями
3.3.3 Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка .
3.4 Задачи поиска на декартовых произведениях линейноупорядоченных множеств данных (задача о доминировании)
3.4.1 Последовательные алгоритмы решения задачи о доминировании
ОГЛАВЛЕНИЕ
3.4.2 Оценки В-сложности задачи о доминировании .
3.4.3 Математическая модель фоновых алгоритмов поиска
3.4.4 Фоновый алгоритм решения двумерной задачи о доминировании
4 Задача поиска на евклидовом параллелепипеде при запросах вида его подпараллелепипедов (интервальный поиск)
4.1 Одномерная задача интервального поиска
4.1.1 Случай базового множества характеристических функций
4.1.2 Случай простого базового множества
4.1.3 Базовое множество логарифмического поиска .
4.1.4 Базовое множество сверхлогарифмического поиска
4.1.5 Мгновенное решение
4.2 Многомерная задача интервального поиска
4.2.1 Мгновенное решение многомерной задачи интервального поиска
4.2.2 Пример оценки константы специальной ограниченности
4.2.3 Оценки В-сложности задачи интервального поиска
5 Об устойчивости канонического эффекта информационно-графовой модели хранения и поиска данных
5.1 Понятие канонического эффекта
5.2 Неустойчивость канонического эффекта по отношению к базовому множеству
5.3 Неустойчивость канонического эффекта по отношению к объему памяти
5.4 Устойчивость канонического эффекта по отношению
к е-расширению запроса
5.4.1 6-расширение задачи поиска идентичных объектов
ВВЕДЕНИЕ

в которых для любой ориентированной цепи нагрузки любых двух различных ребер этой цепи не пересекаются по переменным (скажем, что две элементарные монотонные конъюнкции пересекаются по переменным, если в формулах, описывающих эти конъюнкции, встречаются одинаковые переменные).
Справедлива следующая теорема [33].
Теорема 24 Пусть Т одно из двух базовых множеств (1Сп, 0) или (Хп, 0), тогда для любой ЗИП I типа Зь001 ИГ над базовым множеством Т, являющийся оптимальным в классе бесповторных графов для задачи I, имеет вид дерева.
В четвертом пункте данного раздела доказывается нижняя оценка сложности включающего поиска в два раза лучшая, чем мощностная нижняя оценка [28, 140].

Теорема 26 (нижняя оценка) Пусть I — (Вп,У,У) — ЗИП типа Им. Пусть базовое множество имеет вид Д = (АЛп, 0), где А4п — множество монотонных булевых функций. Тогда
Т(1,Д)>2.^ПО(у,Ъ))~*о,

где tc| = I, если в библиотеке V есть запись (0,0,..., 0), и ^ = 0 в противном случае.
Эта теорема была получена с помощью метода характеристических носителей графа. Приведем краткое описание этого метода применительно к задаче включающего поиска. На первом этапе показывается, что для каждой записи из библиотеки задачи в ИГ, решающем данную задачу, существует главная цепь, то есть цепочка ребер, ведущая из корня ИГ в лист, которому приписана данная запись, и по этой цепочке проходят все запросы, которым удовлетворяет данная запись. Далее перебирая различные варианты пересечения главных цепей, показывается, что библиотеку можно разбить на непересекающиеся части таким образом, что каждой части можно сопоставить свое подмножество ребер графа (такие