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


 

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

62925. Воспитание патриотизма на уроках музыки в начальной школе 40.68 KB
  Теоретические основы патриотического воспитания школьников Патриотическое воспитание школьников: цель задачи принципы. Возрастные особенности младших школьников. Общетеоретическое значение для изучения педагогических аспектов патриотического воспитания...
62928. Вторая мировая война: причины, итоги, уроки 97.49 KB
  Пора разобраться с этим вопросом и сказать союзникам простое человеческое спасибо ибо 9 Мая –день окончательной победы над фашизмом –день одинаково важный для фронтовиков –участников Второй мировой войны.
62929. Структура Уголовного кодекса; правила квалифицирования 8 MB
  Задачи: дать детям начальные знания о правовой системе РФ; объяснить актуальность изучения уголовного права; показать взаимосвязь поступков и характеров для развития в детях стремления к сознательному самовоспитанию; предупредить о последствиях противоправного поведения...
62930. Моделирование и стилизация национального костюма народов Поволжья (на примере костюма Казанских татар XIX-начала XX вв.) 15.65 KB
  Цель: изучение самобытных древних традиций становления национального костюма и использование в стилизации и моделировании костюма в создании образа авторской куклы. Развивать познавательное ориентированное отношение к стилистическим элементам национального костюма казанских татар...
62932. Як музика розповідає про зиму? 252.82 KB
  Давайте привітаємось Я до вас а ви до мене. Давайте проспіваємо поспівку Під березу їжачок. Співаю Давайте візьмемо нотку ля розспівуємося А зараз давайте всі разом заспіваємо: Під березу їжачок наносив сінця стіжок.