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

На правах рукописи

БОРИСЕНКОВ Дмитрии Васильевич

/ у

СПЕЦИАЛЬНОЕ МАТЕМАТИ^СКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ МАНИПУЛИРОВАНИЯ РАСПРЕДЕЛЕННЫМИ ОБЪЕКТАМИ В РЕЛЯЦИОННОЙ СУБД НА ОСНОВЕ ПОЛИТОМИЧЕСКИХ ПРЕДСТАВЛЕНИЙ

Специальность 05 И 1 I - Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

ООЗ 1Б623Т

Воронеж - 2007

003166237

Работа выполнена в Воронежской государственной лесотехнической академии

Научный руководитель

доктор технических наук, профессор Харин Валерий Николаевич

Официальные оппоненты

доктор технических наук, профессор Барабанов Владимир Федорович, Воронежский государственный технический университет,

кандидат технических наук Неприков Антон Алексеевич ЗАО НПП "РЕЛЭКС'

Ведущая организация

Воронежский государственный университет

Защита состоится 20 декабря 2007 г в 10°" часов в конференц-зале на заседании диссертационного совета Д 212 037 01 Воронежского государственного технического университета по адресу 394026, г Воронеж, Московский просп, 14

С диссертацией можно ознакомиться в научной библиотеке Воронежского государственного технического университета

¿Я

Автореферат разослан ноября 2007 г

Ученый секретарь ^-> * л .»^¿¿^

диссертационного совета "<*' Питолин В М

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

(

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

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

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

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

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

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

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

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

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

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

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

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

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

парата таблиц и индексов РСУБД и элементов иерархической организации данных

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

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

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

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

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

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

Публикации. По материалам диссертации опубликовано 12 научных работ, в том числе 1 в издании, рекомендованном ВАК РФ, получено 2 свидетельства о регистрации программ В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателем предложены [2] - описание общих принципов построения компилятора языка SQL, [4,5] - обзор существующих стандартов поддержки ГИС в СУБД и методов их реализации, [7,8] - разработка нотации описания представлений распределенных объектов и способов манипулирования ими, [9,10] - описание аспектов использования СУБД в процессе реализации разработанных методов, [6,11,12] - описание реализации подсистемы геоданных в РСУБД Линтер, [И,14] - разработка и реализация компилятора языка SQL и алгоритмов обработки запросов в ядре СУБД

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Для представления пространственных данных в реляционных СУБД используются геометрические объекты, являющиеся экземплярами типов, входящих в иерархию типов геометрических объектов За основу классификации объектов берется их размерность (пустое множество не имеет размерности, точка имеет размерность О, линия - I, фигура - 2, составной объект - максимальную из размерностей компонентов) Возможно также представление 2,5D-объектов с ограниченной функциональностью третьей координаты (высоты) Все геометрические объекты являются топологически замкнутыми Каждый объект задается множеством базовых точек, объект размерности 0 является множеством этих точек, одномерный - линией, соединяющей точки по определенным правилам, двумерный - фигурой, ограниченной такой линией Базовые точки соединяются отрезками прямых, что улучшает быстродействие по сравнению с использованием дуг окружностей или других кривых

Над геометрическими объектами определено (исходя из практических соображений) множество операций, делящееся на несколько основных категорий

• получение геометрических объектов из их внешнего (текстового или двоичного) представления или преобразование их во внешнее представление,

• получение характеристик объекта (качественных или количественных),

• получение информации об относительном расположении объектов,

• получение новых геометрических объектов из объектов-операндов

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

метрических типов применяются различные типы индексных структур. В исследовании дан сравнительный анализ средств, используемых современными РСУБД (Oracle. IBM DB2, PostgreSQL, MySQL) для решения этих задач.

На основе проведенного анализа сформулированы цель и задачи исследования.

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

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

Рис. 1. Примеры распределенных объектов: а) фрагмент карты сети железных дорог; б) фрагмент схемы микропроцессора.

Рис. 2. Иерархия классов геометрических объектов

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

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

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

Все синтаксически правильные представления объектов разделены на допустимые (правильные с семантической точки зрения) и недопустимые (не соответствующие никакому геометрическому объекту) На множестве представлений объектов введены функция семантического контроля представлений объектов ул/к/ О —> {¡гие./аИе/ и отношение совпадения (=) Выделено множество допустимых представлений объектов (3, = ¡дСО \>а1к!(д)=1гие} и на нем введена функция 0!у О, —> О, ставящая в соответствие каждому допустимому представлению описываемый им объект На множестве геометрических объектов О введено отношение равенства Рассмотрены свойства введенных функций и отношений для различных классов объектов, влияющие на реализацию манипулирования представлениями распределенных объектов

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

Рассмотрим географическую карту М как прямоугольник на двумерной координатной плоскости

М = Кх, у)} хе[ *,„„ ,*,„,„ ],\'в[ у......\'„„ ],х......е 9?,дг„„„ е ЭД, у„„„ е 9?, \„„„ е 91,

