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

• Борисенков, Дмитрий Васильевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Борисенков, Дмитрий Васильевич

Введение.

Глава 1. Современное состояние задачи поддержки представлений распределенных объектов в РСУБД.

1.1 Различные классы информационных систем и их интеграция.

1.2 Обзор стандартов представления геоданных и манипулирования ими в РСУБД.

1.3 Поддержка распределенных объектов в современных РСУБД.

1.4 Цель и задачи исследования.

Глава 2. Математическая модель представления распределенных объектов.

2.1 Векторное представление распределенных объектов.

2.2 Политомическое представление распределенных объектов.

Глава 3. Манипулирование представлениями распределенных объектов.

3.1 Алгоритмы операций над полигонами.

3.2 Алгоритмы операций над политомическими представлениями распределенных объектов.

Глава 4. Разработка подсистемы поддержки геоданных в РСУБД.

4.1 Общая структура и отдельные компоненты РСУБД.

4.2 Базовая часть подсистемы поддержки геоданных.

4.3 Поддержка политомического представления геоданных.

Основные результаты работы.

Введение диссертации (часть автореферата) на тему «Специальное математическое и программное обеспечение манипулирования распределенными объектами в реляционной СУБД на основе политомических представлений»

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

Универсальным средством для хранения структурированной информации являются базы данных (БД), работающие под управлением систем управления базами данных (СУБД). Из них наибольшее распространение получили реляционные СУБД (РСУБД), которые обладают мощным декларативным языком описания запросов для поиска информации (SQL) и способны выполнять запросы, не предусмотренные изначально при создании структуры базы данных.

РСУБД традиционно ориентированы на работу с элементами числовых, символьных и временных типов данных, имеющими простую внутреннюю структуру и занимающими небольшой объем памяти, и позволяют эффективно выполнять над этими данными поисковые и вычислительные операции [43]. Информационные системы некоторых других классов, например, географические информационные системы (ГИС) и системы автоматизированного проектирования (САПР), напротив, специализируются на представлении и обработке распределенных пространственных объектов, обычно имеющих достаточно сложную иерархическую структуру и занимающих большой объем памяти. Однако эти информационные системы не имеют такого арсенала средств эффективного хранения больших объемов данных, оптимизации выполнения поисковых запросов и обеспечения многопользовательской работы, как РСУБД [71].

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

Существующие международные стандарты [86,94] содержат требования к СУБД в отношении поддержки работы с пространственной информацией, удовлетворение которых необходимо для обеспечения совместимости СУБД с другими информационными системами. В то же время стандарты не касаются таких важных вопросов, как подготовка пространственных данных для хранения их в реляционной БД, эффективность хранения и извлечения этих данных с точки зрения занимаемого объема памяти и скорости обработки, индексация пространственных данных для обеспечения быстродействия поисковых операций, разграничение доступа к пространственной информации. Необходимо решение этих вопросов - как теоретическое, с учетом результатов анализа существующих подходов и выработкой собственных методов, так и практическое, заключающее в воплощении этих методов в конкретной разрабатываемой СУБД. В связи с хранением в базах данных стратегически важной информации и возникающими при этом вопросами информационной безопасности, ключевым моментом является использование СУБД, основанной на оригинальных отечественных разработках [63,66]. Этим и определяется актуальность темы исследования.

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

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

Для достижения цели исследования необходимо решить следующие задачи:

1. Проведение сравнительного анализа существующих методов создания представлений распределенных объектов и манипулирования ими в реляционных СУБД.

2. Создание математической модели представления распределенных объектов в реляционной СУБД.

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

4. Разработка способов представления структур БД и формирования компонентов реляционной СУБД, необходимых для поддержки хранения и обработки предложенных представлений распределенных объектов.

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

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

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

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

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

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

4. Структура подсистемы реляционной СУБД, предназначенной для хранения представлений распределенных объектов и манипулирования ими, отличающаяся учетом архитектурных особенностей СУБД "Линтер".

5. Языковые средства манипулирования представлениями распределенных объектов, интегрированные в компилятор языка SQL реляционной СУБД и отличающиеся поддержкой политомических представлений объектов.

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

