16. Реляционная модель данных.

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

№с	Сотрудник		№с	№д	Оклад		№д	Должность
С1	Иванов		С1	Д1	150		Д1	Инженер
С2	Петров		С2	Д2	180		Д2	Ст.инженер
С3	Титов		С2	Д4	200		Д3	Водитель
			С3	Д1	140		Д4	Нач.отдела

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

17. Иерархическая модель данных.

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

Минусы – поиск требует обход всего дерева.

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

18. Сетевая модель данных.

Сетевая модель:

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

Поиск:

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

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

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

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

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

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

Файлы организованы по принципу индексных структур (есть указатели).

Минусы: при разрастании системы становится неудобным.

19. ЛОГИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. (ЭЛЕМЕНТ, ГРУППА (КОРТЕЖ), ОТНОШЕНИЕ, ПРЕДСТАВЛЕНИЕ)

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

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

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

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

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

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

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

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

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

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

7. Тип

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

Типы данных:

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

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

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

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

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

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

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

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

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

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

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

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

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

20. ОРГАНИЗАЦИЯ ФИЗИЧЕСКИХ ЗАПИСЕЙ. СПОСОБЫ ВЫДЕЛЕНИЯ ЭЛЕМЕНТОВ В ФИЗИЧЕСКОЙ ЗАПИСИ.

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

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

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

1. Совпадают

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

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

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

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

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

1.:

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

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

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

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

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

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

21 Структуры хранения. Понятие метода доступа.

Внимание специалистов к структурам хранения и методам доступа вызвано очень медленной внешней памятью. Основным способом повышения производительности является минимизация числа дисковых операций ввода-вывода данных.

любое упорядочение (расположение) данных на диске называется структурой хранения. Можно организовать самые разные структуры хранения, обладающие различной производительностью и оптимальные для различных способов использования. Однако не существует идеальной структуры хранения, которая была бы оптимальна для любых задач. Исходя из этого, можно заключить, что совершенная СУБД должна содержать несколько разных структур хранения для различных частей системы. Кроме того, следует также предусмотреть возможность изменения структуры хранения по мере изменения требований к производительности системы.

1.                Сначала в СУБД определяется искомая запись, а затем для ее извлечения запрашивается диспетчер файлов.

2.                Диспетчер файлов определяет страницу, на которой находится искомая запись, а затем для извлечения этой страницы запрашивает диспетчер дисков.

3.                Наконец, диспетчер дисков определяет физическое положение искомой страницы на диске и посылает соответствующий запрос на ввод-вывод данных.

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

Диспетчер файлов. При работе с диском как набором хранимых файлов, диспетчер файлов использует все имеющиеся средства диспетчера дисков согласно определенному в СУБД способу. При этом каждый набор страниц может содержать один или несколько хранимых файлов. Каждый хранимый файл имеет имя (file name) или идентификационный номер (file ID), уникальные в данном наборе страниц. А каждая хранимая запись, в свою очередь, обладает идентификационным номером записи (record number или record ID), уникальным, по крайней мере, в пределах данного хранимого файла.

22. ПОСЛЕДОВАТЕЛЬНЫЙ ФАЙЛ, ФАЙЛ С УКАЗАТЕЛЕМ, ИНДЕКСИРОВАНИЕ ПО ОДНОМУ ЭЛЕМЕНТУ.

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

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

№	Фирма	Статус	город
1 2 3 4 5	Весна Свобода Скороход Днипро Арарат	10 20 30 20 30	Москва Москва Спб Киев Ереван

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

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

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

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

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

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

23. ИНВЕРТИРОВАННАЯ ОРГАНИЗАЦИЯ ФАЙЛОВ.

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

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

24. СПИСКОВЫЕ СТРУКТУРЫ (списки).а

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

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

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

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

6

Прохоров

50

Москва

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

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

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

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

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

25. ХЭШ-АДРЕСАЦИЯ.

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

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

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

0	1	2	3
	3)Скороход
4	5	6	7
	2)Свобода	5) Арарат
8	9	10	11
	1) Весна	4) Днипро
12

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

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

Хэш-функции вычисляют адрес страницы, на которой будет храниться запись, на основе одного или более полей в записи. Функции хэширования, выбираются для того, чтобы обеспечить равномерное распределение адресов через адресное пространство. ‘размещение’ как правило, 40 % — 60 % от общего размера файла. уникальный адрес не гарантируется этим методом, поэтому необходимы механизмы определения столкновений и механизмы исправления столкновений. открытая адресация; цепное/ нецепное переполнение. Плюсы и минусы; эффективен для точных соответствий по ключевым полям; не подходит для диапазона поиска, который требует последовательного хранения; вычисляет, где хранятся записи, на основе полей в записи; хэш-функции обеспечивают равномерное распределение данных; Возможны столкновения, поэтому требуются обнаружение столкновений и восстановление.