х„„„ < хт, \'„„„ < \ ,„ „

и некоторое множество геометрических объектов Ом, расположенных на этой

карте (все точки каждого из этих объектов должны лежать в границах прямоугольника карты: ое Ои => ое О л о с М ).

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

• ■*„„„ - х„„„ ■ 7Г~ • V' , - У„,,„ . --

х1 = .V......+1 ■------,/ = О.п; V, = )'„„.„ + J ■1-"—- ,/ = и,ш,

п " ............т

М . = !(х, у )1: хе IX, /,уе / у7.'= !■»,] = /,т

Рис. 3. Разбиение карты для политомического представления объектов

Математическая модель политомического представления объектов базируется на том, что каждому объекту ое 0„, ставится в соответствие совокупность векторных представлений его пересечений с каждым из квадратов карты (фрагментов объекта в квадратах карты):

о = и о,,.' = ¡.п.] = !,т;оц сг М ц ;о =оглМ |(. (1)

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

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

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

Операции над объектами размерностей 0 и 1 (точками и ломаными), как правило, достаточно просты в реализации Напротив, операции над объектами размерности 2 (полигонами) довольно сложны, поскольку алгоритмы их реализации должны учитывать большое число различных случаев взаимного расположения операндов Основными операциями над полигонами являются INTERSECTION, UNION и DIFFERENCE

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

Таблица 1

Возможные результаты операций над простыми полигонами

Операция Тривиальные случаи Результаты в других случаях

INTERSECTION 1 Кольца не имеют общих точек, и ни одно из них не лежит внутри другого Результат -пустой объект 2 Кольцо первого (второго) полигона лежит внутри кольца второго (первого) полигона Результат - первый (второй) операнд Точка, ломаная, простой полигон, коллекция из любого числа перечисленных объектов

UNION 1 Кольца не пересекаются, но могут касаться в любом конечном числе точек, и ни одно из них не лежит внутри другого Результат -коллекция из двух операндов 2 Кольцо первого (второго) полигона лежит внутри кольца второго (первого) полигона Результат - второй (первый) операнд Один полигон с любым числом внутренних колец

DIFFERENCE 1 Кольца не пересекаются, но могут касаться в любом числе точек или на любом числе отрезков, и ни одно из них не лежит внутри другого Результат - первый операнд 2 Кольцо первого полигона лежит внутри кольца второго Результат - пустой объект 3 Кольцо второго полигона лежит внутри кольца первого, и они могут касаться не более чем в одной точке Результат - один полигон с одним внутренним кольцом Любое количество простых полигонов

Структурная схема алгоритма операции над простыми полигонами приведена на рис 4 Процесс формирования границы результата для операций над простыми полигонами описан в табл 2 Далее в диссертации приведены описания последующих этапов алгоритмов вычисления результатов операций INTERSECTION, UNION и DIFFERENCE над сложными полигонами

Рис 4 Алгоритм выполнения операции над простыми полигонами

Таблица 2

Формирование границы результата для операций над простыми полигонами

Операция Что включается в границу результата

INTERSECTION Все отрезки границы каждого из операндов, внутренние точки которых расположены внутри другого операнда, общие отрезки границ операндов такие, что оба операнда расположены с одной стороны от этого общего отрезка

UNION Все отрезки границы каждого из операндов, внутренние точки которых расположены вне другого операнда, общие отрезки границ операндов такие, что оба операнда расположены с одной стороны от этого общего отрезка

DIFFERENCE Все отрезки границы первого операнда, внутренние точки которых расположены вне второго операнда, все отрезки границы второго операнда, внутренние точки которых расположены внутри первого операнда, общие отрезки границ операндов такие, что оба операнда расположены с разных сторон от этого общего отрезка

Для операции INTERSECTION в результат также добавляются объекты меньшей размерности 1) общие отрезки границ первого и второго операндов такие, что оба операнда расположены с разных сторон от этого общего отрезка, 2) все общие точки границ операндов, не включенные ранее

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

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

операция пересечения фрагментов с =о глЬ a =0v/j = 0=>с =0,

II IJ I] Ч ч IJ

а = М => с = b , b = М => с = и , (2)

Ч Ч '} Ч ' Ч Ч Ч Ч ' '

