Лекция №5

План лекции № 5

1.Основные структуры компьютерных файлов

2.Базы данных (общие вопросы)

Черепанова Екатерина Сергеевна, к.г.н., кафедра картографии и геионформатики

Важнейшая функция ГИС:

хранение объектов и их атрибутов таким образом,

который позволяет нам выбирать, например, для отображения, любую комбинацию этих объектов.

Это требует от компьютера способности хранить, отыскивать и выбирать записи, устанавливать

перекрестные ссылки. Другими словами, каждый графический объект должен храниться в явном виде,

вместе со своими атрибутами, так, чтобы мы могли выбирать нужную их комбинацию за приемлемое время.

Например, имеем список

имен, адресов и номеров телефонов.

Неупорядоченные файлы

простейшая структура файла – неупорядоченный массив записей

В примере с именами и адресами это будет выглядеть

так: создание для каждого имени в картотеке отдельной карточки в порядке поступления данных о человеке (последовательности их ввода)

Сидоров, улица Букирева, 7, 2396345

Иванов, улица Данщина, 5, 2396856 Петров, улица Генкеля, 6, 2396789

Преимущество: для добавления новой записи

нужно просто поместить ее в конец файла, позади всех других записей

Недостаток:

длительный поиск

отсутствие упорядоченности

при большом количестве записей – найти данные

быстро - невозможно.

Например, наша база данных содержит 200'000 записей.

Если файл неупорядочен, то нам, возможно, потребуется просмотреть все 200'000 записей, чтобы найти нужную.

Если, например, для выборки одной карточки требуется одна секунда, то поиск займет (в среднем) (n+1)/2

операций [Burrough, 1983], то есть почти 28 часов для поиска одной записи.

Следовательно, нам нужно провести какие-то

организационные мероприятия для повышения эффективности поиска.

Последовательно упорядоченные файлы

Большинство картотек ( и телефонные справочники в том числе) упорядочены по алфавиту.

Этот метод использует сравнение каждой новой записи с имеющимися для определения того, где ее место. Такие последовательно упорядоченные

файлы могут использовать буквы алфавита, как в

нашем примере с картотекой, или числа, которые тоже имеют определенную последовательность.

Обычная стратегия поиска упорядоченной таким образом информации является поиск делением пополам (дихотомия)

Поиск начинается разделением всего массива записей на две половины и выборкой записи в середине. Если она оказывается той, что нужна, то процедура поиска закончена. Если искомая запись находится прежде выбранной, то мы выполняем ту же операцию с первой

половиной, если после — со второй. Таким образом, программе не требуется просматривать большую часть

файла. В нашем прежнем примере время поиска

сокращается до немногим более двух часов вместо прежних 28-ми.

В обоих предыдущих примерах записи идентифицировались и сравнивались по ключевому атрибуту - слову или числу. Стратегия поиска была основана на значениях самих ключевых атрибутов.

Элементы, которые мы ищем в ГИС, это главным образом точки, линии и области.

Однако вряд ли мы будем искать их по присвоенным

им номерам. Другими словами, мы не будем запрашивать ГИС отобразить линию номер 3001 (ее

порядковый номер при вводе в систему).

Каждому объекту даются некие описательные

атрибуты (характеристики), поэтому чаще всего

ищутся элементы с определенным набором атрибутов. Так, например, вы могли бы попросить ГИС отыскать для отображения и анализа все районы Пермского края с населением менее 16 тысяч человек и площадью менее 3000 км2.