Структуры данных. Реляционная модель данных (relation data model)

Физические модели данных

Реляционная модель данных (relation data model).

Модели данных на основе записей

Объектные модели данных

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

- модель типа «сущность – связь», или ER-модель (Entity-Relationship model);

- семантическая модель;

- функциональная модель;

- объектно-ориентированная модель.

В настоящее время ER-модель стала одним из основных методов концептуального проектирования БД.

Широко развивается объектно-ориентированная модель данных.

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

1. иерархическая модель данных (hierarchical data model);

2. сетевая модель данных (network data model);

Физические модели данных описывают то, как данные хранятся в компьютере, предоставляя информацию о структуре записей, их упорядоченности и существующих путях доступа. Самыми популярными из физических моделей являются обобщающая модель (unifying model) и модель памяти кадров (frame memory).

Структуры данных бывают линейными (массивы, последовательности, таблицы) и нелинейными (списки, деревья, сети).

1. Порядок следования элементов линейных структур имеет линейный характер и соответствует порядку расположения элементов в памяти: один за другим без каких-либо промежутков. Адрес элемента соответствует его положению и определяется индексом – порядковым номером элемента в последовательности размещения. К элементу имеется прямой доступ, если известен его индекс.

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

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

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

c. Таблица – последовательность, представляемая строками – совокупностями разнотипных элементов. Таблица – это множество записей, каждая из которых представляет набор поименованных полей.

Однако с точки зрения размещения элементов таблица может быть представлена как одномерный массив (или последовательность) с однородными композиционными элементами, каждый из которых представляет собой совокупность разнотипных элементов. Именно это позволяет свести ввод/вывод таких типов структур к последовательным элементарным операциям.

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

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

a. Списки. Как и массив, список представляет собой совокупность однотипных элементов. Однако, порядок выборки элементов может отличаться от порядка следования в памяти, определенного при размещении. Наиболее очевидный способ установления однонаправленного порядка выборки элементов - это сопоставить каждому элементу списка ссылку, указывающую на следующий элемент. Соответственно, для организации двунаправленного списка, допускающего выборку в прямом и обратном порядках, каждый элемент должен иметь, кроме ссылки на следующий элемент, еще и ссылку на предыдущий. Такая организация не допускает возможности прямого доступа по номеру элемента.

Число элементов списка, как и в случае последовательностей, может быть неизвестно до размещения.