Реферат: Правила Джексона для перехода от модели Чена к реляционной модели. Реляционная модель данных. 12 правил Кодда

Базы данных [24-26]


Проектирование базы данных с помощью нормализации.

Операция «соединение» и ее свойства.

Разложение без потерь. Теорема. Примеры.

Полностью соединимые отношения. Примеры.

Операторы описания данных в SQL.

Операторы манипулирования данными в SQL.

Управление транзакциями.

Технологии «клиент-сервер».

Оператор Select.

Индексация. Достоинства и недостатки. Примеры.

В-дерево. Добавление и удаление элементов.

Методы прямого доступа.

Архитектуры БД.

Управление правами доступа в SQL.

Модель Чена.

Примеры бинарных связей.

Правила Джексона для перехода от модели Чена к реляционной модели.

Реляционная модель данных. 12 правил Кодда.

Ограничения целостности в реляционной модели данных и их поддержка в SQL.

Восстановление данных в БД.

1. Проектирование базы данных с помощью нормализации.

^ Проектирование реляционной базы данных.

Проектирование состоит в разложении таблиц на элементарные таблицы, так чтобы не возникали аномалии технологических операций. Таблицы, отвечающие условиям отсутствия аномалий технологических операций, называются нормальными формами (Н.Ф.).

1Н.Ф.


2Н.Ф.


3Н.Ф. Н.Ф.Б.К.


4Н.Ф.


5Н.Ф.

Таблица находится в первой нормальной форме (1Н.Ф.), если все ее атрибуты атомарные.

Таблица находится во второй нормальной форме (2Н.Ф.), если она находится в 1Н.Ф. и все не ключевые атрибуты функционально полно зависят от ключа.

Таблица находится в третьей нормальной форме (3Н.Ф.), если она находится во 2Н.Ф. и устранены транзитивные зависимости внутри таблицы.

Таблица находится в нормальной форме Бойса-Кодда (Н.Ф.Б.К.), если она находится во второй нормальной форме и каждая детерминанта функциональной зависимости является возможным ключом ( , где является детерминантом).

Таблица находится а четвертой нормальной форме (4Н.Ф.), если она находится в третьей нормальной форме и в ней поддерживаются все возможные многозначные функциональные зависимости.

Таблица находится в пятой нормальной форме (5Н.Ф.), если она разложима без потерь.

Проектирование реляционной базы данных начинается с универсального отношения. Универсальное отношение – это одна таблица, которая содержит все атрибуты, используемые в нашей системе. Например, универсальное отношение для базы Поставщик- Деталь-Поставка имеет вид:

фамилия

статус

Город пос-

тавщика

Название детали

вес

цвет

Город детали

количество

Иванов

70

Пермь

гайка

12

красный

Пермь

100










болт

13

синий

Кунгур

200

...






















...






















Проектирование сводится к постепенному переводу универсального отношения к пятой нормальной форме.

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

Чтобы прейти ко второй нормальной форме нужно разбить данную таблицу на таблицы, так чтобы это было разложение без потерь. Для этого разобьем таблицу на две, первая будет содержать поля - фамилия поставщика (ключ), статус, город поставщика, вторая таблица будет содержать поля – фамилия поставщика, название детали, вес, цвет, город детали, количество, причем фамилия +название детали=ключ.

После данного разбиения первая таблица будет находится не только во второй нормальной форме, но и в третьей. А во второй таблице сохранятся аномалии технологических операций, т.е. вторую таблицу необходимо еще разбить на две: таблица 2.1 с полями - название детали, вес, цвет, город детали; таблица 2.2 с полями - фамилия поставщика, название детали, количество(эти две таблицы находятся в 3Н.Ф.).


^ Метод нормализации.


Метод начинается с универсального отношения и основан на постепенном переходе к пятой нормальной форме.

Пример:

Фамилия автора

произведение

Пушкин

