Обобщенные структуры называют также моделями данных, т.к. они отражают представление пользователя о данных реального мира.
Любая модель данных должна содержать три компоненты:
- структура данных - описывает точку зрения пользователя на представление данных.
- набор допустимых операций, выполняемых на структуре данных. Модель данных предполагает, как минимум, наличие языка определения данных (ЯОД), описывающего структуру их хранения, и языка манипулирования данными (ЯМД), включающего операции извлечения и модификации данных.
- ограничения целостности - механизм поддержания соответствия данных предметной области на основе формально описанных правил.
В процессе исторического развития в СУБД использовалось следующие модели данных:
- иерархическая;
- сетевая;
- реляционная.
В последнее время все большее значение приобретает объектно-ориентированный подход к представлению данных.
Это так называемые модели реализации, т. е. модели, ориентированные на получение ответа на вопрос: "Каким образом следует описывать структуры данных?“.
Единственное исключение составляет понятийная модель "сущность-связь", это ближайший союзник реляционной модели, но отвечающий не за реализацию, а за логику будущей БД.
4. Методы доступа к данным. Поиск по дереву. Хеширование.
Существуют два класса методов, реализующих доступ к данным по ключу:
- методы поиска по дереву;
- методы хеширования.
Метод поиска по дереву:
Определение:Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:
- между узлами имеет место отношение типа "исходный-порожденный " (“родитель-потомок”);
- есть только один узел, не имеющий исходного. Он называется корнем;
- все узлы за исключением корня имеют только один исходный; каждый узел может иметь несколько порожденных;
- отношение "исходный-порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.
Число порожденных отдельного узла (число поддеревьев данного корня) называется его степенью. Узел с нулевой степенью называют листом или концевым узлом. Максимальное значение степени всех узлов данного дерева называется степенью дерева.
Если в дереве между порожденными узлами, имеющими общий исходный, считается существенным их порядок, то дерево называется упорядоченным. В задачах поиска почти всегда рассматриваются упорядоченные деревья.
Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти.
Хеширование:
Этот метод используется тогда, когда все множество ключей заранее известно и на время обработки может быть размещено в оперативной памяти. В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией. Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае ключевые данные, используемые для определения адреса записи организуются в виде таблицы, называемой хеш-таблицей.
5. Назначение модели «сущность-связь». Элементы модели «сущность-связь».
Прежде, чем приступать к созданию системы автоматизированной обработки информации, разработчик должен сформировать понятия о предметах, фактах и событиях, которыми будет оперировать данная система. Для того, чтобы привести эти понятия к той или иной модели данных, необходимо заменить их информационными представлениями. Одним из наиболее удобных инструментов унифицированного представления данных, независимого от реализующего его программного обеспечения, является модель "сущность-связь".
Модель "сущность-связь" основывается на некой важной семантической информации о реальном мире и предназначена для логического представления данных.
Любой фрагмент предметной области может быть представлен как множество сущностей, между которыми существует некоторое множество связей. Дадим определения:
Сущность- это объект, который может быть идентифицирован неким способом, отличающим его от других объектов.
Набор сущностей - множество сущностей одного типа (обладающих одинаковыми свойствами).
Сущность фактически представляет из себя множество атрибутов, которые описывают свойства всех членов данного набора сущностей.
Множество значений (область определения) атрибута называется доменом.
Отсюда определяется ключ сущности - группа атрибутов, такая, что отображение набора сущностей в соответствующую группу наборов значений является взаимно-однозначным отображением.
Связь- это ассоциация, установленная между несколькими сущностями.
Роль сущности в связи - функция, которую выполняет сущность в данной связи.
Набор связей - это отношение между n (причем n не меньше 2) сущностями, каждая из которых относится к некоторому набору сущностей.
То число сущностей, которое может быть ассоциировано через набор связей с другой сущностью, называют степенью связи.
6. Диаграмма «сущность-связь». Пример построения диаграммы.
Существует несколько вариантов обозначения элементов диаграммы "сущность-связь", каждый из которых имеет свои положительные черты.
| Обозначение | Значение |
| Набор независимых сущностей |
| Набор зависимых сущностей |
| Атрибут |
| Ключевой атрибут |
| Набор связей |
Атрибуты с сущностями и сущности со связями соединяются прямыми линиями.
В процессе построения диаграммы можно выделить несколько очевидных этапов:
1. Идентификация представляющих интерес сущностей и связей.
2. Идентификация семантической информации в наборах связей
3. Определение кардинальностей связей.