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


 

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

49724. Совершенствование обязательно документированных процедур 1004.28 KB
  АНАЛИЗ ПРОЦЕДУРЫ ПРОВЕДЕНИЯ АУДИТА. КРАТКОЕ РАЗЪЯСНЕНИЕ ЭТАПОВ АУДИТА. Аудит систематический независимый и документированный процесс получения свидетельств аудита и объективного их оценивания с целью установления степени выполнения согласованных критериев аудита Аудитор лицо обладающее компетентностью для проведения аудита
49725. Оценка кредитоспособности физического лица 346 KB
  Целью данной курсовой работы является оценка кредитоспособности клиента от различных параметров. Основными задачами настоящей курсовой работы являются: Изучение факторов, влияющих кредитоспособность; Изучение принципов работы нейросети с использованием программы «Нейросимулятор»;
49726. ТЕПЛОВЫЕ И МЕТАЛЛУРГИЧЕСКИЕ ПРОЦЕССЫ ПРИ СВАРКЕ 658.36 KB
  Цель работы разработка методики теплового расчета расчетов химического состава металла оценки равновесной концентрации кислорода и оценки стойкости металла шва к образованию горячих трещин. В результате исследования было рассчитано и построено температурное поле определен химический состав металла шва по смешению и с учетом коэффициентов перехода определена концентрация кислорода и оценена стойкость металла шва к образованию горячих трещин.1 Расчет состава металла шва 16 6.3 Оценка склонности металла шва к образованию горячих трещин 27...
49728. Проблема оценки эффективности инвестиционных проектов на действующих промышленных предприятиях 252.33 KB
  Инновационная деятельность – одна из важнейших составляющих деятельности любого предприятия, в том числе и промышленных. Без составления и грамотной реализации инвестиционной стратегии невозможно достижение и поддержание в долгосрочном плане не только конкурентных преимуществ предприятия, но и его нормального функционирования.
49729. Технические возможности способов сварки плавления, изделия кожух камеры сгорания изготовленного из сплава алюминия АМг-3, толщиной металла 4 мм 319 KB
  Сварка алюминия и его сплавов Металлургические особенности сварки алюминия и его сплавов определяются взаимодействием их с газами окружающей среды интенсивностью испарения легирующих элементов а также особенностями кристаллизации в условиях сварки. Ручная дуговая сварка неплавящимся вольфрамовым электродом в инертных газах с присадочной проволоки; Ручная дуговая сварка неплавящимся вольфрамовым электродом в инертных газах без присадочной проволоки; 3. Автоматическая сварка неплавящемся электродом в инертных газах с присадочной...
49731. Проектирование «АРМ менеджера «Издательской компании «Лада» и разработка отдельных его компонентов 257.5 KB
  Это какая продукция какой тираж какие работы должны быть выполнены какие материалы будут использованы при выполнении обговорить ориентировочную стоимость заказа. Таблица Вспомогательные материалы: хранит информацию о дополнительных материалах используемых на производстве например фольга пленка для ламинирования клей декстрин. Таблица Переплетные материалы: хранит информацию о переплетных материалах используемых в производстве например бумвинил эфолин. Таблица Поставки: является связующей между таблицами Бумага Вспомогательные...