Евгений Онегин, Капитанская дочка, ...

Лермонтов

Герой нашего времени, Кавказский пленник, ...

В этой таблице атрибут Произведение является повторяющейся группой, таблица не является нормализованной. Для перехода к первой нормальной форме дублируем:


автор

произведение

Пушкин

Евгений Онегин

Пушкин

Капитанская дочка

Пушкин

...

Лермонтов

Герой нашего времени

Лермонтов

Кавказский пленник

Лермонтов

...

Таблица находится в первой нормальной форме, является реляционной таблицей.

Пример:

r( поставщик, статус, город поставщика, деталь, количество) – это универсальное отношение. Установим функциональные зависимости:

поставщик +деталь = первичный ключ;

П+Д С (от поставщика и детали зависит статус);

П+Д Г (город);

П+Д К (количество);

Г С;

П С;

П Г.

Получаем ситуацию, когда некоторые атрибуты полностью зависят от комбинации П+Д, а некоторые атрибуты зависят только от П, т.е. присутствует неполная функциональная зависимость, а также присутствуют аномалии добавления, удаления, изменения. Разобьем таблицу на 2, так чтобы сохранились функциональные зависимости:

Т1(Поставщик, Статус, Город), Т2(Поставщик, Деталь, количество). Данные 2 находятся во второй нормальной форме. Установим функциональные зависимости для Т1:

П С;

П Г;

Г С.

П С это транзитивная зависимость.




Г

В таблице Т1 сохраняются аномалии технологических операций: при удалении поставщика теряется зависимость Город Статус, не можем добавить нового поставщика пока не знаем статуса города. Следовательно необходимо таблицу Т1 разбить еще на 2: Т11(П,Г) и Т12(Г,С).

Таблицы Т11, Т12, Т2 представляют нашу базу в третьей нормальной форме.

Пример:

Т(№служащего, фамилия, №проекта, название работы).

Предположим, что в таблице нет однофамильцев, тогда ключом является либо №служащего+№проекта, либо фамилия+№проекта,

тогда №служащего фамилия. Приведем таблицу в Н.Ф.Б.К., для этого разложим таблицу на две: Т1(№служащего, фамилия), Т2(№служащего, №проекта, Название работы).

Пример:

Т(№детали,№проекта,№поставщика).

№проекта+№детали №поставщика;

№поставщика №проекта. Следовательно нужно разбить еще на 2:

Т1(№детали, №поставщика) и Т2(№поставщика,№проекта).

Чтобы перевести таблицу в 4Н.Ф. нужно многозначную Ф.З. выделить в отдельную таблицу, в 5Н.Ф. все таблицы должны соединяться без потерь.


^ 2. Операция «соединение» и ее свойства.


Операция соединения (основная).


Обозначение: Join или .

Существует внутренняя операция соединения и внешняя, при этом внешняя делится на правую и левую.

Внутренняя

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

r(A,B,C) s(A,B,D) = q(A,B,C,D)

11a 112a

11b 112b

123 42c 113a

113b

421c

операция соединения для таблиц с одинаковыми схемами равносильна операции пересечения:

r(A,B) s(A,B) = q(A,B)

11 11 11

12 42 42

14

42

Операция соединения для таблиц с разными схемами равносильна декартовому произведению:

r(A,B) s(C,D) = q(A,B,C,D)

11 cd 11cd

12 c1d 11c1d

14 12cd

42 12c1d

14cd

14c1d

42cd

42c1d

б) Тета-соединение ().

Это соединение не обязательно по равенству, операция соединения происходит по любой операции сравнения(=(эквивалентное соединение),<>, <,>).

Тета-соединение осуществляется не обязательно по одноименным столбцам, а по разным тоже, но столбцы должны быть определены на одних и тех же доменах.

r(A,B,C) s(D,E) = q (A,B,C,D,E)

B=D

a1c 1e a1c1e

a12c 1e1 a1c1e1

