Цветков В.Я. Геоинформационные системы и технологии

Подождите немного. Документ загружается.

Задачи классификации четвертого типа назовем процедурными.

В них выполняются анализ и классификация процедур

преобразования, а не данных.

Задачи классификации пятого типа - структурно-аналитичес-

кие. С их помощью производятся анализ и классификация

аналитически-логических связей в системах, алгоритмах и

программах. Основу такой классификации составляют методы

структурного и системного анализа.

В ГИС задачи классификации первого типа возникают и

решаются при разработке классификаторов, т.е. при организации

информационной основы, задачи второго типа - при сборе

первичных данных и при использовании ГИС для экспертных

решений или оценок. Задачи классификации третьего типа

возникают в приложениях ГИС для решения проблем в области

экологии, землепользования, статистики и т.п. Задачи четвертого

типа классификации требуют решения при организации и выборе

основных технологических процессов ГИС, пятого типа - при

организации информационной системы, представлении

(формализации) и оптимизации ее технологических процессов.

Строго говоря, классификационные задачи пятого типа должны

предшествовать классификационным задачам четвертого и других

типов.

3.3. Аспекты рассмотрения моделей

данных

Модель, как правило, отражает наиболее общие свойства

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

аспектов рассмотрения и критериев оценки моделей данных

позволяет на основе объективного сравнительного анализа

выбирать оптимальную модель для решения возникающих

проблем.

Семиотика. Модель как знаковая система должна содержать

три основные характеристики: синтаксис, семантику и прагматику.

Этот подход определяет содержание элементарной (атомарной)

модели как элементарной единицы данных, включающей в себя

правила построения, имя объекта, свойства объекта, значения

свойств. Разнообразие атомарных моделей создает условия для

построения множества моделей данных.

Типизация. Одно из противоречий описания моделей

заключается в стремлении отразить, с одной стороны, общие

свойства класса объектов, с другой - индивидуальные признаки

более узкого подкласса и ин

дивидуальные признаки конкретного объекта. Это

обусловливает разделение моделей данных на два класса:

сильно типизированные и слабо типизированные.

Сильно типизированные - это модели, в которых

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

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

(типу). Если исходные данные нельзя отнести к одному типу,

то их можно с помощью искусственных приемов (введением

дополнительных условий или ограничений) отнести к набору

типов с помощью процедур типизации. Сильно типизиро-

ванные модели эффективны при обработке однотипных

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

ГИС служат координатные (метрические) данные и все

табличные данные.

Слабо типизированные - это модели, в которых данные

разнородны по формату, структуре. Они, в общем, слабо

связаны условиями относительно известных типов. Слабо

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

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

моделей обеспечивается исчислением предикатов. Примером

слабо типизированных моделей в ГИС могут быть описатель-

ные характеристики (временные наборы данных).

Изменчивость. Можно выделить два класса моделей:

статические и динамические.

К статическим относят модели, инвариантные

относительно времени. Динамические модели не только

допускают изменение параметров и структур во времени, но и

служат для описания изменения процессов и моделей именно

во времени. Примерами таких моделей в ГИС могут служить

два вида электронных карт: электронные карты в режиме

разделения времени (электронные атласы) - статическая мо-

дель, электронные карты в реальном масштабе времени

(навигационные системы) - динамическая модель.

Следует подчеркнуть, что понятие изменчивости моделей

данных в ГИС относительно, так как вся информация носит

пространственно-временной характер и через какое -то время

требует обновления. Поэтому, применяя понятия

статические и динамические модели, необходимо указывать

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

информационных данных, или определять альтернативную

модель при сравнении с исходной.

Любая модель данных должна в разной степени обладать

двумя этими свойствами. Динамика моделей определяет их

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

модель со множеством правил порождения и множеством

операций.

Агрегация (взаимосвязь). Отдельные части модели образуют ее

структуру. Одним из основных способов структуризации данных

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

данных, так и для построения одних категорий на основе других.

Представление моделей. Выделяют табличные и графовые

формы

представления моделей. .

Табличная форма дает представление модели или ее

характеристик в виде одной или совокупности взаимосвязанных

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

произвольно, они подчиняются определенным правилам, в

частности, по столбцам располагают типизированные данные.

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

служить логическая запись (см. рис 3.4, 3.5), которая представляет

собой верхнюю строку таблицы.

Графовая форма основана на построении модели в виде

графической схемы, называемой графом. Эта схема включает

элементы графа, называемые вершинами (узлами) к ребрами

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

модель, как и табличная, строится по определенным правилам. В

частности, каждое ребро может быть ориентировано, если

определен путь от одной вершины к другой, и не ориентировано,

что соответствует возможному пути от одной вершины к другой в

