13009

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

Лекция

Информатика, кибернетика и программирование

Лекция №2.4. Структури баз картографічних даних в геоінформаційних системах реального часу. План 1.Cтруктури файлів баз картографічних даних реального часу побудованих на основі: послідовної організації даних методу хешування ідентифікатора індекснопослідовно...

Украинкский

2013-05-07

154.5 KB

0 чел.

Лекция №2.4.

Структури баз картографічних даних в геоінформаційних системах реального часу.

План

1.Cтруктури файлів баз картографічних даних реального часу, побудованих на основі: послідовної організації даних, методу хешування ідентифікатора, індексно-послідовної організації даних, дерев розбиття.

Математические модели методов доступа к БД ГИС РВ.

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

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

Далее будет проведена оценка математического ожидания времени поиска записи в файле БД ГИС РВ для двух граничных оценок - законов распределения вероятности обращения к записям файла БД (равномерного и «Зипфа») и закона, при котором удовлетворяется правило «80-20». На основе известных данных, характеризующих потребителей, именно такие законы распределения обращения к записям файла имеют место при обращении к БД. Данное обстоятельство подчеркивает необходимость и важность учета отмеченных законов при построении структур БД ГИС РВ.

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

К отмеченным особенностям следует добавить, что анализ зарубежных систем, а так же опыт использования известных ГИС РВ, показал преобладание запросов пакетного типа, когда число ДО в запросе составляет от 10% до 70%, от общего числа ДО в БД ГИС РВ, что обусловлено выполнением пространственных запросов по поиску ДО в рамках НЛ, представленных ЦКМ местности.

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

2.4.1. Последовательная организация данных.

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

Для такой структуры файла БД ГИС математическое ожидание времени поиска записи в файле БД ГИС, при условии блочного считывания с внешнего запоминающего устройства, может быть представлено формулой (1).

,             (1)

где jномер записи в файле БД ГИС; m – количество блоков; l – количество записей в блоке; r номер блока; t0 время поиска блока; t1 - время поиска записи в блоке, p(r-1)l+jвероятность обращения к записи файла БД ГИС.

Рассмотрим случай, когда вероятность обращения к записям файла БД распределена по равномерному закону (с = 0). В этом случае:

,               (2)

где N – количество записей в файле БД ГИС РВ.

Математическое ожидание времени поиска для равномерного закона может быть выражено формулой (3).

,           (3)

где jномер записи; m – количество блоков; l – количество записей в блоке; N – количество записей в файле БД ГИС РВ.

Преобразуя формулу (3), получим следующее выражение:          (4)

Дифференцируя (4) по l и находя корень полученного выражения с помощью формулы Кордано [80] определим количество записей в блоке, при котором математическое ожидание времени поиска записи в файле БД ГИС РВ будет минимальным:

,         (5)

где , а N, t0 ,t1  имеют тот же смысл, что и в формулах (1), (2).

При распределении вероятности по закону «Зипфа» (), (1) примет вид, как показано ниже:

,   (2.13)

где ; С =0,577– постоянная Эйлера; С1=0.5ln(2π).

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

Рассмотрим закон, при котором удовлетворяется правило «80-20» (с=0.8614), как один из наиболее распространенных случаев, когда . Формула (1) после преобразований и с учетом приближения сумм [62], примет вид:

,      (6)

где ; ;

.

Таким образом, были получены выражения для математического ожидания времени поиска записи в файле БД ГИС РВ.  

2.4.2. Файл БД ГИС, построенный на основе метода хеширования идентификатора.

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

Метод хеширования идентификатора (рис. 2.4.2) и получаемый в результате файл, широко распространен как метод доступа, обеспечивающий быструю произвольную выборку и обновление записей, однако в сильной степени зависит от «управляемости» значений ключа (значения поля перемешивания) и часто требует неоправданно больших служебных издержек памяти.

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

2.4.3. Индексно-последовательный файл.

Для индексно-последовательного файла (рис. 2.4.3) приведем лишь результаты проведенных исследований.

Выражение для вычисления значения количества записей в блоке, при которых математическое ожидание времени поиска записи в файле БД ГИС РВ будет минимальным, представлено в формуле (7). При равномерном, «Зипфа» и удовлетворяющем правилу «80-20» законах распределения вероятности обращения к записям файла БД ГИС выражения, при которых математическое ожидание времени поиска записи в файле БД будет минимальным, приведены в (8) – (10).

,          (7) где prlвероятность обращения к блоку записей БД ГИС, r[1,m], p(r-1)l+j – вероятность обращения к записи файла БД ГИС РВ.

;           (8)

     (9)

,        (10) где m, l, С, С1, НN,, t1, t0, c  – имеют тот же смысл, что и в формулах (1), (2), (3).

2.4.4. Файл БД ГИС, основанный на деревьях разбиения.

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

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

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

Ниже представлена предложенная соискателем, формула (11), позволяющая оценить время поиска записи в файле БД ГИС для древовидных структур:

,         (11)

где b определяется видом дерева разбиения, (например, для двоичного дерева b=2), m[1.. N].

Соответственно, для трех законов распределения вероятности обращения (равномерного, удовлетворяющего правилу «80-20», а так же «Зипфа») полученные автором выражения для математического ожидания времени поиска записи в файле БД ГИС представлены формулами (12) - (14).