a11c2 2e a2c2e

a13c 2e1 a12c2e1

a11c21e

a11c21e1

r(A,B,C) s(D,E) = q (A,B,C,D,E)

B>D

a1c 1e a12c1e

a12c 1e1 a12c1e1

a11c2 2e a13c1e1

a13c 2e1 a13c1e

a13c2e

a13c2e

внешнее соединение. Рассмотрим на примере естественного соединения. тогда внешнее соединение выполняется по тем же правилам, что и естественное, но в ответ выписываются строки из левой таблицы, если соединение левое (из правой таблицы, если соединение правое).

Пример:

r(A,B,C) s(A,D) = q(A,B,C,D)

left

1ac 1d 1acd

2a1c 2d 1acd1

1ac1 1d1 2a1cd

3ac 1ac1d

4a1c 1ac1d1

3ac null

4a1c null


Свойства

С помощью операции соединения можно выполнить операцию селекции, при этом операция селекции равносильна квантору существования.

Если дано r(R), и необходимо выполнить операцию селекции , то ее можно выполнить с помощью операции соединения r s(A)

a

Пример

Запрос: существует ли поставщик из Березников со статусом 80?

(Поставщик s(город, статус))

Березники, 80

Операция соединения коммутативна:

r s = s r

Операция соединения ассоциативна:

r1 (r2 r3)=(r1 r2) r3

Операция соединения дистрибутивна относительно операций пересечения, объединения и разности:

(r1r2) s = (r1s) (r2s);

(r1r2) s = (r1s) (r2s);

(r1\r2) s = (r1\s) (r2\s)/

Свойство идемпотентности:

q q=q;

q r = q (q r )

Свойство полусоединения:

(r s) = (r) s


^ 3. Разложение без потерь. Теорема. Примеры.


Условие разложения без потерь.


q(R,S) r= s=

r s==q’

q’q(R,S) т.е. q’ есть надмножество q

Если q’=q, то это разложение без потерь.


Пример:

R(X,Y,Z) r1(X,Y) r2(X,Z) r1 r2 = (X,Y,Z)

123 12 13 123

323 32 33 127

117 11 17 122

132 13 12 323

417 41 47 113

117

112

133

137

132

417

то есть это разложение с потерями.

Рассмотрим другое измерение:

r3(X,Y) r4(Y,Z) r3 r4 = (X,Y,Z)

12 23 123

32 17 323

11 32 117

13 132

417

это разложение без потерь.


^ 4. Полностью соединимые отношения. Примеры.


Условие полного соединения.


Дано r(R) и s(S), тогда q(RS)=r s

, если выполняется равенство, то r полностью соединимо.


, если выполняется равенство, то s полностью соединимо.


Пример:

r(A,B) s(A,B) q(A,B,C)

ab1 b1c ab1c

ab2

A,B

ab – неполное соединение

B,C

b1c - полное соединение.

Для того чтобы было полное соединение необходимо, чтобы в соединяемых столбцах были все значения R и S.


^ 5. Операторы описания данных в SQL.


Типы данных в SQL.

Integer – целое,занимает 4 байта;

Smallint - короткое целое, занимает 2 байта;

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

Float – число с плавающей точкой, занимает 8 байт;

Smallfloat – короткое число с плавающей точкой, занимает 4 байта;

decimal(P[,n]) – упакованное число, Р – общее количество цифр в числе, n- обозначает сколько чисел после запятой, C положительное число, D – отрицательное;

money(P,n) – для представления денежных едениц;

date – для хранения дат;

datetime a to b – временный интервал от а до b, значения а и b могут быть следующие:

year

day

month

hour

minute

second

fraction(1,2,3),

например, datetime year to hour 2000-04-10-13

char – строки постоянной длины;

char(n) – строки постоянной длины до n;

varchar – строки до 255;

varchar(n) – строки до n;

text – произвольные тексты до 2ГБ;