обоих направлениях. Простейший пример ориентированного графа

- вектор в трехмерном пространстве, а неориентированного графа -

кривая пути из одной точки в другую. Кроме вершин и ребер

существуют другие элементы, значение которых не столь суще-

ственно.

Некоторые специалисты в области моделирования данных

заменяют термины вершина и ребро терминами узел и дуга. При

анализе графовых форм применительно к моделям данных в ГИС

эти термины следует считать взаимно заменяемыми.

Форма отображения объекта в модель. Этот аспект рассмотре-

ния определяет дискретную и аналоговую модели. Примерами

таких моделей в ГИС могут служить обычная (аналоговая) карта и

цифровая карта.

Аналоговые модели в свою очередь разбиваются на две группы:

прямой и косвенной аналогии. Модели прямой аналогии создаются

на основе физического моделирования (аналоговые карты, модели

судов, самолетов, гидротехнические сооружения и т. п.), модели

косвенной аналогии - на основе математического моделирования

(аналитического описания), например, цифровая модель рельефа,

построенная на основе аналитического описания поверхности.

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

функций набором дискретных значений аргументов и функций. Диск-

ретность определяется шагом квантования. Для сохранения информа-

тивности дискретной модели по отношению к объекту шаг

квантования должен выбираться с учетом теоремы Шенона -

Котельникова. Примером дискретных моделей являются большинство

цифровых моделей, на основе которых впоследствии осуществляется

аналоговое представление информации ГИС.

ЗА. Базовые модели данных,

используемые в ГИС

Инфологическая модель

Инфологическая модель занимает особое положение по

отношению к другим моделям. Она соответствует четвертому этапу

построения сложной системы и дает формализованное описание

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

Инфологическая область моделирования данных охватывает

естественные для человека концепции отображения реального мира.

Создание этой модели является первым шагом процесса формали-

зации. В отличие от представления на естественном языке она в

основном исключает неоднозначность за счет использования средств

формальной логики.

Одно из главных понятий инфологической модели - объект. Это

понятие связано с событиями: возникновение, исчезновение и измене-

ние. Объекты могут быть атомарными или составными.

Атомарный объект- это объект определенного типа, дальнейшее

разложение которого на более мелкие объекты внутри данного типа

невозможно.

Составные объекты включают в себя множества объектов,

кортежи объектов. Применяя это определение, рекурсивно можно

получить произвольную структуру составных объектов.

Обычно объект имеет некоторое свойство или взаимосвязь (связь)

с другими объектами. Свойство может быть не определено

формально, а лишь охарактеризовано как некоторое утверждение по

поводу множества объектов.

Инфологическая модель позволяет выделить три категории

фактов: истинные, значимые и ложные. С одной стороны, это

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

определенные сложности.

Различия между традиционными и инфологическими моделями

данных аналогичны различию между мнением и истиной. Во

многих моделях большинство сообщений относится к одной из

двух категорий: истинные или ложные. Инфологическая модель

предполагает возможность представления любого сообщения с

какой-то долей вероятности, т.е. в виде аналога мнения. Анализ

такого сообщения возможен при учете конкретного контекста. В

правильном контексте сообщение истинно. Но и ошибочное

утверждение может рассматриваться как мнение.

Цель инфологического моделирования - формализация

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

информации в соответствии с поставленными задачами обработки

и требованиями представления данных естественными для

человека способами сбора и представления информации.

Инфологические модели позволяют получать произвольные

представления простых событий. На их основе могут быть

сконструированы также типы моделей, подобные поддерживаемым

сильно типизированными моделями.

В таких моделях ссылки на объекты и сами объекты

разделены, а сообщения интерпретируются с учетом контекста. Это

позволяет реализовать множественность ссылок и обеспечить

разнообразие интерпретации.

Инфологическая модель может включать в себя ряд

компонентов (рис. 3.6). Принципиальной особенностью этой

модели является возможность отображения как формализуемых

средствами формальной логики процессов и объектов, так и

неформализуемых в дальнейшем процессов.

Основными компонентами мифологической модели являются:

• описание предметной области;

• описание методов обработки;

• описание информационных потребностей пользователя.

Инфологическая модель носит описательный характер. В силу

некоторой произвольности форм описания в настоящее время не

существует общепринятых способов ее построения. Используют

аналитические методы, методы графического описания, системный

подход.

Рис. З.6. Основные компоненты инфологической модели

Иерархическая модель

К наиболее простым структурно определенным относится

иерархическая модель. В этой модели данных связи между ее

частями являются жесткими, а ее структурная диаграмма должна

быть упорядоченным деревом.

Одно из важных понятий для этой модели - уровень. Для

описания разных уровней применяют понятия: корень, ствол,

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

