|
Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.
Функционально-сетевые базы данных и сверхбыстрые алгоритмы поиска
Гасанов Э.Э.
Учебное пособие
Скачать пособие полностью в формате PDF (440 кб): funksetbd.zip
Для просмотра Вам понадобится Adobe Acrobat Reader 4.x-5.x
УДК 517.977 + 681.3 513
Факультет защиты информации
Кафедра математической и программной защиты информации
Центр компьютерных технологий образования
Гасанов Э. Э.
Функционально-сетевые базы данных и
сверхбыстрые алгоритмы поиска. Конспект лекций. -
М.: Издательский центр РГГУ. 1997. 88 с.
Курс лекций
"Оптимальный поиск в базах данных"
читается на факультете защиты информации
Российского государственного гуманитарного
университета в качестве спецкурса
для специальности 220600 "Организация и
технология защиты информации".
В книге описывается подход к
исследованию сложности алгоритмов поиска,
основанный на построении математической
модели алгоритмов поиска. Приводятся
сверхбыстрые в "среднем" алгоритмы
поиска, используемые в геометрических
базах данных.
Для математиков-прикладников,
специалистов в области теории баз данных,
защиты информации и т.д., а также для
аспирантов и студентов вузов как учебное
пособие по математической теории баз данных
и теории быстрых алгоритмов поиска.
Автор: к.ф.-м.н., доц. Э. Э. Гасанов
Рецензент: проф. А. С. Строгалов
© Российский государственный гуманитарный университет, 1997
Введение
Считается почти нормальным, что теория всегда
будет идти позади. Но все-таки, действительно, надо
бы обращать внимание на более простые вопросы, не
завихряясь вокруг сложностей, так чтобы ну хоть
где-нибудь забежать вперед и протянуть практике руку
помощи.
М.Р. Шура-Бура
Управляющая система, функционирующая в среде, –
это центральное понятие кибернетики.
Управляющие системы можно разбить на два класса: те,
которые действуют без памяти (рефлекторно), и те,
которые имеют память. Второй класс неизмеримо богаче, чем
первый, и изучается в первую очередь. Примеры управляющих
систем без памяти: вирусы, микробы, разменные аппараты.
Высшие животные, человек, в технике – адаптивные
системы, компьютеры – управляющие системы с памятью.
Естественно возникает вопрос оптимальной организации
памяти в таких системах,
которую можно отождествить с содержательным пониманием
баз данных.
Как следует из известных справочников
[26,30],
база данных –
это именованная совокупность данных, отражающая состояние
объектов и их отношений в рассматриваемой предметной
области.
Если следовать Дж. Мартину [25],
К. Дейту [19], Т. Тиори и Дж. Фраю [32], то
организацию базы данных можно условно разделить на
логическую и физическую. Логическая организация
базы данных отражает представление о базе
данных прикладного программиста и пользователя,
а физическая – представление системного
программиста и аналитика. В [32]
выделяется еще один уровень, более
абстрактный, чем логический, называемый
концептуальным представлением и отражающий
представление администратора базы данных.
Общепринято, что основными моделями
логической организации базы данных
являются следующие три модели:
иерархическая, сетевая и реляционная.
Самой известной системой, использующей
иерархическую модель данных, является
система IMS фирмы IBM
[46,54,55,56].
В иерархической модели отношения
между данными бывают типа "родитель – потомки",
то есть у каждого объекта только один
родитель (у корневого объекта нет родителя),
но в принципе может быть несколько потомков.
Такие отношения принято изображать в виде
дерева, где ребро между объектами отображает
наличие некоторого отношения, причем название
отношения пишется на ребре. Например, между
объектами "клиент" и "заказ" может быть
отношение, которое называется "делает",
а между "заказ" и "товары" – отношение
"состоит из".
В случае, когда граф отношений между объектами
может представляться не только древовидными
структурами, мы имеем дело с сетевой моделью
данных, предложенной ассоциацией CODASYL
[21,36,37,38].
Понятно, что сетевая
модель как более общая предоставляет большие
возможности по сравнению с иерархической, но,
с другой стороны, она сложнее в реализации
и использовании.
Заслуга разработки и развития реляционной модели
баз данных принадлежит Е. Кодду
[39,40,41,42,43,44,45,47].
Реляционная база данных состоит из плоских таблиц,
называемых отношениями. Строки таблицы
(экземпляры записей) называются кортежами,
а столбцы – доменами.
Для описания отношений и операций над ними существуют
точные математические обозначения, основанные на
алгебре отношений или на исчислении отношений.
Е. Кодд [42] разработал специальный язык манипулирования
данными для такой базы.
Различные пользователи могут выделять в базе данных
различные наборы элементов данных и связи между ними.
Следовательно, необходимо иметь возможность извлекать
подмножества столбцов таблицы для одних пользователей, создавая
таблицы меньшей размерности, а также объединять таблицы
для других пользователей, создавая при этом
таблицы большей размерности. Язык Е. Кодда
содержит обе операции. Благодаря операциям разрезания и
склеивания таблицы обладают гибкостью, которой
лишено большинство древовидных и сетевых структур.
С логической точки зрения база данных – это
множество двумерных таблиц с операциями извлечения и
объединения столбцов.
С помощью метода нормализации Е. Кодда [40] можно
древовидное или сетевое описание преобразовать к
набору плоских таблиц.
При физической организации баз данных мы имеем
дело не с представлением данных в прикладных
программах, а с их размещением на запоминающих
устройствах.
Критерии, определяющие выбор физической организации,
отличаются от тех, которые определяют выбор логической
организации данных. При выборе физической организации
решающим фактором является эффективность, причем
согласно Дж. Мартину [25] на первом месте
стоит обеспечение эффективности поиска, далее идут
эффективность операций занесения и удаления и затем
обеспечение компактности данных. Кроме того, в последнее
время большую актуальность приобрели проблемы защиты
данных от несанкционированного доступа.
Методы физической организации данных хорошо изложены в классических
книгах Д. Кнута [23], Дж. Мартина [25],
А. Ахо, Дж. Хопкрофта, Дж. Ульмана [3].
Автор данной работы относит себя к разработчикам структур и
алгоритмов физической организации данных.
Так, предлагаемая в данной работе модель, предназначается
для исследования
структур и
алгоритмов поиска информации.
В этой модели, представляющей собой
нагруженную ориентированную сеть,
граф сети отражает структуру данных, а
нагрузка сети функциями над множеством
запросов предоставляет способы ориентации
в данных, запирая или открывая проводимость
ребер на конкретных запросах.
Академик АТН РФ, профессор В.Б.Кудрявцев
предложил более широко взглянуть на эту
модель, подчеркнув, что ее можно рассматривать
и как модель логической организации данных.
В этой модели, которую академик В.Б.Кудрявцев предложил
назвать функционально-сетевыми базами данных,
граф сети, так же как и в сетевой модели
отображает структуру и отношения между данными,
а нагрузка ребер сети характеризует отношение
между объектами, но в отличие от сетевой
модели это отношение становится
функциональным, то есть его содержание
зависит от текущего запроса (или в более общем понимании от
текущего состояния базы данных).
Представляется, что это настолько интересная и перспективная
концепция, что ее название вынесено в заголовок
книги.
Данная работа посвящена исследованию сложности
алгоритмов, предназначенных для решения
задач поиска. В понятие задачи поиска исследователи
вкладывают по крайней мере 3 различных смысла.
Специалисты в теории исследования операций
понимают задачи
поиска как задачи управления сближением
одной системы (поисковой) с другой (искомым объектом)
по неполной априорной информации. Понимается, что
цель поиска – это обнаружение искомого объекта,
определяемое как выполнение
определенных терминальных условий.
Интенсивно проблемой поиска подвижных
объектов начали заниматься в период Второй мировой войны.
Интерес к этой проблеме в тот период был
вызван необходимостью разработки тактики
борьбы против подводных лодок. Среди работ,
посвященных этой тематике, можно выделить, например,
работы В. А. Абчука, В. Г. Суздаля
[1],
О. Хеллмана [33] и
Д. П. Кима [22].
Другое понимание задач поиска можно найти
в книге Р.Альсведе, И.Вегенера "Задачи поиска"
[2]. Приведем поясняющий пример из этой
книги.
Во время Второй мировой войны все призываемые в армию
США подвергались проверке на реакцию Вассермана.
При этом проверялось, есть ли в крови обследуемого
определенные антитела, имеющиеся только у больных.
Во время этого массового обследования было замечено,
что разумнее анализировать пробу крови целой группы людей.
Если такая объединенная проба крови не содержит антител,
то, значит, ни один из обследуемых не болен. В противном
случае среди них есть хотя бы один больной.
Хороший алгоритм поиска для этой задачи – это тот,
который для типичной выборки людей
позволяет "наискорейшим образом" выявлять
множество всех больных.
Другой пример мы находим в статье
Д.Ли, Ф.Препараты "Вычислительная геометрия"
[24].
Дано множество горизонтальных и вертикальных
отрезков. Надо найти все точки пересечения отрезков.
Эти два примера объединяет то, что в обоих случаях поиск
производится однократно. Это порождает свои
особенности таких задач поиска. Как правило,
данные в этих задачах не имеют сложной организации.
Фиксация множества, в котором производится поиск,
однозначно определяет множество найденных объектов.
"Хорошесть" алгоритма поиска определяется при
варьировании множества, в котором производится поиск.
В третьем понимании задачи поиска предполагается
многократное обращение к одним и тем же данным, но
возможно каждый раз с разными требованиями к искомым
объектам, то есть с разными запросами на поиск. Такие
задачи поиска обычно возникают в системах, использующих
базы данных. Многократное использование порождает
особую проблему – проблему специальной организации
данных, направленной на последующее ускорение поиска.
Процесс такой специальной организации данных,
проводимый до того, как осуществляется поиск,
называется предобработкой и часто может занимать
очень большое время, которое затем окупается
сторицей в результате многократности поиска.
Простейшим примером предобработки является
сортировка. Построение "хорошего" алгоритма
поиска в этом случае сводится к нахождению
хороших структур данных, то есть к осуществлению
такой хорошей предобработки данных, которая
обеспечила бы хорошую скорость поиска.
"Хорошесть" алгоритма поиска в этом случае определяется
варьированием запроса на поиск, например, как
среднее время поиска на запросе.
Такие задачи поиска, возникающие в системах
баз данных и предполагающие многократное обращение
к одним и тем же данным, и являются объектом
рассмотрения в данной работе.
Спецкурс
"Оптимальный поиск в базах данных",
на основе которого написана данная работа,
читается на кафедре
математической и программной защиты информации
факультета защиты информации
Российского государственного гуманитарного
университета
для специальности 220600 "Организация и
технология защиты информации".
Целью спецкурса является описание подхода
к исследованию сложностных характеристик
алгоритмов поиска с помощью математического
моделирования. В задачи спецкурса входит:
ввести строгую математическую
модель алгоритмов поиска, направленную на исследование
среднего времени поиска; описать структуры данных,
используемых в алгоритмах поиска; описать сверхбыстрые
в "среднем" алгоритмы решения геометрических задач
поиска, относящихся к интенсивно развивающемуся
в последние годы
направлению, получившему название "Вычислительная
геометрия" [24]. В отличие от спецкурса
в данной книге практически не нашли отражения
известные алгоритмы и структуры данных,
которые можно найти, например, в классических
учебниках
Д. Кнута [23], Дж. Мартина [25],
А. Ахо, Дж. Хопкрофта, Дж. Ульмана [3].
В заключение автор хотел бы выразить благодарность
В.Б.Кудрявцеву и А.С.Подколзину за помощь в работе,
Э.А.Применко и А.С.Строгалову за ценные замечания,
а также Российскому фонду фундаментальных исследований
за частичную финансовую поддержку
(грант 95-01-00597 "Исследование сложности алгоритмов
поиска").
-
- 1
-
Абчук В. А., Суздаль В. Г. Поиск объектов.
М.: Советское радио, 1977.
- 2
-
Альсведе Р., Вегенер И. Задачи поиска.
М.: Мир, 1982.
- 3
-
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ
вычислительных алгоритмов. М.: Мир, 1979.
- 4
-
Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения
по курсу дискретной математики. М.: Наука, 1992.
- 5
-
Гасанов Э. Э. Некоторые оценки сложности поиска информации //
Физическое и математическое моделирование дискретных
систем. Межвузовский сборник трудов 56. М.: Изд-во Моск. энерг.
ин-та, 1985. – С. 43-47.
- 6
-
Гасанов Э. Э. Алгоритмы построения информационных деревьев.
Препринт Р-5-188 ИЯФ АН УзССР. Ташкент, 1985.
- 7
-
Гасанов Э. Э. Оценки средней сложности поиска информации.
Препринт Р-5-186 ИЯФ АН УзССР. Ташкент, 1985.
- 8
-
Гасанов Э. Э. О сложности
информационного поиска: Дис. канд. физ.-мат. наук. -
М., 1985.
- 9
-
Гасанов Э. Э. О некоторых оценках сложности поиска информации //
Алгебра, логика и теория чисел: Сб. статей. – М.:
Изд-во МГУ, 1986. – С. 37-39.
- 10
-
Гасанов Э. Э. О виде оптимальных информационных сетей для
отношений линейного квазипорядка.
Препринт Р-5-303 ИЯФ АН УзССР. Ташкент, 1987.
- 11
-
Гасанов Э. Э. Оптимальные информационные сети для отношений
поиска, являющихся отношениями линейного квазипорядка //
Конструкции в алгебре и логике: Сб. статей.
– Тверь, Изд-во Тверского гос.
ун-та, 1990. – С. 11-17.
- 12
-
Гасанов Э. Э. Об одной математической модели
информационного поиска //
Дискретная математика. – 1991. – Т. 3. Вып. 2. – С. 69-76.
- 13
-
Гасанов Э. Э. Математические модели и сложность информационного
поиска // Proceedings of the graduate workshop in mathematics
and its applications in social sciences. Ljubljana. – 1991. – P. 37-53.
- 14
-
Гасанов Э. Э., Ерохин А. Н. О быстром в среднем решении
n-мерной задачи интервального поиска // Методы и системы
технической диагностики: Тезисы X международной конференции
по проблемам теоретической кибернетики. – Саратов,
Изд-во Саратовского университета, 1993. – С. 48-49.
- 15
-
Гасанов Э. Э. О сложности поиска в базах данных //
Искусственный интеллект: Межвузовский сборник трудов. -
Саратов, Изд-во Саратовского университета, 1993. – С. 41-56.
- 16
-
Гасанов Э. Э. Некоторые задачи поиска, допускающие
мгновенное в среднем решение // Фундаментальная и прикладная
математика. – 1995. – Т. 1. Вып. 1. – С. 123-146.
- 17
-
Гасанов Э. Э. Об одномерной задаче интервального поиска //
Дискретная математика. – 1995. – Т. 7. Вып. 2. – С. 40-60.
- 18
-
Гасанов Э. Э. Мгновенно решаемые задачи поиска //
Дискретная математика. – 1996. – Т. 8. Вып. 3. – С. 119-134.
- 19
-
Дейт К. Введение в системы баз данных. М.: Наука,
1980.
- 20
-
Ершов А.П. Некоторые субъективные замечания к актуальным
проблемам программирования // Перспективы системного
и теоретического программирования: Труды Всесоюзного
симпозиума, Новосибирск, 20-22 марта, 1978 г. -
ВЦ СО АН СССР, Новосибирск, 1979. – С. 113-127.
- 21
-
Информационные системы общего назначения.
М.: Статистика, 1975.
- 22
-
Ким Д. П. Методы поиска и преследования подвижных
объектов. М.: Наука, 1989.
- 23
-
Кнут Д. Искусство программирования для ЭВМ:
Т.3: Сортировка и поиск. М.: Мир, 1978.
- 24
-
Ли Д., Препарата Ф. Вычислительная геометрия. Обзор //
Кибернетический сб. – 1987. Вып. 24. – С. 5-96.
- 25
-
Мартин Дж. Организация баз данных в вычислительных
системах. М.: Мир, 1980.
- 26
-
Наумов А. Н., Вендров А. М., Иванов В. К. и др.
Системы управления базами данных и знаний: Справ. изд.
М.: Финансы и статистика, 1991.
- 27
-
Ньюмен У. М., Спруэлл Р. Ф. Основы интерактивной машинной
графики. М.: Мир, 1976.
- 28
-
Решетников В. Н. Алгебраическая теория информационного поиска //
Программирование. – 1979. – 3. – С. 68-74.
- 29
-
Селтон Г. Автоматическая обработка, хранение
и поиск
информации. М.: Советское радио, 1973.
- 30
-
Системы управления базами данных
для ЕС ЭВМ: Справочник / Под общ. ред. В. М. Савинкова.
М.: Финансы и статистика, 1984.
- 31
-
Солтон Дж. Динамические библиотечно-информационные
системы. М.: Мир, 1979.
- 32
-
Тиори Т., Фрай Дж. Проектирование структур баз данных:
В 2-х кн. М.:
Мир, 1985.
- 33
-
Хеллман О. Введение в теорию оптимального поиска.
М.: Наука, 1985.
- 34
-
Ben-Or M. Lower bounds for algebraic computation trees //
Proc. 15th ACM Annu. Symp. Theory Comput. – Apr. 1983. –
P. 80-86.
- 35
-
Chazelle B. M. Filtering search: a new approach to
query-answering // Proc. 24th IEEE Annu. Symp. Found.
Comput. Sci. – Nov. 1983. – P. 122-132.
- 36
-
CODASYL Systems Committee, Feature Analysis of Generalized
Data Base Management Systems, ASM, New York, 1971b.
- 37
-
CODASYL Systems Committee, Selection and Acquisition Of
Data Base Management Systems, ASM, New York, Mar. 1976.
- 38
-
CODASYL – The Stored-Data Definition and
Translation Task Group, Stored-Data Description and
Data Translation: A Model and Language //
Inf. Syst. – 1977. – V. 2, 3. – P. 95-148.
- 39
-
Codd E. F. A Relation Model of Data for Large
Shared Data Banks // Comm. ACM 13, 6, ACM, New York,
London, Amsterdam, June 1970. P. 377-387.
- 40
-
Codd E. F. Further Normalization of the Data
Base Relational Model //
Courant Computer Sci. Symposia (vol. 6: "Data-Base System"),
ed. by R. Rustin, Prentice-Hall, Inc., Englewood Cliffs,
New Jersey, 1972.
- 41
-
Codd E. F. Relational Completeness of Data
Base Sublanguages //
Courant Computer Sci. Symposia (vol. 6: "Data-Base System"),
ed. by R. Rustin, Prentice-Hall, Inc., Englewood Cliffs,
New Jersey, 1972.
- 42
-
Codd E. F. A Data Base Sublanguage Founded on the Relational
Calculus //
Proc. of the 1971 ACM-SIGFIDET Workshop on Data
Description, Access, and Control, ACM, New York,
London, Amsterdam, 1972.
- 43
-
Codd E. F. Access Control for Relational Data
Base Systems //
BCS Symposium on Relational Data-Base Concepts,
Apr. 1973, British Computer Soc.,
London, 1973.
- 44
-
Codd E. F. Recent Investigations in Relational
Data-Base Systems //
Information Processing'74, North-Holland,
Amsterdam, 1974.
- 45
-
Codd E. F. Relational Database: A Practical Foundation
for Productivity //
Commun. of ACM. -
1982. – V. 25, 2. -
P. 140-155.
- 46
-
Data Language/I-System/370 DOS/VS,
General Information Manual GH20-1246, IBM, White Plains,
New York, 1974.
- 47
-
Date C. J., Codd E. F. The Relational and Network
Approaches: Comparison of the Application Programming
Interfaces //
Proc. of the 1974 ACM-SIGFIDET Workshop,
ACM, New York,
London, Amsterdam, 1974.
- 48
-
Dobkin D. P. A nonlinear lower bound on search tree programs
for solving knapsack problems // J. Comput. Syst. Sci. -
1976. – V. 13. – P. 69-73.
- 49
-
Dobkin D. P., Lipton R. J. A lower bound of ... on linear
search programs for the knapsack problem // J. Comput. Sci. -
1978. – V. 16. – P. 413-417.
- 50
-
Dobkin D. P., Lipton R. J. On the complexsity of computations
under varying sets of primitives // J. Comput. Syst. Sci. -
1979. – V. 18. – P. 86-91.
- 51
-
Edelsbrunner H., Overmars M. H., Siedel R. Some methods of
computational geometry applied to computer graphics //
IIG,
Technische Univ. Graz, Austrua, Tech. Rep. F117. – June 1983.
- 52
-
Gasanov E. E.
On fast solving of interval search problem //
Proceedings of International Congress of Mathematicians.
Zurich, Switzerland, 1994. – P. 137.
- 53
-
Gasanov E. E.
Instantly solvable search problems //
Proceedings of International Symposium on Intelligent
Data Analysis (IDA-95). Baden-Baden, Germany. – IIAS Press, 1995. -
P. 65-69.
- 54
-
Information Management System Virtual Storage (IMS/VS),
General Information Manual GH20-1260, IBM, White Plains,
New York, 1974.
- 55
-
Information Management System/360, Version 2,
Application Programming Reference Manual SH20-0912, IBM, White Plains,
New York, 1974.
- 56
-
Information Management System/360, Version 2,
System
Programming Reference Manual SH20-0911, IBM, White Plains,
New York, 1974.
=400
=5pt
- 57
-
Lee D. T., Wong C. K. Quintari trees: A file structures for
multidimensional database system // ACM Trans. Database Syst. -
Sept. 1980. – V. 1, 1. – P. 339-353.
- 58
-
Steele J. M., Yao A. C. Lower bounds for algebraic decision
trees // J. Algorith. – 1982. – V. 3. – P. 1-8.
- 59
-
Yao A. C., Rivest R. L. On the polyhedral decision problem //
SIAM J. Comput. – 1980. – V. 9. – P. 343-347.
Издательский центр РГГУ, Москва, 1997.
Наверх
|
