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

 

Министерство образования  и науки РФ

Федерального государственного автономного

образовательного учреждения высшего

профессионального образования

«Сибирский федеральный  университет»

 

 

 

 

 

 

Кафедра «Информационные системы»

Специальность ________

Дисциплина «Базы и банки знаний».

Группа  ________

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

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

 

 

Пояснительная записка

 

 

 

 

 

 

 

 

 

 

 

 

Руководитель работы ________________  С.В. Капустина                                     

^{(подпись,  дата)   (И.О.Ф.)}

Разработал студент ________________  ___________________

^{(подпись,  дата)   (И.О.Ф.)}

 

 

 

 

Красноярск 2012

 

ЗАДАНИЕ

 

ПО КУРСОВОЙ РАБОТЕ

 

 

1. Тема работы (проекта): Автоматизация проектирования реляционных: синтез В-схемы.

2. Исходные данные: Множество атрибутов и функциональных зависимостей.

3. Специальная часть (раздел): Разработать алгоритм и составить программу для проектирования баз данных. Оформить отчет в текстовом редакторе Word.

 

АННОТАЦИЯ

Данный документ является пояснительной запиской к курсовому проекту на тему «Автоматизация проектирования реляционных баз данных: синтез В-схемы», целью которого является разработка пакета программ для решения задач, связанных с проектированием реляционных баз данных.

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

Данный отчёт  состоит из страниц.

 

 

Оглавление

 

Введение 5

1 Техническое задание 6

1.1 Постановка задачи 6

2 Описание пакета программ .10

2.1 Входные и выходные данные. .10

2.2 Решение практической задачи вручную 12

2.3 Решение практической задачи с помощью разработанного                              пакета программ 18

Заключение 21

Список литературы 22

 

ВВЕДЕНИЕ

Данная курсовая работа является промежуточной стадией обучения в Ачинском филиале Федерального государственного автономного образовательного учреждения высшего профессионального образования «Сибирский федеральный университет»и служит закреплением практических и теоретических знаний, полученных при изучении дисциплины "Базы и банки знаний".

Целями данной работы являются:

• Детальное изучение основных алгоритмов теории нормализации, связанных с автоматизацией проектирования реляционных баз данных (БД);

 

1 Техническое задание

 

1.1 Постановка задачи

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

Результатом моделирования предметной области  является, прежде всего, логический проект БД - схема БД.

Физическое  проектирование БД - доводка логического  проекта с учетом особенностей выбранной СУБД и требований к эксплуатационным характеристикам БД.

Основная  задача проектировщика БД - получение  хорошего логического проекта БД. Исходными данными для решения этой задачи являются:

• множество атрибутов, значения которых требуется хранить в БД;
• множество связей между атрибутами.

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

• модель "сущность - связь" (ЕR-модель). Семантическая структура предметной области представляется ЕК-диаграммой;
• язык функциональных зависимостей (ФЗ). Семантическая структура предметной области представляется F-описанием - множеством ФЗ F.

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

Рассмотрим проблемы, возникающие при синтезе схемы БД и алгоритмические способы решения этих проблем.

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

Для всякой предметной области  можно построить несколько эквивалентных F-описаний. Для этого существуют соответствующие алгоритмы «чистки» F-описания.

«Чистка»  исходного F-описания выполняется в два этапа:

I. вначале из F удаляются все избыточные ФЗ (они логически следуют из оставшихся). Полученное в результате множество ФЗ называют неизбыточным покрытием F и обозначают F_неизб;

II. далее из F_неизб удаляются посторонние атрибуты. Этот процесс называется редуцированием, а полученное в результате множество ФЗ называется редуцированным покрытием и обозначается F_ред.

Проблема 2 - оценка качества проектных решений.

Известно, что  к организации БД предъявляются  три требования (правило «Три НЕ»): неизбыточность, непротиворечивость, независимость. Последнее из них - независимость данных от приложений достигается в основном средствами СУБД. Неизбыточность и непротиворечивость БД можно обеспечить путём выбора подходящей схемы БД.

В теории нормализации доказано, что БД будет неизбыточной и средствами СУБД можно достичь её непротиворечивого  состояния, если её схема будет эффективной  относительно заданного F-описания предметной области.

Пусть R - множество имен атрибутов, значения которых требуется хранить в БД, и F - множество ФЗ, описывающих связи между атрибутами.

Схема БД над R            m

^{_Р={R₁,R₂,...,R_n|UR_i=R}}

                                           i=1

называется эффективной относительно F, если она сохраняет F, обладает свойством соединения без потерь информации и находится в НФБК.

Теорема. Для любого множества ФЗ из F, заданного на конечном множестве атрибутов R, всегда существует схема БД

         m

^{_Р={R₁,R₂,...,R_n|UR_i=R}}

                                   i=1

обладающая  свойством соединения без потерь, сохраняющая все ФЗ из F и находящаяся в 3НФ.

Схему БД, удовлетворяющую  условиям данной теоремы, принято называть В-схемой. Приведённая теорема свидетельствует, что можно всегда найти В-схему для заданных R,F. Свойство В-схемы вполне приемлемы для практики, так как они гарантируют непротиворечивость БД. 3НФ допускает определённое избыточное дублирование данных, но с этим приходится мириться и учитывать в программах ввода и редактирования данных.

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

 

