Методы организации систем управления данными на основе нумерационных методов и интервальных вычислений тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Белоусов, Алексей Леонидович

• Белоусов, Алексей Леонидович
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Белоусов, Алексей Леонидович

ВВЕДЕНИЕ.

1. СПОСОБЫ ОПТИМИЗАЦИИ ЗАПРОСОВ В СИСТЕМАХ УПРАВЛЕНИЯ

ДАННЫМИ „

1.1. Стадии оптимизации запросов. Логическая оптимизация.

1.1.1. Алгебраическая оптимизация запросов.

1.1.2. Семантическая оптимизация запросов.

1.1.3. Выбор процедурных планов выполнения запроса.

1.2. Физическая организация данных и оптимизация запросов.

1.3. Проблемы оптимизации запросов в архитектуре клиент/сервер.

1.4. Использование параллельных архитектур для повышения эффективности систем управления данными

1.5. Применение систем управления данными при работе с хранилищами данных (DataWaгehouse)

ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ.

2. НУМЕРАЦИИ И ИНТЕРВАЛЬНЫЕ ВЫЧИСЛЕНИЯ В РЕАЛИЗАЦИИ ЗАПРОСОВ.

Вводные замечания.

2.1.Применение доменно-ориентированной методологии в реализации реляционных моделей данных.

2.2. Интервальные вычисления.

2.3. Преобразование логических выражений в интервальные уравнения.

2.4. Нечеткие интервалы и операции над ними.

2.5. Преобразование логических выражений и нечеткие интервалы.

ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ.

3. ОРГАНИЗАЦИЯ НУМЕРАЦИОННЫХ ДОМЕННО-ОРИЕНТИРОВАННЫХ СУБД.

3.1. Организация системы управления данными на основе интервальных вычислений.

3.2. Организация хранения и обработки данных

3.3. Алгоритмы реализации отдельных функций обработки запросов выбора элементов БД.

3.3.1. Лексический и синтаксический анализ.

3.3.2.Преобразование предиката в систему интервальных уравнений.

3.3.3.Решение интервальных уравнений.

3.3.4. Выборка кортежей отношений.

3.4. Применение интервальных вычислений для реализации других запросов языка SQL.

3.5. Анализ эффективности разработанной системы.

ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ.

Введение диссертации (часть автореферата) на тему «Методы организации систем управления данными на основе нумерационных методов и интервальных вычислений»

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

Другая специфическая проблема оптимизации запросов и структур хранения и стратегий доступа относится к системам управления базами данных в оперативной памяти. Такие системы становятся все более актуальными в связи с постоянным увеличением объемов доступной в ЭВМ оперативной памяти и ее удешевлением.

Проблемы, связанные с эффективной обработкой запросов в системах управления данными, рассматриваются в работах отечественных и зарубежных специалистов в области проектирования баз данных (Д. Мейер, К. Дейт, Д. Ульман, С. Кузнецов и др.). Линьковым В.М. рассматривалось применение нумерационных методов для решения задач эффективного хранения и управления данными. Использование монотонных отображений в нумерации дает возможность производить интервальные вычисления над числовыми номерами для эффективной обработки данных.

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

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

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

Задачи исследования. Для достижения поставленной цели решаются следующие задачи:

1.Разработка формальной модели базы данных на основе доменно-ориентированной структуры системы с использованием нумерационных методов.

2.Разработка методов преобразования запроса в интервальные уравнения.

3.Исследование возможностей применения нечетких интервалов для оптимизации процесса обработки запроса о

4.Разработка эффективных методов решения интервальных уравнений.

5.Разработка архитектуры системы управления данными на основе интервальных вычислений и методов проектирования СУБД.

6.Разработка алгоритмов реализации функций обработки запросов к системе управления данными.

Научная новизна.

1.Обосновано применение нумерационных методов для повышения эффективности обработки запросов в системах управления данными.

2.Разработана внутренняя модель данных и архитектура СУБД на основе нумерационных методов с использованием домен-но-ориентированного подхода к организации хранения и обработки данных, что позволило применить интервальные вычисления в реализации эффективных методов доступа к данным.

3.Предложены методы преобразования запросов в интервальные уравнения^ позволяющие эффективно решать задачу оптимизации запросов.

4. Для повышения эффективности в использовании ресурсов ЭВМ при обработке запросов предложены методы, основанные на работе с нечеткими интервалами.

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

Основные результаты и положения, выносимые на защиту:

1.Внутренняя модель данных в виде совокупности бинарных отношений.

2.Метод преобразования реляционной модели во внутреннюю модель данных.

3.Методы преобразования запросов, представленных в виде предиката, в систему интервальных уравнений.

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

5.Метод применения показателя нечеткости для оптимизации использования имеющихся ресурсов.

