English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу

Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.

Функционально-сетевые базы данных и сверхбыстрые алгоритмы поиска

Гасанов Э.Э.
Учебное пособие

Скачать пособие полностью в формате 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.

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru