Теория хранения и поиска информации

Гасанов Э.Э.
Кудрявцев В.Б.






            Теория хранения и поиска информации









МОСКВА ФИЗМАТЛИТ ®

УДК 519.71 tt Издание осуществлено при поддержке ББК 22.18 F                  Российского Фонда фундаментальных
      Е91          '*        исследований по проекту 02-01-14018

   Г а с а н о в Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. - М.: ФИЗМАТЛИТ; 2002. - 288 с. ISBX 5-9221-0235-4

   Вводится новый вид представления баз данных, называемый информационнографовой моделью данных, обобщающий известные ранее модели. Рассматриваются основные типы задач поиска информации в базах данных и исследуются проблемы сложности решения этих задач применительно к информационно-графовой модели. Разработан математический аппарат решения этих задач, основанный на методах теории сложности управляющих систем, теории вероятностей, а также на оригинальных методах характеристических носителей графа, оптимальной декомпозиции и снижения размерности.
   Для математиков, кибернетиков, информатиков и инженеров как научная монография и новый технологический аппарат, а также как учебное пособие для студентов и аспирантов, специализирующихся в области математической кибернетики, дискретной математики и математической информатики.
   Ил. 36. Библиогр. 216 назв.











Рецензент: доктор физико-математических наук, академик РАН, профессор Ю. И. Журавлев





















ISBX 5-9221-0235-4

© Гасанов Э.Э., Кудрявцев В.Б, 2002

ОГЛАВЛЕНИЕ



Введение................................................ 6

Глава 1. Информационно-графовая модель данных ...        13
1.1. Понятие информационного графа (ИГ)................ 13
1.2. Критерий допустимости ИГ.......................... 33
1.3. Полнота для информационных графов................. 36
1.4. Сложность информационных графов................... 39
1.5. Мощностная нижняя оценка.......................... 46
1.6. Случай оптимальности перебора..................... 49
1.7. Основные задачи................................... 50

Глава 2. Задачи поиска с коротким ответом.............. 52
2.1. Некоторые свойства задач поиска с коротким ответом. 52
   2.1.1. Существование древовидного оптимального ИГ для задач поиска с коротким ответом.......................... 53
   2.1.2. Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей ............. 58
   2.1.3. Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом ....................................... 64
   2.1.4. Леммы о сведении............................. 68
2.2. Поиск идентичных объектов......................... 70
   2.2.1. Бинарный поиск .............................. 71
   2.2.2. Константный в среднем алгоритм поиска........ 74
   2.2.3. Константный в худшем случае алгоритм поиска.. 80
   2.2.4. Оценки памяти константного в худшем случае алгоритма поиска ............................................ 80
2.3. Задачи о близости................................. 85
   2.3.1. Бинарный поиск .............................. 86
   2.3.2. Константный в среднем алгоритм поиска........ 87
   2.3.3. Константный в худшем случае алгоритм поиска.. 90

Глава 3. Задачи поиска на частично-упорядоченных множествах данных...................................... 92
3.1. Задачи поиска на конечных частично-упорядоченных множествах данных......................................... 92

Оглавление

3.2. Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных......................... 95
   3.2.1. Включающий поиск.................................. 96
   3.2.2. О недревовидности оптимальных ИГ включающего поиска 97
   3.2.3. 0 древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей............................. 108
   3.2.4. Нижняя оценка сложности включающего поиска ...... 109
   3.2.5. Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесповторных или древовидных ИГ.......................................... 117
   3.2.6. Оценки сложности одного метода решения задачи включающего поиска ............................................ 122
   3.2.7. Оценки В-сложности включающего поиска ........... 142
3.3. Задачи поиска на линейно-упорядоченных множествах данных ....................................................... 143
   3.3.1. Последовательные алгоритмы решения задачи поиска с от        ношением поиска вида линейного предпорядка......... 143
   3.3.2. Моделирование поиска в системах с несколькими вычислителями ................................................. 149
   3.3.3. Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка ............................. 158
3.4. Задачи поиска на декартовых произведениях линейно-упорядоченных множеств данных (задача о доминировании) .... 174 3.4.1. Последовательные алгоритмы решения задачи о доминировании ..................................................... 174
   3.4.2. Оценки В-сложности задачи о доминировании ....... 183
   3.4.3. Математическая модель фоновых алгоритмов поиска .... 184
   3.4.4. Фоновый алгоритм решения двумерной задачи о доминировании .................................................. 189


Глава 4. Задачи интервального поиска....................... 200
4.1. Одномерная задача интервального поиска................ 201
   4.1.1. Случай базового множества характеристических функций . 202
   4.1.2. Случай простого базового множества .............. 202
   4.1.3. Базовое множество логарифмического поиска........ 209
   4.1.4. Базовое множество сверхлогарифмического поиска... 212
   4.1.5. Мгновенное решение .............................. 216
