60.3 Проектирование реляционной бд, функциональные зависимости, декомпозиция отношений, нормальные формы.

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

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

1) в таблице не м.б. двух кортежей (строк) с одинаковым содержанием;

2) все знач-я в столбце любой таблицы явл-ся однородными, т.е. отображают одну и ту же хар-ку кортежа;

3) кажд. столбец во всей схеме БД должен иметь уникальн. наименование, и если наименов-ие столбцов в различных таблицах совпадают, то это одна и та же хар-ка различных классов объектов;

4) кажд. таблица в сх-е описания данных должна иметь уникальное имя;

5) кажд. элемент таблицы д.б. элементом дан-х либо агрегатом данных.

6) связи на схеме устанавлив-ся только за счет одноименных данных в таблице.

Реляционные от англ. отношения. Область опред-ия атрибута элемента данных наз-ся доменом (Dom(Aj)). Таблица, состоящая из двух столбцов-бинарная, из 3-тернарная, из n-n-арная. Таблица, удовлетвор-ая перечисленным требованиям, находится в 1НФ.

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

Правила преобраз-я: Если м/у двумя лог.записями установл. связь 1:М, то ключ-е поле 1-го типа записи дополняется во 2-ой тип записи и становится неключевым. Если м/у двумя типами записи установл. связь М:М,то формируем новый тип записи, содерж-ий только ключ. поля исходн. записей; связь М:М удаляется из записи, от старых типов записи к новому устанав-ся связь 1:М (рис1)

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

Вывод: реляц. модели наиболее полно реализуют принцип назавис-ти данных.

1НФ – отношение, в котором на пересечении каждой строки и каждого столбца содержится только одно значение.

Ниже приведено определение концепции функциональной зависимости для второго пункта.

Пусть R является переменной отношения, а X и Y – произвольными подмножествами множества атрибутов отношения R. Тогда Y функционально зависимо от X, что в символическом виде записывается какXY (и читается либо как "X функционально определяет Y ", либо как "X стрелка Y "), тогда и только тогда, когда для любого допустимого значения отношения R каждое значение Х связано в точности с одним значением Y.

Иначе говоря, для любого допустимого значения отношения R, когда бы два кортежа отношения R ни совпадали по значению X, они также совпадают и по значению Y.

Students
StNo	GrNo	StName	CityNo
1	1	Иванов	1
2	1	Петров	3
1. SGN				SC
StNo	GrNo	StName		StNo	CityNo
1	1	Иванов		1	1
2	1	Петров		2	3

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

Теорема Хеза. Пусть R{A, B, C} является отношением, где A, B, C – атрибуты этого отношения. Если R удовлетворяет зависимости AB, то отношение R равно соединению его проекций {A, B} и {A, C}.

Говорят, что отношение находится в некоторой нормальной форме, если удовлетворяет заданному набору условий. Например, отношение находится в первой нормальной форме, или сокращенно в 1 НФ, тогда и только тогда, когда оно содержит только скалярные значения.

Отсюда следует, что каждое нормализованное отношение находится в первой нормальной форме. Иначе говоря, термины "нормализованное" и "1НФ" означают одно и то же. Однако следует отметить, что термин "нормализованное" часто используется для обозначения нормальной формы более высокого уровня, хотя такое обозначение не очень корректно.

Все нормализованные отношения находятся в 1НФ.

Первая, вторая и третья нормальные формы.

1НФ – отношение, в котором на пересечении каждой строки и каждого столбца содержится только одно значение.

Вторая нормальная форма.

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

Атрибут A функц-но полностью зависит от набора атр-тов X, если он функц-но зависит от X и не зависит от любого подмн-ва X.