byte произвольная последовательность байтов до 2ГБ;

null – пустое значение, причем 2 пустых значения не равны между собой.


Атрибуты, используемые для описания таблиц.

Атрибуты, описывающие характеристики столбца:

^ Primary key - данное поле является первичным ключом;

References имя_таблицы (имя_поля) – данный столбец является внешним ключом, он взят из таблицы и поля, указанного в атрибуте;

Not null – в этом столбце не должно быть пустых значений;

^ Default значение – указывает значение, которое принимается по умолчанию.

Unique - все значения в этом поле должны быть уникальными, по умолчанию поле Primary key должно быть Not null и Unique;

Check (Условие) – задает условие, которое должно быть истинным при заполнении информации в этом поле.

^ Атрибуты на уровне таблицы.

Check (Условие) – это значение должно быть истинным, чтобы компьютер признал все изменения правильными;

Unique (список полей) – все значения в комбинации полей должны быть уникальными;

^ Primary key (список полей) – указывается на уровне таблицы, если первичный ключ состоит из нескольких полей;

References имя_поля1 from имя_таблицы1 (поле1) – в нашей таблице имя_поля1 берется из таблицы1, поля1.


^ 6. Операторы манипулирования данными в SQL.


Добавление информации в таблицу.

Insert into имя_таблицы (список полей) values (список выражений)

добавление одной записи,

Чтобы добавить несколько значений из другой таблицы можно использовать следующий оператор –

Insert into имя_таблицы [(список добавляемых полей)]

или использовать полузапрос

select список полей

from список таблиц

where условие

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

Оператор обновления.

Update имя_таблицы set поле=значение [where условие] (все что записано в квадратных скобках это не обязательно, может быть, а может и не быть).

Удаление записи из таблицы.

Delete from имя_таблицы [where условие]

Если where условие опущено, то удаляются все записи.

Оператор поиска данных в таблицах

distinct

Select all список_полей from список_таблиц

[where условие] [group by список_полей] [having условие]

[order by поля[asc,desc]] [union [all] подзапрос]


distinct – режим, исключающий повторяющиеся записи в ответе.

All – режим, при котором в ответ включаются все записи. По умолчанию принято all, его можно не указывать.

Если одновременно присутствует where и having, то сначала будет выполняться where.

Если присутствует where, having, group by, то сначала выполнится where, потом group by, а потом having.

Select список_полей - указывает имена полей, которые должны содержаться в ответе;

from список_таблиц – указывает имена таблиц, которые участвуют в запросе;

where условие – задает условие отбора записей в ответ;

group by список_полей – задает условие группировки записей, группировка – это операция разбиения на группы, каждая из которых содержит одинаковые значения в отмеченных столбцах;

having условие задает условие отбора групп, если нет group by, то это условие применяется ко всей таблице;

order by поля[asc,desc] – задает тип сортировки записей в ответе, asc – это сортировка по возрастанию, desc – по убыванию, по умолчанию ставится asc;

union [all] подзапрос позволяет объединить главный Select с результатом подзапроса, подзапросом называется вложенный оператор Select.


^ 8. Технологии «клиент-сервер».


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

Клиент – это программа или компьютер, обращающийся к услугам сервера

Существуют разные технологии клиент-сервер.

Любая программа может быть представлена из нескольких частей:

Ввод/вывод (интерфейсная часть);

Вычисление на основе каких-либо бизнес правил;

Обращение к данным;

Управляющая часть, создает единый алгоритм.

В зависимости от того, как поделить эти части между сервером и клиентом, получаются различные технологии.


^ 1 вариант - файловый сервер.
Введем обозначения: К – клиент, С – сервер.

К выполняет 1,2,4 части, а на С содержится информация, необходимая для запроса, т.е. С выполняет 3 часть.

запрос

К С

ответ-файл

В данной технологии основная нагрузка падает на клиента.

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