Реализация и результаты внедрения. Основные теоретические и практические результаты работы внедрены и используются в HI 111 "РЕЛЭКС" при разработке программных средств, входящих в состав реляционной СУБД "ЛИНТЕР", а также используются в НЛП "РЕЛЭКС" в процессе обучения сотрудников предприятия с целью повышения уровня их компетенции в области взаимодействия РСУБД с информационными системами других классов.

Апробация работы. Результаты диссертационной работы докладывались на следующих конференциях и семинарах: Международной научно-практической конференции "Опыт и проблемы природопользования при реализации президентских программ в Черноземье" (Воронеж, 2005), Международном симпозиуме "Надежность и качество" (Пенза, 2006).

Публикации. По материалам диссертации опубликовано 12 научных работ, в том числе 1 в издании, рекомендованном ВАК РФ; получено 2 свидетельства о регистрации программ. В работах, опубликованных в соавторстве, лично соискателем предложены: [11] - описание общих принципов построения компилятора языка SQL; [14, 15] - обзор существующих стандартов поддержки ГИС в СУБД и методов их реализации; [16,17] - разработка нотации описания представлений распределенных объектов и способов манипулирования ими; [18,19] - описание аспектов использования СУБД в процессе реализации разработанных методов; [58,59,63] - описание реализации подсистемы геоданных в РСУБД Линтер; [10,50] - разработка и реализация компилятора языка SQL и алгоритмов обработки запросов в ядре СУБД.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 127 страницах, списка литературы из 101 наименования и приложений на 9 страницах, содержит 19 рисунков и 14 таблиц.

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

Основные результаты диссертационной работы:

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

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

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

4. Структура подсистемы СУБД, предназначенной для хранения представлений распределенных объектов и манипулирования ими, отличающаяся учетом архитектурных особенностей СУБД "ЛИНТЕР", что позволяет использовать эту подсистему в составе указанной СУБД для решения задач интеграции информационных технологий.

5. Языковые средства манипулирования представлениями распределенных объектов, отличающиеся поддержкой политомических представлений объектов, интегрированы в компилятор языка SQL реляционной СУБД, что обеспечивает их поддержку со стороны РСУБД.

128

6. Основные теоретические и практические результаты исследования использованы в НПП "РЕЛЭКС" в проекте СУБД "ЛИНТЕР" при составлении технического задания на разработку подсистемы обработки геоданных для СУБД "ЛИНТЕР", проектировании и реализации данной подсистемы. Участие автора в разработке как СУБД "ЛИНТЕР" в целом, так и библиотеки управления геоданными для нее подтверждено свидетельствами об официальной регистрации программ для ЭВМ.

Список литературы диссертационного исследования кандидат технических наук Борисенков, Дмитрий Васильевич, 2007 год

1.Андерсон Дж. Дискретная математика и комбинаторика. - М.: Издательский дом "Вильяме", 2006. - 960 с.

2. Андрианов В.Ю. Англо-русский толковый словарь по геоинформатике. М.: ДАТА+, 2001. - 122 с.

3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1 — Синтаксический анализ. М.: Мир, 1978. - 612 с.

4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.2 Компиляция. - М.: Мир, 1978. - 486 с.

5. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструменты. / Пер. с англ. М.: Издательский дом "Вильяме", 2001. - 768 с.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. / Пер. с англ.: Учебное пособие. М.: Издательский дом "Вильяме", 2000. -384 с.

7. Бартунов О., Сигаев Ф. Новые и важные изменения в СУБД PostgreSQL. Тезисы доклада конференции "Корпоративные базы данных". -М:, 2006.

8. Бен-Ари М. Языки программирования. Практический сравнительный анализ. / Пер. с англ. М.: Мир, 2000. - 366 с.

9. Берлянт A.M. Геоинформационное картографирование. М.: Астрея, 1997.-64 с.