.           (12)

.         (13)

,         (14)

где N, m, l, b, t1, t0, c  – имеют тот же смысл, что и в формулах (1), (2) и (3).

PAGE  5


1

l

1

m

N

2l

Рис. 2.4.1. Упорядоченный по значению первичного ключа последовательный файл.

Преобразование ключа в адрес

Ключ

23

8

32

1

3

7

5

Память (Блок)

Рис. 2.4.2. Метод хеширования идентификатора.

Файл БД ГИС

Рис. 2.4.3. Индексно-последовательный файл.

.

1

l

2l

1

N

2

1

m


 

А также другие работы, которые могут Вас заинтересовать

32154. Цепочка стоимости и система стоимости 24 KB
  Цепочка стоимости и система стоимости Виды деятельности при конкуренции в какойлибо конкретной отрасли можно разделить на категории. Они объединены в так называемую цепочку стоимости. Все виды деятельности входящие в цепочку стоимости вносят свой вклад в конечную потребительскую стоимость продуктатовара. Выбранная конкурентная стратегия определяет способ которым организация выполняет отдельные виды своей деятельности а также всю цепочку стоимости в целом.
32155. Переход от стратегического планирования к стратегическому менеджменту 36.5 KB
  Переход от стратегического планирования к стратегическому менеджменту Предшественником стратегического планирования была система долгосрочного планирования longrnge plnning. В арсенал новых методов используемых стратегическим планированием входят: модели анализа инвестиционных портфелей компаний разработка ситуационных планов развития применение сценарного планирования использование систем экспертных оценок применение различных аналитических матриц для исследования альтернатив возможного стратегического развития и т. Некоторые...
32156. Модели стратегического менеджмента 27 KB
  Модели стратегического менеджмента Одно из классических образных представлений о стратегическом мышлении в отличие от других видов мышления сделано К. В соответствии с моделью укрупненными являются следующие три этапа или фазы стратегического цикла организации: 1 стратегический анализ; 2 разработка стратегии стратегический синтезразвитие; 3 реализация стратегии. Отметим что рассматриваемая модель характеризует стратегическое управление организации и как органичную систему. В рамках предлагаемой модели стратегический...
32157. Анализ внешней среды организации. SWOT-анализ и PEST 38 KB
  Анализ внешней среды организации. К особенностям целевого SWOТ анализа при исследовании внешней среды организации относятся следующие. Вовторых анализ сильных и слабых сторон организации на втором этапе желательно увязывать с соответствующими результатами которые были выявлены и зафиксированы на первом этапе. Но и ценность любого тщательно просчитанного оптимального решения если оно появляется слишком поздно становится равной нулю На основании последовательного рассмотрения этих факторов принимаются решения по корректировке целей и...
32158. Анализ внутренней среды организации. SNW-анализ 26.5 KB
  Анализ внутренней среды организации. SNWанализ Исследование внутренней среды организации как части стратегического анализа представляет отдельный блок. Анализ внутренней среды организации осуществляемый во имя ее стратегических целей так же как и стратегический анализ внешней среды должен быть системным и многофакторным. При стратегическом анализе вся внутренняя среда организации и ее отдельные подсистемы и компоненты рассматриваются как стратегический ресурс развития организации.
32159. Стратегические беседы. Первичный формат сценарного планирования 27 KB
  Стратегические беседы Особую роль в становлении высокой стратегической культуры организации может сыграть система так называемых стратегических бесед strtegic converstions. Один из результативных способов построения системы стратегических бесед это проведение в организации серии беседдиалогов между соответствующими менеджерами и специалистами в процессе освоения и или развития метода сценарного планирования. Сценарный метод был разработан для того чтобы в коммерческой организации сформировать некоторое общее понимание...
32160. Восемь шагов методики сценарного планирования по П. Шварцу 30.5 KB
  Первый критерий это важность каждого фактора для принятия стратегических решений уровня шага 1. Второй критерий степень неопределенности по факторам уровней шага 3 и шага 2 для решения стратегических вопросов уровня шага 1. 5Выявление логики каждого сценария Результатом данного шага должны стать так называемые логические стержни т. суть в том чтобы выйти на относительно небольшое число сценариев которые являются действительно существенно разными по критерию содержания решений принимаемых по стратегическим вопросам уровня шага 1.
32161. Министратегии организации 26.5 KB
  Министратегии организации Министратегия организации состоит из трех элементов: миссии целей и стратегических приоритетов. Миссия это главная цель организации которая может быть сформулирована в относительно общем виде но при этом обязана достаточно четко выражать основную причину существования именно данной организации. Цели должны полностью раскрывать целевой аспект всей деятельности организации. В результате своеобразного синтеза стратегических целей организации и системы приоритетов по ее ресурсам получается система стратегических...
32162. Определение миссии, цели, стр. приоритетов организации 28.5 KB
  приоритетов организации С помощью министратегии выстраивается простейший так называемый управленческий мост от стратегии организации к ее тактической деятельности. Миссия это главная цель организации которая может быть сформулирована в относительно общем виде но при этом обязана достаточно четко выражать основную причину существования именно данной организации. Миссия стратегического управления организации это ее наиболее общая цель. Конкретная формулировка миссии утверждается руководством организации.