<< Пред. стр. 6 (из 8) След. >>
Список литературы по разделу
Данные в памяти ЭВМ обычно хранятся раздельно в виде составных единиц информации. Отдельное значение СЕИ, находящееся в памяти ЭВМ, называется записью. Множество записей образует массив, или файл. Термин массив обычно используется при рассмотрении данных в оперативной памяти ЭВМ, термин файл применяется для данных, хранимых на внешних запоминающих устройствах.
Организацией значений данных – это относительно устойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения взаимосвязи между записями.
Организация значений данных (далее называемая просто организацией данных) может быть линейной и нелинейной (Рис. 14).
Методы организации данных
Линейные Нелинейные
Последовательная Цепная Древовидная
(Списковая)
Бинарное дерево
Рис. 14. Методы организации данных
При линейной организации данных каждая запись, кроме первой и последней, связана с одной предыдущей и одной последующей записями. У записей, соответствующих нелинейной организации данных, количество предыдущих и последующих записей может быть произвольным.
Линейные методы организации данных различаются только способами указания предыдущей и последующей записи по отношению к данной записи. Но это приводит к тому, что алгоритмы, эффективные для одних методов организации данных, становятся неприемлемыми для других методов.
Среди линейных методов выделяются последовательная и цепная организации данных. При последовательной организации данных записи располагаются в памяти строго одна за другой, без промежутков, в той последовательности, в которой они обрабатываются. Последовательная организация данных обычно и соответствует понятию массив (файл).
Записи в массиве, с точки зрения способа указания их длины делятся на записи фиксированной, переменной и неопределенной длины. Записи фиксированной (постоянной) длины имеют одинаковую, заранее известную длину.
Адреса промежуточных записей фиксированной длины в массиве задаются формулой:
А(i) = А(l)+(i-1)*L,
где А(1) - начальный адрес первой записи;
А(i) - начальный адрес i-й записи;
L - длина одной записи.
Если длины записей неодинаковы, то длина указывается в самой записи. Такие записи называют записями переменной длины. Вместо явного указания длины записи можно отмечать окончание записи специальным символом-разделителем, который не должен встречаться среди информационных символов значения записи. Записи, заканчивающиеся разделителем, называются записями неопределенной длины. Записи переменной и неопределенной длины занимают меньший объем памяти, но их обработка ведется с меньшей скоростью, поскольку затруднено обнаружение следующей записи.
В структуре записей последовательного массива обычно выделяется один или несколько ключевых атрибутов, по значениям которых происходит доступ к остальным значениям атрибутов той или иной записи. Ключевые атрибуты в записях обозначаются через р(i), где i - номер записи, общее число записей в массиве обозначается через М.
Записи массива могут быть упорядоченными или неупорядоченными по значениям ключевого атрибута (ключа), имя которого одинаково во всех записях. Ключевой атрибут обычно является атрибутом-признаком. Часто требуется поддерживать упорядоченность записей по нескольким именам ключевых признаков. В этом случае среди признаков устанавливается старшинство. Условие упорядоченности записей в массиве (и вообще для линейной организации данных) выглядит следующим образом:
р (i) <=р (i+ 1)- упорядоченность по возрастанию;
р(i) >= р(i+1) - упорядоченность по убыванию.
Наиболее важными и часто применяемыми алгоритмами обработки данных являются формирование данных, их поиск и корректировка, а также последовательная обработка. Эти алгоритмы могут быть реализованы с использованием достаточно большого количества методов организации данных.
§ 3.2. Сравнение методов организации данных
Для сравнения методов организации данных обычно анализируются следующие величины:
• время формирования данных, т. е. время создания в памяти ЭВМ так или иначе упорядоченного представления данных (упорядочение способно ускорить выполнение алгоритмов поиска данных);
• время поиска данных. Как известно, условия поиска (выборки) на практике могут быть достаточно разнообразные. Анализируется обычно простейший и наиболее распространенный случай (поиск по совпадению) – найти записи, у которых значение ключевого атрибута равно заранее известной величине q;
• время корректировки данных. Из всех возможных вариантов корректировки учитывается включение или исключение одной записи;
• объем дополнительной памяти, расходуемой под служебную информацию (например, адреса связи).
На время выполнения алгоритмов влияет и ряд других факторов, например, быстродействие конкретной ЭВМ, применяемый язык программирования, стиль программирования конкретного программиста. Чтобы можно было не принимать во внимание подобные факторы, целесообразно анализировать не время, а количество выполняемых элементарных операций, в частности операций сравнения значений ключевых атрибутов и искомых величин. Время выполнения алгоритма обычно прямо пропорционально числу требуемых сравнений, и подобная замена критерия эффективности алгоритма вполне законна.
При анализе алгоритмов необходим еще ряд допущений, обеспечивающих использование равномерного распределения вероятностей для всех случайных величин, описывающих работу алгоритма, в том числе:
• распределение значений ключевых атрибутов в массиве из М записей - равномерное;
• значение q при поиске по совпадению выбрано случайно: это означает, что поиск с одинаковой вероятностью 1/М может закончиться на любой записи массива;
• положение включаемой (исключаемой) записи при корректировке определяется теми же вероятностями, что и при поиске.
Массив, обладающий наибольшей неопределенностью своего состояния, будем называть случайным массивом. Все его М! состояний равновозможны. Через М! обозначено произведение 1*2*...*М.
Таким образом, минимальное число сравнений, необходимое для упорядочения массива из М записей, определяется как
С = log М!,
что соответствует минимально возможному числу вопросов о состоянии массива с возможными ответами типа: да – нет (логарифм по основанию 2).
Сравнение методов организации данных Табл. 1.
Методы организации данных Лучшийметод
Критерии оценки последовательный цепной бинарное дерево
Время формирования ~ М log М ~ М log М ~ М log М цепной, бинарное дерево
Время поиска ~ log М ~ М ~ log М последовательный, бинарное дерево
Время корректировки ~ М ~ М ~ log М бинарное дерево
Объем дополнительной памяти 0 ~ М ~ М последовательный
Время формирования массива примерно одинаковое для всех методов, но при пересылке в последовательном массиве пересылаются целые записи, а прицепной и древовидной организации пересылаются адреса связи. Минимальный объем памяти необходим при последовательной организации данных, минимальное время поиска – для последовательной и цепной организации, минимальное время корректировки – для бинарного дерева. Наиболее важным критерием считается минимальное время, поэтому предпочтение можно отдать бинарному дереву.
Поиск в последовательном массиве
Поиском называется процедура выделения из некоторого множества записей определенного подмножества, записи которого удовлетворяют некоторому заранее поставленному условию, называемому запросом на поиск. Простейшее условие поиска – это поиск по совпадению, т. е. равенство значения ключевого атрибута i-й записи р(i) и некоторого заранее заданного значения q.
Базовым методом доступа к массиву является ступенчатый поиск. Этот метод предполагает упорядоченность обрабатываемых записей по возрастанию или по убыванию. Для определенности будем считать, что массив отсортирован по возрастанию значений ключевого атрибута р(i).
Рассмотрим простейший вариант ступенчатого поиска – одноступенчатый или последовательный поиск. Искомое значение q сравнивается с ключом первой записи, если значения не совпадают, с ключом второй записи и т. д. до тех пор, пока q не станет больше ключа очередной записи.
Для двухступенчатого поиска в массиве, состоящем из М записей выбирается константа d1, называемая шагом поиска. Если необходимо отыскать запись со значением ключевого атрибута, равным q, производятся следующие действия.
Значение q последовательно сравнивается с рядом величин р(1), р(1+d1), р(1+2*d1), ..., р(1+k*d1) до тех пор, пока будет впервые достигнуто неравенство р(1+m*d1) =>q. Здесь заканчивается первая ступень поиска. На второй ступени q последовательно сравнивается со всеми ключами, которые имеют номер 1+m*d1 и больше, до тех пор, пока в процессе сравнений будет достигнут ключ, больший, чем q. Извлеченные при этом записи с ключом q образуют результат поиска.
Эффективность поиска измеряется количеством произведенных сравнений.
Важным вариантом ступенчатого поиска является бинарный поиск. Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь массив, т. е. А=0, В=М+1. Вычисляется середина интервала i по формуле i=(А+В)/2 с округлением в меньшую сторону. Ключ i-й записи р(i) сравнивается с искомым значением q. Если р(i) = q, то поиск заканчивается. В случае р(i)>q записи с номерами i+1, i+2,..., М заведомо не содержат ключа, и надо сократить интервал поиска, приняв В=i. Аналогично при р(i) < q надо взять А=i. Далее середина интервала вычисляется заново, и все действия повторяются. Если будет достигнут нулевой интервал, то требуемой записи в массиве нет.
Корректировка последовательного массива
Корректировка массива может касаться одной его записи или группы записей. Отдельная запись может включаться в массив и исключаться из него. Кроме того, в записи могут быть изменены значения отдельных атрибутов (как правило, неключевых). В любом случае перед непосредственно корректировкой выполняется поиск местонахождения корректируемой записи.
Включение новой записи (например, со значением ключевого атрибута q в последовательный упорядоченный массив не должно нарушать его упорядоченность. Поэтому сначала необходимо найти положение новой записи относительно имеющихся в массиве записей, т. е. выполнить поиск ключа новой записи q. Если значения q в массиве нет, то поиск остановится там, где должна находиться запись с ключом q при сохранении общей упорядоченности массива. Новая запись не может сразу занять место, где остановился поиск, необходимо выполнить пересылку записей, чтобы освободить его. Пересылка начинается с последней записи (она после пересылки занимает следующую позицию по направлению к концу массива), затем предпоследняя запись пересылается на место последней и т. д. В результате освобождается место для новой записи.
Итак, время включения записи складывается из времени поиска и времени пересылки записей. В среднем пересылка затрагивает примерно половину записей массива. Время пересылки одной записи пропорционально ее длине.
При исключении записи из массива также необходимо сначала найти в массиве ключ удаляемой записи, а затем выполнить пересылки записей в направлении к началу массива для уничтожения исключаемой записи в памяти. Очевидно, что время исключения записи описывается той же формулой, что и время включения записи.
Можно прийти к выводу, что включение-исключение записей поодиночке является очень длительной процедурой. Поэтому в ряде случаев удобно накапливать корректирующие записи в специальном массиве изменений, а не вносить их по мере появления.
Массив записей, подвергающихся изменениям, называется основным. Изменения, которые необходимо внести в основной массив, накапливаются в специальном упорядоченном массиве изменений, рассчитанном на 1<=m<=М записей. Обычно m составляет несколько процентов от М. При необходимости обработки основного массива он объединяется с массивом изменений.
При объединении основного массива с массивом изменений выполняются следующие операции (алгоритм слияния):
• ключ очередной записи основного массива сравнивается с ключом очередной записи массива изменений, и запись с меньшим значением ключа добавляется в новый массив (результат слияния);
• когда все записи одного из массивов будут перезаписаны полностью, оставшиеся записи другого массива добавляются в результирующий массив, и алгоритм заканчивается.
§ 3.3. Цепная (списковая) организация данных
Решение целого ряда задач обработки данных требует применения таких методов организации данных, которые позволили бы связать физически разнесенные в памяти данные в логическую последовательность, определяющую порядок их обработки. Простейшим методом, применяемым для этих целей, является списковая (цепная) организация данных.
Списком называется множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. Адресом связи некоторой записи называется атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработки записей в списке определяется возрастанием значений ключа в записях.
В списке выделяется собственная информация (записи с содержательными сведениями) и ассоциативная информация, т. е. все адреса связи.
Возможны два способа организации списка - совместное размещение собственной и ассоциативной информации, когда запись и ее адрес связи образуют одно целое (рис. 15, а), и раздельное, когда имеется списковая организация адресов связи и последовательное хранение собственной информации (рис. 15, б). При списковой организации данных необходим специальный атрибут, называемый указателем списка, который содержит начальный адрес или номер первой в порядке обработки записи списка.
Адреса связи
Ш
Указатель 1 2 3 4
списка
а) Записи
Ассоциативная информация
Ш
Указатель
списка 1 2 3 4
б) Записи
Рис. 15. Варианты списковой организации данных:
а) - совместное хранение записей и адресов связи;
б) - раздельное хранение записей и адресов связи
(Ш – конец списка)
Кроме того, адрес связи последней записи списка должен содержать специальное значение, называемое концом списка и отмечающее, что последующих записей у данной записи нет. Обычно конец списка отмечается нулем.
На рисунках адрес связи изображается прямоугольником со стрелкой, стрелка указывает на запись, адрес хранения которой содержится в адресе связи.
При формировании упорядоченного списка записей возможны два варианта:
• вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу;
• создать сначала неупорядоченный список, а затем отсортировать его.
Учитывая, что для сортировки можно использовать метод слияния, второй вариант следует признать более целесообразным.
В итоге время формирования упорядоченного списка пропорционально Т~М*1оgМ.
Поиск в упорядоченном списке основан на использовании тех же методов, что и в последовательном массиве, но так как адреса связи создают возможность быстрого доступа только к следующей записи, эффективность этих методов иная.
Последовательный поиск применяется для поиска данных в однонаправленном списке. Ключевой атрибут сравнивается с искомым значением, затем происходит переход по адресу связи к следующей записи и т. д. Время поиска пропорционально количеству записей Т~М.
Бинарный поиск для списковой организации является неэффективным, так как число переходов от записи к записи при доступе к середине интервала представляется величиной практически равной количеству записей.
При применении двунаправленных и кольцевых списков время доступа к записям уменьшается. На рис. 16 приведены примеры этих списков.
Адреса связи Указатель
обратного
Ш
Указатель Ш
прямого направления
направления
1 2 3 4
а) Записи
Указатель
списка 1 2 3 4
б) Записи
Рис. 16. Организация списков: а) двунаправленная; б) кольцевая
Двунаправленный список образован двумя цепочками адресов связи - от первой записи к последней и от последней записи к первой. В кольцевом списке последний адрес связи указывает на первую запись.
§ 3.4. Цепной каталог
Цепной каталог – это сплошной участок памяти (или несколько таких участков), в котором одновременно размещаются список обрабатываемых записей и список свободных позиций памяти. Адрес связи, отмечающий первую обрабатываемую запись, называется указателем списка. Адрес связи, отмечающий первую свободную позицию памяти, называется указателем свободной памяти. Адрес связи последней записи (или последней позиции свободной памяти) в списке называется концом списка и отмечается нулевым значением.
Включение и исключение записей в цепном каталоге предполагает поиск местоположения включаемой (исключаемой) записи и замену значений адресов связи для установления новой последовательности записей основного списка и списка свободной памяти.
Для того, чтобы включить или исключить запись в цепном каталоге необходимо найти местоположение записи и заменить значения адресов связи для установления новой последовательности основного списка и списка свободной памяти.
Оценка времени корректировки складывается из времени реализации поиска и времени на замену значений адресов связи. В последнем случае число пересылок адресов связи всегда одинаково и не зависит от числа записей в цепном каталоге, поэтому затраты времени на поиск при корректировке являются доминирующими и время корректировки пропорционально количеству записей Т~М.
§ 3.5. Древовидная организация данных
Древовидной организацией данных (деревом) называется множество записей, расположенных по уровням следующим образом:
•на 1-м уровне расположена только одна запись (корень дерева),
• к любой записи i-го уровня ведет адрес связи только от одной записи уровня i-1.
В данном определении понятия "дерево" и "уровень" вводятся одновременно. Если записи получат номера уровней, соответствующие определению, то они получат и древовидную организацию.
Количество уровней в дереве называется рангом. Записи дерева, которые адресуются от общей записи (i-1)-го уровня, образуют группу. Максимальное число элементов в группе называется порядком дерева. В дереве на рис. 17 порядок равен 3 и ранг составляет 4 (записи дерева обозначены заглавными латинскими буквами).
Деревья обычно формируются двунаправленными, адрес связи от записи уровня i+1 к записи i-го уровня называется обратным.
При размещении дерева в памяти ЭВМ каждая запись может занимать произвольное место.
Рис. 17. Пример древовидной организации данных
А
В С D
M K
N
S P
Рис. 18. Представление древовидной организации данных в памяти ЭВМ
Назовем звеном связи набор адресов связи, принадлежащих одной записи. Если порядок дерева равен р, то звено связи состоит из р+1 адресов (один адрес обратный, определяющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указателя дерева. Незанятые адреса связи содержат признак конца списка. В качестве примера размещения дерева в памяти ЭВМ на рис. 18 показан один из возможных вариантов представления дерева с рис. 17, обратные адреса связи не показаны.
Рассмотрим бинарные деревья (порядка 2 ). Они интересны тем, что составляющие их записи могут быть упорядочены. Для этого один из атрибутов записи должен быть объявлен ключевым.
Чтобы определить понятие упорядоченности бинарных деревьев, требуется ввести ряд новых понятий. В качестве примера рассмотрим бинарное дерево на рис. 19 (внутри показаны значения ключевого атрибута). Запись А - корень дерева. Записи, у которых заполнены два адреса связи, называются полными, записи с одним заполненным адресом - неполными, записи с двумя незаполненными адресами - концевыми. На рис. 19 записи А, В, Е, C- полные, G - неполная. D, F, T, H, R - концевые.
Рис. 19. Бинарное дерево
Адреса связи делятся на левые и правые. Каждая запись имеет левую и правую ветви. Правую (левую) ветвь записи образует поддерево, адресованное из этой записи через правый (левый) адрес связи. В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше, чем ключ любой записи на ее правой ветви.
Упорядоченное бинарное дерево формируется из неупорядоченного массива записей по специальному алгоритму.
Вопросы и задания
Назовите критерии оценки методов организации данных.
Почему время формирования массива у бинарного дерева и цепной организации данных меньше, чем у последовательной для одинакового количества записей?
В чем заключается бинарный поиск?
Что такое корень дерева, ранг, и порядок?
Приведите схемы списковой организации данных при совместном и раздельном хранении записей и адресов связи.
По какой формуле определяются адреса промежуточных записей фиксированной длины?
ГЛАВА 4. МОДЕЛИРОВАНИЕ ПРЕДМЕТНЫХ
ОБЛАСТЕЙ В ЭКОНОМИКЕ
§ 4.1. Семантические модели данных
Напомним, что предметной областью называется подмножество (часть реального мира), на котором определяется набор данных и методов манипулирования с ними для решения конкретных задач или исследований.
Для того чтобы полностью отобразить объекты реального мира и все их свойства, понадобилась бы бесконечно большая база данных. Поэтому необходимо свести множество данных к конечному объему, легко поддающемуся анализу и управлению. Это достигается применением моделей, сохраняющих основные свойства объектов исследования и не содержащих второстепенных свойств. Поэтому первым этапом разработки информационной системы или технологии ее применения является обоснование выбора моделей данных для создания информационной основы системы, позволяющей в дальнейшем реализовать автоматизированный доступ к данным с целью их анализа и принятия решения.
Известные средства описания данных ориентируются на формы представления информации в виде синтаксических и семантических моделей. К числу синтаксических моделей относятся реляционная, сетевая и иерархическая модели данных, семантические модели – это модель сущностей и связей, модель семантических сетей.
Модель как знаковая система должна содержать три характеристики: синтаксис, семантику и прагматику. Этот подход определяет содержание атомарной (элементарной) модели, как элементарной единицы данных, включающей в себя правила построения объекта, свойства объекта, значения свойств. Разнообразие атомарных моделей создает условия для построения множества моделей данных.
Семантическая модель – полуформальный механизм, используемый для описания смыслового содержания базы данных, т.е. концептуальной семантики; схема семантической модели выполняет роль спецификации информации, что позволяет разработчику точно и исчерпывающе представить содержимое базы данных, не зависимо от конкретной СУБД.
Семантическое моделирование взаимосвязано с задачами кодирования и лингвистического обеспечения, поэтому оно в большей степени используется на уровне сбора первичной информации. Это также обусловлено большим объемом и разнообразием входной информации, сложностью ее структуры, возможным наличием ошибок.
Направление научных исследований, получившее название семантического моделирования сложилось в середине 70-х годов. Термин «семантическая модель» был раскрыт в работах Абриэля (1974), Сенко (1975), Чена (1976), Бахмана (1977) и других.
Общеизвестно, что семантические модели данных должны отвечать следующим требованиям:
обеспечивать интегрированное представление о предметной области;
понятийный аппарат модели должен быть понятен как специалисту предметной области, так и администратору БД;
модель должна содержать информацию, достаточную для дальнейшего проектирования экономической информационной системы.
В семантических моделях используются конструкции естественного языка, называемые высказываниями, декомпозиция которых невозможна без утраты смысла. Элементами высказываний служат атомарные факты. Атомарный факт – это любой объект, разложение которого на другие объекты в рамках данной предметной области не производится. Атомарный факт представляется тремя компонентами:
(x, y, t),
где x – множество объектов О1, О2, …, Оk;
y – свойство или связь объектов;
t – время.
Объекты могут вступать в отношения двух типов – обобщения, когда один объект определяется в виде множества других объектов, и агрегации, когда объект соотносится с именем действия, в котором он может участвовать. Обобщения и агрегации могут образовывать иерархические структуры. Эти абстракции применяются в управлении файлами: агрегации – при конструировании файла для группирования полей в запись; обобщения – для представления множества записей общим типом объекта – файлом, а также для выборки из файла множества записей. На рис 20 и 21 приведены примеры иерархии обобщения и агрегации.
Известно достаточно большое число семантических моделей, наиболее известными из которых являются модель сущностей и связей и модель семантических сетей.
Модель «сущность-связь» или ER-модель – это отражение реального мира в виде сущностей (Entity) и связей между ними (Relationship). На схеме сущности изображаются прямоугольниками, связи ромбами. Число связываемых объектов указывается цифрой на линии соединения.
Теоретической основой этого подхода является известная модель, введенная М. Ченом в 1976 году и получившая широкое распространение в качестве средств концептуального проектирования баз данных.
Различные методики построения ER-моделей анализируются по следующим основным аспектам:
Терминологический аппарат, лежащий в основе методики.
Семантические возможности модели для отображения различных ситуаций реального мира.
Наличие алгоритма перехода от ER-модели к различным даталогическим и конкретно к реляционной даталогической модели.
Эффективность алгоритма перехода.
Технология построения модели, сложность процесса моделирования.
Рис. 20. Иерархия обобщения
Как уже упоминалось, идеи Чена являются своеобразным стандартом для построения ER-моделей. Другие модели могут отличаться набором графических символов, некоторыми особенностями моделирования, но основные правила остаются теми же.
Под сущностью понимается нечто, что можно идентифицировать, при этом проектировщик должен суметь определить какие именно сущности имеют значение для моделирования, а какие – нет.
<< Пред. стр. 6 (из 8) След. >>
Список литературы по разделу