Запросы пишутся на динамическом SQL. А в ответ получаем ту порцию информации, которую запросили, эта порция информации называется курсором.

Динамический SQL - это операторы SQL, которые передаются и выполняются не сервере.

Имеют место следующие операторы:

Prepare имя_оператора from строка

Select

Insert

Delete

Update

Execute имя_оператора – позволяет выполнить запомненный на сервере оператор;

Drop имя_оператора – позволяет удалит оператор;

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

Exec sql “sql оператор”.

Описание курсора на SQL:

Declare имя_курсора [scroll] cursor for подзапрос [for update].

Курсор может быть обычным, то есть просматриваемым в одном направлении, от начала к концу, если стоит scroll, то просматривать курсор можно в любом направлении. Если стоит for update, то это значит, что курсор изменяемый, все изменения будут запоминаться на сервере.

Операции с курсором:

Open имя_курсора – позволяет получить курсор;

Fetch имя_курсора – позволяет перейти к следующей записи курсора, если перед именем курсора поставить Last, то перейдем к последней записи, First – к первой записи, Current к текущей;

Close имя_курсора – закрытие курсора, но он остается определенным;

Free имя_курсора – удаление курсора.


^ 3 вариант – сервер Базы Данных.





Бизнес-правила хранятся на сервере в виде хранимых процедур. Хранимые процедуры – это программы, написанные на некотором языке хранимых процедур с SQL вставками. Их можно написать заранее и поместить в библиотеку.


^ Рассмотрим операторы для программирования хранимых процедур.

Create имя_процедуры (параметры)

[return список выходных данных]

тело

End procedure - создание процедуры;

Execute procedure имя (аргументы)[into список переменых] -– выполнение процедуры, созданной заранее;

drop procedure имя – удаление хранимой процедуры;

define список переменных – позволяет объявить переменные, которые являются локальными в хранимой процедуре;

call имя (аргументы) into список переменных – позволяет вызвать другую процедуру;

переменная:=выражение – присвоение;

if условие then оператор [else оператор] end if – условный оператор;

операторы цикла

for переменная:=целое1

to целое2 step целое

end for


while условие

тело

end while


for each имя_курсора

операторы

end for each


Среди операторов ТЕЛА используются следующие:

Exit - позволяет выйти из цикла до его завершения;

Continue – позволяет начать выполнение цикла, не заканчивая предыдущий шаг;

System – позволяет выполнить команды ОС;

Return – позволяет сформировать результаты и вернуть их из процедуры;

Begin

. – блок, часть пограммы, в которой могут быть объявлены

. локальные переменные.

end
^ 4 вариант – сервер приложений.



С помощью протокола API передается информация о том какие программы и в какой последовательности нужно выполнять.

В технологии клиент-сервер есть специальные активные программы, которые называют триггерами.

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

Create trigger имя событие_действие - создание триггера;

Drop trigger - удаление.

Запись события:

Insеrt on имя_таблицы – наступает тогда, когда в таблицу заносится информация;

Delete on таблица – наступает при удалении из таблицы;

Update of список_полей on имя_таблицы - возникает при изменении заданных полей в указанной таблице.

Действия бывают трех видов:

Before (оператор) – перед добавлением, удалением, изменением;

Foreach row (оператор) – для каждой строки таблицы;

After (оператор) после добавления, удаления, изменения.

В триггерах есть возможность сослаться на одно и тоже поле до изменения и после:

Referencing old as имя – запомнить до изменения;

Referencing new as имя – запомнить после изменения;

When (условие)(оператор) – задает дополнительные условия для работы с триггерами.

Пример.

Изменить статус поставщиков только в том случае, если новый статус не меньше старого и не больше 100%.

Нужно создать триггер, который будет обновлять статус:

Create trigger Sstat

Update of статус on Поставщики

Referencing old as c1

Referencing new as c2

Foreach row

When ( с1.статус >=с2.статус)