4.2. Многомерная задача интервального поиска............... 221
   4.2.1. Мгновенное решение многомерной задачи интервального поиска ................................................... 222
   4.2.2. Пример оценки константы специальной ограниченности . . 233
   4.2.3. Оценки В-сложности задачи интервального поиска... 235
4.3. Оценки сложности двумерной задачи интервального поиска 236
   4.3.1. Формулировка результата.......................... 236
   4.3.2. Неформальное описание алгоритма.................. 239
   4.3.3. Построение информационного графа................. 241
   4.3.4. Допустимость информационного графа............... 249

Оглавление

5

   4.3.5. Объем информационного графа .................. 251
   4.3.6. Сложность информационного графа .............. 256

Глава 5. Свойство канонического эффекта................. 261
5.1. Понятие канонического эффекта...................... 261
5.2. Неустойчивость канонического эффекта по отношению к базовому множеству........................................ 263
5.3. Неустойчивость канонического эффекта по отношению к объему памяти......................................... 264
5.4. Устойчивость канонического эффекта по отношению к е-расширению запроса...................................... 264
   5.4.1. е-расширение задачи поиска идентичных объектов. 264
   5.4.2. е-расширение задач о доминировании и интервального поиска ................................................ 267

Литература.............................................. 269

Предметный указатель.................................... 282

Предметный указатель.................................... 282

ВВЕДЕНИЕ



   В последние десятилетия активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, именуемое теорией информационного поиска. Одним из главных носителей этого направления является теория баз данных. Возникшее под влитием практических задач, оно и сейчас в основном обслуживает приложения, а собственно теоретическая его часть, как представляется, обретает контуры. Как всякая научная дисциплина это направление должно характеризоваться следующими чертами: предметом исследования, проблематикой, методами и результатами. В развитой теории каждая из этих черт должна иметь достаточно общий характер. В то же время важно отметить, что молодые дисциплины возникают, как правило, через рассмотрение отдельных конкретных важных примеров, которые затем с развитием дисциплин обобщаются как в постановочной, так и в проблемно-методологической частях. Подобных примеров достаточно много в кибернетике, информатике и других разделах науки. К числу характерных из них может быть отнесена теория управляющих систем. В своей практической деятельности человек столкнулся с конкретными видами таких систем, которые далее играли роль модельных управляющих систем. В инженерном деле — это вентильные и контактные схемы, схемы из функциональных элементов и некоторые другие, в математике — формулы, алгоритмы и т. д., в биологии — нейроны, нейронные сети, автоматы и т. и. Для этих видов управляющих систем рассматривались две такие главные задачи анализа и синтеза соответствующих управляющих систем. Первая состояла в изучении “поведения” таких систем, а вторая — в создании соответствующей системы с заданным “поведением”. На первом этапе эти постановки связывались непосредственно с модельными системами и для каждой из них разрабатывался конкретный метод решения. Со временем наступил этап, когда большинство из этих систем могли уже рассматриваться с единых позиций и исследование указанных общих задач достигалось уже с помощью общих методов решения [9]. Хотя по-прежнему модельные управляющие системы, имея свою специфику, продолжают оставаться в центре внимания теории управляющих систем.
   Аналогичный путь развития проходит теория информационного поиска. В ней также первоначально возникли конкретные примеры способов хранения и представления данных и соответствующих этим способам алгоритмов поиска информации. К их числу относятся: лексикографические, древовидные, реляционные и др. Задачи поиска для них имеют конкретные виды и модификации, такие как задача поиска

Введение

Г

