ВВЕДЕНИЕ

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

Аналогичный путь развития проходит теория информационного поиска. В ней также первоначально возникли конкретные примеры способов хранения и представления данных и соответствующих этим способам алгоритмов поиска информации. К их числу относятся: лексикографические, древовидные, реляционные и др. Задачи поиска для них имеют конкретные виды и модификации, такие как задача поиска идентичных объектов, задача о близости, включающий поиск и др. Они играют роль модельных задач для выбранных способов хранения информации и изучались на протяжении многих лет, привлекая каждый раз для своего решения специальные исследовательские средства, которые носили ограниченный по своим возможностям характер.

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

Это и составляет содержание исследований данной монографии.

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

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

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

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

Также как логическая сеть со свободными элементами [62] обобщает известные в теории управляющих систем виды управляющих систем, так и информационно-графовая модель обобщает наиболее известные модели данных. Так, алгоритмы и конструкции, используемые в древовидных и лексикографических базах данных, описываются древовидными информационными графами. Сетевые базы данных естественным образом перекладываются на язык информационнографовой модели. Алгоритм поиска, используемый в дедуктивных базах данных, при переходе на язык информационных графов приводит к константному дереву. Алгоритмы в реляционных базах данных приводят к древовидным информационным графам специального вида.

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

Формальное определение информационно-графовой модели данных и некоторые ее свойства можно найти в первой главе монографии.

В монографии рассматриваются 7 модельных типов задач поиска, являющихся наиболее распространенными задачами поиска в базах данных. Анализ этих 7 модельных типов позволил разбить их на 3 крупных базовых класса. Первый класс включает в себя задачи поиска, в которых для почти всех запросов ответ на них содержит ограниченное малой константой число элементов. Этот класс получил название задач поиска с коротким ответом и исследуется во второй главе.

Второй класс, названный задачами поиска на частично-упорядоченных множествах данных, состоит из задач, в которых в ответ на запрос надо перечислить все элементы базы данных, которые в заданном частичном порядке меньше, чем запрос. Задачи из этого класса рассматриваются в третьей главе монографии.

И, наконец, третий класс содержит так называемые задачи интервального поиска, результат которых в некотором смысле можно рассматривать как пересечение решений двух задач из второго класса. Этот класс исследуется в четвертой главе.

Классификация 7 модельных классов задач поиска и объединение их в 3 базовых класса, конечно, не единственный способ обобщения задач поиска. Одним из естественных методов является е -расширение запроса, которое позволяет ответу на задачу несколько отходить (на величину е) от требований задачи.

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

К первому типу относятся задачи, имеющие константную сложность, т. е. которые можно решить в среднем за константное число шагов. Константную сложность имеют некоторые задачи из первого базового класса.

Ко второму типу относятся задачи поиска с условно константной сложностью. Это задачи, для решения которых помимо перечисления ответа (а это сложность, которую избежать никак нельзя, и она носит название мощностной нижней оценки) требуется в среднем константное число вычислений. Такие задачи встречаются во втором и третьем базовых классах.

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

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

Для решения задач оптимального синтеза для базовых классов разработаны следующие 3 основных метода.

Первый метод мы называем методом оптимальной декомпозиции. Он состоит в таком разбиении задачи на подзадачи, которые допускают простое решение и при этом сложность поиска подзадачи, дающей решение исходной задачи, также осуществляется просто. Этот метод использовался при решении опорных или одномерных задач поиска.

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

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

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

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

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

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

Содержание книги составил материал, который использовался при чтении обязательных и специальных курсов в МГУ им. М. В. Ломоносова по кафедре математической теории интеллектуальных систем на механико-математическом факультете и факультете вычислительной математики и кибернетики. Отдельные главы читались как специальные курсы в Российском государственном гуманитарном университете на факультете защиты информации и в научно-учебном центре МГУ - ВЦ РАН - РГГУ “Интеллектуальные системы и нечеткие технологии” (ФЦП “Интеграция”, грант JV® 431, направление 2.1).

Авторы выражают особую благодарность А. С. Подколзину, предложения которого, советы и обсуждения отличались характерной для него щедростью.

Авторы благодарят академика Ю. И. Журавлева, член-корреспондента РАН О. Б. ЛуПанова, профессоров А. В. Михалева, Г. П. Шанки- на и А. Б. Фролова за внимание к работе и ее поддержку.

Нам приятно поблагодарить весь коллектив кафедры Математической теории интеллектуальных систем механико-математического факультета Московского государственного университета им. М. В. Ломоносова, чье постоянное внимание, доброжелательная критика и советы способствовали появлению этой книги.

Авторы выражают благодарность Российскому фонду фундаментальных исследований за частичную финансовую поддержку (гранты 95-01-00597, 98-01-00130, 01-01-00748, 02-01-14018).

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

