Введение в базы данных Ограничения, присущие файловым системам

Лекция 3. Структуры и модели данных

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

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

Рисунок 3.2 - Структура односвязного списка

Рисунок 3.3 - Структура двухсвязного списка
Структуры данных могут быть однородными и неоднородными.
В однородных структурах все элементы данных представлены записями одного и того же типа.
В неоднородных - элементами одной структуры могут являться записи разных типов.
Пример неоднородной записи - совокупность сведений о некотором студенте.
Объект "студент" обладает свойствами:
 "личный номер" - характеризуется целым положительным числом;
 "фамилия-имя-отчество" - характеризуется строкой символов и т.д.
Пример: var
rec:record
num :byte; { личный номер студента }
name :string[20]; { Ф.И.О. }
fac, group:string[7]; { факультет, группа }
math,comp,lang :byte; {оценки по мат-ке, выч. технике, ин.яз.}
end;
Различные структуры данных предоставляют и различный доступ к своим элементам: в одних структурах доступ возможен к любому элементу, в других - к строго определенному.
Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на линейные и нелинейные структуры.
К линейным структурам относят массив, стек, очередь, таблица.
Массив – линейная структура данных фиксированного размера, реализуемая с использованием последовательного представления данных. Каждый элемент массива идентифицируется одним или несколькими индексами. Индекс – это целое число, значение которого определяет позицию соответствующего элемента в массиве и используется для осуществления доступа к этому элементу. Отдельные элементы массива могут изменяться, но общее число элементов массива остается неизменным. (Для массива не реализуются операции удаления и добавления, только модификации). В зависимости от числа индексов различают одно мерные и многомерные массивы.

Рисунок 3.4 – Одномерный массив

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

Рисунок 3.6 - Стек
Очередь – линейная структура данных переменного размера. Исключение элементов из очереди допускается только с одного конца – с начала очереди. Включение элементов возможно лишь в конец очереди. Данные обрабатываются по принципу «первым пришел – первым ушел». Доступ к элементам осуществляется по указателям начала и конца. Для реализации очереди может использоваться как последовательное, так и связное представление.

Рисунок 3.7 - Очередь
Таблица – линейная структура данных, каждый элемент которой характеризуется определенным значением ключа и доступ к элементам которой осуществляется по ключу. По ключу осуществляется и включение и исключение элементов структуры. Для реализации таблицы может использоваться как последовательное, так и связное представление. Обычно таблицы упорядочивают по какому-либо принципу (например, по возрастанию/убыванию значений ключа).

Рисунок 3.8 – Таблица
В нелинейных структурах связь между элементами структуры (записями) определяется отношениями подчинения или какими-либо логическими условиями. К нелинейным структурам принадлежат деревья, графы, многосвязные списки и списковые структуры.
Отношения между объектами реального мира часто носят нелинейный характер. Это могут быть отношения, определяемые логическими условиями, отношениями типа "один-ко-многим" или "многие-ко-многим". Отношения "один-ко-многим" носят иерархический характер и отображаются древовидными структурами. В виде иерархии может быть представлена например, структура учебных подразделений ВУЗа.
Отношения "многие-ко-многим" носят более универсальный характер и отображаются структурами графов. Пример такого отношения. Каждый ВУЗ распределяет своих выпускников на различные предприятия. В то же время предприятие поучает специалистов из различных ВУЗов.
Граф общего вида состоит из ряда вершин (узлов) и ребер, связывающих пары вершин. Если в понятия "ребро" и "вершина" вложить определенную смысловую нагрузку, то графы можно использовать для представления данных. Так вершинам графа можно сопоставить определенные объекты, тогда ребра будут соответствовать отношениям между объектами. В литературе по структурам баз данных модель данных, имеющую вид ориентированного графа, называют сетью.

Рисунок 3.9 - Граф
Дерево представляет собой граф с некоторыми ограничениями, то есть это ориентированный граф, не имеющий циклов. Вершины (узлы) дерева организованы по уровням, то есть, подчинены определенной иерархии. Любой узел дерева связан с единственным узлом более высокого уровня - порождающим - и с m узлами ближайшего уровня - порожденными. На самом верхнем уровне, в начале дерева имеется единственный узел, называемый корнем. Узлы, расположенные в конце каждой ветви дерева и не имеющие порожденных, называются листьями. В деревьях направление обязательно от порождающего к порожденному. Количество уровней дерева определяет высоту дерева. Древовидные структуры данных более удобны для реализации в памяти компьютера, чем сетевые. При обработке древовидных структур наиболее типичной является операция обхода - процедура, при выполнении которой каждый узел обрабатывается ровно один раз. Способы обхода (нисходящий, восходящий, смешанный) отличаются точкой входа в дерево, направлением движения по дереву. Структуры деревьев могут реализовываться в памяти компьютера с использованием как последовательного, так и связанного представления данных.

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

Рисунок 3.11 – Линейный список
При разработке структур данных всех уровней должен обеспечиваться принцип независимости от данных. Независимость данных - возможность изменения логической и физической структуры БД без изменения представлений пользователей.
Физическая независимость от данных означает, что любые изменения в физическом расположении данных или техническом обеспечении БД не должны отражаться на логических структурах и прикладных программах, то есть не должны вызывать в них изменений. [Такие изменения внутренней (физической) схемы данных как переход на новую файловую систему, другое устройство хранения, изменение индексов или способа хэширования, должны осуществляться без необходимости внесения изменений на логическом уровне]. Пользователи могут заметить изменения только за счет изменения общей производительности системы.
Логическая независимость от данных означает, что изменения в структурах хранения не должны вызывать изменения в логических структурах данных и в прикладных программах. Такие изменения, как добавление или удаление новых объектов (таблиц БД), атрибутов или связей, должны осуществляться без необходимости внесения изменений в уже существующие схемы или корректировки прикладных программ. Пользователи, для которых эти изменения предназначались, должны о них знать, но важно, чтобы другие пользователи даже и не подозревали о них.
Соблюдение принципа независимости данных позволяет использовать особые виды данных: виртуальные и прозрачные.
Виртуальные данные существуют лишь на логическом уровне. Пользователю эти данные представляются реально существующими, и он оперирует ими при необходимости. Каждый раз при обращении к этим данным система определенным образом их генерирует на основании других данных, физически существующих в системе.
Прозрачные данные представляются несуществующими на логическом уровне. Это позволяет скрыть от пользователя многие сложные механизмы, используемые при преобразовании логических структур данных в физические (примером могут служить индексы).