Теория экономических информационных систем Методы организации данных

Основные понятия Методы хранения данных в памяти компьютера предполагают раздельное хранение значений каждой СЕИ. Отдельное значение СЕИ в памяти компьютера называется записью. Запись включает в себя значения атрибутов, входящих в состав СЕИ. Множество записей образует массив. Под организацией значений данных понимается относительно устойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения взаимосвязи между записями.

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

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

Последовательная организация данных При последовательной организации данных записи располагаются в памяти строго одна за другой. Записи составляющие массив разделяются на записи: Фиксированной длины – имеют одинаковую, заранее известную запись; Переменной длины – длина записи указывается в самой записи; Неопределенной длины – окончание записи помечается специальным символом – разделителем записей. Для массива записей постоянной длины адреса промежуточных записей в массиве могут быть определены по простой формуле: A(i)=A(1)+(i-1)*L, где A(i) – адрес i-й записи, L – длина записи

Ключевые атрибуты записи В структуре записей последовательного массива обычно выделяется один или несколько ключевых атрибутов, по значениях которых осуществляется доступ к остальным значениям атрибутов записи. Рассмотрим последовательный массив записей фиксированной длины, имеющий единственный ключевой атрибут. Обозначим данный атрибут как p(i), где i – номер записи. Общее число записей массива пусть будет равным M.

Упорядоченность данных массива Записи массива могут быть упорядоченными или неупорядоченными по значениям ключевого атрибута, имя которого одинаково во всех записях. В качестве ключевого реквизита выступает, как правило, атрибут-признак. Условие упорядоченности записей в массиве определяется следующим образом: p(i) p(i+1) – упорядоченность по возрастанию; p(i) p(i+1) – упорядоченность по убыванию. Если требуется поддерживать упорядоченность по нескольким ключевым признакам, то среди признаков устанавливается старшинство.

Обработка данных Наиболее часто используемыми алгоритмами обработки данных являются: Формирование данных; Поиск данных; Корректировка данных; Последовательная обработка. Данные возникают в неупорядоченной форме. Перед обработкой целесообразно упорядочить их по значениям ключевого атрибута. Процедуру упорядочивания называют операцией сортировки – одна из основных операций по формированию данных. Упорядоченные данные эффективны для организации быстрого поиска информации.

Критерии эффективности алгоритмов Для оценки эффективности алгоритма служит время его выполнения в зависимости от ряда параметров хранимой информации. Для каждого метода организации данных анализируются следующие величины: время формирования данных – время создания в памяти компьютера упорядоченного представления данных; время поиска данных (например, поиск по совпадению – найти запись, значение ключевого атрибута которой совпадает с заранее заданной величиной q); время корректировки данных (например, включение и исключение записи); объем дополнительной памяти, используемой под служебную информацию. Поскольку на скорость выполнения алгоритма влияет ряд факторов независящих от природы самого алгоритма (быстродействие компьютера, язык программирования и т.д.) при оценке эффективности алгоритмов анализируется количество выполняемых элементарных операций (таких как сравнение значений ключевого атрибута записи с заданной величиной).

Допущения применяемые при анализе алгоритмов Для простоты рассмотрения вводится ряд допущений, обеспечивающих использование равномерного распределения вероятностей: распределение значений ключевого атрибута в массиве – равномерное; значение q при поиске по совпадению выбрано случайно (это означает, что поиск с одинаковой вероятностью 1/M может закончится на любой записи массива); Положение включаемой (исключаемой) записи при корректировке массива определяется теми же вероятностями, что и при поиске.

Сортировка последовательного массива Массив, обладающий наибольшей неопределенностью называется случайным массивом. Все его M! состояний равновероятны. Минимальное число сравнений C при выполнении упорядочивания массива с числом записей M задается формулой C=log M! По формуле Стирлинга при больших M можно переписать данное выражение в виде: C=M (logM – 1.43) Или С M log M Данная формула и определяет порядок времени сортировки.

Поиск в последовательном массиве Поиском называют процедуру выделения из множества записей некоторого подмножества, удовлетворяющего некоторому заранее поставленному условию. Простейшее условие – поиск по совпадению. Базовый метод поиска – ступенчатый поиск. Рассматривается заранее упорядоченный массив. Простейший вариант ступенчатого поиска – последовательный поиск. Алгоритм поиска: Искомое значение сравнивается с ключом первой записи, далее второй и до тех пор пока искомое значение атрибута q не станет больше ключа очередной записи. Оценка числа необходимых операций C ~ M (числу записей массива)

Поиск в последовательном массиве Двухступенчатый поиск в массиве. Для заданного M выбирается константа d, называемая шагом поиска. При поиске записи со значением ключевого атрибута – q, производятся действия: Искомое значение q последовательно сравнивается с величинами P(1), P(1+d), P(1+2d) и т.д. до тех пора не будет достигнуто равенство P(1+m*d) q. На тором этапе q последовательно сравниваются со всеми ключами имеющими номера 1+m*d и больше, пока не будет достигнут ключ, больший чем q. Количество операций для поиска оценивается в данном случае C ~ SQRT(M)

