Лекция 6. Геоинформационные структуры данных Харитонов А. Ю. Министерство образования и науки Украины Донецкий национальный технический университет Кафедра компьютерных систем мониторинга ГЕОИНФОРМАЦИОННЫЕ СИСТЕМЫ

2 Неупорядоченные файлы Единственное преимущество такой структуры файла - для добавления новой записи нужно просто поместить ее в конец файла. Пример: база данных содержит 200'000 записей.. Если, для выборки одной записи требуется одна секунда, то поиск займет (в среднем) (n+1)/2 операций, то есть почти 28 часов для поиска одной записи. © Харитонов А. Ю.

3 Последовательно упорядоченные файлы - могут использовать буквы алфавита, или числа, которые тоже имеют определенную последовательность. Стратегия поиска - поиск делением пополам (или дихотомия). Среднее количество операций в этой стратегии определяется как log2(n+1). © Харитонов А. Ю.

4 Индексированные файлы внешний индекс - из исходного файла в новый файл копируются значения одного атрибута для всех записей вместе с положениями этих записей. Каждая запись в новом файле состоит из значения атрибута и адреса записи в исходном файле, из которой это значение было взято. Затем упорядочиваем записи нового файла в соответствии со значениями атрибута. Чтобы найти запись с заданным значением атрибута, в новом файле используется поиск делением пополам. Найдя нужные записи в индексном файле, получаем адреса записей исходного файла, по которым получаем все атрибуты объектов. © Харитонов А. Ю.

5 Иерархическая структура данных взаимосвязь между данными, называемая отношением "один ко многим: каждый элемент данных имеет прямую связь с некоторым числом "потомков", и каждый такой потомок, в свою очередь, может иметь связь со своими потомками и т.д. Такая система иллюстрируется иерархической системойклассификации растений и животных, называемой таксономией. © Харитонов А. Ю.

6 Иерархическая структура данных Ветвление основано на формальных ключевых признаках, которые определяют продвижение по этой структуре от одной ветви к другой.

7 Сетевые структуры - отношение "многие ко многим", при котором один элемент может иметь многие атрибуты, при этом каждый атрибут связан явно со многими элементами. C каждым элементом данных связан указатель (pointer), который направляет ко всем другим элементам данных, связанным с этим. Вместо того, чтобы ограничиваться древовидной структурой связей, каждый отдельный элемент данных может быть прямо связан с любым местом базы данных, без введения отношения "предок-потомок". © Харитонов А. Ю.

8 Реляционные базы данных данные хранятся как упорядоченные записи или строки значений атрибутов. Они группируются в отдельных строках в виде отношений (relations), поскольку они сохраняют свои положения в каждой строке и определенно связаны друг с другом. Каждая колонка содержит значения одного атрибута для всего набора объектов. Атрибуты объектов могут также объединяться в другие, связанные, таблицы. Реляционные системы основаны на наборе математических принципов, называемых реляционной алгеброй или алгеброй отношений © Харитонов А. Ю.

9 Реляционные базы данных

10 Реляционные базы данных Реляционные системы основаны на наборе математических принципов, называемых реляционной алгеброй или алгеброй отношений. Реляционные системы позволяют собирать данные в достаточно простые таблицы, при этом задачи организации данных также просты. При необходимости можно стыковать строки из одной таблицы с соответствующими строками из другой таблицы, используя связующий механизм, называемый реляционным соединением. © Харитонов А. Ю.

11 Первая нормальная форма - утверждает, что таблица должна состоять из строк и колонок и, поскольку колонки будут использоваться в качестве ключей поиска, в каждой из них на каждой строке должно находиться только одно значение. Представьте себе, как трудно было бы искать информацию по названию, если бы колонка названия имела по несколько значений в каждой строке. © Харитонов А. Ю.

12 Вторая нормальная форма - требует, чтобы каждая колонка, не являющаяся первичным ключом, полностью зависела от первичного ключа. Это упрощает таблицы и уменьшает избыточность ограничением, что каждая строка данных может быть найдена только через ее первичный ключ. Если вы хотите найти заданную строку, используя другие отношения, то вы можете использовать реляционное соединение вместо того, чтобы дублировать колонки в разных таблицах. © Харитонов А. Ю.

13 Третья нормальная форма - требует, чтобы колонки, которые не являются первичным ключом, "зависели" от первичного ключа, в то время, как первичный ключ не зависит от какого-либо не первичного ключа. Другими словами, вы должны использовать первичный ключ для поиска значений в других колонках, но вам не нужно использовать другие колонки для поиска значений в колонке первичного ключа. Цель, опять же, уменьшение избыточности, использование наименьшего числа колонок. © Харитонов А. Ю.