операция объединения фрагментов

f „ = ач U Ьч С1ч = М ч V Ь, = М„=> Сч = Мч '

а ~ 0 => с = b , b = 0 => с = а , П)

Ч Ч > Ч 'J ч '

операция разности фрагментов

с =а \b b =0=>с =а ,b = М =>с =0,

Ч IJ Ч Ч Ч IJ ч ч ч

dim( av) > dim( bv )=>си = av (4)

предикат равенства фрагментов

(а — 0 л b =0)v(a =М a h =М }=>а =Ь ,

' У 1J ' У и IJ „ 1 ' ч ,) '

(я =0л/) *0)v(« Ф0лЬ = 0)=>я , (5)

'у у Ь ЧЧЧ v

f я =М a b * М ) V (а * М лЬ =М ) => я * /? ,

1 У У t I II IJ у у у у

предикат включения фрагментов (я„ = 0v/)|=Mij )=>«„<=/>,,

(а =М лЬ )v(a *0лЬ =0)=>а ctb (6)

'у У и 4 1 U Ч У

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

1) найти все пары ( ) такие, чго я #0л b:j Ф 0,

2) в цикле для всех этих пар ( i,j ) вычислить с = яу учитывая (2),

Ч) преобразовать политомическое представление полученного объекта в векторное с = а n b = (Je

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

Использование политомических представлений объектов полезно также для вычисления пространственных отношений между этими объектами Ниже приведен пример алгоритма для вычисления предиката 0\eilaps (перекрытия объектов) Данный предикат означает, что пересечение объектов имеет ту же размерность, что и они оба и не совпадает ни с одним из них В случае dim( а ) Ф chm( b ) предикат Overlaps возвращает значение false Oveilaps( a,b j <=> dtm( a nb ) = dim( a ) = dini( b) л я ez b a b (t a

1) установить значение трех признаков (dim(a nb) = dim(a ) = dim(b), a (tb и b (ta) в false,

2) найти все пары (i,j) такие, что a:j í0viif В тривиальном случае (6) для a:j<tb4 и b (ta выставить в tine значения признаков a<tb и b <t я соответственно В тривиальном случае (2) « ní> —М выставить значение признака dtm( a n,b ) = dim( a ) = dun(b) в tute Если значения всех трех признаков выставлены в true, то завершить алгоритм с возвратом значения tute,

в цикле для всех отобранных пар (¡,j ) с исключением тривиальных случаев (а * 0 лb Ф0 л а Ф М лh Ф М )

v у у у у у '

а) если значение признака a <t b равно false, то проверить выполнение предиката я \/>ч Ф 0 и, если он выполняется, выставить это значение в tine,

б) если значение признака bet а равно false, то проверить выполнение предиката Ь \а Ф0 и, если он выполняется, выставить это значение в true.

в) если значение признака dim(а глЬ) = dim(а )- dim(Ь) равно false, то проверить выполнение предиката dim(a r\b:j) — dim( а) и, если он выполняется, выставить это значение в true,

г) если значения всех трех признаков выставлены в true, то завершить алгоритм с возвратом значения true,

4) алгоритм завершается и возвращает значение false

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

В четвертой главе описана структура подсистемы РСУБД, обеспечивающей хранение и обработку представлений распределенных объектов Реляционная СУБД представляет собой комплекс программ, работающих под управлением операционной системы Для поддержки работы с данными геометрических типов в структуру РСУБД автором включена подсистема обработки геоданных Эта подсистема реализована в виде библиотеки, вызовы функций которой используют другие компоненты РСУБД (ядро РСУБД и компилятор языка SQL), схема их взаимодействия приведена на рис 5 Кроме того, и сами эти компоненты подвергнуты доработкам

Клиент

Прикладная j 1 Прикладная ■

программа программа

1 А

1 i 1 1

Запрос Ответ

Запрос Ответ

Сервор

Ядро СУБД

i

т

-Вызов функции- Реэультат—i

I i

Текст Запрос Возврат

SOL информации информации запроса об объектах БД об объектах БД

Г

I

Внутреннее представление SQL запроса

Подсистема обработки геоданных

Компилятор языка SQL

-Результат—' -Вызов функции-

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

Все доработки, которым были подвергнуты компоненты РСУБД, могут быть разделены на базовую часть (поддержка векторного представления объектов) и оптимизационную часть (поддержка политомического представления)

В синтаксис, воспринимаемый компилятором языка SQL, внесены следующие изменения