6.Архитектура системы управления данными и алгоритмы поиска ответа на запрос, позволяющие эффективно использовать предложенную модель данных.

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

- определены основные требования, предъявляемые к базам данных на основе использования нумерационных методов и доменно-ориентированного подхода;.

- разработаны принципы построения системы управления данными на основе применения нумерационных методов, которые нашли свое применение в ряде информационных систем.

Апробация работы. Основные результаты работы докладывались :

-на международной выставке-конференции "Новые компьютерные технологии в учебном процессе и научных исследованиях" (г. Москва, 1995г.);

-на II международной конференции "Новые информационные технологии и системы" (г. Пенза, 1996);

-на Международной методической конференции "Университетское образование в условиях формирования рыночных отношений (г. Пенза, 1997г.);

-на научно-практическом семинаре "Применение баз данных" (г. Пенза, 1997);

-на всероссийской научно-технической конференции "Непрерывная и смежные логики в информатике, экономике и социологии" (Пенза, 1997).

Реализация работы» Основные результаты, изложенные в диссертационной работе, использованы в НИР, проводимой в рамках гранта «Доменно-ориентированная нумерационная система управления базами данных» программы «Конверсия и высокие технологии. 1997-2000 гг.». Кроме того, результаты работы использованы в НИР, выполненных для КПФ "Пензснаб" (г. Пенза) и РКК "Энергия" (г. Москва) и внедрены:

-в автоматизированную информационную систему "Пензснаб", что подтверждено соответствующим актом;

-в автоматизированную обучающую систему для кафедры спортивных игр ПГПУ, что подтверждается соответствующим актом.

Публикации. Основные результаты диссертации опубликованы в 13 печатных работах.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 83 наименований и двух приложений. Работа содержит 142 страницы текста, 7 рисунков, 25 таблиц, 7 страниц библиографии, 8 страниц приложений.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Белоусов, Алексей Леонидович

Основные результаты диссертационной работы получили отражение в 13 печатных работах автора [6-7,73-83], а также докладывались на конференциях и семинарах.

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ

БД - база данных

ВЗУ - внешнее запоминающее устройство ВСН - внутрисистемный номер ВП - внешняя память

ОЗУ - оперативное запоминающее устройство ОП - оперативная память

СУБД - система управления базами данных

ЗАКЛЮЧЕНИЕ

Диссертационная работа посвящена вопросам применения нумерационных методов в реализации запросов к системе управления данными.

Список литературы диссертационного исследования кандидат технических наук Белоусов, Алексей Леонидович, 1999 год

1. Мейер Д. Теория реляционных баз данных. М. : Мир, 1987.- 608 с.

2. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД// Программирование, 1989. N6. - С. 46-59.3= Змитрович А.И., До Суан Тхо Оптимизация квазиконъюнктивных запросов// Программирование, 1990. N4. - С. 63-67.

3. Кузнецов С.Д. Стандарты языка реляционных баз данных SQL: Краткий обзор// СУБД, 1996. N2. - С. 6-36.

4. Линьков В.М. Нумерационные методы в проектировании систем управления данными: Монография. Пенза: Изд-во Пенз. гос. техн. ун-та, 1994. - 156 с.

5. Белоусов А.Л. Применение интервальных вычислений для реализации запросов языка SQL // Новые информационные технологии и системы: Материалы II международной конференции. Пенза: ПГТУ, 1996. Ч.1.- С. 39-40.

6. Чери С., Готтлоб Г., Танка Л. Дейталог: исчерпывающий обзор. Часть 2// Программирование, 1991. N5. - С. 9-31.

7. Х.-А. Фернандес, Дж. Минкер. Теория и алгоритмы дизъюнктивных дедуктивных баз данных// Программирование, 1993. -N3. С. 33-46.

8. Задорожный В.И., Никитченко Н.С. Алгебраический подход к формализации дедуктивных языков запросов// Программирование, 1992. -N6. С. 29-47.

9. Задорожный В.И. Расширение дедуктивных языков запросов конструкциями с ограниченным квантором всеобщности// Программирование, 1995. N2. - С. 9-20.

10. Цикритзис Д., Лоховски Ф., Модели данных. М. : Финансы и статистика, 1985г. - 342 с.

11. Системы управления базами данных и знаний/ Под ред. Наумова A.B. М.: Финансы и статистика, 1991. - 348 с.

12. Иванов Ю.Н., Кочин Ю.Я. Представление и реализация запросов в системах баз данных// Автоматика и телемеханика, 1996. N2. - С. 178-186.

13. Кузнецов С.Д. Выработка оптимальных планов выполнения запросов в реляционных СУБД// Программирование, 1990. N2. -С. 28-43.

14. Батлер Б. Персональные SQL СУБД: все ближе к пользователю// PC Magazine/ Russian Edition, 1996. N5. - С. 158171.

