Файл: СПОСОБЫ ПРЕДСТАВЛЕНИЯ ДАННЫХ В ИНФОРМАЦИОННЫХ СИСТЕМАХ (Данные и модели данных).pdf

Развитие структур данных на всех уровнях должно обеспечить
принцип независимости данных. Если у меня есть данные, то я не имею данных, указывает, что изменения в физическом местоположении данных и в техническом на эти системы не должны влиять логические структуры и
программы, т. е. не должны вызывать их изменения. Данные не означают, что изменения в структурах хранения не должны вызывать изменения в логических структурах данных и в структурах данных приложения программы. Кроме того, внесены изменения в логические структуры данных из-за появления новых пользователей и новых запросов, не следует на приложениях других пользователей системы.

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

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

Структура данных. ОРВ имеют многоуровневую структуру данных, которая формируется из отдельных элементов, связанных определенными отношениями. Элементы каждого уровня имеют определенное название. Формирование - элементы более высокого уровня сделаны из элементов более низкого уровня по определенным правилам. Многоуровневая структура- самый низкий уровень-элементарные данные:

числа, символы, логические данные, знаки. Элементарные данные считываются программист целиком, доступ к их частям невозможен. Эти данные не являются непосредственным объектом информационного поиска, но в некоторых случаях они должны быть доступны. Например, в процессе поиска можно возможно, потребуется сравнить отдельные символы в строках. Элементарные данные каждого типа имеют определенную форму.-

при выводе в оперативную память компьютера, память выделяется строго ОП- ограниченная память. Знание элементарных форматов хранения данных

позволяет рассчитать объем памяти, необходимый для размещения массивов

данные и программы.

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

Каждый признак объекта имеет наименование и значение. Так, для студентов, записи о которых хранятся в СОД, в качестве признаков могут использоваться: номер студенческого билета, ФИО, средний балл успеваемости. Каждый конкретный студент характеризуется определенными значениями этих признаков, например, наименование признака средний балл, значение признака 4,7. Отдельные студенты отличаются значениями одноименных признаков.

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

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

В записи могут предусматриваться дополнительные поля для хранения

служебной информации: меток, ссылок, указателей.

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

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

Поля записи объединяются в группу данных (агрегат данных, групповое данное). Группа данных − элемент третьего уровня внутренней структуры записи − представляет собой поименованную совокупность элементов данных, рассматриваемую как единое целое. Например, группа данных, имеющая наименование адрес, состоит из элементов данных город, улица, № дома, № квартиры. В качестве элемента группа может иметь другую группу данных.

Группа данных имеет определенный смысл и может быть объектом поиска, но не имеет смысловой завершенности. Например, адрес полезно знать лишь в том случае, если известно, кому он принадлежит.

Логическая запись представляет ч е т в е р т ы й уровень структуры данных − это поименованная совокупность полей или групп данных. Запись является отдельной логической единицей и имеет смысловую завершенность. Каждая запись описывает индивидуальный объект или класс объектов. Логическая запись является непосредственным объектом информационного поиска и основной единицей обработки информации в СОД.

Перечень полей, последовательность их расположения и взаимосвязь

между ними составляет внутреннюю структуру записи, которая в конечном

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

Отдельные логические записи, описывающие определенный класс объектов- проекты группируются в наборе данных, образуя последний p I -

t-й уровень структуры данных. Массивы, хранящиеся во внешней памяти,

называется файлы. Файл имеет имя и обрабатывается как единое целое. На-

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

Типы структур данных. В процессе функционирования ОРВ записи и

массивы претерпевают изменения. Новые записи добавляются в массивы, UDA- старые становятся ненужными. Процесс ведения информации обновленный массив, состоящий из добавления и удаления для написания называется ведущим.

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

Для любой манипуляции с их записями, прежде всего, необходимо

найти в массиве. Поиск записей-одна из основных операций в ОРВ, поэтому

время поиска является наиболее важным параметром, который в значительной степени определяет общую скорость обработки информации в ОРВ.

Для обеспечения общей "жизнеспособности" информационной массы-

Структуры данных VA должны быть организованы таким образом, чтобы один временно предоставляется: обслуживание массива; исправление отдельных записей; быстрый поиск записей; минимальное потребление памяти для массива. Все эти требования исследования в значительной степени противоречивы, т. е. улучшение некоторых характеристик СОД может сопровождается ухудшением состояния окружающих. Поэтому перед проектировщиком ОРВ задача состоит в том, чтобы выбрать компромиссное решение, которое позволяет DOS- Тип эффективное сочетание этих характеристик.

Структуры данных делятся на линейные и нелинейные. Линейный

структуры данных включают массив, стек, очередь, таблицу. В нелинейном

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

Ряд структур данных, однажды созданных, не допускают включения или ключевые записи, и позволяет только коррекцию записей. Это структуры

фиксированный размер. Напротив, структуры переменного размера позволяют включать и исключать записи, позволяя информацию массив динамически изменяется.

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

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

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

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

представления данных в памяти СОД различают структуры хранения с последовательным и связанным представлением данных.

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

Для хранения информационного массива в виде последовательного

списка в памяти выделяется блок свободных ячеек под максимальный размер

массива. Так, массив записей, имеющий логический порядок

Запись В

Запись А

Запись F

Запись C

. . . . . . . .

Запись N

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

При связанном представлении в каждой записи предусматривается

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

Структуры хранения, основанные на связанном представлении данных,

называют связанными списками. Если каждая запись содержит лишь один указатель, то список односвязный, при большем числе указателей – список многосвязный.

Пусть структура данных имеет следующую логическую последовательность записей:

Запись А

Запись В

Запись С

Запись F

Записи размещены в ячейках с адресами 01, 05, 03, 10. В поле указателя

каждой записи размещается адрес связи (АС), определяющий адрес ячейки с

логически следующей записью. Порядок чтения записей указан стрелками.

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

Ведение списка не требует перезаписи элементов массива, а производится с

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