Теория экономический информационных систем Тема: «Методы организации данных» Автор: Лаврушина Е.Г.
Модели организации данных Под организацией значений данных понимают относительно устойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения взаимосвязи между записями. Методы хранения данных в памяти ЭВМ обычно предполагают раздельное хранение значений каждой составной единицы информации (СЕИ). Отдельное значение СЕИ, находящееся в памяти ЭВМ, называется записью. Запись состоит из значений атрибутов, входящих в структуру СЕИ. Множество записей образует массив, или файл. Термин массив обычно используется при рассмотрении данных в оперативной памяти ЭВМ, а термин файл применяется для данных, хранимых на внешних запоминающих устройствах. Как правило, файл содержит записи, принадлежащие одной и той же СЕИ, хотя в общем случае это не является обязательным.
Организация значений данных Линейная При линейной организации данных каждая запись, кроме первой и последней, связана с одной предыдущей и одной последующей записями. Линейные методы организации данных различаются только способами указания предыдущей и последующей записи по отношению к данной записи. Алгоритмы, эффективные для одних методов организации данных, становятся неприемлемыми для других методов. Нелинейная У записей, соответствующих нелинейной организации данных, количество предыдущих и последующих записей может быть произвольным.
Линейные методы организации данных Среди линейных методов выделяются последовательная и цепная организации данных. При последовательной организации данных записи располагаются в памяти строго одна за другой, без промежутков, в той последовательности, в которой они обрабатываются. Последовательная организация данных обычно и соответствует понятию массив (файл). Записи, составляющие массив, с точки зрения способа указания их длины делятся на записи фиксированной, переменной и неопределенной длины. Записи фиксированной (постоянной) длины имеют одинаковую, заранее известную длину, Если длины записей неодинаковы, то длина указывается в самой записи. Такие записи называют записями переменной длины. Вместо явного указания длины записи можно отмечать окончание записи специальным символом-разделителем, который не должен встречаться среди информационных символов значения записи. Записи, заканчивающиеся разделителем, называются записями неопределенной длины.
Адреса промежуточных записей адреса промежуточных записей фиксированной длины в массиве задаются формулой A(i) = A(l)+(i-l)*L, ! где A(l) - начальный адрес первой записи; A(i) - начальный адрес i-й записи; L - длина одной записи. для массива записей переменной и неопределенной длины подобной простой формулы не существует. Они занимают меньший объем памяти, но их обработка ведется с меньшей скоростью, поскольку затруднено обнаружение следующей записи.
Упорядочение записей при линейной организации данных В структуре записей последовательного массива обычно выделяется один или несколько ключевых атрибутов, по значениям которых происходит доступ к остальным значениям атрибутов той или иной записи. Состав ключевых атрибутов необязательно соответствует понятию первичного ключа. Ключевые атрибуты в записях обозначаются через p(i), где i - номер записи, общее число записей в массиве обозначается через М. Записи массива могут быть упорядоченными или неупорядоченными по значениям ключевого атрибута (ключа), имя которого одинаково во всех записях. Ключевой атрибут обычно является атрибутом-признаком. Часто требуется поддерживать упорядоченность записей по нескольким именам ключевых признаков. В этом случае среди признаков устанавливается старшинство. Условие упорядоченности записей в массиве (и вообще для линейной организации данных) выглядит следующим образом: р (i) < = р (i + 1) - упорядоченность по возрастанию; p(i) >= p(i+l) - упорядоченность по убыванию. Наиболее важными и часто применяемыми алгоритмами обработки данных являются формирование данных, их поиск и корректировка, а также последовательная обработка. Эти алгоритмы могут быть реализованы с использованием достаточно большого количества методов организации данных. Далее будем считать все массивы упорядоченными по возрастанию значений одного атрибута, когда для ключа i-й записи p(i) справедливо условие p(i)
Критерии эффективности алгоритма по времени его выполнения в зависимости от ряда параметров хранимой информации Для каждого метода организации данных требуется анализировать следующие величины: время формирования данных; время поиска данных; время корректировки данных; объем дополнительной памяти, расходуемой под служебную информацию. На время выполнения алгоритмов влияет, однако, ряд факторов, которые не хотелось бы рассматривать при теоретическом анализе алгоритмов. Среди них - быстродействие конкретной ЭВМ, применяемый язык программирования, стиль программирования конкретного программиста. Чтобы можно было не принимать во внимание подобные факторы, целесообразно анализировать не время, а количество выполняемых элементарных операций, в частности операций сравнения значений ключевых атрибутов и искомых величин. Время выполнения алгоритма обычно прямо пропорционально числу требуемых сравнений, и подобная замена критерия эффективности алгоритма вполне законна
Ряд допущений, обеспечивающих использование равномерного распределения вероятностей для всех случайных величин, описывающих работу алгоритма распределение значений ключевых атрибутов в массиве из М записей - равномерное; значение q при поиске по совпадению выбрано случайно: это означает, что поиск с одинаковой вероятностью 1/М может закончиться на любой записи массива; положение включаемой (исключаемой) записи при корректировке определяется теми же вероятностями, что и при поиске. Минимальное число сравнений при упорядочении последовательного файла можно определить, не рассматривая ни одного конкретного алгоритма с помощью рассуждений, характерных для теории информации. Процедура упорядочения состоит из серии сравнений ключевых атрибутов и тех или иных перераспределений записей по результатам сравнения. Массив, обладающий наибольшей неопределенностью своего состояния, будем называть случайным массивом. Все его М! состояний равновозможных. Через М! обозначено произведение М.
Критерии эффективности алгоритмов Минимальное число сравнений, необходимое для упорядочения массива из М записей, определяется как С = log М!, что соответствует минимально возможному числу вопросов о состоянии массива с возможными ответами типа: «да – нет». Функция log обозначает логарифм по основанию 2. После преобразований по формуле Стерлинга получаем: C=M-(logM-1.43). В анализе алгоритмов принято учитывать в подобных формулах лишь те слагаемые, которые ощутимо влияют на общую сумму (разность). Соответствующее преобразование выглядит как С ~ М log М (читается: С пропорционально М logM). Справедлива запись выражения для времени сортировки Т ~ М log М.
Цепная (списковая) организация данных Списком называется множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. Адресом связи некоторой записи называется атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработки записей в списке определяется возрастанием значений ключа в записях. В списке выделяется собственная информация (записи с содержательными сведениями) и ассоциативная информация, т. е. все адреса связи. Описание записей списка может быть произведено двумя способами: Определение адресов связи как начальных адресов записей: Определение адресов связи как номеров записей Второй вариант является более практичным, особенно если требуется хранить список на внешнем запоминающем устройстве.
Способы организации списка совместное размещение собственной и ассоциативной информации, когда запись и ее адрес связи образуют одно целое раздельное, когда имеется списковая организация адресов связи и последовательное хранение собственной информации При списковой организации данных необходим специальный атрибут, называемый указателем списка, который содержит начальный адрес или номер первой в порядке обработки записи списка. Кроме того, адрес связи последней записи списка должен содержать специальное значение, называемое концом списка и отмечающее, что последующих записей у данной записи нет. Обычно конец списка отмечается нулем. Для ускорения доступа к списку могут быть рекомендованы такие варианты использования адресов связи, как двунаправленный и кольцевой список: двунаправленный список образован двумя цепочками адресов связи - от первой записи к последней и от последней записи к первой; в кольцевом списке последний адрес связи указывает на первую запись.
Формирование упорядоченного списка записей При формировании упорядоченного списка записей возможны два варианта: вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу; создать сначала неупорядоченный список, а затем отсортировать его. Время формирования упорядоченного списка пропорционально T~M-logM. Для поиска в упорядоченном списке можно использовать те же методы, что и в последовательном массиве, однако эффективность этих методов иная, поскольку адреса связи создают возможность быстрого доступа только к следующей записи списка. Для поиска данных в однонаправленном списке используется единственный метод - последовательный поиск. Ключевой атрибут первой записи (ее адрес извлекается из указателя списка) сравнивается с искомым значением q, затем такое же сравнение выполняется для ключа второй записи, которая извлекается по адресу связи первой записи, и т. д. Время поиска пропорционально Т~М. Неэффективность бинарного поиска для списковой организации данных объясняется тем обстоятельством, что для достижения середины интервала требуется последовательное движение в соответствии с адресами связи и суммарное количество переходов от записи к записи достаточно велико.
Цепной каталог Цепным каталогом называется сплошной участок памяти (или несколько таких участков), в котором одновременно размещаются список обрабатываемых записей и список свободных позиций памяти. Адрес связи, отмечающий первую обрабатываемую запись, называется указателем списка. Адрес связи, отмечающий первую свободную позицию памяти, называется указателем свободной памяти. Адрес связи последней записи (или последней позиции свободной памяти) в списке называется концом списка, и здесь отмечается нулевым значением. Алгоритм вставки записи с ключом F в цепной каталог: 1. Найти в каталоге запись с ключом непосредственно меньше, чем F (предшествующая запись). 2. Поместить запись с ключом F в первую позицию свободной памяти. 3. Заменить указатель свободной памяти (УСП) на адрес связи новой записи, этот адрес - на адрес связи предшествующей записи, а последний - на первоначальное значение УСП. Алгоритм удаления записи с ключом W из каталога: 1. Найти в каталоге запись с ключом непосредственно меньше, чем W (предшествующая запись). 2. Заменить УСП на адрес связи предшествующей записи, этот адрес - на адрес связи исключаемой записи, а последний - на первоначальное значение УСП.
Древовидная организация данных Древовидной организацией данных (деревом) называется множество записей, расположенных по уровням следующим образом: на 1-м уровне расположена только одна запись (корень дерева), к любой записи i-го уровня ведет адрес связи только от одной записи уровня i-1. Если записи получат номера уровней, соответствующие определению, то они получат и древовидную организацию. Количество уровней в дереве называется рангом. Записи дерева, которые адресуются от общей записи (i-l)-ro уровня, образуют группу. Максимальное число элементов в группе называется порядком дерева. Деревья обычно формируются двунаправленными, адрес связи от записи уровня i+1 к записи i-го уровня называется обратным. При размещении дерева в памяти ЭВМ каждая запись может занимать произвольное место. Звено связи - набор адресов связи, принадлежащих одной записи. Если порядок дерева равен р, то звено связи состоит из р+1 адресов (один адрес обратный, определяющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указателя дерева. Незанятые адреса связи содержат признак конца списка.
Бинарные деревья (второго порядка) Их записи могут быть упорядочены. Для этого один из атрибутов записи должен быть объявлен ключевым. Чтобы определить понятие упорядоченности бинарных деревьев, требуется ввести ряд новых понятий (А - корень дерева). Записи, у которых заполнены два адреса связи, называются полными, записи с одним заполненным адресом - неполными, записи с двумя незаполненными адресами - концевыми (записи А, В, Е, F - полные, С - неполная, D, H, I, J, К – концевые). Адреса связи делятся на левые и правые (адрес от Е к Н -левый, от Е к I – правый). Каждая запись имеет левую и правую ветви. Правую (левую) ветвь записи образует поддерево, адресованное из этой записи через правый (левый) адрес связи (у записи С правая ветвь состоит из записей F, I, К, левая ветвь пустая). В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше, чем ключ любой записи на ее правой ветви.
Алгоритм построения упорядоченного бинарного дерева 1. Первая запись массива с ключом р(1) становится корнем дерева. 2. Значение ключа второй записи р(2) сравнивается с р(1), находящимся в корне дерева. Если р(2)p(i)), а при p(l)
Поиск данных по совпадению в упорядоченном бинарном дереве Просматривается некоторый путь по дереву, начинающийся всегда в его корне. Искомое значение ключа q сравнивается со значением корня р(1). Если p(l)>q, просмотр дерева продолжается по левой ветви корня, если p(l)q - производится переход к записи, расположенной на левой ветви p(i); p(i)
Списки В древовидной организации данных связь какой-то записи с N записями, составляющими ее группу, реализуется с помощью N адресов связи. Возможно, однако, связать все записи группы в цепочку и адресовать с предшествующего уровня первую запись группы. Таким образом получается новая нелинейная организация данных - список. Списком называется множество элементов, каждый из которых может быть либо записью, либо списком. Структуру списка выражают формулой, в которой записи помечаются буквами, а списки заключаются в круглые скобки. Список, включенный в другой список, называется подсписком. Перечисление всех списков из записей al, a2,...,aN, образующих множество LO, сводится к следующему: обозначим через Li' множество всех кортежей с элементами из Li. Введем последовательность множеств: L1=LO'+LO (+ здесь означает знак объединения множеств) L2=L1'+L1 L3=L2'+L2 Введенный аппарат списков намного шире, чем требуется для представления деревьев. Он используется самостоятельно также в задачах искусственного интеллекта и анализа текстовой информации.
Оценка методов организации данных Критерии оценки Методы Лучший метод ПоследовательныйЦепнойБинарное дерево Время формирования ~ MlogM цепной, бинарное дерево Время поиска~ logM~ М~ logMпоследовательный, бинарное дерево Время корректировки ~ M~ М~ logMбинарное дерево Объем дополнительной памяти 0~ m~ Mпоследовательный
Методы ускорения доступа к данным Ускорение доступа к данным достигается применением методов размещения информации и ее поиска либо путем создания массивов вспомогательной информации о хранимых данных. Эти же методы необходимы при организации доступа к информации по нескольким ключевым атрибутам одновременно. Доступ к требуемым записям может осуществляться не только путем сравнения искомого значения ключа с ключами записей, извлекаемых из массива по определенному алгоритму (как это было в рассмотренных методах обработки данных), но и в результате вычисления местоположения требуемой записи. Сами записи могут быть упорядочены алгоритмом сортировки либо используется специальная расстановка записей. Используются в методах ускорения доступа к данным: Индексы Адресные функции
Адресная функция Адресной функцией называется зависимость i=f(p), где i - номер (адрес) записи; р - значение ключевого атрибута в записи. Адресная функция может вырабатывать одинаковое значение i для значений р, принадлежащих разным записям, которые в этом случае называются синонимами. К функции f предъявляются следующие требования: она должна быть задана аналитически и вычисляться достаточно быстро; ключевые атрибуты, подчиняющиеся произвольному распределению, функция должна переработать в равномерно распределенные номера записей (это условие обычно соблюдается приближенно); число записей-синонимов должно составлять % от общего числа записей.
Индексы Имеются три важные разновидности индексов: информация о каждой записи основного массива попадает в индекс (сплошная индексация); номера записей, информация о которых выносится в индекс, образуют арифметическую прогрессию с шагом d> 1. Основной массив, дополненный таким индексом, обычно называется индексно-последовательным; ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию. Сплошной индекс связан с созданием инвертированного массива ключевых атрибутов к основному массиву. Этот случай уже рассмотрен. Индексно-последовательный массив представляет собой последовательный массив, отсортированный по значениям ключевого атрибута, к которому создается дополнительный массив индексов. В индекс выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d. Поиск значения q в индексно-последовательном массиве происходит в две стадии: в массиве индексов (который отсортирован в силу упорядоченности основного массива); среди записей основного массива, расположенных между двумя соседними индексами, найденными на первой стадии. Индексом называется набор ключей и адресов записей, которые выбираются из основного массива по определенному закону. Отдельный элемент набора индексов также называется индексом, хотя это не соответствует значению слова index -список.
Рандомизация индекса Если ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию, мы получаем ситуацию с адресной функцией для индекса (рандомизация индекса). Точное описание рандомизированного индекса состоит в следующем: индекс с номером п хранит адрес записи основного массива, ключ которой равен или непосредственно больше значения p(l)+z(n-l), где z - константа (шаг арифметической прогрессии); р(1) - значение ключа первой записи основного массива. Важной разновидностью доступа к данным, которая требует специальных методов ускорения доступа, является обработка информации по нескольким ключевым признакам. В структуре записи массива определяется несколько ключевых атрибутов, причем в различных прикладных программах требуется доступ к записям по различным сочетаниям этих атрибутов и, возможно, требуется последовательная обработка всего массива. Среди ключевых атрибутов записи устанавливается порядок старшинства. Извлекаемые на обработку записи должны быть упорядочены в пределах всего массива по самому старшему ключу. В пределах группы записей с одинаковым значением старшего ключа должна соблюдаться упорядоченность по значениям следующего по старшинству ключа и т. д.
Оптимальное вторичное индексирование Если ключ является многоатрибутным, то по его отдельным атрибутам может существовать вторичный индекс. Затраты времени на реализацию поиска и корректировки данных в файле будем выражать количеством прочитанных или записанных блоков информации, предполагая, что длина блока одинакова и в основном файле, и в файлах-индексах. Обозначим через c(i,j) количество прочитанных блоков для удовлетворения j- го типа запроса при помощи i-й стратегии поиска. Очевидно, что стратегия не способна удовлетворить запрос, если атрибуты-входы запроса и вторичные ключи не содержат общих имен. В этом случае c(iJ) равно количеству блоков информации в основном файле. Формулы для расчета числа блоков обычно приводятся в технической документации на СУБД и чаще всего имеют вид ML/B, где M>>L - число записей в основном массиве я длина записи в байтах, В - размер блока в байтах. Когда атрибуты-входы запроса и вторичные ключи содержат общие имена, формулы для c(iJ) сильно зависят от состава общих имен. Пусть общим является атрибут А(х) с количеством различных значений т(х) и длиной значения 1(х). Количество блоков в файле-индексе, построенном по атрибуту А(х), обозначим через n(х). Формулы для расчета n(х) сильно различаются у разных СУБД из-за многообразия способов реализации индекса.
Мультисписки Мультисписком называется множество списков, организованных на общем множестве записей. Если требуется доступ к записям по t ключам, то формируется t списков для каждого ключевого атрибута в отдельности. При размещении мультисписка во внешней памяти необходимо размещать каждый список в небольшом числе рядом расположенных участков, что позволит уменьшить время доступа. Эффективная организация мультисписка предполагает выполнение следующих условий: число записей в каждом списке должно быть небольшим, адреса хранения записей должны монотонно возрастать.
Организация данных во внешней памяти ЭВМ Данные на внешнем запоминающем устройстве хранятся в виде файлов. Каждый файл имеет уникальное имя файла. В простейшем случае файл представляет последовательный массив записей на внешнем запоминающем устройстве. Существует ряд стандартных методов организации файлов на магнитном диске и соответственно методов доступа к этим файлам. Виды организации файлов во внешней памяти: последовательная; индексно-последовательная; индексно-произвольная; прямая. Соответствие доли выборки записей и методах организации файла: Доля выборки записей Наилучшая организация файла 1-я запись Прямая % Прямая, индексная % Последовательная
Последовательная и индексно-последовательная организация данных во внешней памяти При последовательной организации файла на магнитном диске возможен доступ от только что обработанной записи к последующей записи (по направлению к концу файла). Переход в обратном направлении невозможен, единственный путь состоит в закрытии файла, повторном его открытии и движении к нужной записи в прямом направлении. Индексно-последовательный файл представляет собой последовательный файл, снабженный индексами. На магнитном диске выделяются три области - первичная, индексная и область переполнения. В первичной области помещаются упорядоченные по значениям ключевого атрибута записи, когда файл впервые создается. В зависимости от размера первичной области могут создаваться один, два или три уровня индексов: индекс первого уровня отмечает последнюю запись каждой дорожки магнитного диска; индекс второго уровня отмечает последнюю запись каждого цилиндра магнитного диска. Итоговые характеристики индексно-последовательного доступа: значения ключей записей должны быть отсортированы; в индекс заносится наибольший ключ для всех записей блока (дорожки); наличие повторяющихся значений ключа недопустимо; эффективность доступа зависит от числа уровней индексации, распределения памяти для размещения индекса, числа записей в файле и размера области переполнения.
Прямая и индексно-произвольная организация данных во внешней памяти Если в индекс попадает информация о ключе каждой записи, то получаем индексно- произвольньй доступ. Записи файла могут быть при этом не упорядочены по значению ключа. Индекс для индексно-произвольного метода доступа практически всегда формируется как многоуровневый. Типичная организация многоуровневого индекса соответствует понятию В-дерева. Нижний уровень В-дерева образуют индексы со ссылкой на каждую запись основного массива. Благодаря использованию адресных ссылок упорядоченность основного массива не обязательна. Индексы нижнего уровня разделены на страницы, и в конце каждой страницы оставляется резервная память. Последний индекс каждой страницы поступает на страницу предпоследнего уровня В-дерева. Когда эта страница будет почти заполнена индексами, последний из них поступит на страницу более высокого уровня и т. д. Прямой метод доступа соответствует файлу, который использует адресную функцию вида i=p-a. Для прямого доступа характерны следующие особенности: не требуется упорядоченность записей файла; наличие повторяющихся значений ключа недопустимо; значениям нескольких ключей может соответствовать.один и тот же адрес (блок). На выбор между четырьмя рассмотренными методами организации файлов существенное влияние оказывает количество записей, которое должно быть обработано в процессе реализации запроса. Этот параметр называется долей выборки и равен отношению числа требуемых при выборке записей файла к общему числу записей в файле.
Контрольные вопросы: Что понимается под организацией значений данных? Охарактеризуйте методы организации значений данных. Опишите способы формирования адресов промежуточных записей. Перечислите критерии эффективности алгоритма по времени его выполнения в зависимости от ряда параметров хранимой информации. Дайте определение адреса связи. Охарактеризуйте способы создания списка. Что понимается под указателем списка? Опишите процессы формирования упорядоченного списка записей. Дайте определений цепного каталога. Опишите принципы организации древовидной структуры данных. Что понимается под рандомизацией индекса? Кратко охарактеризуйте виды организации файлов во внешней памяти ЭВМ. Для каких целей служит вторичное индексирование?