Разработка онлайн-органайзера с использованием объектно-ориентированного подхода. Исследование 1 Методология проектирования информационных систем

• Название: Исследование 1 Методология проектирования информационных систем
• Анкор: Разработка онлайн-органайзера с использованием объектно-ориентированного подхода
• Дата: 25.05.2022
• Размер: 1.64 Mb.
• Имя файла: 132640.rtf
• Тип: Исследование; #550069
• страница: 7 из 19

2.3 Нормализация отношений

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

В настоящее время известно несколько нормальных форм, самой "слабой" из которых является первая нормальная форма (по тексту будем обозначать 1НФ), далее по мере "усиления" - 2НФ, 3НФ и нормальная форма Бойса-Кодда (НФБК). Практика показывает, что приведение Базы данных хотя бы к 3НФ позволяет избежать в большинстве случаев почти всех недостатков.

Первая нормальная форма (1НФ)

Отношение со схемой R и множеством функциональных зависимостей F находится в 1НФ, если любой экземпляр схемы R удовлетворяет следующим условиям:

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

Вторая нормальная форма (2НФ)

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

Третья нормальная форма (3НФ)

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

Нормальная форма Бойса-Кодда (НФБК)

Схема отношения R с множеством функциональных зависимостей F находится в НФБК, если левая часть каждой зависимости (X  A)  F, где A  X , есть первичный или возможный первичный ключ.

В теории реляционных баз данных доказано, что любое отношение может быть заменено набором декомпозиционных подсхем, каждая из которых будет находиться в 3НФ, а декомпозиция будет обладать как свойством соединения без потерь информации, так и свойством сохранения исходного множества функциональных зависимостей. При приведении к НФБК в общем случае гарантируется лишь выполнимость свойства соединения без потерь информации. [3]

Для построения “хорошей” реляционной реализации концептуальной схемы БД, которая находилась хотя бы в третьей нормальной форме, можно использовать два способа:

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

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

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

• 
  Сложность алгоритма выше, чем полиномиальная.
  
• 
  Число порожденных декомпозиционных подсхем может оказаться больше, чем необходимо.
  
• 
  При декомпозиции схемы отношения могут возникнуть частичные зависимости, которые также могут порождать в результате лишние декомпозиционные подсхемы.
  
• 
  Декомпозиция может не обладать свойством сохранения функциональных зависимостей.
  
• 
  Декомпозиция может порождать схемы со “скрытыми” транзитивными зависимостями.
  

Существует еще один метод построения реляционной БД, который использован не будет, но достоин упоминания - это модель "Сущность-Связи" (часто ее называют кратко ER-моделью).

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

2.3.1 Алгоритм синтеза

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

Результатом работы алгоритма является схема автоматизированной системы управления в виде набора декомпозиционных подсхем {R1, R2, . . . , Rp}, удовлетворяющих следующим условиям.

• 
  Каждая подсхема Ri с БД должна находится хотя бы в ЗНФ относительно множества функциональных зависимостей F и соответственно G.
  
• 
  Синтезируемая информационная система содержит минимальный набор декомпозиционных подсхем Ri, I == 1, . . . , Р. Это условие защищает информационную систему от избыточности.
  
• 
  Для любого экземпляра r(БД), удовлетворяющего F, выполняется соотношение . Это условие гарантирует выполнимость свойства соединения без потерь информации.
  

Схема автоматизированной системы управления, удовлетворяющая условиям 1,2 и 3, называется полной схемой автоматизированной системы управления.

Рассмотрим шаги алгоритма.

Шаг 1. Строим расширенное множество F функциональных зависимостей, которое имеет следующую структуру зависимостей:
F = { (XI -> YI)| (XI ->YI) F, YI = XI +\ XI}
Этот шаг делается с целью построения неизбыточного или условно неизбыточного покрытия F, что позволит в некоторой степени удовлетворить условию 3. Полностью обеспечить условие 3 удастся после введения в рассмотрение понятия эквивалентности функциональных зависимостей на шаге 5.

Шаг 2. Строим неизбыточное покрытие F, исключая из F в любой последовательности лишние зависимости.

Очевидно, это покрытие не является каноническим.

Шаг 3. Если среди функциональных зависимостей из F' нет зависимости, включающей все атрибуты из U, то добавляем к F' тривиальную зависимость U-> Ø.

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

Зависимость XI —>YIявляется элементарной, если не существует таких наборов атрибутов XJ XI , что (Xj —>YI) .Если - существует, то зависимость XI —>YI заменяется зависимостью (XJ —>YI).

Шаг 5. Разбиваем множество полученных зависимостей на классы эквивалентности. Это делается для того, чтобы на следующем шаге оставить в каждом классе одного представителя, тем самым минимизировать количество декомпозиционных подсхем в результирующей БД и полностью удовлетворить условию 3.

Зависимости XI ->YI и XJ —>YJ будем называть эквивалентными, если