Рисунок 1

 

2 Описание пакета программ

 

2.3 Решение практической задачи вручную

 

 

Исходные  данные практической задачи приведены  в таблице 3.

 

 

Таблица 3 - Расписание экзаменов

Имя атрибута	Семантика
K1	Номер команды
K2	Название команды
T1	Код тренера
T2	Ф. И. тренера
I1	Номер игрока
I2	Ф.И. игрока
I3	Результативность игрока
P	Номер площадки (спортивного зала)
D	Дата тренировки команды

 

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

 

Таблица 4 - Условное обозначение функциональных зависимостей

Функциональная  зависимость	Семантика
K1 → K2	Номер однозначно идентифицирует команду
T1 → T2	Код однозначно идентифицирует тренера
I1 → I2I3	Номер игрока однозначно определяет его Ф.И. и результативность
K1 → T1T2	Для каждой команды определен  только один тренер, однако один и тот же тренер может тренировать несколько команд
I1 → K1	Каждый игрок входит в состав только одной команды
PD → K1T1	Площадка закрепляется за командой и соответствующим тренером на весь день
DT1T2 → P	Каждый тренер одновременно может находиться только на одной площадке
DK1 → PT2	Каждая команда одновременно может тренироваться только на одной  площадке под руководством одного тренера

 

Построение В-схемы включает себя следующие этапы.

 

1) Построение неизбыточного покрытия

 

 Для построения неизбыточного покрытия необходимо удалить избыточные ФЗ. Для этого вычислим замыкания для каждой ФЗ:

 

1. F₁=F/{ K₁ → K₂}={ T₁ → T₂, I₁ → I₂I₃, K₁ → T₁T₂, I₁ → K₁, PD → K₁T₁, DT₁T₂ → P, DK₁ → PT₂};

(K₁)⁺ _F1 = K₁T₁T₂, следовательно, данная ФЗ не является избыточной в F.

 

2. F₂=F/{ T₁ → T₂}={ K₁ → K₂, I₁ → I₂I₃, K₁ → T₁T₂, I₁ → K₁, PD → K₁T₁, DT₁T₂ → P, DK₁ → PT₂};

(T₁)⁺_F2 = T₁, следовательно, данная ФЗ не является избыточной в F.

 

3. F₃=F/{ I₁ → I₂I₃}={ K₁ → K₂, T₁ → T₂, K₁ → T₁T₂, I₁ → K₁, PD → K₁T₁, DT₁T₂ → P, DK₁ → PT₂};

( I₁)⁺_F3 = I₁K₁K₂T₁T₂, следовательно, данная ФЗ не является избыточной в F.

 

4. F₄=F/{ K₁ → T₁T₂}={ K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, I₁ → K₁, PD → K₁T₁, DT₁T₂ → P, DK₁ → PT₂};

(K₁)⁺_F4 = K₁K₂, следовательно, данная ФЗ не является избыточной в F.

 

5. F₅=F/{ I₁ → K₁}={ K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁T₂, PD → K₁T₁, DT₁T₂ → P, DK₁ → PT₂};

(I₁)⁺_F5 = I₁I₂I₃, следовательно, данная ФЗ не является избыточной в F.

 

6. F₆=F/{ PD → K₁T₁}={ K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁T₂, I₁ → K₁, DT₁T₂ → P, DK₁ → PT₂};

(PD)⁺_F6 = PD, следовательно, данная ФЗ не является избыточной в F.

 

7. F₇= F/{ DT₁T₂ → P}={ K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁T₂, I₁ → K₁, PD → K₁T₁, DK₁ → PT₂};

(DT₁T₂)⁺_F7 = DT₁T₂, следовательно, данная ФЗ не является избыточной в F.

 

8. F₈= F/{ DK₁ → PT₂}={ K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁T₂, I₁ → K₁, PD → K₁T₁, DT₁T₂ → P};

(DK₁)⁺_F8 = DK₁T₁T₂P, следовательно, данная ФЗ является избыточной в F и ее можно удалить.

 

Итак, F_неизб будет выглядеть следующим образом:

F_неизб ={ K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁T₂, I₁ → K₁, PD → K₁T₁, DT₁T₂ → P}

2) Построение редуцированного покрытия

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

Леворедуцирование приводит к следующим результатам.:

F* = { K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁T₂, I₁ → K₁, PD → K₁T₁, DT₁ → P}.

Праворедуцировапие:

F* = { K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁, I₁ → K₁, PD → K₁, DT₁ → P }.

В итоге получим:

F_ред = { K₁ → K₂, T₁ → T₂, I₁ → I₂I₃, K₁ → T₁, I₁ → K₁, PD → K₁, DT₁ → P }.

4) Синтаксическое разложение множества атрибутов R по F_ред дает следующую схему базы данных:

ρ^* = {R₁(K₁K₂), R₂(T₁T₂), R₃(I₁I₂I₃), R₄(K₁T₁), R₅(I₁K₁), R₆(PDK₁), R₇(DT₁P)}.