Файл: Способы представления данных в информационных системах.pdf

Элементарные данные каждого типа имеют определенную форму представления в памяти; для их хранения выделяется строго определенный объем памяти. Знание форматов хранения элементарных данных позволяет рассчитать объем памяти, необходимый для размещения данных и программ.

Элементом второго уровня является поле записи. Это последовательность элементарных данных, которая имеет определенное значение, но не имеет значимой полноты. Данные, образующие отдельное поле записи, описывают соответствующий атрибут - свойство объекта.

Каждая особенность объекта имеет имя и значение (рис. 1.1.). Например, для учеников, чьи записи хранятся в AIS, в качестве знаков можно использовать идентификационный номер ученика, фамилию и знак средней оценки. Каждый конкретный ученик характеризуется определенными значениями этих знаков, например, названием знака. Средний балл, значение 4,7. Отдельные студенты различаются в значениях знаков одного и того же имени.

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

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

Запись может содержать дополнительные поля для хранения служебной информации: теги, ссылки, различные указатели. Поле записи может быть объектом поиска информации в различных приложениях, а также в тех случаях, когда это поле является ключевым. Однако, как уже отмечалось, поле записи не имеет смысловой полноты. Например, поле «СРЕДНИЙ ШАР» может быть объектом поиска, но информационное значение этого поля будет иметь значение только тогда, когда известны фамилия, имя и отчество учащегося.

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

Поля записи объединяются в группу данных (агрегация данных, сгруппированные данные). Группа данных - элемент третьего уровня внутренней структуры записи - это именованная коллекция элементов данных, которая рассматривается как единое целое. Например, груп­па данных, имеющая наименование АДРЕС, состоит из элементов данных ГОРОД, УЛИЦА, НОМЕР ДОМА, НОМЕР КВАРТИРЫ. В качестве своего элемента группа может иметь другую группу данных. Группа данных имеет определенный смысл и может быть объектом поиска, но не имеет смысловой завершенности. Так, например, адрес полезно знать лишь в том случае, если известно, чей он.

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

Каждая запись описывает отдельный объект или класс объектов. Логическая запись является непосредственным предметом поиска информации, основной единицей обработки информации.

Список полей, последовательность их расположения и взаимосвязь между ними составляют внутреннюю структуру записи, которая в конечном итоге определяет тип записи. Поля записи могут быть расположены один за другим, в этом случае запись называется неструктурированной. Запись может быть структурированной, со сложными нелинейными связями между полями. Структурирование записей является одним из основных понятий баз данных.

Рис. 1.3. Структурированные и неструктурированные записи

Отдельные логические записи, которые описывают определенный класс объектов, группируются в информационный массив. Массивы, хранящиеся в ВЗУ, называются файлами. Файл имеет имя и рассматривается как единое целое. Например, совокупность записей всех студентов учебной группы можно рассматривать как отдельный файл.

Рис. 1.4. Логические записи, информационные массивы и файлы

1.3 Классификация структур данных

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

Процесс поддержания массива информации в его текущем состоянии, который состоит в добавлении (включении) и удалении (исключении) записей, называется обслуживанием.

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

Конечной целью любой операции, выполняемой в АИС, является отдельная запись. Чтобы добавить, удалить или настроить обработку информации, содержащейся в конкретной записи, сначала необходимо найти нужную запись или ее местоположение в массиве. Таким образом, поисковые операции являются традиционными для систем обработки и хранения информации и, можно считать, наиболее часто выполняемыми операциями в AИС. Поиск записей должен выполняться как можно быстрее, поскольку время поиска существенно определяет общее время обработки информации. Очевидно, что эти свойства AИС зависят от того, как организован уровень хранилища и какие правила, алгоритмы применяются для поиска записей в массивах и файлах.

Рис 1.5. Операции над записями в массивах