Execute procedure error (с1.статус,с2.статус)

When (с2.статус>100%)

Execute procedure error1 (с1.статус,с2.статус)


9. Оператор Select.


Оператор поиска данных в таблицах

distinct

Select all список_полей from список_таблиц

[where условие] [group by список_полей] [having условие]

[order by поля[asc,desc]] [union [all] подзапрос]


distinct – режим, исключающий повторяющиеся записи в ответе.

All – режим, при котором в ответ включаются все записи. По умолчанию принято all, его можно не указывать.

Если одновременно присутствует where и having, то сначала будет выполняться where.

Если присутствует where, having, group by, то сначала выполнится where, потом group by, а потом having.

Select список_полей - указывает имена полей, которые должны содержаться в ответе;

from список_таблиц – указывает имена таблиц, которые участвуют в запросе;

where условие – задает условие отбора записей в ответ;

group by список_полей – задает условие группировки записей, группировка – это операция разбиения на группы, каждая из которых содержит одинаковые значения в отмеченных столбцах;

having условие задает условие отбора групп, если нет group by, то это условие применяется ко всей таблице;

order by поля[asc,desc] – задает тип сортировки записей в ответе, asc – это сортировка по возрастанию, desc – по убыванию, по умолчанию ставится asc;

union [all] подзапрос позволяет объединить главный Select с результатом подзапроса, подзапросом называется вложенный оператор Select.


^ Рассмотрим пример использования оператора поиска на примере БД о поставщиках, деталях и поставках.

Запрос - выдать информацию о всех деталях:

Select * from Детали 2 варианта

Select код_детали, вес, цвет, город from Детали

Звездочка * означает, что нужно выдать все поля из таблицы.

Выдать номера всех поставляемых деталей:

Select distinct код_детали from Поставки

Получит информацию о красных деталях, которые находятся в Лондоне:

Select * from Детали where цвет=’красный’ and город=‘Лондон’ order by вес DESC

Это конъюнктивный запрос, записи в ответе будут отсортированны по убыванию веса.


^ 10. Индексация. Достоинства и недостатки. Примеры.


Индекс – это таблица, состоящая из двух полей, первое поле – это ключ, второе поле – это ссылка на запись в БД с этим ключом индексации.

Индекс позволяет выполнить две работы:

Выполнить сортировку файла не перемещая физически его записи;

Ускорить поиск информации.

Пример.

Файл а1:

адреса

А1

А2

А3

A0

d

1

F

A1

a

2

M

A2

C

3

F

A3

B

4

M

A4

Z

3

M

A5

I

2

F

A6

J

2

M

A7

k

5

M


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

Запишем файл упорядоченный по полю А1:

B

A1

адрес

B1

A

A1

B2

B

A3

B3

C

A2

B4

D

A0

B5

I

A5

B6

J

A6

B7

K

A7

B8

Z

A4

Создадим индекс второго уровня, для этого разбиваем индекс на группы по три записи:


A1

адрес

C

B1

J

B4

z

B7

В первом столбце записан старший ключ, во втором столбце младший ключ.

Рассмотрим, например поиск записи с ключом I.

Смотрим в последнюю таблицу и ищем где ключ больший I, это J, его адрес B4, теперь обращаемся ко второй таблице, находим тройку записей, у которой младший индекс B4, это тройка D,I,J, находим в ней I, смотрим какой она имеет адрес – A5, обращаемся в первую таблицу и находим запись с адресом А5.


Индекс с инвертированными списками.

Инвертированный список хранит список ключей для каждого значения где это значение встречается.


А3

Список адресов

F

A0, A2,A5

M

A1,A3,A4,A6,A7



^ 11. В-дерево. Добавление и удаление элементов.


В-дерево – это сбалансированное дерево.

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

В основе В-дерева лежат следующие аксиомы:

В-дерево порядка n содержит 2n ключей 2n+1 ссылку;