М. Н. Назаровым предложена математическая модель доступа к распределенным данным с помощью параллельного вычисления булевых функций [217]. Им получены оценки сложности вычисления булевых функций на нескольких независимых наборах, на основе которых удалось оптимизировать параллельный доступ к криптографически защищенным базам данных. По этим результатам М. Н. Назаровым под руководством проф. А. Е. Андреева и проф. Э. Э. Гасанова защищена кандидатская диссертация «Параллельное вычисление булевых функций как модель доступа к распределенным информационным ресурсам».

Е. С. Быченкова исследовала задачу о метрической близости, которая созвучна задаче, рассматриваемой в разделе 2.3 данной книги. В [218] она предложила оптимальный по порядку метод синтеза поискового оператора о метрической близости в классе автоматных схем специального вида.

В работе [219] А. А. Харина (Фещук) ввела математическую модель для нечетких задач поиска и рассмотрела вопросы сводимости нечетких задач поиска к обычным задачам поиска. Это направление исследований еще в самом начале и ждет своего исследователя.

Т. Д. Уварова (Блайвас) занималась исследованиями сложности интервального поиска на булевом кубе [220—222]. Эти исследования являются развитием исследований по интервальному поиску, рассматриваемому в 4 главе данной книги, для случая, когда поиск производится на булевом кубе (см. раздел 3.2 данной книги). В этом направлении достигнуты существенные продвижения. Получены точные значения сложности для сбалансированных деревьев и асимптотические оценки функции Шеннона в классе древовидных схем. По этим результатам Т. Д. Уваровой под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «О сложности интервального поиска на булевом кубе».

Г. А. Майлыбаевой [223—224] построена математическая модель протоколов конфиденциального доступа к данным (PIR-протоколов), на основе которой получены рекордные нижние оценки коммуникационной сложности, доказывающие оптимальность по порядку разработанных PIR-протоколов. На основе этих результатов Г. А. Майлы- баевой под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «Коммуникационная сложность протоколов доступа к данным без раскрытия запросов».

Н. С. Кучеренко под руководством проф. Э. Э. Гасанова защитила кандидатскую диссертацию «Сложность поиска в случайных базах данных». Ею построены серии функций роста сложности поиска информации в случайных базах данных в зависимости от функций распределения элементов баз данных и запросов, порождающие бесконечную возрастающую шкалу функций роста, которая начинается с ограниченных функций и заканчивается двоичным логарифмом [225—227].

Ю. С. Шуткиным под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «Сложность реализации булевых функций информационными графами». Им получена асимптотика сложности реализации булевых функций информационными графами и разработан метод синтеза контактных схем, асимптотически оптимальный и по мощности и по объему [228—232].

А. П. Пивоваровым под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «Неперечислительные задачи информационного поиска». Им разработаны математические модели для неперечислительных задач информационного поиска. Получены оценки сложности некоторых вычислительных задач информационного поиска и задач поиска представителя [233—236].

Е. А. Снеговой (Скиба) под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «Сложность задачи о предотвращении столкновений». Ею получены критерии сводимости задачи о предотвращении столкновений к некоторым простым геометрическим задачам поиска, и на основе этого сведения получены сверхбыстрые алгоритмы поиска движущихся объектов [237—239].

И. С. Лапшов исследовал динамические базы данных, основывающиеся на хешировании методом цепочек [240]. Далее тема динамических баз данных была развита А. А. Плетневым в работах [241—244]. А. А. Плетневым разработана математическая модель динамических баз данных. Эта модель основывается на двух основных понятиях: понятии информационного графа, который отражает структуру хранения данных, и понятии конечного автомата, который отвечает за перестройку структуры базы данных в соответствии запросами на вставку и удаление данных. Эта конструкция названа динамическим информационным графом. Исследуется вопрос обслуживания динамическим информационным графом произвольных потоков запросов. Здесь идет речь о одновременной бесконфликтной работе сколь угодно большого количества автоматов на одной структуре данных. Фактически предлагаемый подход позволяет строить бесконечно распараллеливаемые алгоритмы обработки данных. На основе этих результатов А. А. Плетневым под руководством проф. Э. Э. Гасанова подготовлена кандидатская диссертация «Моделирование динамических баз данных».

Е. М. Перпер исследовал задачи поиска, возникающие при семантическом анализе текстов, в частности задача поиска подслова в базе данных слов [245—248]. Им получены нижние оценки временной и объемной сложности задачи поиска подслова и предложен оптимальный по порядку алгоритм поиска в множестве слов вхождений подслова. На основе разработанных алгоритмов Е. М. Перпером предложен подход, который позволяет по тексту нормативного акта автоматически строить компьютерную программу, которая выполняет действия, предписанные нормативным актом. На основе этих результатов Е. М. Перпером под руководством проф. Э. Э. Гасанова подготовлена кандидатская диссертация «Семантический анализ текстов и связанные с ним задачи поиска».

Для облегчения изучения данной книги могут оказаться полезными следующие учебники, вышедшие в издательстве «» [249-253].

Авторы: Гасанов Эльяр, Кудрявцев Валерий