• разрешены геометрические типы данных для столбцов в предложениях CREATE TABLE (для создания столбцов геометрических типов при создании таблицы) и ALTER TABLE ADD COLUMN (для добавления столбцов геометрических типов в уже существующую табчицу) Реализованный набор геометрических типов данных основан на модели векторного представления объектов Для каждого типа существуют различные варианты в зависимости от наличия или отсутствия дополнительных координат Z и М,

• в набор встроенных функций включены функции, имеющие аргументы или возвращающие значения геометрических типов Представление (описание) данных геометрических типов осуществляется либо в текстовом (WKT -Weil-Known Text), либо в двоичном (WKB - Well-Known Binary) формате, каждый из которых расширен с целью возможности представления объектов, не описанных в стандарте OpenGIS (прямая, круг и т д ) Имена функций являются контекстными, то есть распознаются как соответствующие лексемы только перед открывающей скобкой - признаком функции,

• добавлены новые предложения языка SQL, предназначенные для управления функционированием подсистемы обработки геоданных

Загрузка данных геометрических типов в таблицы БД выполняется с помощью SQL-предложения INSERT и набора встроенных функций РСУБД, преобразующих представленные в формате WKT или WKB данные в соответствующий столбцу геометрический тип Особенностью реализации является возможность определения геометрического типа данных из контекста Значения геометрических типов данных могут быть просмотрены в формате WKT или WKB с помощью соответствующих функций (AsText и AsBinary)

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

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

• добавлен механизм сравнения значений геометрических типов,

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

• добавлено распознавание предикатов, содержащих данные геометрических типов, и выбор для этих предикатов соответствующих стратегий обработки

Подсистема обработки геоданных состоит из следующих модулей

• головной модуль, содержащий все точки внешних вызовов,

• модуль преобразования объектов из WKT-представления и обратно,

• модуль преобразования объектов из WKB-представления и обратно,

• модуль проверки корректности представлений объектов,

• модуль основных графических примитивов (пересечение отрезков, принадлежность точки полигону и т п ),

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

• модуль обработки MBR (ограничивающих прямоугольников) объектов,

• модуль вычисления операций INTERSECTION, UNION и DIFFERENCE,

• модуль поддержки политомического представления объектов

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

