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


 

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

19749. Порядок росжига, регулирования и остановка котлов, работающих на твёрдом, газообразном, жидком топливе 23.7 KB
  Порядок росжига регулирования и остановка котлов работающих на твёрдом газообразном жидком топливе РАСТОПКА КОТЕЛЬНОГО АГРЕГАТА 30. Растопка котла должна производиться в течение времени установленного руководством организации владельца котельной и указанн
19750. Допуск персонала к самостоятельной работе по обслуживанию котельных установок. Проведение противоаварийных тренировок персонала с целью предотвращения аварий 17.77 KB
  Допуск персонала к самостоятельной работе по обслуживанию котельных установок. Проведение противоаварийных тренировок персонала с целью предотвращения аварий Допуск к самостоятельной работе вновь принятые работники или имеющие перерыв в работе более 6 месяцев в за...
19751. Особенности эксплуатации паровых и водогрейных котлов. Пуск, обслуживание во время работы, остановка котла 19.18 KB
  Особенности эксплуатации паровых и водогрейных котлов. Пуск обслуживание во время работы остановка котла Учитывая местные особенности котельной установки конструкцию котла топки вид топлива расположение арматуры способ топливоподачи и золоудаления...
19752. Наблюдение за работой котла по показаниям эксплуатационных КИП. Составление теплового баланса по данным суточной ведомости 15.65 KB
  Наблюдение за работой котла по показаниям эксплуатационных КИП. Составление теплового баланса по данным суточной ведомости Во время работы водогрейного котла необходимо: поддерживать нормальное давление воды до и после котла не допуская его выше или ниже разрешенног
19753. Организация эксплуатации внутренних систем. Техническое освидетельствование трубопроводов и сосудов, работающих под давлением 16.83 KB
  Организация эксплуатации внутренних систем. Техническое освидетельствование трубопроводов и сосудов работающих под давлением Техническое освидетельствование сосуда работающего под давлением проводится: до пуска в работу первичное; после монтажа периодически...
19754. Организация эксплуатации тепловых сетей. Категорийность трубопроводов 16.24 KB
  Организация эксплуатации тепловых сетей. Категорийность трубопроводов На каждом предприятии должно быть организовано круглосуточное управление режимами работы теплопотребляющих установок и тепловых сетей задачами которого являются: ведение заданных режимов ра...
19755. Организация эксплуатации водонагревательного и теплоиспользующего оборудования 18.46 KB
  Организация эксплуатации водонагревательного и теплоиспользующего оборудования Э231. Для каждого водоподогревателя на основе проектных данных и испытаний должна быть установлена техническая характеристика со следующими показателями: а тепловая производительность...
19756. Порядок и сроки освидетельствования теплоиспользующего оборудования 17.95 KB
  Порядок и сроки освидетельствования теплоиспользующего оборудования Теплоиспользующие установки подвергаются наружному и внутреннему осмотру а также гидравлическому испытанию. Внутренний осмотр и гидравлическое испытание теплоиспользующих аппаратов подлежащи...
19757. Виды ремонта теплотехнического оборудования. Их планирование и организация. Основные неисправности, возникающие при эксплуатации котлов и теплотехнического оборудования 18.3 KB
  Виды ремонта теплотехнического оборудования. Их планирование и организация. Основные неисправности возникающие при эксплуатации котлов и теплотехнического оборудования капитальные ремонты. Текущий ремонт выполняют за счет оборотных средств а капитальный за счет