со структурой дерева.

Граф иерархической модели (ее схемное представление)

включает два типа элементов: дуги и узлы (или записи).

Дуги соединяют разные узлы между собой. Дуги,

соответствующие функциональным связям, должны быть всегда

направлены от корня в листья дерева, т.е. они являются

ориентированным графом. Такая структурная схема называется

иерархическим деревом определения или деревом определения [17].

Дуга дерева определения, соответствующая

функциональному типу связи, называется связью исходный-

порожденный. Между двумя типами записей в

иерархической модели может быть не более одной такой

связи. Дуга исходит из тит родительской (порождающей)

записи и заходит в тип дочерней (порожденной) записи.

В простейшем случае иерархическая модель представляет

собой описание процесса или системы, состоящей из

совокупности уровней, связанных одной дугой (рис. 3.7).

Мифологическое моделирование

Мифологическая модель

Даталогическое моделирование

Даталогическая модель (схема)

Физическое проектирование

Физическая модель

Рис. 3.7. Иерархическая модель проектирования ГИС

Рассматривая последовательность связей "исходный-

порожденный", можно естественным образом

идентифицировать типы родительской и порожденной

записей.

Первую порождающую запись называют корневой (реже

стволом), промежуточные записи - ветвями, записи самого

нижнего уровня иерархической модели - листьями.

Понятия корневой, ствол, ветви, листья определяют тип

записи в иерархической модели.

Иерархический путь, или маршрутизация, - это

последовательность типов записей, начинающаяся с типа

корневой записи, в которой типы записей выступают

переменно в ролях исходного и порожденного.

Известная программистам последовательность "диск-

корневой каталог-подкаталог - программа" - характерный

пример иерархической модели.

Уровень типа записи относительно типа корневой записи

определяется как длина пути от корневой записи, выраженная

в числе дуг. Так, тип корневой записи "диск" находится на

нулевом уровне, "корневой каталог" - на первом,

"подкаталог" - на втором, имя файла - на третьем и т.д.

Расширение дерева определения иерархической модели

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

расширение каждой связи "исходный-порожденный" -

множеством соединений между таблицами.

Альтернативным способом представления расширения

дерева определения является "лес", или совокупность

отдельных деревьев, состоящих из одной корневой записи и

всех ее зависимых записей. Такое дерево называется деревам

базы данных. Оно конструируется в соответствии с деревом

определения.

Иногда структуру иерархической модели называют Е-

деревом (см. рис. 3.2,3.6).

Иерархическим моделям данных присущи два внутренних

ограничения. Первое ограничение - все типы связей должны

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

быть древовидной. Следствием этих ограничений является

необходимость соответствующей структуризации данных. В

силу функциональности связей запись может иметь не более

одной исходной записи любого типа, т.е. связь должна иметь

жесткий вид -1: n (один ко многим). Очевидный недостаток

иерархических моделей - снижение времени доступа при

большом числе уровней, поэтому в ГИС не используют

модели при большом числе уровней (более 10). В то же время

иерархические модели довольно . устойчиво применяются для

составления различного рода классификаторов.

Квадратомическое дерево

Иерархическая структура данных, известная как

квадратомическое дерево, используется для накопления и

хранения географической информации. В этой структуре

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

разделяется на квадранты, что определило название данной

модели.

На рис. 3.8 показан фрагмент двухмерной области QT,

состоящей из 16 пикселей. Каждый пиксель обозначен

цифрой. Вся область разбивается на четыре квадранта: А, В,

С, D. Каждый из четырех квадрантов является узлом

квадратомического дерева. Большой квадрант QT становится

узлом более высокого иерархического уровня

квадратомического дерева, а меньшие квадранты появляются

на более низких уровнях.

Уровень 2 Уровень 1

Рис. 3.9. Квадратомическое дерево в виде Е-

структуры

Уровень О

Рис. 3.8. Фрагмент растра, квантованный для построения

квадратомического дерева

Технология построения квадратомического дерева основана на

рекурсивном разделении квадрата на квадранты и подквадранты до

тех пор, пока все подквадранты не станут однородными по

отношению к значению изображения (цвета) или пока не будет

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

разрешения.

Если регион состоит из 2n x 2n пикселей, то он полностью

представлен на уровне n, а единичные пиксели находятся на

нулевом уровне. Квадрант уровня 1 (0<1<n) содержит 21 х 21

пикселей, всего 41.

На рис. 3.9 показано квадратомическое дерево, построенное по

данным рис. 3.8. Как видно, эта структура являет собой

классический пример Е-дерева. Преимущество такой структуры

состоит в том, что регулярное разделение обеспечивает

накопление, восстановление и обработку данных простым и