10. П.Бойченко И.А., Борисенков Д.В., Пешков А.В. О некоторых особенностях реализации трансляторов языка запросов SQL // Информатика. Образование. Экология : материалы V Междунар. конф. Астрахань, 2000. - С. 152158.

11. Борисенков Д.В. Язык запросов SQL. Особенности реализации в СУБД "Линтер" // Математика, образование, экология, тендерные проблемы : труды Междунар. конф. Воронеж, 2000. - С. 44-46.

12. Борисенков Д.В. Способы декомпозиции операций над полигонами для подсистемы работы с геоданными в реляционной СУБД // Системы управления и информационные технологии : науч.-техн. журнал. 2007. №2.2(28). С. 229-233.

13. Борисенков Д.В., Харин В.Н. Логическое представление распределенных пространственных объектов ГИС // Современные проблемы механики и прикладной математики : сб. тр. междунар. школы-семинара. Воронеж: ВГУ, 2005.-4.1. С. 65-68.

14. Борисенков Д.В., Харин В.Н. Краткий обзор стандартов поддержки ГИС в реляционных СУБД и вариантов их реализации. // Технология клиент-сервер. 2005. №3. С. 40-45.

15. Борисенков Д.В., Харин В.Н. Язык описания представлений распределенных геометрических объектов и манипулирования ими в реляционной СУБД // Надежность и качество : тр. междунар. симпозиума. Пенза: Изд-во Пенз. гос. ун-та, 2006. - Т.1. С. 164-168.

16. Борисенков Д.В., Харин В.Н. Представление картографической информации в реляционной СУБД // Информационные технологии моделирования и управления : науч.-техн. журнал. 2006. №8(33). С. 1021-1027.

17. Борисенков Д.В., Харин В.Н. Алгоритм преобразования картографической информации в политомическое представление // Информационные технологии моделирования и управления : науч.-техн. журнал. 2006. №9(34). -С. 1137-1141.

18. Боуман Дж., Эмерсон С., Дарновски М. Практическое руководство по SQL. М.: Издательский дом "Вильяме", 2001. 336с.

19. Бубнов И.А., Кремп А.И., Калинин А.К., Шленников С.А. Военная топография. Учебник для военных училищ Советской армии. Издание второе, исправленное. Воениздат. М., 1969. - 352 с.

20. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд. / Пер. с англ. М.: Бином, 1998.

21. Вахрамеева JI.A., Бугаевский JI.M., Казакова З.Л. Математическая картография: Учебник. М.: Недра,1986. 285 с.

22. Вирт Н. Алгоритмы и структуры данных. / Пер. с англ. М.: Мир, 1989.-360 с.

23. Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс / Пер. с англ. М. : Издательский дом "Вильяме", 2004. -1088 с.

24. Геоинформатика. Толковый словарь основных терминов. Под ред. А.М.Берлянта и А.В.Кошкарева. М.: ГИС-Ассоциация, 1999. - 204 с.

25. ГОСТ Р 52438-2005. Национальный стандарт Российской Федерации. Географические информационные системы. Термины и определения. М., 2005.

26. Грабер М. Справочное руководство по SQL. / Пер. с англ. М.: Лори, 1998.-291 с.

27. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998.

28. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. / Пер с. англ. М.: Мир, 1981. - 366 с.

29. Дал У., Дейкстра Э., Хоор К. Структурное программирование. / Пер. с англ. М.: Мир, 1975.

30. Дейт К.Дж. Введение в системы баз данных. 8-е изд. М.: Вильяме, 2006. - 1328 с.

31. ДеМерс М. Географические информационные системы. Основы / Пер. с англ. М.: Дата+, 1999. - 491 с.

32. Дюбуа П. MySQL. / Пер. с англ. М., Издательский дом "Вильяме", 2004. - 1088 с.35.3икопулос П., Бакларц Дж., де Рус Д., Мельник P. DB2 версии 8: официальное руководство. / Пер. с англ. М.: КУДИЦ-Образ, 2004. - 380 с.

33. Кайт Т. Oracle для профессионалов. Архитектура, методики программирования и основные особенности версий 9i и 10g. / Пер. с англ. М.: Издательский дом "Вильяме", 2007. - 848 с.