Дано отношение R, определ-ое на мн-ве атрибутов U={А₁,…,А_n} и F- исходное мн-во функцион-ых завис-ей. Атрибут В функционально полностью зависит от мн-ва атр. Х, если х->BЄF⁺ и ни для какого y истинного подмнож-ва Х (yCX) не выполнено y->BЄF⁺. Отношение R находится в 2НФ, если оно находится в 1НФ и любой атрибут, не являющийся эл-ом ключа, функцион-но полностью зависит от любого первичного ключа в R.

Способы формирования F.

1)Послед-но формируем сочетания без повторений из n-элементов по k, где k=1,2,3..n. Для атрибутов, соответств-их текущ. сочетанию, определяем мн-во атрибутов, которые функц-но полностью определяются этим сочетанием. Преребор прекращается, если сформиров-ые функц-ые завис-ти содержат все атр. из мн-ва U.

2)Последовательно просматриваем атр. Из мн-ва U и для текущего выпис. мн-ва атр-ов, которыми он функц-но полностью определяется.

Правило формирования 2НФ.

1.В мн-ве F объединяем функц-ые завис-ти с совпадающими лев.частями

x->Ai

x->Aj =>x->AiAj

Объединяем завис-ти с совпадающими обл-ми опред-ия.

2.Формируем декомпозицию исходн. cхемы R: Разбиваем мн-во атр. U на подмнож.y₁,…,y_K т.о., что в y₁ входят атр-ы 1-ой функц. зав-ти, в y_K атр. из k-ой функц. завис-ти. Мн-ва y_K объявляются подсхемами Ri (yi=>Ri). А1(№ издел) А2 (№ поставщика) А3 (наименов. поставщ) А4 (цена изделия)

Отношение R, сформированное на этом мн-ве атр. удовл. 1НФ.

А₁->Ø A₁A₂->A₄

A₂ ->A₃ A₁A₃

A₃ ->Ø A₁A₄

A₄ ->Ø

Покрывают все множ. атрибутов. Следуя по правилу формир-ия 2НФ получим

F={A₂ ->A₃ ; A₁A₂ ->A₄} (рис1) Сформир-ое отнош-ие обладает однозначной семантической интерпретацией. Преимущества 2НФ перед 1НФ:

1)если поставщик временно ничего не поставляет, то сведения о нем будут удалены в 1НФ, а в 2НФ удалять их нет необх.

2)если изменилось название поставщика, то в 1НФ необходимо просмотреть всю табл., чтобы заменить соответ. наименов., в 2НФ наименов. в единств.экземпляре

3)объем БД в 2НФ обычно<, чем в 1НФ.

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

Отношение R определено на множ-ве атрибутов U={A₁…A_N} и F-исходн. множ-во функциональн-х зависимостей. Отношение R наход-ся в 3НФ, если оно нах-ся во 2НФ и невыполнено след.усл-е: Пусть х первичн. ключ отнош-ия R, Y-некот-е подмнож-во U- Y€U и атрибут Ai не принадлеж. объедин-юXUY

1)X ->Y Є F⁺(х функционально определяет y и принадлеж. замыканию)

2) Y->Ai Є F⁺

3)Y ->X не Є F⁺(Yне является альтернативным первичным ключом)

Выполнение этих 3-х усл-ий явл-ся транзитивной завис-ю.

Правило формир-ия 3НФ: Если на множ-е атрибутов U найдены множ-ва X,Y и Ai, удовлетвор-ие услов-ю 1-3, то выполняя декомпозицию исходной сх R на две подсхемы R₁ содержит атрибуты все, кроме Ai, и R₂ содержит атрибуты Y, Ai (рис1) A₁ ->A₂A₃A₄A₅A₆ отсюда следует, что совокуп- ть атрибутовA₁-A₆ в качестве заголовка R гарантирует, что оно нах-ся во 2НФ. A₄ ->A₅A₆, A₄ не ->A₁ (рис2) Приемущества 3НФ перед 2НФ:

1) Если над проектом временно никто не трудится, то сведения о проекте будут удалены во 2НФ, а в 3НФ сведения хранятся отдельно от сотрудников (удалены не будут)