идентичных объектов, задача о близости, включающий поиск и др. Они играют роль модельных задач для выбранных способов хранения информации и изучались на протяжении многих лет, привлекая каждый раз для своего решения специальные исследовательские средства, которые носили ограниченный по своим возможностям характер.
   Тем самым можно считать, что современное состояние теории информационного поиска напоминает то состояние теории управляющих систем, которое соответствовало первому этапу развития последней, когда накапливались данные лишь о конкретных видах модельных управляющих систем. В то же время, как выяснилось, опыт развития теории управляющих систем в своей методологической части давал возможность сделать попытку с более общих позиций провести исследование как модельных баз данных, так и модельных задач для них, с соответствующей разработкой достаточно общей теории.
   Это и составляет содержание исследований данной монографии.
   Мы предлагаем новую модель данных (частными случаями которой могут считаться уже известные) с наследственно определенными средствами поиска информации, с соответствующими понятиями сложности такого поиска, а также разрабатываем основы теории решения базовых задач поиска применительно к этой модели. Если продолжить аналогию с теорией синтеза управляющих систем, то можно отметить, что различным видам управляющих систем соответствуют различные виды хранения и представления данных (модели данных), классам функций, исследуемым в теории синтеза, соответствуют типы задач поиска, исследуемые в теории информационного поиска. И в теории синтеза и в теории поиска вводятся понятия сложности и ставятся задача оптимального синтеза и задача исследования функций сложности шенноновского типа. Таким образом, мы стремимся к тому, чтобы приблизить состояние теории информационного поиска по степени продвинутости к современному состоянию теории управляющих систем.
   Уточним сказанное. Во-первых, мы предлагаем новую формализацию понятия задачи поиска. Тип задач поиска охватывает класс однотипных вопросов к базе данных. Тип задач поиска заключает в своем определении три объекта: множество запросов, множество записей и бинарное отношение, заданное на декартовом произведении этих множеств, называемое отношением поиска. Здесь запись — это поисковый образ элемента данных, т. е. поле или множество полей элемента данных, которые представляют интерес в данном типе вопросов. Запрос — это минимальный элемент, содержащий суть вопроса. Запрос совместно с отношением очерчивает тот круг объектов, которые отвечают на данный вопрос. Задача поиска заданного типа получается выделением из множества записей конечного подмножества, называемого библиотекой. А именно, задача поиска состоит в том, чтобы по произвольному запросу перечислить все записи из библиотеки, находящиеся в заданном отношении с запросом (удовлетворяющие запросу). При фиксации отношения поиска каждая запись задает предикат, определенный на множестве запросов, который равен 1, если

Введение

данная запись удовлетворяет запросу — аргументу функции. Поэтому если вернуться к аналогии с теорией синтеза управляющих систем, то тип задач поиска есть способ описания некоторого конкретного класса предикатов, задаваемых на множестве запросов, а задача поиска — это конкретное подмножество предикатов из этого класса.
   Во-вторых, мы предлагаем новую управляющую систему, называемую информационным графом, которая в общей иерархии теории управляющих систем находится в не очень высоких слоях залегания и является в некотором смысле обобщением контактных схем. Фактически нам нужны лишь графы, дискретные функции и вычисление волновых процессов на графах, и этого хватает, чтобы с достаточно общих позиций посмотреть на ту разрозненную картину, которая наблюдается в теории информационного поиска.
   В предлагаемой информационно-графовой модели данных структура данных задается ориентированным графом (называемым информационным), ребра и вершины которого нагружены элементами данных и функциями, определенными на множестве запросов. В графе выделена одна вершина, называемая корнем и ассоциируемая со входом, а вершины графа, нагруженные элементами данных, ассоциируются с выходами. Этот же граф описывает алгоритм поиска, на вход которого поступает запрос, а на выходе получается некоторое подмножество данных. При этом процесс поиска начинается с корня и распространяется в зависимости от значений нагрузочных функций на запросе возможно сразу по нескольким направлениям. Если этот волновой процесс на графе достигает элементов данных, то эти элементы включаются в ответ алгоритма на исходный запрос. Информационный граф будет решать некоторую задачу поиска, если для произвольного запроса ответ на этот запрос содержит все те и только те записи из библиотеки, которые удовлетворяют запросу. Таким образом, информационный граф, с одной стороны, дает новую концепцию хранения данных, а, с другой стороны, предлагает новый подход к поиску информации как волнового процесса на графах, управляемого нагрузочными функциями. Нагрузочные функции, которые называются базовыми, разделены на два класса — предикаты и переключатели, и являются одними из основных управляющих параметров модели. Нагрузочные функции по сути определяют функции проводимости между вершинами графа, и проблема нахождение решения задачи поиска сводится к проблеме синтеза информационного графа, реализующего систему функций, задаваемую задачей поиска.
   Также как логическая сеть со свободными элементами [62] обобщает известные в теории управляющих систем виды управляющих систем, так и информационно-графовая модель обобщает наиболее известные модели данных. Так, алгоритмы и конструкции, используемые в древовидных и лексикографических базах данных, описываются древовидными информационными графами. Сетевые базы данных естественным образом перекладываются на язык информационнографовой модели. Алгоритм поиска, используемый в дедуктивных базах данных, при переходе на язык информационных графов приводит

Введение

9