CREATE MAP_SPLIT имя_разбиенмя [USING 1шя_системы_координат] X BETWEEN xmiл AND xmах [STEP xstep] [COUNT xcount] Y BETWEEN ymin AND ymax [STEP ystepl [COUNT ycount], DROP MAP_SPLIT имя_разблеш1я [CASCADE] ,

Столбец геометрического типа может быть "связан" с политомическим разбиением Эта связь подобна индексу, создаваемому на столбец одного из обычных типов данных СУБД отсутствие связей столбца с разбиениями не сужает набор операций над ним, но влияет на производительность этих операций Один и тот же столбец может быть связан с несколькими различными разбиениями Для хранения информации об этих связях введена специальная системная таблица $$$MAP_SPLIT_USE Для создания и удаления связей между столбцами и разбиениями также введены новые команды языка SQL

ALTER TABLE имя_таблицы SET MAP_SPLIT имя_разбиения [FOR имя_столбца [, ] ] ,

ALTER TABLE имя_таблицы CANCEL MAP_SPLIT имя_разбиения [FOR имя_столбца [, ] ] ,

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

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

CREATE TABLE $$$SPLIT_INDEX_IDcTOj6aa_IDpa36ifeHHtf ( ID_ROW INTEGER, SQUARE INTEGER, WHOLE BOOLEAN, SECTION GEOMETRY,

Здесь ГОстолбца и Юразбиения - числовые значения внутренних идентификаторов (ROWID) соответствующих записей в системных таблицах столбцов ($$$ATTR!) и разбиений ($$$MAP_SPLIT) Прямые ссылки на внутренние номера записей представляют собой элементы иерархической организации данных в РСУБД Поле ID_ROW указывает ROWID соответствующей записи в основной таблице, поле SQUARE - номер квадрата разбиения Флаг WHOLE (используемый для значений размерности 2 в основной таблице) указывает, весь ли квадрат занимает соответствующая фигура или только его часть Значение поля SECTION равно пересечению соответствующего значения основной таблицы с квадратом разбиения, определяемым номером SQUARE, и может быть NULL-значением только в том случае, если установлен флаг WHOLE

При таком подходе обеспечивается возможность использования аппарата обычных индексов при выполнении операций над вспомогательными таблицами $$$SPLIT_INDEX_ B-tree индексы на столбцы ID_ROW и SQUARE строятся при создании такой таблицы и удаляются вместе с ней

Над вспомогательными таблицами запрещены любые явные операции, а неявные операции над ними выполняются в следующих случаях

• создание/удаление вспомогательной таблицы - при создании/удалении связи между разбиением и столбцом либо удалении основной таблицы,

• добавление/удаление записей вспомогательной таблицы - при добавлении, удалении и обновлении значении геометрического типа в столбце основной таблицы,

• поиск по lD_ROW (выбрать все записи с данным 1D_R0W) - вспомогательная операция в процессе удаления записей,

• поиск по ID_ROW, SQUARE и комбинированный (в том числе со слиянием индексов) - вспомогательные операции при обработке поисковых запросов

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

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

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

• компилятор языка SQL - поддержка синтаксиса новых операций и отражения их во внутреннем представлении запроса,

• словарь БД - SQL-скрипты для создания системных таблиц,

1 s

• утилита верификации целостности БД - проверка соответствия (когерентности) содержимого основной и вспомогательной таблиц,

• утилиты администрирования БД - создание и удаление разбиений и связей между разбиениями и столбцами, а также просмотр информации о них

Основные научные положения и выводы исследования реализованы в виде компонентов программного обеспечения, функционирующих на всех платформах, поддерживаемых СУБД "ЛИНТЕР" (семейства операционных систем Windows, UNIX, QNX, OS9000 и многие другие) Исходный код компонентов написан на языке программирования С и имеет размер около 800 Кб

В заключении подведены основные итоги проделанной работы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

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

Статьи и материалы конференций

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

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

4 Борисенков Д В , Харин В H Логическое представление распределенных пространственных объектов ГИС II Современные проблемы механики и прикладной математики сб тр Междунар школы-семинара - Воронеж ВГУ, 2005 - Ч 1 С 65-68

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

6 Приоритетные направления обеспечения устойчивого развития территориальных образований региона на основе использования возможностей информационных технологий ГИС и СУБД "Линтер" / MB Ермаков, Д В Борисенков, В Л Борисов и др // Опыт и проблемы природопользования при реализации президентских программ в Центрально-Черноземном регионе материалы VI Междунар науч -практ конф Воронеж Федеральное агентство кадастра недвижимости Центрально-Черноземный филиал ФГУП «Госземка-дастрсъемка» - ВИСХАГИ, 2006 - С 40-50

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

8 Борисенков Д В , Харин В H Нормализация представлений распределенных геометрических объектов в реляционной СУБД // Математическое моделирование, компьютерная оптимизация технологий, параметров оборудования и систем управления лесного комплекса межвуз сб науч тр Воронеж ВГЛТА, 2006 Вып 11 С 116-119

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

10 Борисенков Д В , Харин В H Алгоритм преобразования картографической информации в политомическое представление // Информационные техно-

логин моделирования и управления науч -техн журнал 2006 №9(34) -С ¡137-1141

11 Основы устойчивого социального и экономического развития территориальных образований с использованием ГИС-технологий теория и практика В 2-х кн Кн 1 Направления практической деятельности поддержки социального и экономического развития территориальных образований на основе ГИС и OLAP технологий по результатам аэрокосмического зондирования (с использованием возможностей СУБД ЛИНТЕР) учеб пособие / Д В Борисенков, В Л Борисов, M В Ермаков и др , под ред акад РАЕН П С Русинова - Воронеж Истоки, 2006 - 214 с

12 Основы устойчивого социального и экономического развития территориальных образований с использованием ГИС-технологий теория и практика В 2-х кн Кн 2 Основные положения концепции региональной системы электронной оценки эффективности устойчивого социального и экономического развития учеб пособие / Д В Борисенков, В Л Борисов, M В Ермаков и др , под ред акад РАЕН П С Русинова - Воронеж Истоки, 2006 -238 с

Зарегистрированные программы

13 Мобильная система управления базами данных ЛИНТЕР версия 5 7 (СУБД ЛИНТЕР) / А В Пешков, И А Бойченко, И Я Попов, С П Маркин, Д В Борисенков и др - Российское агентство по патентам и товарным знакам Свидетельство об официальной регистрации программы для ЭВМ №2000610794 от 25 08 2000

14 Библиотека управления геоданными СУБД ЛИНТЕР / Д В Борисенков, M В Ермаков, Д Б Коваль,- Федеральная служба по интеллектуальной собственности, патентам и товарным знакам Свидетельство об официальной регистрации программы для ЭВМ №2007614510 от 25 10 2007

6 / и

Подписано в печать 16 11 2007 Формат 60x84/16 Бумага для множительных аппаратов Уел печ п 1,1 Тираж 100 экз Заказ № £~$Э

ГОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп , 14

Введение.

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

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.