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

Оглавление
Введение 5
1 Информационный граф (ИГ) как управляющая система, моделирующая алгоритмы хранения и поиска информации 58
1.1 Задачи хранения и поиска в базах данных...........58
1.2 Понятие информационного графа.....................86
1.3 Критерий допустимости ИГ..........................91
1.4 Полнота для информационных графов.................93
1.5 Сложность информационных графов...................95
1.6 Мощностная нижняя оценка.........................103
1.7 Случай оптимальности перебора ...................106
2 Задачи информационного поиска с коротким ответом 108
2.1 Задачи поиска с коротким ответом.................108
2.1.1 Существование древовидного оптимального ИГ для задач поиска с коротким ответом .............109
2.1.2 Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей ................................... 116
2.1.3 Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом........................123
2.1.4 Леммы о сведении...........................128
2.2 Поиск идентичных объектов........................130
2.2.1 Бинарный поиск.............................131
2.2.2 Константный в среднем алгоритм поиска . . . 134
2.2.3 Константный в худшем случае алгоритм поиска141
2.2.4 Оценки памяти константного в худшем случае алгоритма поиска.................................141
2.3 Задачи о близости................................147
1
ОГЛАВЛЕНИЕ
2
2.3.1 Бинарный поиск..............................148
2.3.2 Константный в среднем алгоритм поиска . . .150
2.3.3 Константный в худшем случае алгоритм поиск а 154
3 Задачи поиска на частично-упорядоченных множествах данных 157
3.1 Задачи поиска на конечных частично-упорядоченных множествах данных..................................157
3.2 Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных . . .161
3.2.1 Включающий поиск............................161
3.2.2 О недревовидности оптимальных ИГ включающего поиска.......................................163
3.2.3 О древовидпости оптимальных ИГ включающего поиска в классе бссповторных сетей . . .176
3.2.4 Нижняя оценка сложности включающего поиска ..............................................178
3.2.5 Нижняя оценка сложности включающего по-
иска для базового множества переменных в классе бесповторных или древовидных ИГ . . .188
3.2.6 Оценки сложности одного метода решения задачи включающего поиска............................194
3.2.7 Оценки В-сложности включающего поиска . .219
3.3 Задачи поиска па линейно-упорядоченных множествах данных...........................................220
3.3.1 Последовательные алгоритмы решения зада-
чи поиска с отношением поиска вида линейного предпорядка............................221
3.3.2 Моделирование поиска в системах с несколькими вычислителями.................................229
3.3.3 Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка . 239
3.4 Задачи поиска на декартовых произведениях линейноупорядоченных множеств данных (задача о доминировании) ..............................................258
3.4.1 Последовательные алгоритмы решения задачи о доминировании.................................259
ОГЛАВЛЕНИЕ 3
3.4.2 Оценки В-сложности задачи о доминировании . 270
3.4.3 Математическая модель фоновых алгоритмов поиска ........................................... 270
3.4.4 Фоновый алгоритм решения двумерной задачи о доминировании.................................277
4 Задача поиска на евклидовом параллелепипеде при запросах вида его подпараллелепипедов (интервальный поиск) 292
4.1 Одномерная задача интервального поиска............292
4.1.1 Случай базового множества характеристических функций ..................................... 293
4.1.2 Случай простого базового множества..........294
4.1.3 Базовое множество логарифмического поиска . 302
4.1.4 Базовое множество сверхлогарифмического поиска ..............................................307
4.1.5 Мгновенное решение .........................312
4.2 Многомерная задача интервального поиска...........318
4.2.1 Мгновенное решение многомерной задачи интервального поиска ............................... 319
4.2.2 Пример оценки константы специальной ограниченности ........................................333
4.2.3 Оценки В-сложности задачи интервального поиска ..............................................335
5 Об устойчивости канонического эффекта информационно-графовой модели хранения и поиска данных337
5.1 Понятие канонического эффекта.....................337
5.2 Неустойчивость канонического эффекта по отношению к базовому множеству...............................341
5.3 Неустойчивость канонического эффекта по отношению к объему памяти....................................341
5.4 Устойчивость канонического эффекта по отношению
к £-расширеиию запроса.......................... 342
5.4.1 е-расширение задачи поиска идентичных объектов ................................'............342
ОГЛАВЛЕНИЕ
4
5.4.2 ^-расширение задач о доминировании и интервального поиска ..................... 346
Литература 348
Предметный указатель 366
Введение
В последние десятилетия активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, условно называемое нами теорией информационного поиска. Одним из главных носителей этого направления является теория баз данных. Возникшее под влиянием практических задач оно и сейчас в основном обслуживает приложения, а собственно теоретическая его часть, как представляется, обретает контуры. Как всякая научная дисциплина это направление должно характеризоваться следующими чертами: предметом исследования, про блематикой, методами и результатами. В развитой теории каждая из этих черт должна иметь достаточно общий характер. В то же время важно отметить, что молодые дисциплины возникают как правило через рассмотрение отдельных конкретных важных примеров, которые затем в развитии дисциплины обобщаются как в постановочной, так и в проблемно-методологической частях. Подобных примеров достаточно много в кибернетике, информатике и других разделах науки. К числу характерных из них может быть отнесена теория управляющих систем. В своей практической деятельности человек столкнулся с конкретными видами таких систем, которые далее играли роль модельных управляющих систем. В инженерном деле — это вентильные и контактные схемы, схемы из функциональных элементов и некоторые другие, в математике — формулы, алгоритмы и т.д., в биологии — нейроны, нейронные сети, автоматы и т.п. Для этих видов управляющих систем рассматривались две главные задачи анализа и синтеза соответствующих управляющих систем. Первая состояла в изучении ’’поведения” таких систем, а. вторая — в создании соответствующей системы с заданным ’’поведением”. На первом этапе эти постановки связывались непосредственно с модельными системами и для каждой из них разрабатывался конкретный метод решения. Со временем наступил этап, когда большинство из этих систем могли уже рас-
•5
ВВЕДЕНИЕ
6
сматриваться с единых позиций и исследование указанных общих задач достигалось уже с помощью общих методов решения. Хотя по прежнему модельные управляющие системы, имея свою специфику, продолжают оставаться в центре внимания теории управляющих систем.
Аналогичный путь развития проходит теория информационного поиска. В ней также первоначально возникли конкретные примеры способов хранения и представления данных и соответствующих этим способам алгоритмов поиска информации. К их числу относятся: лексико-графические, древовидные, реляционные и др. Задачи поиска для них имеют конкретные виды и модификации, такие как: задача поиска идентичных объектов, задача о близости, включающий поиск и др. (число основных из которых достигает семи). Они играют роль модельных задач для выбранных способов храпения информации и изучались на протяжении многих лет, привлекая каждый раз для своего решения специальные исследовательские средства, которые носили ограниченный по своим возможностям характер.
Тем самым можно считать, что современное состояние теории информационного поиска напоминает то состояние теории управляющих систем, которое соответствовало первому этапу развития последней, когда накапливались данные лишь о конкретных видах модельных управляющих систем. В то же время, как выяснилось, опыт развития теории управляющих систем в своей методологической части давал возможность сделать попытку с более общих позиций провести исследование как модельных баз данных, так и модельных задач для них, с соответствующей разработкой достаточно общей теории.
Это и составляет содержание исследований диссертации. Мы предлагаем новый вид баз данных (частными случаями которых могут считаться уже известные) с наследственно определенными средствами поиска информации, с соответствующими понятиями сложности такого поиска, а также разрабатываем основы теории решения обобщенных базовых задач для таких баз данных. Таким образом, мы стремимся к тому, чтобы приблизить состояние теории информационного поиска по степени продвинутости к современному состоянию теории управляющих систем.
ВВЕДЕНИЕ
7
Уточним сказанное. Мы предлагаем новую управляющую систему, называемую информационным графом, которая в общей иерархии теории управляющих систем находится в не очень высоких слоях залегания и является в некотором смысле обобщением контактных схем. Фактически нам нужны лишь графы, дискретные функции и вычисление волновых процессов на графах, и этого хватает, чтобы с достаточно общих позиций посмотреть на ту разрозненную картину, которая наблюдается в теории информационного поиска.
Информационный граф, который представляет собой ориентированный граф, ребра и вершины которого нагружены функциями и элементами данных, с одной стороны дает новую концепцию хранения данных, а с другой стороны предлагает новый подход к поиску информации как волнового процесса па графах, управляемого нагрузочными функциями. Нагрузочные функции, которые называются базовыми, разделены на два класса — предикаты и переключатели, и являются одним из основных управляющих параметров модели.
Кроме того, информационные графы позволяют ввести новое понятие сложности поиска. Это понятие новое как с точки зрения теории управляющих систем, так и с точки зрения теории баз данных. В теории управляющих систем обычно иод сложностью понимается или число ребер, или число элементов-функций, а здесь сложность понимается как часть графа, захваченного волновым процессом, и существенно зависит от значений нагрузочных функций, и тем самым не является просто количественной характеристикой графа, такой как число ребер или вершин. Новизна же в теории баз данных заключается в том, что такое введение сложности после осреднения но множеству запросов адекватно соответствует среднему времени поиска — традиционно трудной для изучения характеристики алгоритмов поиска информации. Кроме того, при соответствующем введении сложности информационные графы оказываются удобными для изучения как параллельных, так и фоновых алгоритмов поиска. И, наконец, в информационных графах совсем просто контролируется такой важный управляющий параметр в задачах информационного поиска, как объем памяти, который в данном случае характеризуется количеством
ВВЕДЕНИЕ
8
ребер графа.
Анализ рассматриваемых в диссертации 7 модельных классов задач поиска позволил разбить их на 3 крупных базовых класса. Первый класс включает в себя задачи поиска, в которых для почти всех запросов ответ на них содержит ограниченное малой константой число элементов. Этот класс получил название задач поиска с коротким отпетом. Второй класс, названный задачами поиска на частично-упорядоченных множествах данных, состоит из задач, в которых в ответ на занрос надо перечислить все элементы базы данных, которые в заданном частичном порядке меньше чем запрос. И наконец третий класс содержит так называемые задачи интервального поиска, результат которых в некотором смысле можно рассматривать как пересечение решений двух задач из второго класса.
Классификация 7 модельных классов задач поиска и объединение их в 3 базовых класса, конечно, не единственный способ обобщения задач поиска. Одним из естественных методов является е-расширение запроса., которое позволяет ответу на задачу несколько отходить (на величину е) от требований задачи.
Для базовых задач поиска ставится проблема, оптимального синтеза, которая состоит в построении для заданной задачи информационного поиска, информационного графа, который решает эту задачу и имеет наименьшую или близкую к ней сложность. Результаты, полученные при решении проблемы оптимального синтеза для базовых задач, характеризуются, во-первых, тем, что для всех задач из модельных классов, кроме так называемых задач включающего поиска из второго базового класса, получены точные и (или) асимптотические результаты, а для задач включающего поиска получена асимптотика функции Шеннона, а для некоторых базовых множеств и асимптотика сложности для почти всех задач и для средней сложности но задачам. Во-вторых, полученные результаты можно условно разбить па 4 типа.
К первому типу относятся задачи, имеющие константную сложность, то есть которые можно решить в среднем за константное число шагов. Константную сложность имеют некоторые задачи из первого базового класса.
Ко второму типу относятся задачи поиска с условно констант-
ВВЕДЕНИЕ
9
ной сложностью. Это задачи, для решения которых помимо перечисления ответа (а это сложность, которую избежать никак нельзя, и она носит название мощностной нижней оценки) требуется в среднем константное число вычислений. Такие задачи встречаются во втором и третьем базовых классах.
К третьему типу относятся задачи с логарифмической сложностью, решение которых не может быть получено за время, меньшее, чем логарифм от объема, базы данных. К этому тину относятся некоторые задачи из первого базового класса, когда из множества базовых функций исключены переключатели.
И, наконец, к четвертому типу относятся задачи с быстро растущей сложностью, то есть разность между сложностью которых и мощностной нижней оценкой является растущей функцией. К четвертому типу относятся задачи включающего поиска, из второго базового класса.
Для решения задач оптимального синтеза для базовых классов разработаны следующие 3 основных метода.
Первый метод мы называем методом оптимальной декомпозиции. Он состоит в таком разбиении задачи на подзадачи, которые допускают простое решение и при этом сложность поиска иодзада.-чи, дающей решение исходной задачи, также осуществляется просто. Этот метод использовался при решении опорных или одномерных задач поиска.
Второй метод, назывгюмый методом снижения размерности, применяемый к многомерным задачам, сводится к тому, чтобы с помощью некоторых опорных задач последовательно понижать размерность задачи и в конце концов свести ее к опорной задаче, решение которой уже известно.
Третий метод назван методом характеристических носителей графа и использовался при получении нижиих оценок. Он заключается в выделении в информационном графе, являющемся оптимальным решением, подграфов с заданными свойствами (характеристических носителей) и в последующем подсчете СЛОЖНОСТИ характеристических носителей.
Полученный свод результатов, описывающих вид функций сложности, доставляющих оптимальное решение базовых классов, назовем каноническим эффектом, и нам хотелось бы понять насколь-
ВВЕДЕНИЕ
10
ко чувствительна основная модель по отношению к каноническому эффекту при вариации 3-х основных управляющих параметров модели, таких как объем памяти, имеющийся в распоряжении (то есть число ребер информационного графа), множество функций, которые разрешается использовать при решении (то есть множество базовых функций, используемых при нагрузке графа), и е-расширение запроса. Показывается, что при любой вариации, кроме е-расширения запроса, мы уходим от каноническою эффекта.
Постановка базовых проблем
В задачах поиска, возникающих в базах данных, имеется 3 основных объекта:
• множество запросов X с заданным на нем вероятностпым пространством;
• множество потенциальных ответов У, будем называть элементы этого множества записями, а само множество — множеством записей; •
• бинарное отношение р, заданное на X х У, называющееся отношением поиска и описывающее критерий семантического соответствия записи запросу, то есть если хру, то будем говорить, что запись у удовлетворяет запросу х\
В достаточно общем случае значительный интерес представляет описываемая ниже проблема, которую мы назовем задачей информационного поиска. Тройку (А,У,р) будем называть типом задан информационного поиска, а тройку (А, У, р) (или четверку (А, У, р;У)), где V — конечное подмножество У, называемое библиотекой, — задачей информационного поиска (ЗИП). Содержательно будем считать, что ЗИП / = (А, V, р\ У) состоит в перечислении для произвольно взятого запроса х € X всех тех и только тех записей из У, которые находятся в отношении р с запросом х, то есть удовлетворяют запросу х.
Реально эта проблема допускает вариацию как за счет уточнения самой задачи, так и за счет допущения разных предположений относительно базовых компонент А, У,р, У, составляющих ЗИП.
ВВЕДЕНИЕ
11
Для исследования были выбраны 7 основпых классов ЗИП, играющих роль модельных объектов.
1) ЗИП, в которых вероятность множества запросов, ответ на которые содержит болсс с записей (с = равна нулю;
2) поиск идентичных объектов, когда в библиотеке надо найти записи равные запросу;
3) задачи о близости, которые состоят в поиске в лииейно-упо-рядоченном множестве объекта, ближайшею к объекту-запросу;
4) ЗИП, когда отношение поиска является отношением частичною порядка, заданное на конечном множестве, в частности, включающий поиск (это задача поиска на булевом кубе точек не больших по-компонентно, чем запрос);
5) ЗИП, когда отношение поиска является отношением линейною предпорядка;
6) задача о доминировании, которая состоит в поиске в конечном подмножестве п-мерпого пространства всех тех точек, которые не больше но каждой из компонент, чем запрос, являющийся в данном случае точкой п-мерного пространства.
7) задача интервальною поиска, которая состоит в поиске в конечном подмножестве п-мерного пространства всех тех точек, которые попадают в п-мерный параллелепипед-запрос;
Выбор модельных классов определяется как повсеместностью использования их в базах данных, так и частотой цитирования в литературе [43, 49, 55, 59, 69, 71, 72, 77, 94, 97, 98, 101, 102, 108, 132, 133, 157, 161].
Нетрудно видеть, что все эти случаи 1-7 возникают как соответствующие многообразия ЗИП либо за счет фиксации свойств решения ЗИП, либо за счет дополнительных предположений относительно X, У, V, р.
Анализ случаев 1-7 позволяет заметить, что все модельные задачи можно разбить на 3 класса. К первому классу, получившему название задач поиска с коротким ответом, относятся первые три модельные задачи. Во второй класс, названный задачами поиска на частично-упорядочеипых множествах данных, попали четвертая, пятая и шестая модельные задачи. И седьмая задача образовала третий класс.
Целью диссертационной работы является
ВВЕДЕНИЕ
12
• создание достаточно общей модели хранения и поиска информации. опирающейся на опыт основных моделей баз данных;
• рассмотрение в рамках данной модели базовых задач поиска информации и разработка теории решения этих задач;
• разработка оптимальных или близких к ним алгоритмов решения базовых задач поиска информации.
Научная новизна и практическая ценность работы состоит в том, что впервые
• разработана информационно-графовая модель хранения и поиска данных, которая с одной стороны дает новую концепцию хранепия данных, а с другой стороны предлагает новый подход к поиску информации;
• введена новая модель задач информационного поиска, обобщающая базовые задачи поиска;
• введены понятия, характеризующие сложность решения задач поиска и оценены функции сложности шенноновского типа;
• разработан математический аппарат для исследования такой традиционно сложной характеристики поиска как среднее время поиска;
• разработан метод характеристических носителей графа, с помощью которого получены нижние оценки сложности базо вых задач поиска;
• построены оптимальные или близкие к ним алгоритмы решения базовых задач поиска информации, большинство из которых опираются на разработанные методы оптимальной декомпозиции и снижения размерности;
• разработана математическая модель для исследования фопо-вых алгоритмов поиска;
ВВЕДЕНИЕ
13
• разработана математическая модель параллельных алгоритмов поиска;
• проведено исследование устойчивости шенноновских эффектов заданною вида для многообразия базовых задач поиска при вариации их характеристических параметров с выделением зон такой устойчивости и нарушения ее.
Основные результаты диссертации докладывались на Международной конференции ”Интеллектуальные системы" (Краснови-дово, 1990, 1991, 1992, 1993, Москва, 199-5, 1996, 1997), Международной конференции по проблемам теоретической кибернетики (Саратов, 1993, Ульяновск, 1996, Красновидово, 1997, Нижний Новгород, 1999), Международном семинаре по дискретной математике (Москва, 1993, 1995), Международной конференции ”Основы теории вычислений’* РСТ 87 (Казань, 1987), Международном семинаре ”Управление и сетевой анализ” (Прага, Чехословакия, 1987), Международной школе по математике и ее приложениям в социальных науках (Любляна, Словения, 1991), Всемирном конгрессе математиков (Цюрих, Швейцария, 1994, Будапешт, Венгрия, 1996), Международном симпозиуме по интеллектуальному анализу данных, ША-95 (Бадсп-Баден, Германия, 1995), Международной конференции по нейроматематикс (Москва, 1996), Международном симпозиуме ” Математика в турецком мире” (Ел аз иг, Турция, 1999), Ломоносовских чтениях МГУ им. М. В. Ломоносова (Москва, 1990-1998), на семинарах МГУ по теории автоматов академика АТН РФ, профессора В. Б. Кудрявцева, по математической кибернетики член-корреспондента РАН, профессора С. В. Яблонского, на ссмипаре под руководством член-корреспондента РАН Л.II.Королева, а также на семинарах лаборатории проблем теоретической кибернетики и кафедры математической теории интеллектуальных систем механико-математического факультета МГУ.
Результаты диссертации опубликованы в 32 научных работах. В совместных работах автору принадлежат постановки задач и основные результаты.
Диссертационная работа состоит из пяти глав.
ВВЕДЕНИЕ
И
В первой главе» состоящей из семи разделов, приводится обзор литературы, вводится формальное понятие ИГ, и доказываются некоторые общие свойства ИГ.
В первом разделе приводится обзор литературы, посвященных задачам поиска в базах данных и описывается общее состояние дел в математической теории баз данных и информационного поиска.
Прежде чем переходить к последующему изложению приведем, ряд определений и обозначений, используемых в дальнейшем.
Пусть М — некоторое конечное множество. Через \М\ обозначим число элементов во множестве Л/, называемое мощностью множества М.
Через {1,т} договоримся обозначать множество {1,2,...,т}.
Некоторые оценки мы будем приводить с точностью до главного члена, поэтому введем обозначения, обычно принятые при описании асимптотических оценок.
Будем писать а(п) = ё(1), если lirri а(п) = 0; Л(п) = ö(B(n))y если А(п) = В(п) • о(1). Скажем, что А(п) асимптотически не превосходит В(п) при п —► оо и обозначим А £ В, если существует а(гг) = о(1) такое, что начиная с некоторого номера по, Л(п) < (1 -f а(п)) • В(п). Если А ~ В и В ~ Л, то будем говорить, что А и В асимптотически равны при п —> оо и обозначать А ~ В. Будем писать А Д В. если существует такая положительная константа с, что, начиная с некоторого номера. п0, А(п) < с-В(п). Если Л ~ В и В < А, то будем говорить, что А и В равны по порядку при п —* оо и обозпачать Ах В или А = 0(B).
Через ^ будем обозначать число сочетаний из п элементов по к. Если г — действительное число, то через [г] будем обозпачать максимальное целое, не превышающее г, а через ]г[ — минимальное целое, не меньшее, чем г. Значок = будем понимать как ”по определению равно1*. Математическое ожидание будем обозначать значком М, а значок Мх будем понимать как среднее значение при вариации переменной х.
Договоримся также о теоретико-графовой терминологии.
Пусть нам дай ориентированный граф. В ориентированном ребре (oc>ß) вершину а будем называть началом ребра, а ß — концом. Скажем, что ориентированное ребро графа исходит из вершины ß
ВВЕДЕНИЕ
15
(входит в вершину /?), если /? — начало (конец) данного ребра. Скажем, что ребро инцидентно вершине, если эта вершина является одним из концов данного ребра. Полустепенью исхода (захода) вершины графа назовем число ребер, исходящих из данной вершины (входящих в данную вершину). Степенью инцидентности вершины назовем число инцидентных ей ребер. Вершину графа назовем концевой, если полустепеиь ее исхода равна 0. Остальные вершины графа назовем внутренними.
Последовательность ориентированных ребер графа
(^1? ^2)5 (о^2> О'з), • • ♦ у (Отп—1, ОСт)
назовем ориентированной цепью от вершины от к вершине ат.
Информационный граф — новая концепция хранения данных и новый подход к поиску информации
Во втором разделе дано строгое формальное определение понятия ИГ и некоторые другие определения и обозначения, используемые далее в диссертации.
Опишем основной объект, который называется информационным графом (ИГ). Вводить ИГ мы будем, одновременно иллюстрируя его на примере одномерной задачи интервального поиска. Сначала задаются 4 множества:
• множество запросов Х\
• множество записей У:
• множество Е одноместных предикатов, заданных на множестве X;
• множество одноместных переключателей, заданных на множестве X ( ет переключатели — это функции, область значений которых является начальным отрезком натуральною ряда).
В примере эти множества имеют вид:
ВВЕДЕНИЕ
16
. Хм = {(и,»): 0 < и < V < 1};
• Ум = [0,1!;
• Р = Г, иГ„, где Рг = {Д,„ : а € [0,1]}, Г2 = {Л.а = * 6 [0,1]},
1, если и < а
1, если V > а О, если V < а
• С? = Сп и^2 и) где б?х = {<7,т : т € IV},
^2 = {<7-,т : ш 6 N}1 (?3 = {д<,а ' а € (0,1]},
ИГ определяется следующим образом. Берется конечная многополюсная ориентированная сеть. В ней выбирается некоторый полюс, который называется корнем. На рисунке 0.1 он изображен полым кружком. Остальные полюса называются листьями (на рисунке они изображены жирными точками) и им приписываются записи из У (на рисунке это символы у с индексами), причем разным листьям могут быть приписаны одинаковые записи. Некоторые вершины сети (в том числе эго могут быть и полюса) называются переключательными и им приписываются переключатели из <7 (на рисунке таких вершин 7). Ребра, исходящие из каждой из переключательных вершин, нумеруются начиная с 1 и называются переключательными ребрами (на рисунке таких ребер 14). Ребра, не являющиеся переключательными, называются предикатными и им приписываются предикаты из множества F (на рисунке таких ребер 18). Таким образом нагруженную многополюсную ориентированную сеть называем ИГ над базовым множеством Т — {Р, С).
д.,т(и,г>) = тах(1,]н • т[),
{], если V — и < 1 /т 2, если V - и > 1/т
д<,а(и,и) =
1, если и < а
2, если и > а
ВВЕДЕНИЕ 17
Функционирование ИГ определяется следующим образом. Скажем, что предикатное ребро проводит запрос х € X, если предикат, приписанный этому ребру, принимает значение 1 на запросе х. Скажем, что переключательное ребро, которому приписан номер п, проводит запрос х € X. если переключатель, приписанный началу этого ребра, принимает значение п ка запросе х. Скажем, что ориентированная цепочка ребер проводит запрос х € X, если каждое ребро цепочки проводит запрос х. Скажем, что запрос х е X проходит в вершину /3 ИГ. если существует ориентированная цепочка, ведущая из корпя в вершину /3, которая проводит запрос х. Скажем, что запись у, приписанная листу а, попадает в ответ ИГ на запрос х 6 X, если запрос х проходит в лист а. Ответом ИГ U на занрос х назовем множество записей, попавших в ответ ИГ на запрос х, и обозначим его Ju(x). Эту функцию Ju(x) будем считать результатом функционирования ИГ U.
Из определения функционирования ИГ естественным образом вытекает, что каждому ИГ U можно сопоставить некую процедуру поиска.
ВВЕДЕНИЕ
18
Предполагается, что эта процедз'ра хранит в своей (внешней) памяти структуру ИГ и. Входными данными процедуры является запрос. Выходными данными является множество записей.
Опишем эту процедуру.
Пусть па вход процедуры поступил запрос х. Вводим понятие активного множества вершин и вносим в него в начальный момент корень ИГ и и помечаем его. Далее по очереди просматриваем вершины из активного множества и для каждой из них проделываем следующее:
• если рассматриваемая вершина — лист, то запись, приписанную вершине, включаем в ответ,
• если рассматриваемая вершина переключательная, то вычисляем на запросе х переключатель, соответствующий данной вершине, и если конец ребра, исходящего из рассматриваемой вершины, нагрузка которого равна значению переключателя, непомеченная вершина, то помечаем его и включаем в множество активных вершин;
• если рассматриваемая вершина предикатная, то просматриваем по очереди исходящие из нее ребра и вычисляем значения предикатов, приписанных этим ребрам, па запросе х. Концы ребер, которым соответствуют предикаты со значениями, равными 1, если они непомеченные, помечаем и включаем в множество активпых вершин;
• исключаем рассматриваемую вершину из активного множества.
Процедура завершается по исчерпании активного множества.
Таким образом, ИГ как управляющая система может рассматриваться в качестве модели алгоритма поиска, работающего над данными, организованными в структуру, определяемую структурой ИГ.
Достоинства ИГ:
1) все основные известные ранее объекты, используемые для моделирования алгоритмов поиска, являются частными случаями ИГ;
ВВЕДЕНИЕ
19
2) все наиболее популярные и известные алгоритмы поиска легко перекладываются на язык ИГ и при этом приобретают свойство метризуемости, то есть становится легко подсчитать такие характеристики сложности алгоритмов как объем памяти, время поиска в среднем и время поиска в худшем случае, причем полученные с помощью ИГ оценки полностью согласуются с оценками полученными другими методами, если такие оценки существовали.
Подтверждение сказанного:
1) Наиболее популярная модель, используемая для оценки сложности алгоритмов, — алгебраическое дерево вычислений (АДВ-модель), а также ее разновидность — алгебраическое дерево решений, при переводе на язык ИГ описываются некоторым классом древовидных ИГ и тем самым являются частным случаем ИГ.
2) Алгоритмы и конструкции, используемые в древовидных и лингвистических базах данных, описываются древовидными ИГ.
3) Алгоритм поиска, используемый в дедуктивных базах данных, при переходе на язык ИГ приводит к константному дереву.
4) Алгоритмы в реляционных базах данных приводят к древовидным ИГ специального вида.
В случае, когда базовое множество переключателей О пусто, то есть в графах нет переключателей, то ИГ называются предикатными информационными графами (ПИГ). Ранее этот термин носил название информационных сетей с дублированием листьев (ИОД). Понятие ПИГ хронологически предшествовало понятию ИГ и впервые эти понятия были опубликованы в [20].
ПИГ, различным листьям которого соответствуют различные записи, называется однозначным информационным графом (ОИГ). Это понятие (под названием '’информационная сеть”) впервые введено в [17]. Более доступными изданиями являются [18, 19].
ОИГ, имеющий вид дерева, листья которого совпадают с концевыми вершинами дерева, назовем информационным деревом (ИД).
Впервые понятие ИД было опубликовано в работах [11, 12, 13, 14, 15, 135).
ИД удобны и интересны тем, что структуры данных, им соответствующие, практичны и их гораздо проще реализовать на ЭВМ.
ВВЕДЕНИЕ
20
Ух У2 Уз Ул___________Уъ У6
0 1/3 2/3 1
Рис. 0.2:
В третьем разделе первой главы вводится определение допустимого ИГ и формулируется критерий допустимости ИГ.
Пусть нам дана ЗИП I = (X, V, р).
Множество
Л(я) = {.V € К : тру}
назовем ответом ЗИП / на запрос ж.
Скажем, что ИГ и разрешает ЗИП Т ~ {Ху V, р), если для любого запроса х £ X ответ на этот запрос содержит все те и только те записи из V, которые удовлетворяют запросу х, то есть
. Л(х) =
ИГ 11, разрешающий ЗИП /, будем также называть допустимым для задачи I.
Если — бинарное отношение на Хы х Уы такое, что
(иуо)рыу и<у < V,
то ИГ, изображенный ' на рисунке 0.1 разрешает ЗИП
I = (Хш,УУрм), где V = {уьу2,Уз,У4,У5,Уб} — библиотека, изображенная на рисунке 0.2, причем данный ИГ, соответствует асимптотически оптимальному решению, полученному по методу оптимальной декомпозиции.
Если / — одноместный предикат, определенный на X , то есть / : X -* {0,1}, то множество Л/ = {х € X : /(х) = 1} назовем характеристгхческим множеством предиката /.
Множество 0(у,р) = {х £ X : хру} назовем тенью записи уеУ.
Функцию Ху.р '• X —► {0,1} такую, что ]УХу/> = 0(у,р) назовем характеристической функцией записи у.
ВВЕДЕНИЕ
21
Пусть в — некоторая вершина ИГ. Предикат, определенный на множестве запросов, который принимает значение 1 на запросе х, если запрос проходит в вершину Д и 0 — в противном случае, назовем функцией фильтра вершины 0 и обозначим <рр(х).
Пусть 1/ — некоторый ИГ, у — запись из У. Через 1и(у) обозначим множество листьев ИГ II, которым соответствует запись
у'
Справедлива следующая теорема [19, 20].
Теорема 1 ИГ И разрешает ЗИП I = (А, V, р) тогда и только тогда, когда для любой записи у € V, такой, что 0(у,р) ф 0, справедливо Ьц(у) / I и \/ (ра = Ху,») а для любой записи
<*€&(/( у)
у <Е V, такой, что 0(у,р) = 0 либо Ьи(у) = 0, либо \/ <ра = 0.
В четвертом разделе первой главы вводится понятие полного базового множества и дается критерий полноты базового множества.
Скажем, что базовое множество Т полно для типа 5 = (X, У, р), если для любой ЗИП 1 = (А, V, р) типа 5 существует ИГ V над базовым множеством Т, разрешающий ЗИП I.
Если п — натуральное число, а д(х) — некий переключатель, то через ££(я) обозначим предикат, определенпый на X , такой, что
-9(х) = п}.
Обозначим
<Э = {£:<7еО,пеМ},
где N — множество натуральных чисел.
Справедлив следующий результат, относящийся к проблеме полноты для ИГ (19, 20].
Теорема 2 Пусть заданы множества запросов X, записей У и отношение поиска р на X х У. Тогда базовое множество Т. — {Е, (7) будет полпьем для типа 5 = (А*, У, р) тогда и только тогда, когда для любой записи у € У такой, что 0(у,р) ^ 0,
ВВЕДЕНИЕ
22
функцию Ху,Лх) можно представить формулой вида
п т»
ху,Лх) — V A
1=1 j=1
где fij € F ü Ö.
Сложность информационных графов
В пятом разделе первой главы вводится понятие сложности ИГ.
Будем считать, что время вычисления любого переключателя из G и любого предиката из F одинаково и равно 1.
Пусть нам дан некий ИГ U и произвольно взятый запрос х € X. Сложностью ИГ U па запросе х назовем число
T(u,x)=Y.M*) + £ Ь ■ Ы*).
ߣP 0eK\V
где 7£ — множество вершин ИГ U,V — множество переключательных вершин ИГ U, фв — количество ребер, исходящих из вершины
ß-
Величина T(U, х) характеризует время работы описанной выше процедуры поиска, сопоставленной ИГ 6Г, поскольку T(U,x) равно количеству переключателей и предикатов, вычисленных данной процедурой при подаче на ее вход запроса х.
Сложность ИГ можно вводить двумя способами. Во-первых, так
же, как и в случае АДВ-модели, то есть как T(U) = max TW, х)
z€X
(здесь мы берем max, а не sup, так как Г(1],х) принимает целые значения, и, значит, sup всегда достигается). Эта величина характеризует время поиска в худшем случае соответствующим ИГ алгоритмом и ее будем называть В-сложностъю ИГ (верхней сложностью). Эта величина оценивается в большинстве работ, посвященных исследованию сложности задач поиска (49, 60, 71, 95, 97, 98, 100, 101, 107, 108, 126, 129, 131, 132, 133, 134, 144, 157, 158, 162, 187, 191], ив сравнительно редких случаях (см., например, [43, 49,102, 106,125, 163, 165, 166, 168, 177, 185]) оценивается среднее время поиска, хотя для задач поиска, используемых в базах
ВВЕДЕНИЕ
23
данных, для которых характерны массовость и многократность, исследование среднего времени поиска представляется более актуальным. Мы в основном будем исследовать среднее время поиска и введем сложность ИГ как среднее значение сложности на запросе.
С этой целью введем вероятностное пространство над множеством запросов X, под которым будем понимать тройку {АГ,(7,Р), где <7 — некоторая алгебра подмножеств множества X, Р — вероятностная мера на <7, то есть аддитивная мера, такая, что
Р(Л) = 1.
В связи с тем, что мы ввели вероятностное пространство над множеством запросов, уточним понятие типа. А именно под типом будем понимать тройку 5 = {X. У, р), считая, что множество запросов X рассматривается вместе со своим вероятностным пространством (Х,а, Р). В тех же случаях, когда мы хотим явно выделить рассматриваемое вероятностное пространство над X мы будем представлять тип пятеркой 6’ = (Х,У, р,<7, Р).
Скажем, что базовое множество Т = (£*, О) измеримое, если алгебра а содержит все множества Л/, где / € .Ри О.
Справедлива следующая основная лемма.
Лемма 1 Если базовое множество Т = (Р, О) измеримое, то для любого ИГ В над базовым множеством Т функция Т(£/, х), как функция от х, яв.аяется случайной величиной.
Далее всюду будем предполагать, что базовое множество измеримое.
Сложностью ИГ V назовем математическое ожидание величины Т( И, ж), то есть число
Т(и) = МхТ(Дх).
Объемом (2(1!) ИГ 1/ назовем число ребер в ИГ V.
Пусть нам дана некая ЗИП I. Сложностью задачи I при базовом множестве Т и заданном объеме назовем число
Т(1,Г,Ч) = Ы{Т(Ц) : и еи(ГГ, и <3(1/) < <?},
гдеЫ(1,Т) — множество всех ИГ над базовым множеством Т, разрешающих ЗИП I.
ВВЕДЕНИЕ
24
Соответственно В-сложпостью задачи I при базовом множестве Т и заданном объеме q назовем число
= min{f(U) : U € U{ItF) и Q(ü) < q}
(здесь мы берем min, а не inf, так как T(U) принимает целые значения, и, значит, inf всегда достигается).
Число
T(I,F) = M{T(Ü):U £К(1,Г)}
назовем сложностью задачи I при базовом мноясестве Т.
Соответственно В-сложностью задачи I при базовом множестве Т назовем число
= min{T(U) : U € U(I,T)}.
Если к — натуральное число, S — тип задач поиска, то обозначим
X(k,S) = {I = (X,V,p)eS:\V\ = k}.
Будем исследовать функции, характеризующие сложность класса ЗИП T(fc,S), такие как функции Шеннона:
T(*,S,*) = sup Т(1, Г),
l£l(k,S)
(в первом случае мы берем max, а не sup, так как Т(1,Т) принимает целые значения, и, значит, sup всегда достигается) и как среднее значение:
f(fc,S,JF) = М,Г(/,П
T{k,S,F) = MiT(I,F)>
где среднее значение берется по всем ЗИП / € 2(k, S).
Если существует такой ИГ U € ^/(/,/‘), что T{U) = T(I, Т), то ИГ U будем называть оптимальным для ЗИП I. Соответственно если T(U) = Tf/,^), то ИГ U будем называть В-оптимальным для ЗИП I.
Справедлива следующая теорема [29].
ВВЕДЕНИЕ
25
Теорема 3 (о существовании оптимальных графов) Пусть 5 = (X, V, р, сг, Р) — такой тип, что множество запросов X конечно, о — множество всех подмножеств X, Р — такая вероятностная мера, что для любого В С X Р(£) > 0. Тогда, если базовое мпозюество Т = {Е, (2) полно для типа 5 и множество F и С конечно, то для любой ЗИП I типа 5 существует оптимальный ИГ.
В шестом разделе доказывается нижняя оценка, являющаяся аналогом мощностной нижней оценки в теории сложности схем.
Скажем, что базовое множество Т допустимо для ЗИП /, если существует ИГ над базовым множеством Т, который разрешает ЗИП I.
Справедлива следующая теорема [19].
Теорема 4 (мощностная нижняя оценка) Пусть I = (X, У,р) — произвольная ЗИП, такая, что существует такая запись у € V, что 0(у,р) Ф 0, Т — измеримое базовое множество, допустимое для I, тогда
Г(Л^)>шах(1,^Р(0(у,/»))),
уЪУ
Т(1,Т) > тахЩг)]..
Смысл этой теоремы состоит в том, что для любой задачи поиска время поиска не меньше чем длина ответа.
Следующая теорема, доказываемая в седьмом разделе, описывает ситуацию, когда перебор является оптимальным алгоритмом.
Теорема 5 Если I = (X, V, р) — ЗИП и Д = (И, 0} — измеримое базовое множество, такие, что для любой записи у € V выполня-ется Xy.fi еИ и 0(у, р) \ ( и ^) ф 0, то
!*Р\ху.Р
ВВЕДЕНИЕ
26
Решение проблемы оптимального синтеза для базовых задач
Во второй главе, состоящей из трех разделов, исследуются задачи поиска, в которых ответ почти всегда содержит не более чем константное число записей.
В первом разделе второй главы исследуются задачи поиска с коротким ответом, которые формально описываются следующим образом.
Скажем, что ЗИП / = {X, V, р) обладает A-свойством, если
• для любой записи у 6 V 0(у,р) € о и Р(0(у,/?)) ф 0;
• для любых у, у' е V, таких, что у ф у'
Р (0(у,р)С\0(у',р)) =0.
Если п — натурачьное число, то скажем, что ЗИП / = (X, V, р) обладает Вп-сбойством, если для любых п + 1 записи из V пересечение теней этих записей равно пустому множеству.
Справедлива следующая теорема [21].
Теорема 6 Пусть 1 — (X, V, р) — ЗИП, Т = (F, 0) — произвольное измеримое базовое множество, допустимое для I, U — произвольный ЛИГ над базовым множеством Т, разрешающий ЗИП I. Тогда,
• если I обладает A-свойством, то существует ИД D € V1, такое, что T(D) < T(U),
• если I обладает В\-свойством, то существует ИД D € V1, такое, что T(D) < T((J).
Здесь и далее формулировки теорем носят несколько упрощенный характер и служат только для того, чтобы отразить общую картину. Строгие формулировки можно найти по ссылкам или в тексте диссертации. В частности здесь V1 — множество ИД специального вида.
ВВЕДЕНИЕ
27
Факт о древовидности оптимальных или близких к оптимальному ИГ полезен, во-первых, потому, что реализовывать и использовать древовидные конструкции всегда легче, а во-вторых, всякое ограничение на структуру помогает при получении нижних оценок сложности. Так во втором пункте раздела с помощью свойства дрс-вовидиости для задач, у которых вероятности теней любых двух записей из библиотеки равны, получена логарифмическая нижняя оценка сложности.
Скажем, что ЗИП I = {Х,У,р) обладает И-свойством, если она обладает Л-свойством и для любых у,у' 6 V справедливо
Р(0(»,/>)) = Р(0(у',/О).
Обозначим
Щк) = ЗА:[1оёз к] + 4(А - 3[“’*! *!) + шах(0, к- 2 • З110*’ *').
Справедлива следующая теорема [21].
Теорема 7 Если I = (X, У,р) — ЗИП, обладающая Е-свойством, Д = (И, 0) — измеримое базовое множество, допустимое для I, то
Т(1,Т)>?{0{у,р))- ЩУ\),
где у 6 У.
Этот результат был получен методом характеристических носителей графа.
Следствие 3 В уыовиях теоремы 7
Т(/,Л>с-Роёз|Ч],
где с < 3.
Для сравнения отметим, что мощностиая нижняя оценка сложности, получаемая с помощью теоремы 4 для задач, обладающих ^-свойством, равна константе, не превышающей 1.
Пусть I = {X, У, р) — некоторая ЗИП, где V = {уь у2,..., у*}, тогда обозначим
ВВЕДЕНИЕ
28
Следствие 4 Если I = (X, V, р) — ЗИП, обладающая И-свойством, Т — (Е, 0) — измеримое базовое множество, допустимое для I, такое, что Е£ С Е, то
Р(0(у,Р)). Щк) < Т(1,Т) < Р(0(у,р)) • Ж*) +1,
где к = Щ 2/ 6 V.
В третьем пункте первого раздела второй главы исследуется В-сложность задач поиска, с коротким ответом.
Обозначим
. , (О, если х < О
згдп^х) = | ^ есди * > 0 ,
где х принимает вещественные значения;
1У(к) = 3[1оёз 4] + агдп+(к — *1) +
+лг<?п+ (* - 3[Ь(Й4 - З11“83 *•-») + sign+(k - 2 • 3Ро*> ч),
где к принимает натуральные значения.
Теорема 8 Если1 — (Х,У,р) —ЗИП, обладаюищя В^-свойством, У = 0) — измеримое базовое множество, допустимое для I,
то Т(1,Е)>\У{\У\).
Следствие 5 Если I = (Х,У,р) — ЗР1П, обладающая В1-свойст-вом, У — {Е, 0) — измеримое базовое множество, допустимте для I, такое, что Е$ С Е, то Т(1,У) = \У(\У\).
Теорема 9 Если I = (Х,У,р) — ЗИП, обладающая В\ -свойством, У — (И, (?) — измеримое базовое множество, допустимте для I, такое, что любой переключатель из (? принимает не более т значений, где т > 1, то Т(1,У) >)^т \У\[.
Результат теоремы 9 аналогичен теоретико-информационной нижней оценке [103), но все же является несколько более сильным, поскольку доказан для произвольных сетей, а не бинарных деревьев.
ВВЕДЕНИЕ
29
В четвертом пункте первого раздела второй главы приведены две леммы о сведении, которые описывают случаи, когда нижние оценки сложности для одних задач могут быть использованы для оценки сложности других задач с помощью этих лемм доказываются следующие теоремы.
Теорема 10 Если п — натуральное число, I = (X, V, р) — ЗИП, обладающая Вп-свойством, Т — (F, G) — измеримое базовое множество, допустимое для I, то T(I,F) > И^([|У|/п])} и если кроме того ЗИП 1, такая, что для любой записи у Є V выполняется Р(0(у,Р)) = г, то Т{1,Т) > Г • R(l\V\/n)).
Теорема 11 Если I = (X, К,р) € S = (X,Y,p,P,a) - ЗИП, обладающая В\ -свойством, такая, что для любой записи у Є V выполняется Р(0(у,р)) > г и существует такое множество Лу € с, что Лу С 0(у,р) и Р(АУ) = г; Т — (F,G) — измеримое базовое множество, допустимое для I, такое, что для любой записи yev fAyeF, где = Ау, moT{I,T) > т • R(\V\).
Во втором разделе второй главы исследуется задача поиска идентичных объектов, то есть рассматривается следующий тип Sid = (Х,Х,рц), где отношение поиска рм есть отношение идентичности, ТО есть xpidy X — у.
В первом пункте на оспове бинарного поиска доказывается следующая теорема.
Теорема 12 Если I = (X, V, pid) — задача поиска идентичных объектов, то есть задача типа Sid, Дып — базовое множество, состоящее из операций сравнения, то
Т(1,Яы,2IVI-1) <]logj|V|[+l,
]bg2 |V|(< Т(/Л„,2|У| - 1) <]log2 |V|[+1.
Во втором пункте второго раздела предлагается метод поиска идентичных объектов, который в среднем эффективен, как хорошие методы хеширования, а в худшем случае такой же, как метод
ВВЕДЕНИЕ
30
бинарного поиска, и плюс к этому в случае неудачного поиска выходит к ближайшим соседям ненайденной записи.
Формально это результат выглядит следующим образом.
Пусть N0 = N и {0} — множество целых неотрицательных чисел и
0, если / = 0
1Х(1) = ■ ]log2/[-Ы, если /=1,2,3 — log2 / + 2, если / > 4
функция, определенная на множестве N0.
Справедлива следующая теорема [27, 139].
Теорема 13 Пусть I = (Х,У,рц) — задача поиска идентичных объектов, то есть задача типа где |У| = к, Т — некоторое измеримое базовое множество, т — натуральное число, с — константа, ограничивающая функцию плотности распределения запросов, Тогда
1 < Т(1,Х, 2 • А- 4- т - 1) <
с (( к \ г ( к
— & - • т • Ьх (
ш \\ ТП ) \ т
( к ) г ( к
+ ( т — к + • т) • Ь\ (
V т / V т
+ 1 +
- -и.
В частности,
1<Т(1,?,(2+с)-к)<2
и Т(/,Е) ~ 1 при к —* оо. Кроме того, для ИГ и € Ы(1,Х), на котором достигается верхняя оценка, Т(Ц) < 2+]1<^9&[.
Здесь под словом ”некоторое” предполагается, что базовое множество содержит функции сравнения и разбиения множества X на приблизительно равные части (умножение).
Эта теорема получена методом оптимальной декомпозиции.
В третьем пункте второго раздела второй главы предлагается алгоритм поиска идентичных объектов, который обеспечивает константное время поиска в худшем случае.
ВВЕДЕНИЕ
31
В четвертом пункте второго раздела оценивается объем памяти. необходимый константному в худшем случае алгоритму поиска идентичных объектов и показывается, что если все ^-элементные библиотеки равновероятны, то доля fc-элементных библиотек, для которых данному алгоритму требуется память, по порядку большая, чем к2, является бесконечно малой величиной, а в типичной ситуации данному алгоритму требуется память, равная к2. Эти результаты опубликованы в [37].
В третьем разделе второй главы исследуются задачи о близости,, которые состоят в поиске во множестве, в котором задан линейный порядок, объекта, ближайшего к объекту-запросу справа или слева.
Поскольку все предложенные в предыдущем разделе алгоритмы поиска идентичных объектов в случае неудачного поиска приводят к ближайшим соседям запроса, то эти алгоритмы после небольшой модификации можно использовать для решения задач о близости. Поэтому результаты, получаемые для задач о близости полностью аналогичны результатам задачи поиска идентичных объектов, и эти результаты приводятся в трех пунктах третьего раздела второй главы.
В третьей главе исследуются задачи поиска, в которых отношение поиска, является отношением частичного порядка. Причем в первом разделе этой главы рассматривается случай, когда множество записей конечно, а именно рассматриваются задачи типа Spart — (Х,Х,У), где X — некоторое конечное множество, У — некоторое отношение частичного порядка на X х X.
Такие задачи поиска встречаются практически во всех системах баз данных и в зависимости от интерпретации носят название включающего поиска [79], дескрипторного поиска [72, 86, 89], поиска по ключевым словам, задачи о доминировании [55, 71] и т. п.
В первом разделе третьей главы доказывается теорема о существовании главных цепей [28, 140].
Пусть а G X, Кс — функция, действующая из X в {0,1} такая,
ВВЕДЕНИЕ
32
что Nxa = {х € X : х У а}. Пусть К. = {Ка(х) : а Ç X}, М =
п
(V : ai € € N}, где N — множество натуральных
i=i
чисел.
Пусть базовое множество имеет вид Т — (М, 0). Пусть V — ИГ над базовым множеством Т. Подмножество {ßu..., ßm} вершин ИГ U назовем характерным, если существует такая запись а <Е X, что
V Ч>& = Ка.
»=1
Пусть U — ИГ над базовым множеством Т = (Л4,0). Пусть Б = {ßx,..., ßm] — характерное подмножество вершин ИГ U такое,
т
что \J <pßt = Ка. Если в ИГ U существует такая цепь, ведущая из
t=i
корня в какую-либо вершину множества В, что проводимость этой цепи равна Ка, то эту цепь назовем главной цепью характерного множества В.
Справедлива следующая теорема [28, 140].
Теорема 21 (о существовании главных цепей) Пусть U — произвольный ИГ над базовым множеством Т — (Л4,0). Пусть В — произвольное характерное подмножество вершин ИГ U. Тогда в ИГ U существует главная цепь множества В.
Пусть U — ИГ над базовым множеством Т = (М,Ъ), разрешающий некоторую ЗИП I — (X, V, >:) типа Svart. Пусть у € V. Если в ИГ U существует такая цепь, ведущая из корня в какую-либо вершину множества Lu(y), что проводимость этой цепи равна то эту цепь пазовем главной цепью записи у.
Следствие 10 Пусть I = (X, V\ >:) — ЗИП типа Spart• Пусть U — ИГ над базовым множеством Т ~ (М,§), разрешающий ЗИП I. Тогда для любой записи у 6 V в ИГ U существует главная цепь записи у.
Теорема 21 и следствие 10 дают серьезные ограничения на структуру оптимального графа (согласно теореме 3 для задач поиска типа 5pCrt существуют оптимальные графы над базовым множеством (МЛ)), и эти ограничения существенно используются при
ВВЕДЕНИЕ
33
получении нижних оценок включающего поиска, понятие которого вводится во втором разделе данной главы.
Данный раздел состоит из шести пунктов.
Под задачами включающего поиска понимаются задачи следу-
ь
ющего типа б&оо/ = {Вп, Вп, <т, Р), где Вп — единичный п-мериый
ь
куб, то есть Вп = {(ат,...,аа) : а* Є {0,1} (г = 1,»)}; Ь — отношение поиска на Вп х определяемое следующим соотношением
г> ___
(хь...,жп)Ь(з/ь-..,Уп) <=> > У», г = 1,п; сг — алгебра подмно-
жеств Вп, представляющая собой множество всех подмножеств Вп\ Р — равномерная вероятностная мера на <х, то есть такая мера, что для любого х € Вп Р(х) = 1/2” и любого А С Вп Р(Л) = \ А\/2п.
Наличие главных цепей записей в ИГ, разрешающих задачи включающего поиска, казалось бы говорит в пользу того, что оптимальные ИГ включающего поиска должны быть древовидны. К сожалению, во втором пункте данного раздела эта гипотеза опровергается. В нем показано, что если базовое множество предикатов является множеством Хп = {хь х2,..., ач} — булевых переменных или /С" — элементарных монотонных конъюнкций, то существуют такие задачи включающего поиска, что для них оптимальные ИГ не древовидны, то есть справедливы следующие теоремы [33].
Теорема 22 Если п > 9 и базовое множество есть множество переменных (Хп,Щ, то существует такая 'ЗИП типа для которой любой оптимальный ИГ над (Хп,0) не является деревом.
Теорема 23 Если п > 26 и базовое множество есть множество элементарных монотонных конъюнкций (£п,0), то существует такая ЗИП типа ЗьО0[, для которой любой оптимальный ИГ над (£”,0) не является деревом.
С другой стороны, в третьем пункте данного раздела доказывается древовидыость оптимальных ИГ включающего поиска в классе бесповторных графов, под которыми будем понимать ИГ над базовым множеством (£",0) или над базовым множеством (Хп,<д),