Поиск в последовательном массиве Частный вариант ступенчатого поиска – бинарный поиск. При бинарном поиске упорядоченный массив разбивается последовательно на два подмножества. Ключ серединной записи сравнивается с заданным атрибутом поиска q. Из данного сравнения выбирается левое или правое подмножество записей и процесс повторяется. Число необходимых операций для выполения поиска оценивается формулой С ~ log M

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

Добавление записи в массив При добавлении записи необходимо не нарушать упорядоченность массива. Поэтому: сначала ищется положение новой записи выполняется пересылка записей для освобождения места (начинается с последней записи) выполняется собственно включение новой записи на освободившееся место. Количество операций для выполнения операций по перемещению записей оценивается формулой: C ~ log M + M*L, где L – длина одной записи

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

Процедура слияния массивов Процедура получения массива С слиянием массивов A и B включает следующие шаги: открываются все три массива, причем указатели в них устанавливаются на 1 (первой записи). сравниваются ключи текущих записей файлов A и B, причем запись с меньшим ключом переносится в файл C. При этом указатели массива C и массива, из которого взята текущая запись, увеличиваются на 1. предыдущий шаг повторяется до тех пор, пока не будет достигнут конец массива A или B. Если достигнут конец одного из массивов, то остаток второго массива переписывается без дальнейших сравнений в массив B.

Цепная организация данных Списковой (цепной) организацией данных называется множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. Адрес связи – атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. В списке выделяется собственная информация и ассоциативная информация (адреса связи). Возможны два способа организации списка: Совместное размещение собственной и ассоциативной информации Раздельное размещение записей и ассоциативной информации. При списковой организации необходим специальный атрибут, называемый указателем списка, содержащий начальный адрес. Кроме того, адрес связи последней записи содержит специальное значение, называемое концом списка.

Цепная организация данных При формировании упорядоченного списка возможны два варианта: Каждая новая запись размещается в списке так, чтобы не нарушать упорядоченность по ключу; Сначала создается неупорядоченный список, а затем выполняется его сортировка. Число операций формирования упорядоченного списка задается формулой: C ~ M log M.

Поиск данных в списке Для поиска данных в однонаправленном списке используется единственный метод – последовательный поиск. Число необходимых операций задается формулой: C ~ M. Для ускорения доступа к списку рекомендуются варианты использования адресов связи, такие как Двунаправленный список – образован двумя цепочками адресов связи – от первой записи к последней и от последней записи к первой; Кольцевой список – последний адрес связи указывает на первую запись.

Древовидная организация данных Древовидной организацией данных называется множество записей, расположенных по уровням следующим образом: на 1 уровне располагается только одну запись (корень дерева); к любой записи i-го уровня ведет адрес связи только от одной записи уровня i-1. Количество уровней в дереве называется рангом. Записи дерева, которые адресуются от общей записи (i – 1) уровня, образуют группу. Максимальное число элементов в группе называется порядком дерева.

Бинарные деревья Деревья порядка 2 называются бинарными. Записи бинарного дерева могут быть упорядочены. Для этого необходимо объявить один из атрибутов записи ключевым. Записи бинарного дерева, у которых заполнены оба адреса связи, называются полными. Записи с одним заполненным адресом – неполные. Записи с двумя незаполненными адресами – кольцевыми. В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше чем ключ любой записи на ее правой ветви. При формировании упорядоченного бинарного дерева выполняется следующее число операций: C ~ 1,4 M*log M