В –дерево растет от листьев к корню;

Путь от корня к листу содержит одно и тоже количество шагов;

Каждый узел заполняется не менее чем на половину, кроме корня.

Пример.

Пусть у нас есть дерево третьего порядка, с ключами 12, 8, 4, 9, 6, 13, 14, 16,100, 10.

Приходит ключ 12, его заносим в корень


12

П
8 12
риходит 8, 8 меньше 12


Приходит 4, места в корне нет, разбиваем на 2




Приходит 9, она больше 8, но меньше 12, 12 сдвигаем, перед ней записываем 9, приходит 6 она меньше 8, но больше 4, записываем ее после 4:




После того как придет 13, 14, 16, 100, 10 вид дерева будет следующим:




^ 12. Методы прямого доступа.


Прямой доступ.

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

Инвертированные списки.

Существует 2 варианта:

1. Фамилия телефон

Фамилия телефон

Фамилия телефон

2. разбиение диска на блоки таким образом, что в каждом блоке информация с определенным ключом.

Примером может послужить картотека в библиотеке, например, один ящик с названиями книг от А до Н, второй ящик с книгами от О до Я.

Индексно–последовательный метод доступа. Пример – оглавление в книге.

Индекс – это таблица, состоящая из двух столбцов; в первом столбце в сортированном порядке находится ключ индексации (№ главы, параграфа); во втором столбце находятся ссылки той информации, которая соответствует ключам (№ страниц).


1

2

Глава 1

Стр.3

Глава 2

Стр.23



^ 13. Архитектуры БД.


Построение архитектуры БнД – это принятый способ построения банка целью обеспечения физической и логической независимости.

Физическая независимость – независимость хранимой информации от носителей, на которых располагается информация.

Логическая независимость – это независимость данных от программ их обработки.

Архитектура чаще всего трехуровневая:





^ Ядро – концептуальная модель – суммарное представление всех пользователей БнД.

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

Внешние модели в совокупности дают концептуальную модель.

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

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


^ 15. Модель Чена.


ER-модель (модель Чена).

Модель сущность-связь – используется для формального представления из предметной области.

Основные понятия:

Сущность (объект) – активно действующий субъект в ПО, информация о котором важна с точки зрения данной ПО. Чаще всего сущность называется существительным.

В диаграмме Чена есть 2 варианта:

ER диаграммы-экземпляров

ER диаграммы-типов.

Тип объекта – это множество значений, которые могут принимать объекты, и множество операций, которые можно проводить с ними.

Работаем не с каждым объектом отдельно, а объединяем их в типы.


Атрибут (свойство) – это характеристика, которая показывает в чем сходство или различие конкретных экземпляров объекта. При этом мы должны использовать столько свойств, чтобы можно было отличить экземпляры.


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

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


Отношения (связи) между сущностями.

Связи – это глаголы или отглагольные формы.


Так представлены диаграммы – типов:


сущности

атрибуты - первичный подчеркивают


отношения

Пример. Поставщики поставляют детали, нас интересует адрес и сколько деталей.


В предметной области две сущности

n поставка n

Поставщик постав- деталь

ляет


код пост код дет.

ФИО статус внешний ключ код нимено

степень детали вание

доверия %

код пост адрес адрес вес




повторяющиеся значения

и пустые не допускаются


Связь имеет свои атрибуты

В поставке ключом является комбинация: код пост. и код дет., а по отдельности - это внешние ключи. Существует также дополнительный код поставки – в данном случае это количество.


^ 16. Примеры бинарных связей.


Виды связи

Оно показывает, сколько экземпляров одного объекта вступает в связь со сколькими экземплярами другого объекта.

Вид связи это не абсолютная характеристика и меняется в зависимости от предметной области, в которой и работает.


Виды связи бывают:


1:1

1:n (один ко многим)

n:1 (многие к одному)

n:n (многие ко многим)