2) Если изменилась дата окончания проекта, то в 2НФ необходимо просмотреть всю БД, в 3НФ эта дата в единственном экземпляре

3)Объем БД в 3НФ обычно меньше, чем во 2НФ.

Отношение находится в 4NF, если оно находится вНормальная форма Бойса — Кодда и не содержит нетривиальных многозначных зависимостей. То есть все многозначные зависимости являются, по сути, функциональными зависимостями от ключей отношения.

61.2 Структурный синтез цифровых автоматов.

Понятие последовательностного автомата

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

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

Для описания последовательностного автомата с памятью, помимо состояний входов X(t) и выходов Y(t), необходимо также знать состояние памяти автомата, как говорят, его внутреннее состояние S(t).

В общем виде, последовательностный автомат рассматривается состоящим из двух частей: комбинационного устройства (КУ) и памяти, состоящей из элементов памяти (ЭП) (рис. 3.1).

В качестве элементов памяти могут быть применены как однобитовые элементы памяти (различные типы триггеров), так и многобитовые (многоразрядные) цепочки триггеров.

Функционирование (т.е. изменение состояния устройства) многотактного автомата происходит в дискретные моменты времени, ход которого обозначается натуральными числами t = 1, 2, 3 и т.д. В каждый момент дискретного времени t автомат находится в определенном состоянии S(t), воспринимает через входы соответствующую данному моменту комбинацию входных переменных X(t), выдает на выходах некоторую функцию выхода Y(t), определяемую как

Y(t) = f (S(t),X(t)), и переключается в новое состояние S(t+1), которое определяется функцией переходов j как S(t+1)= j ( S(t),X(t)).

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

Структурная схема цифрового автомата

ЦА представляет собой последовательностную схему и служит для обработки дискретной информации структурная схема ЦА представлена на рис 1.

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

Процессорное устройство описывается множеством входных сигналов являющихся исходными данными. Множеством результатов Z1-Zm, управляющее устройство вырабатывает множество управляющих сигналов y1-yn, операционное устройство вырабатывает множество признаков X1-Xs, которые позволяют изменить последовательность выполненных микрокоманд. На последовательность выполнения микрокоманд так же влияют внешние признаки Xs+1-XL.

Алгоритм функционирования цифрового автомата

В состав процессорного устройства входят регистры, счетчики и дешифратор. Пусть регистр Р1 хранит число А. В регистр Р2 поочередно заносятся элементы проверяемого массива, счетчик 1 служит для подсчета числа циклов. Счетчик 2 служит для подсчета числа элементов =А. Дешифратор используется для формирования признака х. Алгоритм функционирования автомата в микрооперациях представлен на рис.2

Под действием управляющего сигнала y1 в регистр Р1 записывается проверяемое число х. Под действием управляющего сигнала y2 в регистр R2 записывается число B. Под действием управляющего сигнала y3 в регистре R3 записываются число А ив сумматоре 1 сравнивается числа Аи х. На выходе переноса сумматора вырабатывается признак х. Если х<А то признак х=1 и выполняется переход на формирование управляющего сигнала y5, если наоборот то х=0 и выполняется переход на формирование управляющего импульса у4. Под действием управляющего сигнала y5 в сумматоре 2 должен быть организован режим сложения и в нем вычисляется х+В. Под действием управляющего сигнала у4 в сумматоре должен быть организован режим вычитания и вычисляется х-В. Под действием управляющего сигнала у6 результат полученный в сумматоре 2 записывается в регистр R4.

Алгоритм функционирования цифрового автомата в микрокомандах.

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

Микрокоманда Y1 включает управляющие сигналы y1 ,y2 и у3 ;микрокоманда Y2 включает управляющие сигнал y4; Y3 – y5; Y4 – y6.

а0 – начало/конец алгоритма;

а1–а4 – операторные блоки.

***

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