34. Канер С. и др. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений. / Пер. с англ. Киев: ДиаСофт, 2001. - 544 с.

35. Керниган Б.В., Пайк P. UNIX универсальная среда программирования. - М.: Финансы и статистика, 1992.

36. Керниган Б.В., Ритчи Д.М. Язык программирования С. М.: Финансы и статистика, 1992.

37. Кимельман M.JI. Исследование и разработка языковой подсистемы SQL сервера. Диссертация. М., 1996.

38. Кнут Д.Э. Искусство программирования. Т. 1. Основные алгоритмы. 3-е издание. М.: Издательский дом "Вильяме", 2005. - 720 с.

39. Кнут Д.Э. Искусство программирования. Т. 3. Сортировка и поиск. 3-е издание. М.: Издательский дом "Вильяме", 2005. - 400 с.

40. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. - 800 с.

41. Кодд Э.Ф. Реляционная модель для больших совместно используемых банков данных. Журнал "СУБД", №1, 1995, с. 145-160.

42. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ. / Пер. с англ. М.: МЦНМО, 2001.

43. Кузнецов С.Д. Основы баз данных. Курс лекций. Учебное пособие. -М.: Интернет-университет информационных технологий, 2005. 488 с.

44. Леонов М.В., Никитин А.Г. Эффективный алгоритм, реализующий замкнутый набор булевых операций над множествами многоугольников на плоскости / Препринт Института систем информатики СО РАН № 46. 1997. -20 с.

45. Майерс Г. Искусство тестирования программ. / Пер. с англ. М.: Финансы и статистика, 1982. - 176 с.

46. Мартин Дж. Организация баз данных в вычислительных системах. -М., Мир, 1980.

47. Мобильная реляционная СУБД Линтер. Версия 6.1. Архитектура СУБД. Воронеж, НПП Релэкс, 2007.

48. Мобильная реляционная СУБД Линтер. Версия 6.1. Геометрические типы данных. Воронеж, НПП Релэкс, 2007.

49. Мобильная реляционная СУБД Линтер. Версия 6.1. Системные таблицы. Воронеж, НПП Релэкс, 2007.

50. Мобильная реляционная СУБД Линтер. Версия 6.1. Справочник по SQL. Воронеж, НПП Релэкс, 2007.

51. Нейл М., Стоунз P. PostgreSQL. Основы. / Пер. с англ. М., Символ-плюс, 2003. - 400 с.

52. Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. - 336 с.

53. Орлов С.А. Технологии разработки программного обеспечения. Учебное пособие. 2-е изд. СПб., Питер, 2003. - 480 с.

54. Пратт Т. Языки программирования. Разработка и реализация. 4-е издание. / Пер. с англ. СПб.: Питер, 2002. - 686 с.

55. Рихтер Дж. Windows для профессионалов. СПб.: Питер, 2000. 752 с.

56. Селко Дж. SQL для профессионалов: программирование. / Пер. с англ. М., Лори, 2004. - 456 с.

57. Харин В.Н., Бойченко И.А., Сарайкин В.Г. Проектирование компонентов защиты данных в реляционной СУБД на основе CASE-технологий: Монография. М.:МГУЛ, 2002. - 137 с.

58. Холл М. Комбинаторика. М.: Мир, 1970.

59. Хьюз Дж., Мичтом Дж. Структурный подход к программированию. / Пер с англ. М.: Мир, 1980.

60. Цикритзис Д., Лоховски Ф. Модели данных. / Пер. с англ. М. Финансы и статистика, 1985. - 344 с.

61. Ченцов О.В., Скворцов А.В. Обзор алгоритмов построения оверлеев многоугольников. // Вычислительные методы и программирование. 2002. Т. З.-С. 116-123.

62. Шекхар Ш., Чаула С. Основы пространственных баз данных. / Пер. с англ. М.: КУДИЦ-Образ, 2004. - 336 с.

63. Шилдт Г. Полный справочник по С. М.: Издательский дом "Вильяме", 2007. - 699 с.