15. Плейн С. У. Три СУБД фирмы Borland// PC Magazine/ Russian Edition, 1995. N1. - С. 15-18.

16. Яковлев E. Paradox 5.0 for Windows// КомпьютерПресс, 1994. -Nil. C. 142-144.

17. Федоров A. Borland dBase for Windows// КомпьтерПресс, 1994. N8. - С. 37-39.

18. Риккарди С. СУБД как средства работы с запросами// PC Magazine/ Russian Edition, 1996. N1. - С. 198-206.

19. Сапков A. Microsoft Access для Windows 95// Компьютерра, 1996. N11(138). - С. 42-43.

20. Звозин A. Paradox это силища!// Компьютерра, 1996. - N11(138). - С. 44-45.

21. Злуф М.М. Query-by-Example: язык баз данных// СУБД, 1996. N3. - С. 149-160.

22. Кузнецов С. Д. Об основаниях ненавигационного языка запросов к объектно-ориентированным базам данных// Программирование, 1995. N2. - С. 21-30.

23. Смирнов А., Беляков А., Бронников Г., Филимонов Ю. , Чаянов Н. Зачем нужны объектно-ориентированные СУБД// Компьютер-пресс, 1995. -N9. С. 4 6-50.

24. Боровицкий М.Д., Смирнов С.В. Реализация и исследование производительности объектно-ориентированной СУБД// Программирование, 1992. N6. - С. 18-28.

25. Дейт К. Введение в системы баз данных. М. : Наука, 1980. - 463 с.

26. Ульман Д. Основы систем баз данных. М. : Финансы и статистика, 1983. - 335 с.

27. Рубинов A.M. В*-деревья против индексно-последовательной организации// Программирование, 1988. N6.- С. 71-74.

28. Попов A.A. Программирование в среде СУБД FoxPro 2.0. Построение систем обработки данных.- М.: Радио и связь,1994.- 352 е., ил.

29. Атре Ш. Структурный подход к организации баз данных.- М.: Финансы и статистика, 1983.

30. Каленов Н.Е., Нестеренко А.И. Оптимальное сегментирование данных переменной длины в СУБД// Программирование, 1989. N4. - С. 66-71.

31. Эмпулашвили Б.Г. Оптимизация процессов выборки в инвертированных файлах// Программирование, 1987. N6. - С. 6468 .

32. Тильчин О.Т., Шор O.JI. Организация эффективного хранения и поиска данных на основе анализа частотных свойств потока запросов// Программирование, 1985. N6. - С.64-68.

33. Кузнецов С.Д. Введение в СУБД, Ч. 6// СУБД, 1996. -N2 . С.130-140.

34. Кузнецов С.Д. Введение в СУБД, Ч. 5// СУБД, 1996. -N1. С. 124-143.

35. Borland анаонсирует InterBase 4.2.// Компьютеруик, 1996. N32. - С. 8.

36. Индриков В. Borland InterBase 4.0 //КомпьютерПресс,1995. N3. - С. 32-34.

37. Львов М. InterBase и создание клиент-серверных приложений// Компьютер-пресс, 1996. N3. - С. 35-41.

38. Брюзгин A. SQLBase6// СУБД, 1996. N1. - С. 68-78.

39. Тандоев А.Ю. Архитектура Sybase System 11// СУБД,1996. N2. - С. 77-92.

40. Новиков Б.А. Индексирование во временных базах данных// Программирование, 1995. N2. - С. 31-36.

41. Когаловский М.Р. Статистические базы данных// Программирование, 1995. N2. - С. 37-47.

42. Сахаров А.А. Принципы проектирования и использования многомерных баз данных (на примере Oracle Express Server)// СУБД, 1996. -N3. С. 44-59.

43. Ким Е.К., Шабаев И.Г., Бычков В.А. Проектирование трехмерных баз данных в СУБД universe// СУБД, 1996. N3. -С. 66-76.

44. Кодд Е.Ф. Реляционная модель данных для больших совместно используемых банков данных// СУБД, 1995. N1.

45. Замулин А. Перспективы развития систем баз данных третьего поколения// Программирование, 1992. N2.

46. Кербель В.Г. Параллельный поиск в распределенных базах данных// Программирование, 1985. N1. - С. 63-73.

47. Ладыженский Г.М. Системы управления базами данных -коротко о главном// СУБД, 1995.- N3. С. 128-136.

48. Виноградов Б. Проектирование эффективных сетей. (Структура и характеристики корпоративной сети в архитектуре клиент-сервер)// CompUnity, 1995. N2. - С. 94-98.

49. Петров Ю.К. JAM-инструментальное средство разработки приложений в информационных системах архитекутры "клиент-сервер", построенных на базе РСУБД// СУБД, 1995. N3. - С. 59-65.