, т.е. минимальный ранг имеет зависимость, содержащая все атрибуты из U, а, если ее нет, то - тривиальная зависимость U —> Ø. Всем зависимостям из одного класса эквивалентности назначаем одинаковый ранг. Несравнимым зависимостям ранги назначаем произвольно.

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

Шаг 7. Выполняем транзитивную редукцию зависимостей с большим рангом на зависимости с меньшим рангом. Двигаясь по диаграмме снизу вверх (от зависимостей с большим рангом к зависимостям с меньшим рангом), для каждой текущей зависимости исключаем из правых частей всех зависимостей, расположенных выше текущей, те атрибуты, которые содержатся в правой части текущей зависимости (для тривиальной зависимости атрибуты исключаем из ее левой части).

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

2.3.2 Нормализация схемы данных методом синтеза

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

Предметная область:

• 
  программа-органайзер;
  

Сущности:

• 
  Пользователь;
  
• 
  Заметка;
  
• 
  Задача;
  
• 
  Встреча/событие;
  
• 
  Контакт;
  
• 
  Группы.
  

Множество атрибутов:

1. 
   UserID,
   
2. 
   UserInfo
   
3. 
   NoteDate,
   
4. 
   NoteInfo
   
5. 
   TaskCrDate,
   
6. 
   TaskInfo
   
7. 
   EventCrDate,
   
8. 
   EventInfo
   
9. 
   ContactID,
   
10. 
    ContactInfo
    
11. 
    GroupNames
    

В действительности атрибутов много больше, не важные временно исключены из рассмотрения, чтобы не загромождать модель.
U = {A,B,C,D,E,F,G,H,I,J,K}

F = {A -> B,K ; A,C -> D ; A,E -> F ; A,G -> H ; A,I -> J}
Шаг 1: Построим расширенное множество
A+=ABK

AC+=ACDBK

AE+=AEFBK

AG+=AGHBK

AI+ =AIJBK

= {A -> BK ; AC -> DBK ; AE -> FBK ; AG -> HBK ; AI -> JBK}
Шаг 2: - условно не избыточное расширенное множество.
= {A -> BK ; AC -> DBK ; AE -> FBK ; AG -> HBK ; AI -> JBK}

Шаг 3: = { A -> BK ; AC -> DBK ; AE -> FBK ; AG -> HBK ; AI -> JBK, U→ }

Шаг 4: Все зависимости элементарны.

Шаг 5: Проранжируем полученные зависимости.
Таблица 2.1

X→Y	X Y	rang
A -> BK	ABK	6
AC -> DBK	ACDBK	5
AE -> FBK	AEFBK	4
AG -> HBK	AGHBK	3
AI -> JBK	AIJBK	2
U→	ABCDEFGHIJK	1

Шаг 6: Построим ранжированную диаграмму зависимостей, она изображена на рисунке 2.1:

ABCDEFGHIJK →

1




AE -> FBK

3

4

AG -> HBK

AI -> JBK

AC -> DBK

4




6




A -> BK


Рис 2.1 Ранжированная диаграмма зависимостей
Шаг 7: Выполним транзитивную редукцию зависимостей, результат изображен на рисунке2.2:

ABCDEFGHIJK →

AE -> FBK

1

2

3

4

AG -> HBK

AI -> JBK

AC -> DBK

4




6







A -> BK


Рис 2.2 Ранжированная диаграмма зависимостей после редукции

Шаг 8: Определим декомпозиционные подсхемы и их первичные ключи.

R1 = ACEGI, с ключом К1 = ACEGIR5 = ACD, с ключом К5 = AC

R2 = AIJ, с ключом К2 = AIR6 = ABK, с ключом К6 = A

R3 = AGH, с ключом К3 = AG

R4 = AEF, с ключом К4 = AE

Полученная схема БД находиться в НФБК, так как, по определению НФБК, необходимо чтобы в левой части каждой зависимости подсхемы стоял первичный ключ или возможный ключ и она находилась в 3НФ, и это требование выполняется.

Так как на шаге 3 была добавлена зависимость U→ , необходимо проверить свойство соединения без потерь, без подсхемы R1 = ACEGI.

Проверка показала, что свойство соединения без потерь выполняется.

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

R1 = {ACEGI}, с ключом ACEGI

R2 = {AIJ}, с ключом AI

R3 = {AGH}, с ключом AG

R4 = {AEF}, с ключом AE

R5 = {ACD}, с ключом AC

R6 = {ABK}, с ключом A

Таблица R1 должна быть удалена из схемы, т.к. она содержит в себе лишь ключи всех таблиц и не может хранить никакой осмысленной или значимой информации.

В результате проведенного проектирования при помощи метода синтеза, автоматизированная информационная система будет состоять из пяти таблиц.

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

-Простота алгоритма и легкость автоматизации.

-Возможность получения концептуальной схемы автоматизированной системы управления в НФБК.