эффективным способом. Простота проистекает из геометрической

регулярности разбиения, а эффективность достигается за счет

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

Поскольку квадратомическое дерево известно как

пространственно-рациональный способ представления

сгруппированных однородных или сопряженных изображений, их

преимущество над векторной репрезентацией многих (но не всех)

пространственных алгоритмов относительно затрат машинного

времени весьма существенно.

Первоначально большинство приложений моделей

квадратомических деревьев было сделано для обработки

изображений. Из этой области данная модель была перенесена в

ГИС.

Модели, основанные на квадратомических деревьях,

обеспечивают расчеты площадей, центроидные определения,

распознавание образов, выявление связанных компонентов,

определение соседства, преобразование расстояний, разделение

изображений, сглаживание данных и усиление краевых эффектов.

Вследствие этого появилась возможность использовать

квадратомические деревья для хранения географических данных.

Однако при этом требуется развитие процедур для превращения

растровых данных в формат квадратомического дерева и

усовершенствование техники линейного кодирования.

В первых работах по квадратомическим деревьям связи между

квадрантом и подквадрантом давались в виде дерева со степенью

ветвления, равной четырем. В такой структуре связи между

родительским и дочерним уровнем определяются системой

внешних указателей.

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

одного родителя. В то же время все они, за исключением листьев,

связаны с четырьмя дочерними узловыми точками.

Преимущество представления, основанного на указателях,

заключается в том, что оно выражает только значимую часть

полного квадратомического дерева.

Последние исследования показали, что для больших

квадратомических деревьев наиболее подходящей структурой

является линейное квадродерево. В нем каждый листовой узел

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

упорядоченном списке узловых точек прародителей. Последующее

преобразование дерева в код достигается использованием битового

уровня или модулярной арифметики. Система линейных кодов

обеспечивает эффективную связь между структурами

пространственных данных и алгоритмами, применяемыми в

вычислительной геометрии для решения проблем восстановления

прямоугольников и определения ближайшего "соседа".

Рядом исследователей была рассмотрена возможность

использования искусственного интеллекта для совершенствования

очень больших географических информационных систем,

основанных на квадратомических деревьях.

Иерархические модели, как и прочие, могут описывать

системы, данные и схемы процессов обработки данных. Следует,

однако, подчеркнуть, что правильно составленная иерархическая

схема должна содержать в качестве записей (вершин) атрибуты или

агрегаты атрибутов либо типы сущностей. Атрибуты или агрегаты

атрибутов соответствуют множествам или расширенным

множествам. Дуги могут использоваться для представления

агрегации двух атрибутов в тип сущности или двух типов

сущности в тип связи. На практике часто в запись вставляют не

только сущности базы данных, но и связи. Такая схема

описывается моделью "сущность-связь" и будет рассмотрена ниже.

Анализ иерархических моделей (связей между их частями) с

"неправильным" описанием необходимо проводить, выделяя типы

сущностей.

Реляционная модель

В современных информационных системах и базах данных

наиболее широко представлены реляционные модели (РМ).

Реляционная модель данных, разработанная Коддом еще в

1969-1970 гг. на основе математической теории отношений,

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

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

домен (domain). Доменом называется совокупность значений, не

повторяющихся в одном столбце. Такая модель положена в основу

так называемых электронных таблиц-специализированных баз

данных.

Сущности, атрибуты и связи хранятся в таблицах как данные

определенной структуры. Структура данных обусловливается

используемыми моделями данных.

Таблица состоит из строк и столбцов и имеет имя, уникальное

внутри базы данных. Таблица отражает тип объекта реального

мира (сущность), а каждая ее строка - конкретный объект.

Основным средством структурирования данных в реляционной

модели является отношение (relation). Понятия отношения в

реляционной модели и математике близки, хотя и не совпадают.

Можно определить отношение как декартово произведение

доменов.

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

Таблица имеет столбцы и записи (строки). Каждая запись имеет

набор атрибутов. Записи каждого типа образуют таблицу или

отношение. Каждая строка - это запись или кортеж. Каждый

столбец - это атрибут. Диапазон допустимых значений (домен)

определяется для каждого атрибута. Степень отношения - число

атрибутов в таблице: один атрибут - унарное отношение, два

атрибута - бинарное отношение, n атрибутов - n-арное отношение.

Ключ отношения - это подмножество атрибутов, имеющее

следующие свойства:

• уникальную идентификацию;

• неизбыточность;

• ни один из атрибутов ключа нельзя удалить, не нарушив его

уни

кальности.

Первичный атрибут отношения - это атрибут,

присутствующий по крайней мере в одном ключе, все другие

атрибуты непервичные.

В реляционной модели данных схема отношения может быть