Чтобы обеспечить «жизнеспособность» информационного массива структуры, в которую организованы данные, они должны обеспечить возможность поддержки массива и настройки отдельных записей, быстрого поиска записей и минимального потребления памяти для массива. Перечисленные требования противоречивы, поэтому ужесточение требований, ведущих к улучшению некоторых характеристик АИС, может сопровождаться ухудшением других. При выборе структуры данных они часто останавливаются на компромиссном решении.

Структуры данных делятся на линейные и нелинейные структуры. В нелинейных структурах, в отличие от линейных, связь между элементами структуры (записями) определяется отношениями подчиненности или некоторыми логическими условиями. Линейные структуры данных включают в себя массив, стек, очередь, таблицу. Тенденции, графики, многосвязные списки и структуры списков принадлежат нелинейным структурам.

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




 

Рис. 1.6. Последовательное и связное представление структур данных

Разные структуры данных обеспечивают разный доступ к своим элементам: в одних структурах доступ возможен к любому элементу, в других - к строго определенному. Ограничение доступа сопровождается увеличением времени поиска необходимых записей.

Структуры данных могут быть однородными и разнородными. В однородных структурах все элементы представлены записями одного типа. В гетерогенных структурах элементы одной структуры могут быть записями разных типов.

1.4 Последовательное и связанное представления данных в памяти

На уровне хранения в памяти компьютера данные могут иметь последовательное или связанное представление (см. Рис. 1.7). Соответственно, структуры хранения различаются с использованием согласованного представления данных и связанного представления данных.

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

Для хранения информационного массива в виде последовательного списка в памяти выделяется блок свободных ячеек для максимального размера массива. Записи, имеющие следующий логический порядок: Зап. В, Зап. А, Зап. F, Зап. С, ..., Зап.N, — разместятся в памяти машины так, как это показано на рис. 1.7,а.. Вновь появившиеся записи размеща­ются в конце блока на свободном участке памяти. Если количество новых записей окажется больше, чем число свободных ячеек в зарезерви­рованном блоке, то эти записи не удастся разместить в памяти. Если же записей окажется меньше, чем предполагалось, то память останется неис­пользованной.

В процессе ведения информационного массива записи добавляются и удаляются. Вновь пришедшие записи добавляются в конец списка. Так, запись (N + 1)-я будет размещена в ячейке с адресом 100 + (N + 1). При удалении записей в памяти остаются свободные ячейки. На рис. 1.7,б добавлена запись (N + 1)-я и удалены две записи: Зап. А и Зап. F, Ячейки 102 и 103 оказались свободными. Список, содержащий свободные ячейки памяти, будет свободным. Со временем значительное количество клеток может стать свободным. Чтобы эти разделы памяти не были пустыми, время от времени весь массив данных перезаписывается, а все записи перемещаются, как показано на рис. 1.7, б. Перезапись массива требует дополнительного компьютерного времени. В процессе обновления массива обновляемые записи считываются из памяти и в них вносятся необходимые изменения. Исправленные записи записываются обратно в конец списка в свободных ячейках.

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

Приложения AИС часто имеют дело с данными, которые постоянно обновляются, исправляются, и представление данных в виде последовательного списка приводит к неэффективному использованию памяти, потере компьютерного времени для перезаписи массива. Для ряда задач последовательное представление данных обычно не применимо. В таких случаях связанное представление используется для организации структуры данных.

Рис. 1.7. Последовательное представление данных в памяти ЭВМ. Блок ячеек памяти: 

А) после создания массива;

Б) после удаления и добавления запи­сей;

В) после перезаписи массива.

В связанном представлении дополнительное поле предоставляется в каждой записи, в которой находится указатель (ссылка). Физический порядок записей в этом случае может не соответствовать логическому порядку. В памяти компьютера записи расположены в любых свободных ячейках и связаны друг с другом указателями, указывающими местоположение записи, логически следующие за данной записью. Указатель часто интерпретируется как адрес ячейки памяти, в которой хранится следующая запись.