Автор работы: Пользователь скрыл имя, 22 Марта 2013 в 20:07, курсовая работа
Современные геоинформационные системы (ГИС) представляют собой новый тип интегрированных информационных систем, которые, с одной стороны, включают методы обработки данных многих ранее существовавших автоматизированных систем (АС), с другой - обладают спецификой в организации и обработке данных. Практически это определяет ГИС как многоцелевые, многоаспектные системы.
Некоторые специалисты в области моделирования данных заменяют термины вершина и ребро терминами узел и дуга. При анализе графовых форм применительно к моделям данных в ГИС эти термины следует считать взаимно заменяемыми.
Форма отображения объекта в модель. Этот аспект рассмотрения определяет дискретную и аналоговую модели. Примерами таких моделей в ГИС могут служить обычная (аналоговая) карта и цифровая карта.
Аналоговые модели в свою очередь разбиваются на две группы: прямой и косвенной аналогии. Модели прямой аналогии создаются на основе физического моделирования (аналоговые карты, модели судов, самолетов, гидротехнические сооружения и т.п.), модели косвенной аналогии - на основе математического моделирования (аналитического описания), например, цифровая модель рельефа, построенная на основе аналитического описания поверхности.
Дискретные модели строятся путем замены непрерывных функций набором дискретных значений аргументов и функций. Дискретность определяется шагом квантования. Для сохранения информативности дискретной модели по отношению к объекту шаг квантования должен выбираться с учетом теоремы Шенона - Котельникова. Примером дискретных моделей являются большинство цифровых моделей, на основе которых впоследствии осуществляется аналоговое представление информации ГИС.
Инфологическая модель занимает особое положение по отношению к другим моделям. Она соответствует четвертому этапу построения сложной системы и дает формализованное описание проблемной области независимо от структур данных. Инфологическая область моделирования данных охватывает естественные для человека концепции отображения реального мира.
Создание этой модели является первым шагом процесса формализации. В отличие от представления на естественном языке она в основном исключает неоднозначность за счет использования средств формальной логики.
Одно из главных понятий инфологической модели - объект. Это понятие связано с событиями: возникновение, исчезновение и изменение. Объекты могут быть атомарными или составными.
Атомарный объект - это объект определенного типа, дальнейшее разложение которого на более мелкие объекты внутри данного типа невозможно.
Составные объекты включают в себя множества объектов, кортежи объектов. Применяя это определение, рекурсивно можно получить произвольную структуру составных объектов.
Обычно объект имеет некоторое свойство или взаимосвязь (связь) с Другими объектами. Свойство может быть не определено формально, а лишь охарактеризовано как некоторое утверждение по поводу множества объектов.
Инфологическая модель позволяет выделить три категории фактов: истинные, значимые и ложные, С одной стороны, это обеспечивает модели дополнительную гибкость, с другой - создает определенные сложности.
Различия между традиционными и инфологическими моделями данных аналогичны различию между мнением и истиной. Во многих моделях большинство сообщений относится к одной из двух категорий: истинные или ложные. Инфологическая модель предполагает возможность представления любого сообщения с какой-то долей вероятности, т.е. в виде аналога мнения. Анализ такого сообщения возможен при учете конкретного контекста. В правильном контексте сообщение истинно. Но и ошибочное утверждение может рассматриваться как мнение.
Цель инфологического моделирования - формализация объектов реального мира предметной области и методов обработки информации в соответствии с поставленными задачами обработки и требованиями представления данных естественными для человека способами сбора и представления информации.
Инфологические модели позволяют получать произвольные представления простых событий. На их основе могут быть сконструированы также типы моделей, подобные поддерживаемым сильно типизированными моделями.
В таких моделях ссылки на объекты и сами объекты разделены, а сообщения интерпретируются с учетом контекста. Это позволяет реализовать множественность ссылок и обеспечить разнообразие интерпретации.
Инфологическая модель может включать в себя ряд компонентов (рис. 3.6). Принципиальной особенностью этой модели является возможность отображения как формализуемых средствами формальной логики процессов и объектов, так и неформализуемых в дальнейшем процессов. Основными компонентами инфологической модели являются:
Инфологическая модель носит описательный характер. В силу некоторой произвольности форм описания в настоящее время не существует общепринятых способов ее построения. Используют аналитические методы, методы графического описания, системный подход.
К наиболее простым структурно определенным относится иерархическая модель. В этой модели данных связи между ее частями являются жесткими, а ее структурная диаграмма должна быть упорядоченным деревом.
Одно из важных понятий для этой модели - уровень. Для описания разных уровней применяют понятия: корень, ствол, ветви, листья и лес, что подчеркивает сходство структуры модели со структурой дерева.
Граф иерархической модели (ее схемное представление) включает AM типа элементов: дуги и узлы (или записи).
Дуги соединяют разные узлы между собой. Дуги, соответствующие функциональным связям, должны быть всегда направлены от корня в листья дерева, т.е. они являются ориентированным графом. Такая структурная схема называется иерархическим деревом определения или деревом определения [17].
Дуга дерева определения, соответствующая функциональному типу связи, называется связью исходный - порожденный. Между двумя типами записей в иерархической модели может быть не более одной такой связи. Дуга исходит из типа родительской (порождающей) записи и заходит в тип дочерней (порожденной ) записи.
В простейшем случае иерархическая модель представляет собой описание процесса или системы, состоящей из совокупности уровней, связанных одной дугой (рис. 3.7).
Рассматривая
Первую порождающую запись называют корневой (реже стволом), промежуточные записи - ветвями, записи самого нижнего уровня иерархической модели - листьями.
Понятия корневой, ствол, ветви, листья определяют тип записи в иерархической модели.
Иерархический путь, или маршрутизация, - это последовательность типов записей, начинающаяся с типа корневой записи, в которой типы записей выступают переменно в ролях исходного и порожденного.
Известная программистам
Уровень типа записи относительно типа корневой записи определяется как длина пути от корневой записи, выраженная в числе дуг. Так, тип корневой записи "диск" находится на нулевом уровне, ”корневой каталог” - на первом, ”подкаталог” - на втором, имя файла - на третьем и т.д.
Расширение дерева определения иерархической модели может быть отражено в виде таблиц для записей, а расширение каждой связи "исходный - порожденный" - множеством соединений между таблицами.
Альтернативным способом представления расширения дерева определения является "лес", или совокупность отдельных деревьев, состоящих из одной корневой записи и всех ее зависимых записей. Такое дерево называется деревом базы данных. Оно конструируется в соответствии с деревом определения. Иногда структуру иерархической модели называют Е-деревом (см. рис. (3.2,3.6).
Иерархическим моделям данных присущи два внутренних ограничения. Первое ограничение - все типы связей должны быть функциональными, второе - структура связей должна быть древовидной. Следствием этих ограничений является необходимость соответствующей С1рук1уризации данных. В силу функциональности связей запись может иметь не более одной исходной записи любого типа, т.е. связь должна иметь жесткий вид -1 : п (один ко многим). Очевидный недостаток иерархических моделей - снижение времени доступа при большом числе уровней, поэтому в ГИС не используют модели при большом числе уровней (более 10). В то же время иерархические модели довольно устойчиво применяются для составления различного рода классификаторов.
Иерархическая структура данных, известная как квадратомическое дерево, используется для накопления и хранения географической информации. В этой структуре двухмерная геометрическая область рекурсивно подразделяется на квадраты, что определило название данной модели.
На рис. 3.8 показан фрагмент двухмерной области QT, состоящей из 16 пикселей. Каждый пиксель обозначен цифрой. Вся область разбивается на четыре квадранта: А, В, С, D. Каждый из четырех квадрантов является узлом квадратомического дерева. Большой квадрант QT становится узлом более высокого иерархического уровня квадратомического дерева, а меньшие квадранты появляются на более низких уровнях.
Технология построения квадратомического дерева основана на рекурсивном разделении квадрата на квадранты и подквадранты до тех пор, пока все подквадранты не станут однородными по отношению к значению изображения (цвета) или пока не будет достигнут предопределенный заранее наименьший уровень разрешения.
Если регион состоит из 2n х 2n пикселей, то он полностью представлен на уровне n, а единичные пиксели находятся на нулевом уровне. Квадрант уровня 1 (0<1<n) содержит 21 х 21 пикселей, всего 41.
На рис. 3.9 показано квадратомическое дерево, построенное по данным рис. 3.8. Как видно, эта структура являет собой классический пример Е-дерева. Преимущество такой структуры состоит в том, что регулярное разделение обеспечивает накопление, восстановление иобработку данных простым и эффективным способом. Простота проистекает из геометрической регулярности разбиения, а эффективность достигается за счет хранения только узлов с данными, которые представляют интерес.
Поскольку квадратомическое дерево известно как пространственно-рациональный способ представления сгруппированных однородных ми сопряженных изображений, их преимущество над векторной репрезентацией многих (но не всех) пространственных алгоритмов относительно затрат машинного времени весьма существенно.
Первоначально большинство приложений моделей квадратомических деревьев было сделано для обработки изображений. Из этой области данная модель была перенесена в ГИС.
Модели, основанные на квадратомических деревьях, обеспечивают расчеты площадей, центроидные определения, распознавание образов, выявление связанных компонентов, определение соседства, преобразование расстояний, разделение изображений, сглаживание данных и усиление краевых эффектов. Вследствие этого появилась возможность использовать квадратомические деревья для хранения географических данных. Однако при этом требуется развитие процедур для превращения растровых данных в формат квадратомического дерева и усовершенствование техники линейного кодирования.
В первых работах по квадратомическим деревьям связи между квадрантом и подквадрантом давались в виде дерева со степенью ветвления, равной четырем. В такой структуре связи между родительским и дочерним уровнем определяются системой внешних указателей.
Все узловые точки дерева, за исключением корневой, имеют одного родителя. В то же время все они, за исключением листьев, связаны с четырьмя дочерними узловыми точками.
Преимущество представления, основанного на указателях, заключается в том, что оно выражает только значимую часть полного квадратомического дерева.
Последние исследования показали, что для больших квадратомических деревьев наиболее подходящей структурой является линейное квадродерево. В нем каждый листовой узел представлен линейным числовым кодом, который базируется на упорядоченном списке узловых точек прародителей. Последующее преобразование дерева в код достигается использованием битового уровня или модулярной арифметики. Система линейных кодов обеспечивает эффективную связь между структурами пространственных данных и алгоритмами, применяемыми в вычислительной геометрии для решения проблем восстановления прямоугольников и определения ближайшего "соседа".
Рядом исследователей
была рассмотрена возможность
Иерархические модели, как и прочие, могут описывать системы, данные и схемы процессов обработки данных. Следует, однако, подчеркнуть, что правильно составленная иерархическая схема должна содержать в качестве записей ( вершин) атрибуты или агрегаты атрибутов либо типы сущностей. Атрибуты или агрегаты атрибутов соответствуют множествам или расширенным множествам. Дуги могут использоваться для представления агрегации двух атрибутов в тип сущности или двух типов сущности в тип связи. На практике часто в запись вставляют не только сущности базы данных, но и связи. Такая схема описывается моделью "сущность-связь" и будет рассмотрена ниже.
Анализ иерархических моделей (связей между их частями) с "неправильным" описанием необходимо проводить, выделяя типы сущностей.
В современных информационных системах и базах данных наиболее широко представлены реляционные модели (РМ).
Реляционная модель данных, разработанная Коддом еще в 1969-1970 гг. на основе математической теории отношений, опирается на систему понятий, важнейшие из которых - таблица, отношение, строка, столбец, первичный ключ, внешний ключ, домен (domain). Доменом называется совокупность значений, не повторяющихся в одном столбце. Такая модель положена в основу так называемых электронных таблиц -специализированных баз данных.