Алгоритм построения упорядоченного бинарного дерева 1. Первая запись массива с ключом P(1) становится корнем дерева 2. Значение ключа P(2) сравнивается с P(1), находящемся в корне дерева. Если P(2)P(i)), или по правому (если P(1)

Алгоритм поиска по совпадению в упорядоченном бинарном дереве Искомое значение ключа q сравнивается со значением ключа корневой записи P(1). Если P(1)>q, просмотр продолжается по левой ветви, если P(1)q, или по правой – в противном случае. Поиск заканчивается, когда P(i)=q или у какой-либо записи отсутствует адрес связи, необходимый для продолжения алгоритма.

Сравнение методов организации данных Критерии оценки Методы организации данных Лучший метод последова- тельная цепнаябинарное дерево Время формирования ~ M log M цепной, бинарное дерево Время поиска~ log M~ M~ log M последователь-ный, бинарное дерево Время корректировки ~ M ~ log M бинарное дерево Объем дополнительной памяти 0~ M последователь-ный

Методы ускорения доступа к данным Для ускорения доступа к данным используются следующие подходы: Специальные методы размещения информации; Создание вспомогательных массивов о хранимой информации.

Адресная функция Расстановка записей в массиве производится с помощью так называемой адресной функцией. Методы организации данных при этом часто называются методами рандомизации. Адресная функция определяется как зависимость i = f(p), где i – адрес записи, p – значение ключевого атрибута. Адресная функция может вырабатывать одинаковые значение I для разных значений ключевого атрибута. В этом случае записи называются синонимами. Требования к адресной функции: Быстрота обработки Ключевые атрибуты, подчиняющиеся произвольному распределению должны преобразовываться в равномерное распределение Число синонимов не должно превышать 10-20% от общего числа записей.

Пример адресной функции Если значение ключевого атрибута p – целое число, то в качестве адресной функции можно использовать функцию: i = ОСТ(p/m) – остаток от деления p на m, где m – некоторое целое число (выбирается простое число непосредственно большее или меньшее числа записей массива). Выбирается две зоны памяти – основная и резервная. Основная включает в себя m записей. Резервная предназначена для размещения записей синонимов. При формировании данных согласно адресной функции вначале заполняется основная зона. Если при этом позиция основной зоны уже занята, то запись помещается в резервную зону и адресуется из этой позиции основной зоны.

Организация записей в соответствии с адресной функцией Пусть задан массив со значениями ключевого атрибута {17, 9, 4, 14, 25, 21, 20, 11}. В качестве m выберем 7. Резервная зона заполняется последовательно Адрес связи Ø 29Ø11Ø 317Ø Ø

Индексные файлы Для ускорения поиска записей используется дополнительная информация, организованная в виде массива индексов. Индексом называется набор ключей и адресов записей, которые выбираются из основного массива по определенному закону. Существуют три разновидности индексов: Информация о каждой записи основного массива попадает в индекс (сплошная индексация); Номера записей, информация о которой выносится в индекс, образует арифметическую прогрессию (индексно- последовательный массив); Ключи записей, включенные в индекс, приближенно образуют арифметическую последовательность (рандомизация индекса).

Сплошной индекс Сплошной индекс связан с созданием инвертированного массива ключевых атрибутов к основному массиву. Инвертированный список Должность(Сотрудники) имеет вид: Инженер – 01, 04 Технолог – 02, 03 СотрудникиЗарплата ФамилияДолжностьФамилияДатаЗарплата 01 ПетровИнженер05 Козлов КозловТехнолог06 Седова СедоваТехнолог07 Козлов РоговИнженер08 Петров Рогов Петров Седова

Индексно-последовательный массив Индексно-последовательный массив представляет собой последовательный массив, отсортированный по значениям ключевого атрибута, к которому создается дополнительный массив индексов. В индекс выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d. Поиск значения q в индексно-последовательном массиве выполняется в две стадии: В массиве индексов Среди записей основного массива, расположенных между двумя соседними индексами, найденными на первой стадии.

Индексно-последовательная организация данных Индекс

Рандомизированный индекс Если ключи записей, информация о которых выносится в индекс, приближенно организуют арифметическую прогрессию, речь идет о адресной функции для индекса (рандомизация индекса). В рандомизированном массиве индекс с номером n хранит адрес записи основного массива, ключ которого равен или непосредственно больше значения P(1) + z*(n-1) здесь z – константа (шаг арифметической прогрессии).

Рандомизация индекса Рандомизированный индексZ= Поиск в рандомизированной массиве идет в две стадии. На первой стадии номер индекс определяется по формуле n=(q-p 1 )/z + 1 Результат деления округляется в меньшую сторону. Интервал записей основного массива на второй стадии определяется адресами, указанными в n и n+1 индексах.

Организация данных во внешней памяти В качестве внешней памяти ЭВМ используются различные дисковые накопители информации, как правило, магнитные диски. Данные на внешних запоминающихся устройствах хранятся в виде файлов. Файл представляет собой именованную область на внешнем носителе. Как правило в файле БД помещается множество логически связанных записей. Внешняя память ЭВМ разбита на блоки (секторы), имеющие фиксированный размер. Величина этого размера не зависит от желания проектировщика системы. Обмен с оперативной памятью может выполнятся только целыми секторами.

Методы организации файлов на магнитном диске и доступа к данным Последовательная организации файла – доступ выполняется только от обработанной записи к последующей. Индексно-последовательный файл представляет собой последовательный файл, снабженный индексами.

Индексно-последовательный файл На магнитном носителе выделяются три области – первичная индексная и область переполнения. В первичной области помещаются упорядоченные по значениям ключевого атрибута записи, когда файл создается впервые. В зависимости от размера первичной области создаются один, два или три уровня индексов: Индекс первого уровня отмечает последнюю запись каждой дорожки магнитного диска; Индекс второго уровня отмечает последнюю запись каждого цилиндра магнитного диска. Если файл индекса второго уровня достаточно велик, то для него допускается создание третьего индекса. Область переполнения предназначена для размещения записей, включаемых в индексно-последовательный файл. Новые записи связываются в цепочку и размещаются на том цилиндре, при котором ключи новых записей соответствуют интервалу значений ключей в первичной области этого цилиндра.

Литература А.И. Мишенин. Теория экономических информационных систем. А.И. Мишенин, С.П. Салмин. Теория экономических информационных систем. Практикум.