50. Вьюркова Н. Современные продукты компании Informix// Компьютерра, 1995. N117-118. - С. 38-43.

51. Сахаров А. СУБД и программные продукты фирмы Oracle// Компьютерра, 1995. N117-118. - С. 34-37.

52. Брюзгин А. Интеграция SQLWindows 5.0 с Oracle 7// Компьютерра, 1995. N42(122). - С. 28-31 .

53. Водолазский В. Delphi Client/Server народный компилятор для построения сложных систем// Компьютерра, 1996. N4-5 (131-132) . - С. 42-47

54. Херш Дж., Херш К. Работа с ORACLE v.6.0. -M., 1993.

55. Холмс-Кинселла Д., Брюзгин А. Разработка приложений для СУБД Oracle с помощью SQLWindows фирмы Gupta// СУБД 1996. N2. - С. 107-114.

56. Батлер Б., Мэйс T., SQL СУБД: большой скачок// PC MAGAZINE/ RUSSIAN EDITION, 1995. N1. - С. 20-48.

57. Katherine Bull Истинные и мнимые достоинства СУБД с параллельной обработкой данных// ComputerWeek-Moscow, 1996. -N12. С. 27-29.

58. Орлов С. Реляционные СУБД и параллельные вычисления// ComputerWeek-Moscow, 1996. N14. - С. 23-25, 42.

59. Рыбкин В.М, Комаров П.И., Назаров А. С. Формализация алгоритмов функционирования процессов реляционных баз данных// Программирование, 1985. N1. - С. 70-78.

60. Вьюркова Н.И. Продукты Informix и распределенные вычисления// СУБД, 1995. N4. - С. 18-29.

61. Пресняков M. Oracle Workgroup/2000: Oracle укореняется на PC// Компьютерра, 1995. N32(112). - С. 34-35.

62. Ташек Дж. Oracle накапливает мощность// PC WEEK, 1996. N32-33. - С. 9.

63. Ладыженский Г.М. Tuxedo System: разработка систем клиент-сервер. 4.2.// СУБД, 1996. N2. - С. 94-106.

64. Сахаров A. ORACLE Data Warehouse информационные системы нового поколения// Компьютерра, 1995. - N40(120). -С. 16-20.

65. Горчинская О.Ю. DESIGNER/2000 новое поколение CASE-продуктов фирмы ORACLE// СУБД, 1995. - N3. - С. 9-25

66. Грачев A. Informix решения для Data Warehouse// Компьютерра, 1995. - N40(120). - С. 21-23

67. Повышение производительности хранилищ данных// Комрь-ютеруик, 1996. N32. - С. 28-29, 44.

68. Тейз А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту: от классической логики к логическому программированию/ Пер. с франц. М. : Мир, 1990. - 432 с. , ил.

69. Скорняков JI.A. Элементы общей алгебры. М.: Наука, 1983. - 272 с.

70. Алефельд Г.А., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987. - 353 с.

71. Белоусов A.JI., Линьков В.М. Применение электронных таблиц при решении статистических задач// Новые компьютерные технологии в учебном процессе и научных исследованиях: Материалы международной выставки-конференции. М. : МАДИ, 1995.-С. 9.

72. Белоусов А. Л., Линьков В.М. Применение электронных таблиц при преподавании математических дисциплин// Информационные технологии в образовании: Материалы IV международной конференции-выставки. М.: АО КУДИЦ, 1995.- С. 26-27.

73. V.M.Linkov, V.N.Nedoshivin, V.V.Drozhdin, Е.V.Ogurechnikov, A. L.Belousov, D.V.Majorov. The Intellectual System of Automated Design of Schemes of Measuring Systems (SAPR SI)// INFORMATION TECHNOLOGY IN DESIGN: PROCEEDINGS of

74. EAST-WEST International Conference. Moscow, Russia, 1996. - p. 66-68.

75. Линьков В.М., Дрождин В.В., Майоров Д.В., Белоусов

76. Белоусов А.Л., Мокшанина М.А. Использование компьютера в курсе высшей математики //Математика и информатика: Межвузовский сборник. Пенза: ПГПУ им. В.Г. Белинского, 1996. -С.113-116.

77. Белоусов А.Л., Долгарев А.И., Линьков В.М., Са-муйлова C.B. Решение статистических задач с использованием электронных таблиц: Учебное пособие/ ПГПУ им.

78. B.Г.Белинского.- Пенза, 1996.- 44с.

79. Белоусов А.Л., Дружаев A.A., Иванцов М.А. Применение временных баз данных при многоэтапном проектировании сложных систем//СучаCHi проблеми математики: Матер1али м!жнародно! HayKOBoi конференцЦ. Черн1вцл: Рута, 1998. - Частина 4.1. C.9-11.