к константному дереву. Алгоритмы в реляционных базах данных приводят к древовидным информационным графам специального вида.
   Информационные графы позволяют ввести новое понятие сложности поиска. Это понятие новое как с точки зрения теории управляющих систем, так и с точки зрения теории баз данных. В теории управляющих систем обычно под сложностью понимается или число ребер, или число элементов-функций, а здесь сложность понимается как часть графа, захваченного волновым процессом, и существенно зависит от значений нагрузочных функций, и, тем самым, не является просто количественной характеристикой графа, такой как число ребер или вершин. Новизна же в теории баз данных заключается в том, что такое введение сложности после осреднения по множеству запросов адекватно соответствует среднему времени поиска — традиционно трудной для изучения характеристики алгоритмов поиска информации. Кроме того, при соответствующем введении сложности информационные графы оказываются удобными для изучения как параллельных, так и фоновых алгоритмов поиска. И, наконец, в информационных графах совсем просто контролируется такой важный управляющий параметр в задачах информационного поиска, как объем памяти, который в данном случае характеризуется количеством ребер графа.
   Формальное определение информационно-графовой модели данных и некоторые ее свойства можно найти в первой главе монографии.
   В монографии рассматриваются 7 модельных типов задач поиска, являющихся наиболее распространенными задачами поиска в базах данных. Анализ этих 7 модельных типов позволил разбить их на 3 крупных базовых класса. Первый класс включает в себя задачи поиска, в которых для почти всех запросов ответ на них содержит ограниченное малой константой число элементов. Этот класс получил название задач поиска с коротким ответом и исследуется во второй главе.
   Второй класс, названный задачами поиска на частично-упорядоченных множествах данных, состоит из задач, в которых в ответ на запрос надо перечислить все элементы базы данных, которые в заданном частичном порядке меньше, чем запрос. Задачи из этого класса рассматриваются в третьей главе монографии.
   И, наконец, третий класс содержит так называемые задачи интервального поиска, результат которых в некотором смысле можно рассматривать как пересечение решений двух задач из второго класса. Этот класс исследуется в четвертой главе.
   Классификация 7 модельных классов задач поиска и объединение их в 3 базовых класса, конечно, не единственный способ обобщения задач поиска. Одним из естественных методов является е-расширение запроса, которое позволяет ответу на задачу несколько отходить (на величину е) от требований задачи.
   Для базовых задач поиска ставится проблема оптимального синтеза, которая состоит в построении для заданной задачи информационного поиска информационного графа, который решает эту задачу

Введение

и имеет наименьшую или близкую к ней сложность. Результаты, полученные при решении проблемы оптимального синтеза для базовых задач, характеризуются, во-первых, тем, что для всех задач из модельных классов, кроме так называемых задач включающего поиска из второго базового класса, получены точные и (или) асимптотические результаты, для задач включающего поиска получена асимптотика функции Шеннона, а для некоторых базовых множеств — и асимптотика. сложности для почти всех задач и для средней сложности по задачам. Во-вторых, полученные результаты можно условно разбить на 4 типа.
   К первому типу относятся задачи, имеющие константную сложность, т. е. которые можно решить в среднем за константное число шагов. Константную сложность имеют некоторые задачи из первого базового класса.
   Ко второму типу относятся задачи поиска с условно константной сложностью. Это задачи, для решения которых помимо перечисления ответа (а это сложность, которую избежать никак нельзя, и она носит название мощностной нижней оценки) требуется в среднем константное число вычислений. Такие задачи встречаются во втором и третьем базовых классах.
   К третьему типу относятся задачи с логарифмической сложностью, решение которых не может быть получено за время, меньшее, чем логарифм от объема базы данных. К этому типу относятся некоторые задачи из первого базового класса, когда из множества базовых функций исключены переключатели.
   И, наконец, к четвертому типу относятся задачи с быстро растущей сложностью, т. е. разность между сложностью которых и мощностной нижней оценкой является растущей функцией. К четвертому типу относятся задачи включающего поиска из второго базового класса.
   Для решения задач оптимального синтеза для базовых классов разработаны следующие 3 основных метода.
   Первый метод мы называем методом оптимальной декомпозиции. Он состоит в таком разбиении задачи на подзадачи, которые допускают простое решение и при этом сложность поиска подзадачи, дающей решение исходной задачи, также осуществляется просто. Этот метод использовался при решении опорных или одномерных задач поиска.
   Второй метод, называемый методом снижения размерности, применяемый к многомерным задачам, сводится к тому, чтобы с помощью некоторых опорных задач последовательно понижать размерность задачи и в конце концов свести ее к опорной задаче, решение которой уже известно.
   Третий метод назван методом характеристических носителей графа и использовался при получении нижних оценок. Он заключается в выделении в информационном графе, являющемся оптимальным решением, подграфов с заданными свойствами (характеристических носителей) и в последующем подсчете сложности характеристических носителей.