64. Эмблер С., Садаладж П. Рефакторинг баз данных: эволюционное проектирование. / Пер. с англ. М.: «Вильяме», 2007. - 368 с.

65. Adler D.W. IBM DB2 Spatial Extender Spatial Data within the RDBMS. Proceedings of the 27th VLDB Conference, Roma, Italy, 2001.

66. Bentley J.L., Friedman J.H. Data structures for range searching. Computing Surveys, 13:3 (1979), p. 397-409.

67. Environmental Systems Research Institute, Inc. ESRI Shapefile Technical Description, 1997.

68. Egenhofer M.J., Clementini E., Di Felice P. Topological relations between regions with holes, International Journal of Geographical Information Systems, 1994, #8(2), p. 129-142.

69. Egenhofer, M.J., Franzosa, R. Point-set topological spatial relations. International Journal of Geographical Information Systems. 1991, #5, p. 161-174.

70. Egenhofer M.J., Glasgow J., Gunther O., Herring J.R., Peuquet D.A. Progress in Computational Methods for Representing Geographical Concepts. International Journal of Geographical Information Science. 1999, #13(8), p. 775-796.

71. Egenhofer M.J., Herring, J. A Mathematical Framework for the Definition of Topological Relationships. Proceedings of the Fourth International Symposium on Spatial Data Handling. Zurich, Switzerland, 1990, p. 803-813.

72. Gaede V., Gunther O. Multidimensional access methods. Computing Surveys, 30:2 (1998), p. 170-231.

73. Gruber M. SQL Instant Reference. SYBEX, 1993. 352 p.

74. International Business Machines, Corp. DB2 Spatial Extender. User's

75. Guide and Reference, Version 8.1, 2002.

76. International Business Machines Corp., Armonk, NY, USA. IBM DB2 Spatial Extender and Geodetic Extender User's Guide and Reference, Version 8.2, 2004.

77. ISO/IEC 13249-3:2003. Information Technology Database Languages -SQL Multimedia and Application Packages - Part 3: Spatial, 2nd edition, 2003.

78. ISO/IEC 13249-3:2006. Information Technology Database Languages -SQL Multimedia and Application Packages - Part 3: Spatial, 3rd edition, 2006.

79. ISO/TC 211/WG 4/PT 19136 DIS. Geographic Information Geography Markup Language (GML), 1st edition, 2005.

80. Johnson S.C. Yacc yet another compiler compiler, Computing Science Technical Report 39, AT&T Bell Laboratories, Murray Hill, N.J., 1975.

81. Lesk M.E. Lex a lexical analyzer generator, Computing Science Technical Report 39, AT&T Bell Laboratories, Murray Hill, N.J., 1975.

82. MySQL AB, Uppsala, Sweden. MySQL 5.0 Reference Manual, 2005.

83. Open Geospatial Consortium. OpenGIS Geography Markup Language (GML) Encoding Specification Implementation Specification, Revision 3.1.1, 2004.92.0pen Geospatial Consortium. OpenGIS Simple Features Specification for SQL, Revision 1.1, 1999.

84. Open Geospatial Consortium. OpenGIS Implementation Specification for Geographic Information Simple feature access - Part 1: Common architecture. Version 1.2, 2006.

85. The PostgreSQL Global Development Group. PostgreSQL 8.1.0 Documentation, 2005.

86. Stolze K. Integration of Spatial Vector Data in Enterprise Relational Database Environments. Dissertation. Germany, Jena, 2006.

87. Szalay, A., Kunszt, P., Thakar, A., Gray, J., Slutz, D., and Brunner, R. (2000). Designing and Mining Multi-terabyte Astronomy Archives: The Sloan Digital Sky Survey. In Proceedings of SIGMOD'OO, Dallas TX (pp. 451-462).

88. Worboys, M. GIS: A computing perspective. Taylor and Francis, 1995.

89. Zaniolo C., Ceri C., Faloutsos C., Snodgrass R., Subrahmanian V., Zicari R. Advanced Database Systems, Morgan-Kaufmann, San Francisco, 1997.