Концептуальное проектирование. ER – диаграммы (типа «сущность – связь»)

Концептуальное проектирование:

• Полное представление о содержании БД
• инфологическое проектирование (до выбора СУБД).

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

Элементарные данные, описывающие сущности, называются атрибутами. Между сущностями существуют связи:

а) 1:1

б) 1:n

в) m:n

Пример. Фирма, с клиентами работают менеджеры.

В реляционных БД не используются связи n:m и заменяются на 1:n (договоры дифференцируются по товарам).

Сравнение реляционного, иерархического и сетевого подходов к форме моделей данных.

1) Реляционная модель

Сотрудники

№	сотрудник	отдел	НИИ	…
С1	Иванов
С2	Попов
С3	Титов

Должности

№	Должность	…
D1	Инженер
D2	Ст. Инженер
D3	Ведущий инженер
D4	Начальник отдела

Оклад

№сотр.	№ долж	Оклад
С1	D1
С2	D3
С2	D4
С3	D1

Реляционная модель данных – представление данных в виде взаимосвязанных таблиц.

2) Иерархическая модель

Это первая модель данных, реализованная в СУБД (IMS). Относится к классу навигационных моделей (пользователь должен представлять как будет происходить поиск – в данном случае через вершину дерева). Недостатки модели – нельзя, например, посчитать сумму зарплат инженеров.

3) Сетевая модель.

Замкнутый цикл указателей. Также относится к классу навигационных моделей.

Поиск:

а) Поиск в файле сотрудников (по индексу)

б) Идём к первому файлу, потом к следующему по указателю.

Индекс по связующим полям не строится, а по основным строится.

Достоинство (как и всех списковых структур) – быстрое внесение изменений в Б.Д.

Пример: Попов назначается ведущим инженером (пунктиром). Сначала добавляется оклад.

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

Структуры данных.

Рассмотри логические структуры данных и структуры хранения.

Логические структуры данных.

1) Элемент (поле, атрибут) – минимальная логически неделимая структура данных.

Свойства элементов:

а) Значение элемента данных

б) Имя (существуют ограничения на длину имени и на использование символов)

в) Индикатор существования значения

г) Права доступа (пароль) – ограничение доступа передаётся к данным, также любому элементу может быть присвоен уровень секретности

д) Дата и время последнего изменения

е) Размер (связан с типом данных)

ж) Тип

з) Класс значений – дополнение к типу данных –ОДЗ – задаётся или интервалом, или списком разрешённых или запрещённых значений.

Типы данных:

I. Строковые типы. Символьные типы, типы, представляющие собой строку бит, типы класса BLOP(двоичные блоки большой размерности), в FoxPro – general

BLOP – самый распространённый тип для хранения мультимедиа.

Текстовые типы, предназначенные только для просмотр данных (MEMO).

Существуют также текстовые типы для поиска данных – при описании указываются: символы – разделители слов («», «.», «,»), максимальная длина слова. Этот тип относится к классу множественных полей (под одним именем поля хранится множество значений). Используется в реляционных СУБД, в обычных не используется т.к. противоречит первой нормальной форме.

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

II. Числовые типы.

Включают все типы, встречающиеся в языках программирования: типы с плавающей запятой (Real, Integer), типы с fix запятой (Numeric), денежный, тип – последовательность, тип – интервал.

III. Прочие типы.

Логический (false, true), тип дата, интервал дат, координаты и т.д.

2) Группа – состоит из элементов или других групп. Простая группа состоит только из элементов. В реляционных БД используются только простые группы – атрибуты. Под именем группы хранится таблица строк и её элементов. В реляционных СУБД могут использоваться составные группы – в группу входит другая группа.

FAM	NAME	GR	KAF	должность	должность
Назв.	оклад	Назв.	оклад
Ким	Иван	Ф5-1		Инж.		Лабор.

3) Групповое отношение – состоит из нескольких групп. Множество связанных групповых отношений – логическая структура. Схема группового отношения:

4) Представление – состоит из групповых логических записей. Представление описывается при определении данных, и в него включаются элементы из разных таблиц (связанных отношениями).

Структуры хранения.

I. Организация физических записей.

Логические структуры и физические записи могут быть связаны по-разному:

1. Совпадают

2. хранятся одна в другой в разных соотношениях

II. Способы выделения элементов в физической записи:

1. Элементы хранятся в заданной (вычисляемой) позиции

2. Элементы разделяются разделителем

3. элементы помечаются этикеткой

1.:

а) Элементы начинаются с заданной позиции: ¹ Ким ¹⁸Иван ³⁰Ф5-571

б) Развитие а): информация о начальной позиции хранится в файле.dbt.

в) Хранится информация о количестве символов (числа не учитываются): 3Ким4Иван.. Недостатки – программист должен знать последовательность элементов или начальные позиции.

г) Всю информацию переносят в начало: маркер, справочник, данные. Стандарт ISO 2709

2.: Ким*Иван*Ф5-571*…. Недостаток - разделители нельзя использовать в тексте.

3.: Э1КимЭ2Иван…

Структуры хранения:

1) Последовательный файл

№	Фирма	Статус	город
	Весна Свобода Скороход Днипро Арарат		Москва Москва Спб Киев Ереван

Достоинства – простота

Недостатки – большое время доступа к файлам и большой объём дублирования.

2) Файл с указателем.

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

3) Индексирование по одному элементу

Индекс предназначен для быстрого поиска. Существуют разные способы реализации индекса. Единственная проблема – разное количество указателей. Если определяются индексы по всем полям – инвертированная структура (не путать с инвертированным файлом).

4) Инвертированный файл.

Структура используется в документарно - поисковых системах и Internet. Файл – словарь и собственно инвертированный файл.

5) Списковая структура – структура, в которой не совпадают физическая и логическая последовательность данных.

Логическая структура:

Физическая структура:

Дополнительно добавляем фирму:

Прохоров

Москва

Достоинство: Списковая структура хорошо подходит для изменений и дополнений

Недостаток: Большое время поиска.

Способы ускорения списковых структур:

1.) Экспресс – указатель – дополнительный указатель, который ссылается на много записей вперёд. Иногда добавляется обратный указатель – двусвязанный список.

2.) Зацикливание списка – последний указатель ссылается на первый.

6) Бинарное дерево В – дерево.

Используется для построения индексных файлов.

Логическая структура бинарного дерева:

По алфавиту связи лево – право. В таблице хранятся левые и правые указатели.

7) В + дерево.

На его основе строятся все индексные файлы в современных СУБД. Главное отличие от бинарного дерева – узел дерева хранит не одно, а множество значений ключа, соответствующих определённому интервалу.

8) Иерархическая структура

Реализация:

1й способ

А1	В1	С1	С2	С3	В2	С4	С5	В3
А2	В4	С6	В5	С7	С8	С9

2й способ

9) Хэш–адресация.

Всё пространство памяти (под хранение) делится на фрагменты, и адрес любого фрагмента вычисляется как функция от ключа.

Пример: Хэш-функция

№
	Весна
	Свобода
	Скороход
	Днипро
	Арарат

3)Скороход
2)Свобода	5) Арарат
1) Весна	4) Днипро

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

Поиск – ключ подставляется в Хэш-функцию, подставляем в адрес и ищем на странице.