Класс принадлежности указывает все ли объекты вступают в связь или есть такие, которые не связаны. Бывает:

- обязательный класс принадлежности (все объекты обязательно вступают в связь) в диаграмме типов обозначается


- необязательный класс принадлежности (есть объекты, которые в связь не вступают) обозначается в диаграмме типов


Пример видов связей. (16 – вариантов)

Предметная область – преподаватель читает некоторые лекции.

Пример: тип связи один ко одному.

Существует ПО такая, что один преподаватель читает не больше одной дисциплины, каждая дисциплина читается не больше чем одним преподавателем.

ER-диаграмма экземпляров

преподаватель предмет

1 1

2 2

3 3

4 4

5

тогда диаграмм типов следующая



1 1


Другой вариант

- дисциплина читается обязательно одним преподавателем.










1 1


Третий вариант

- преподаватели все должны читать лекции, но есть предметы, которые не читаются.

1

2

3

4

5

6


1 1


Четвертый вариант

- преподаватель читает одну дисциплину, предмет читается один раз.





4




1



пример: тип связи один ко многим

- преподаватель читает несколько дисциплин, предмет читается не больше чем одним преподавателем.






1 n


- преподаватель читает несколько дисциплин, предмет читается не больше чем одним преподавателем, дисциплины должна быть прочитаны все.










1 n


-преподаватели читают несколько дисциплин, дисциплины и преподаватели все заняты, дисциплина читается одним преподавателем .













5

6

n




- все преподаватели заняты, могут читать несколько предметов.










5

6

7


n



Пример многие к одному

- одна дисциплина может читаться несколькими преподавателями. Преподаватель не может читать несколько дисциплин.












n 1


- одна дисциплина может читаться несколькими преподавателями, все преподаватели заняты.







n 1




- одна дисциплина может читаться несколькими преподавателями, все предметы заняты.










n 1


- одна дисциплина может читаться несколькими преподавателями, все преподаватели и предметы заняты.










n 1


Пример многие ко многим

- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями.







n n


- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями, все предметы и преподаватели заняты.







n n


- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями, заняты все преподаватели.




n n


- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями, заняты все дисциплины.












n n


Рекурсивные связи

-возникают внутри одного и того же объекта.

Существует два типа рекурсивных связей:

-1:n;

-n:n;

1:n – например, отношение сотрудник- подчиненный на множестве подчиненных (но начальник тоже сотрудник).




n

1


Сотрудник в данном случае имеет роль начальника

Вводится понятие роль – это таблица, соединенная сама с собой. Для того чтобы различать объекты даем им разные роли.

n:n

Пример:

Описание структуры изделие, изделие состоит из сборочных единиц.

Изобразим граф изделия:







В данном графе 2,3,4 – это узлы, а 5,6,7 – это детали. Числа рядом с линиями показывают в каком количестве детали входят в узлы, например, в узел 2 входят 3 детали 5, 2 детали 6 и 1 деталь 3.

Роль деталь имеют те сборочные единицы, которые где-то применяются: 2-7.

Узел собирается из нескольких сборочных единиц: 1-4.между ними существует связь:




В реальном проектировании связь М:М представляется в виде трех отношений, причем между 1 3 – 1:М, между 2 и 3 – 1:М.

Таблица 1:

Сборочная единица

1

2

3

4

5

6

7



Таблица 2 (сборка):

Роль- узел (1)

Роль- деталь (2)

Количество (3)

1

2

2

1

3

3

1

4

2

2

3

1

2

5

3

2

6

2

3

5

2

3

7

2

4

6

1

4

7

3

Из этих таблиц:

№изделий = 1\2;

№деталей = 2\1;

№узла = 12.


^ 17. Правила Джексона для перехода от модели Чена к реляционной модели.


7 правил Джексона.


Из модели Чена, используя эти правила, сразу можно получить нормальную форму.

Если отношения 1о:1о (ин