Тема 5. Методы организации данных в эис
Введение.
Организация значений данных – относительно устойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения связей между ними.
Область применения методов организации данных - базы и банки данных.
Необходимые знания: понимание процессов, происходящих при представлении информации в ЭИС.
Список изучаемых разделов лекции:
Анализ алгоритмов и структур данных.
Методы ускорения доступа к данным.
Организация данных во внешней памяти ЭВМ.
Словарь терминов.
СЕИ - набор из атрибутов или других составных единиц информации (СЕИ).
ЗАПИСЬ – отдельное значение СЕИ, находящееся в памяти ЭВМ.
КЛЮЧЕВОЙ АТРИБУТ (атрибут-признак) –атрибут, имя которого одинаково во всех записях
ПОИСК –процедура выделения некоторых записей, удовлетворяющих заранее поставленному условию.
СОРТИРОВКА – процедура, осуществляющая перестановку СЕИ с целю упорядочения значений некоторого ключевого атрибута
КОРРЕКТИРОВКА – процедура включения, исключения, изменения значений отдельных неключевых атрибутов в записях.
СПИСОК – множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи.
ИНДЕКС – набор ключей и адресов записи, которые выбираются из основного массива по определенному закону.
Анализ алгоритмов и структур данных.
Основная информационная структура – запись.
Запись состоит из значений атрибутов, входящих в структуру СЕИ.
Множество записей образует массив (при хранении в ОЗУ) или файл (при хранении на внешних носителях).
Виды организации данных: линейная и нелинейная.
При линейной организации данных каждая промежуточная запись связана с одной предыдущей и одной последующей записью.
При нелинейной организации данных количество предыдущих и последующих записей произвольное.
Формула адреса промежуточной записи фиксированной длины:
A(i) =A(1) + (i-1) *L,
где A(1) - начальный адрес первой записи,
A(i) - начальный адрес i-той записи,
L – длина одной записи.
Последовательная организация данных:
Условие упорядоченности:
p(i)<= p(i+1) - упорядоченность по возрастанию;
p(i)>= p(i+1) упорядоченность по убыванию.
Алгоритмы обработки данных:
Формирование данных
Сортировка (упорядочение по значению ключевых атрибутов)
Поиск и корректировка
Последовательная обработка.
Критерии эффективности алгоритмов:
Время формирования данных,
Время поиска данных (используется поиск по совпадению – нахождение записей, значения ключевого атрибута которых равно заранее известной величине q).
Время корректировки данных (включение или исключение одной записи)
Объем дополнительной памяти, расходуемой под служебную информацию (например, на адреса связи).
Допущения при анализе алгоритмов обработки данных:
Равномерное распределение значений ключевых атрибутов в массиве из М записей,
Значение q при поиске по совпадению выбрано случайно (поиск с одинаковой вероятностью 1\ М может закончится на любой записи массива)
Положение включаемой (исключаемой) записи при корректировке определяется теми же вероятностями, что при поиске.
Минимальное количество сравнений C записей для упорядочения массива:
C ~ M ×log2M
Время сортировки данных:
Т~ M ×log2M